Теоретический тур

Все любят играть в компьютерные игры. Давайте и мы пополним библиотеку компьютерных игр и потратим на это 4 часа, отводимых на теоретический тур. Для каждой из следующих игр проведите анализ наличия выигрышных стратегий, найдите эти стратегии, разработайте и приведите интерфейс игры (в играх с двумя участниками предусмотреть две реализации: "игрок-игрок" и "ЭВМ-игрок").

1. Первый игрок сообщает какую-нибудь дату января. Каждый игрок при своем ходе называет более позднюю дату, увеличивая либо календарную дату в месяце, либо месяц, но не то и другое сразу. Первый, кто доберется до 31 декабря, выигрывает.

2. Али-Баба пытается проникнуть в пещеру. У входа в нее стоит барабан с четырьмя отверстиями по бокам. Около каждого отверстия внутри поставлен переключатель, имеющий 2 положения: "верх", "низ". Разрешается засунуть руки в какие-либо 2 отверстия, пощупать, как стоят переключатели, и переключить их произвольным образом (в частности, можно не переключать). После этого барабан приходит в быстрое вращение, так что после его остановки уже нельзя установить, какие именно переключатели трогали в прошлый раз. Разрешается повторить эту операцию до 10 раз. Дверь в пещеру открывается в тот момент, когда все переключатели стоят одинаково. Как Али-Бабе попасть в пещеру.

3. Двое играют в такую игру: первый называет натуральное число от 2 до 9; второй умножает это число на произвольное натуральное число от 2 до 9; затем первый умножает результат на любое натуральное число от 2 до 9 и т. д.; выигрывает тот, у кого впервые получится произведение больше

а) тысячи;

б) миллиона;

в) заданного натурального числа N.

4. Два человека играют в "алгоритмическую игру". Игровое поле - лист бумаги в линейку, содержащий 20 строк. Игроки задают начальные значения переменных A и B из множества {0,1} (например, A=0, B=0 или A=1, B=0), а затем по очереди вписывают по одному из операторов

A:=1-A

B:=1-B

ЕСЛИ A=1 ТО B:=1-B ВСЕ

ЕСЛИ A=0 ТО B:=1-B ВСЕ

ЕСЛИ B=1 ТО A:=1-A ВСЕ

ЕСЛИ B=1 ТО A:=1-A ВСЕ

в любую незанятую клетку. Когда заполнены все клетки, полученная последовательность операторов выполняется при заданных начальных значениях. Если после исполнения алгоритма значения A и B будут различны, побеждает первый игрок, если равны - побеждает второй игрок.

Практический тур

5. В множестве, состоящем из натуральных чисел, в десятичной записи которых встречаются только цифры 1, 3, 7, все элементы занумерованы в порядке возрастания. По заданному n определить n-ый элемент этого множества.

6. Координаты всех домов в городе заданы парой целых чисел, таких что любой из домов можно однозначно изобразить в виде точки на мониторе компьютера. Мэрия решила выделить средства на постройку кольцевой автодороги вокруг города. Изобразить на экране дорогу минимальной длины в виде прямых отрезков, соединяющих дома, мимо которых должна пройти дорога, при условии, что внутри дороги окажутся все остальные дома города. Вычислить длину кольцевой дороги и площадь города?