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

2009–2010 учебного года

 

 

 

 

1.       «Маршрут» (25 баллов)

Строка, содержащая символы «1», «2», «3», «4», «5», «6»,«7», «8», является описанием маршрута передвижения фишки по узлам решетки со стороной равной 1. Переход осуществляется в соседний узел, заданный символом (см. рисунок). Приведенный на рисунке маршрут задается строкой «81233445557».

Составить программу, которая по маршруту, заданному строкой, вычисляет и сообщает максимальное отклонение фишки от начальной точки. Результат должен быть выведен с точностью до трех знаков после запятой.

Например, для приведенного на рисунке маршрута ответ 4,472.

 

 

2.      «Число» (25 баллов).

Для заданного натурального числа N (N≤32000) найти наименьшее натуральное число K такое, что KN делится на N. 

Например, если N=24, то K=6.

 

 

3. «Билеты» (25 баллов)

Написать программу определения количества 2*N -значных билетов, у которых сумма первых N десятичных цифр равна сумме N последних десятичных цифр; при этом N≤10 -натуральное число.

Например, если N=2, то счастливых билетов K=669.

 

 

4. «Монеты» (25 баллов)

На столе разложено N монет. Из них K монет лежат гербом вниз (решка), а остальные вверх (орел). За один ход разрешается одновременно перевернуть любые 7 монет. Окончательная цель повернуть монеты так, чтобы они все лежали гербом вниз за наименьшее количество ходов.

Составить программу, которая

§         Запрашивает число монет N (7£N£100);

§         Запрашивает число монет лежащих гербом вниз K (0≤K<N);

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

Например, если N=27, K=5, то это достигается за 4 хода (имеется в виду следующее преобразование: 22+5,  21+6, 14+13, 7+20, 0+27).