Олимпиадные задачи по информатике

[The Godfather]

2004-2005 г., Школьная олимпиада, г. Н.Новгород

Задача 1. "Репьюниты". 15 баллов

Репьюниты, десятичные натуральные числа, состоящие только из единиц, обозначаются Rn, где n - число единиц в записи числа.
Для заданных целых чисел n и k (n + k < 3000) подсчитать, какие цифры и сколько раз встречаются в записи произведения Rn * Rk.
Пример: если n = 2, k = 5, то цифра 1 встречается 2 раза, цифра 2 - 4 раза.

Задача 2. "Робот". 20 баллов

Робот перемещается по неограниченному клетчатому полю, ориентированному по сторонам света. Программа робота состоит из символов n - шаг на север, s - шаг на юг, w - шаг на запад, e - шаг на восток.
Для перехода робота, заданного программой (не больше 128 символов), определить количество посещенных им клеток.
Например: программа nnwsse, ответ - 6.

Задача 3. "Кучки". 20 баллов

Имеется кучка из n (n < 32000) орехов. Разрешается разделить ее на две. Каждую из полученных кучек можно также разделить на две. За каждое деление кучки на две неравные полагается штраф - 1 мрот. Деление продолжается до тех пор, пока кучки не будут содержать по одному ореху.
Для введенного с клавиатуры числа орехов определить наименьший возможный штраф за деление.
Например, если n = 100, то наименьший штраф s = 2 мрот.