В этом случае на следующем ходе недополучим 1 единицу ресурса из-за движения рабочего сверху, но уже на второй ход будем добывать 2, таким образом в перспективе выигрывается 1 единица ресурса.
Может я не так считаю, но почему выигрывается 1 единица ресурса? Если не отходить, то добыча по ходам будет [1, 1, 2, 2, ...]. А если подвинуться, то [0, 2, 2, 2, ...]. Вроде бы сумма одинаковая.
Это, конечно, не отменяет того, что подвинуться может быть выгодно по другим причинам (например, чтобы меньше стоять на проходе).
Вот самое легкое задание, которое было предложено на финале (и единственное, которое участники смогли решить):
You are given two Strings: the start string S and the end string E. Both strings have the same length, and each of their characters is either '0' or '1'. Two players A and B play the game that starts with the string S. Player A and player B take alternating turns, with player A going first. In each of her turns, player A picks a contiguous subsequence of the current string and flips it — changing all '0's to '1's and vice versa. (She is allowed to pick an empty subsequence, which results in her not changing the current string.) In each of his turns, player B may pick a character of the current string and flip it. (He is allowed not to pick any character and keep the current string unchanged.)
When the string turns into E, player A wins. If player A can win the game, return the minimum possible number of turns A has to take. (We assume that if player A can ensure a win, then player B uses a strategy that postpones his loss for as long as possible.) If player A cannot win the game, return -1 instead.
Constraints
— S will contain between 1 and 50 characters, inclusive.
— S and E will contain the same number of characters.
— Each character in S and E will be '0' or '1'.
Жду продолжения! А сколько лет в США дается на получение PhD? Кстати, получается, что хорошее знание математики не так важно как умение написать сочинение и рекомендации от профессоров (если в GRE только школьную математику проверяют)? А еще, они дают стипендию/требую плату за обучение?
А в данном конкретном случае разве не лучше перебрать все возможные варианты распределения групп по автобусам (если у нас 3 автобуса и 15 групп, то понадобиться перебрать всего лишь 3^15 = 14 * 10^6 вариантов)? Если точно вести функцию, описывающую «оптимальность» расстановки, то мы меньше чем за секунду (при данных ограничениях) получим самое лучшее решение.
P. S. я не в коем случае не пытаюсь сказать, что эвристические алгоритмы не нужны, только, что в данном случае можно обойтись без них (перебор всех вариантов пишется явно быстрее чем эти эвристики).
Если бы я не понимал… Зачем, по вашему, оценивают «сложность» некоторого алгоритма? Разве не для того, чтобы потом его сравнить с другим и сказать «асимптотически он будет работать быстрее». А в данном случае, мы не можем принять арифметическую операцию умножения за О(1), т. к. «время», потраченное на ее выполнение, зависит от длины числа (причем, пропорционально квадрату, если использовать «наивный» алгоритм). И, как уже отмечалось в другой статье, как раз использование «длинной арифметики» сильно увеличивает время работы этого алгоритма.
P. S. сложность считают относительно числа арифметических операций, когда все числа «влазят» в машинное слово.
Не может это быть подсчитано с логарифмической сложностью, т. к. вам потребуется использовать «длинную арифметику», которая не умеет перемножать два числа за О(1). Мне одному кажется, что про подсчет чисел Фибоначчи была уже не одна статья на Хабре (зачем тогда изобретать колесо)?
Поскольку пользователи бывают очень ленивыми, то большинство из них не будут делать сложную динамическую часть (а, значит, теряется смысл всей идеи). +Обычному пользователю сложно объяснить, как написать «шаблон» своего пароля.
Насколько я понял автора, способов создания «динамического» пароля очень много. И, после регистрации, пользователю будет предложено выбрать, скажем, один из трех доступных способов (во-первых, чтобы пользователю было легче запомнить; во-вторых, чтобы не раскрывать список всех возможных способов злоумышленникам).
Когда я хочу зайти на какой-то сайт, то ввести логин-пароль для меня дело нескольких секунд. И мне это нравится. Если же мне для этого потребуется зайти на какой-то сайт с погодой в каком-то городе, правильно преобразовать эти данные (вспомнить как именно нужно вводить эту погоду в пароле), вспомнить статическую часть пароля, вспомнить как именно их комбинировать, то это затянется на несколько минут. И это плохо. К тому же сейчас брутфорсом взломать пароли довольно сложно (имеется ввиду, что необходимо затратить гораздо больше усилий чем будет получено выгоды).
Сразу таких серьезных косяков в компиляторе Паскаля не вспомню, но в средах разработке в «отладчике» часто показываются не правильные данные (причем, после перезапуска среды, все работает нормально).
«Хорошо разбирающемуся в математике» 11-летний школьник имеет гораздо больше шансов научится программировать чем среднестатистический. И тут дело даже не в том, что «высшая математика» не понадобиться большинству программистов в своей работе (с этим я с вами абсолютно согласен), а в том, что людей можно разделить на две большие группы. Назовем их «гуманитариями» и «логиками». Вторые лучше разбираются в «точных науках» (в том числе, и в программировании), но при этом их можно научить грамотно писать, общаться на 10 языках или сочинять стихи. Но им это никогда не будет приносить удовольствия. С другой же стороны, «гуманитариев» можно научить программировать или решать математические задачи (и я даже знаю много таких людей, которые прекрасно с этим справляются), но это никогда не будет приносить им удовольствия.
P. S. А работать нужно по тому направлению, которое приносит удовольствие.
Так а никто не мешает 11-летнему школьнику, хорошо разбирающемуся в математике, начать самому читать книги по программированию, а при возникновении вопросов, подходить и спрашивать их у преподавателя, ходить в какие-нибудь кружки. Тем более, сейчас очень много возможностей обучатся чему-либо в интернете. Единственным недостатком «самостоятельного обучения» считалось не возможность получения ответов на вопросы, которые возникают при прочтении книг/статей. Но сейчас, по-моему, это уже не проблема.
Вопрос в том, зачем заставлять других учить то, что нужно одному человеку из класса?
<ИМХО> Вот и я думаю… Больше 30% проголосовали за С/С+. Эти люди хотя бы представляют себе средний уровень нынешнего школьника? Да 95% школьниками это программирование, простите, нафиг не нужно. А остальные 5% и так сами все выучат. А если начнут преподавать С++, то тем 5% все-равно будет скучно на уроках, пока учитель будет работать с остальными. Поэтому, я думаю, что лучше учить Pascal, который хотя бы половина школьников поймет хотя бы на начальном уровне. </ИМХО>
Может я не так считаю, но почему выигрывается 1 единица ресурса? Если не отходить, то добыча по ходам будет [1, 1, 2, 2, ...]. А если подвинуться, то [0, 2, 2, 2, ...]. Вроде бы сумма одинаковая.
Это, конечно, не отменяет того, что подвинуться может быть выгодно по другим причинам (например, чтобы меньше стоять на проходе).
You are given two Strings: the start string S and the end string E. Both strings have the same length, and each of their characters is either '0' or '1'. Two players A and B play the game that starts with the string S. Player A and player B take alternating turns, with player A going first. In each of her turns, player A picks a contiguous subsequence of the current string and flips it — changing all '0's to '1's and vice versa. (She is allowed to pick an empty subsequence, which results in her not changing the current string.) In each of his turns, player B may pick a character of the current string and flip it. (He is allowed not to pick any character and keep the current string unchanged.)
When the string turns into E, player A wins. If player A can win the game, return the minimum possible number of turns A has to take. (We assume that if player A can ensure a win, then player B uses a strategy that postpones his loss for as long as possible.) If player A cannot win the game, return -1 instead.
Constraints
— S will contain between 1 and 50 characters, inclusive.
— S and E will contain the same number of characters.
— Each character in S and E will be '0' or '1'.
P. S. я не в коем случае не пытаюсь сказать, что эвристические алгоритмы не нужны, только, что в данном случае можно обойтись без них (перебор всех вариантов пишется явно быстрее чем эти эвристики).
P. S. сложность считают относительно числа арифметических операций, когда все числа «влазят» в машинное слово.
P. S. А работать нужно по тому направлению, которое приносит удовольствие.
Вопрос в том, зачем заставлять других учить то, что нужно одному человеку из класса?