Текст районной/городской олимпиады по информатике

2007–2008 уч. года

 

13 декабря 2007 года

 

 

1.       «Нервы» (15 баллов)

В цепочке из n  (2<n<100) нервных клеток, соединенных в окружность, каждая может находиться в одном из двух состояний: «покой» (на рисунке изображены как окружность) или «возбуждение» (круг). Если клетка возбуждена, то она сразу посылает сигнал, который через единицу времени доходит до обеих ее соседок.  Каждая клетка возбуждается (остается возбужденной) в том и только в том случае, если к ней приходит сигнал только от одной из соседних клеток.

Пусть в начальный момент возбуждена только одна клетка. Сколько будет возбужденных клеток через t (0<t<1000000) единиц времени?

Ваша программа должна:

Ø      запросить число нервных клеток n;

Ø      запросить время t;

Ø      сообщить число возбужденных клеток к этому времени.

Например

   Если n=12, t=5, то число возбужденных клеток 4.

 

 

2.      «Строка» (20 баллов).

Из заданной строки символов (не более 255), содержащей только цифры от 0 до 9, необходимо составить новую строку, полученную из исходной удалением многократно повторяющихся символов (кроме  первого и последнего их вхождения). Порядок следования символов менять нельзя.

Пример 1: исходная строка: 123321123223                Ответ: 123123

Пример 2: исходная строка: 010300000                                  Ответ: 0130

 

 

3. «Число чисел» (30 баллов)

Подсчитать число двоичных n-значных чисел (n£36), в каждом из которых нет трех единиц идущих подряд.

  Ваша программа должна

Ø      запросить значение n;

Ø      найти и сообщить, число n-значных двоичных чисел без трех единиц подряд.

Пример. Исходные данные: 4    Ответ: 6 (Имеются в виду числа 1000, 1001, 1010, 1011, 1100, 1101)

 

 

4. «Игра» (35 баллов)

Двое играют в такую игру: первый записывает натуральное число от 2 до 9; второй умножает его на произвольное натуральное число от 2 до 9; затем первый умножает результат на любое из чисел от 2 до 9 и так далее. Выигрывает тот, кто первым получит результат равный или больший натурального числа n (n<2000000000). Кто выигрывает при правильной игре – начинающий или его соперник?

  Ваша программа должна

Ø      запросить n;

Ø      найти и сообщить, кто выигрывает;

Ø      если выигрывает первый, то сообщить все его возможные первые ходы, ведущие к выигрышу.

Пример 1: Исходные данные: 16    Ответ: Выигрывает второй

Пример 2: Исходные данные: 28    Ответ: Выигрывает первый. Выигрывающий ход: 2 или 3