isaf27's blog

By isaf27, history, 7 years ago, In Russian

Здравствуйте.

Как известно, на данный момент существует два распространённых вида олимпиадных задач — стандартная и интерактивная.

Недавно, решая задачи по математике, я наткнулся на задачу следующего вида — ставится фокус с участием зрителя, фокусника и его помощника. Cначала зритель загадывает некоторый объект, который определен в условии задачи (последовательность чисел, строка и тд). После этого помощник как-то его изменяет, что тоже определено в условии. После этого входит фокусник и, по тому что он видит, угадывает то, что загадал зритель. Конечно помощник и фокусник договариваются о том, как помощнику изменить объект, чтобы потом фокусник мог его отгадать. Чаще всего суть задачи состоит в том, чтобы понять, как им договориться.

Как мне кажется, было бы интересно делать такие задачи и по программированию. На простом примере разберем как это можно сделать. Следующая задача: зритель загадывает последовательность из 10 цифр, после чего помощник должен закрыть одну из цифр. Далее фокусник, видя последовательность с одной закрытой цифрой, должен отгадать, какую цифру закрыли. Решение очень простое: пусть помощник, увидев последовательность a0, a1, ..., a9, закроет цифру под номером . Фокусник видя номер закрытой цифры и сумму всех, кроме неё, может вычесть из номера эту сумму по модулю 10 и получить цифру, которая закрыта. Теперь участнику предлагается написать решение следующим образом: сначала ему будет вводиться число 0 или 1. Если число 0, то это будет означать, что его программа выступает в роли помощника в данный момент, 1 если в роли фокусника. После строка длины 10 — сама последовательность. Если первое число 0, то она будет состоять только из цифр, если первое число 1, то закрытый символ будет 'x', например. И тогда, если программа — помощник, нужно вывести номер закрываемой цифры, если фокусник, то назвать загаданную цифру. Чтобы проверить решение нужно будет запустить решение участника с вводом 0 + последовательность, далее считать номер закрытой цифры и ещё раз запустить решение участника с вводом 1 + последовательность с одной закрытой цифрой и сверить ответ участника с правильным. Отличие от обычных задач — то, что требуется запустить программу участника два раза при проверке на одном тесте.

Хороших задач по математике такого и похожего типа достаточно много. Мне кажется, что это интересная идея, хотя и очень непросто реализуемая. Было бы круто, если этот или другой вид задач начал развиваться, как это было с интерактивными задачами.

Спасибо за внимание. Буду рад услышать ваши мнения и идеи по этому поводу.

  • Vote: I like it
  • +108
  • Vote: I do not like it