Всероссийской олимпиады школьников по информатике

Внимание! Категорически запрещается публиковать данные материалы (или любую их часть), а также размещать их в сети Интернет до 16 ноября 2012 года.

Предлагаемые материалы не являются готовым вариантом школьной олимпиады. Мы предлагаем некоторый набор (заведомо избыточный) задач, которые можно использовать при составлении варианта школьной олимпиады по программированию. В набор включены задачи разной сложности с тем, чтобы можно было выбрать для учеников сравнительно сбалансированный по сложности вариант. Рекомендуемое количество задач в варианте – 3-4. Рекомендуемая продолжительность тура — 2 часа.

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

Проверка решений осуществляется путем запуска программы, ввода тестовых данных и проверки выданных программой ответов. Тесты приведены в конце данного файла (после условий задач). Во всех задачах ответ всегда определен однозначно, т.е. для проверки правильности ответа его достаточно сравнить с приведенным.

В каждой задаче приведено 5 или 10 тестов, каждый тест оценивается 20 или 10 баллами соответственно. Баллы за задачу получаются суммированием баллов за пройденные тесты (суммарный балл за задачу равен 100).

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

Для проверки задач школьного этапа система будет доступна c 11 октября по 15 ноябрявключительно по адресу

Для учителей: olympiads.ru/moscow/2012/school

Для учащихся: olympiads.ru/olymp

Подробнее об использовании тестирующей системы можно прочитать в памятке.

Есть два варианта автоматической проверкой:

▪ Учащийся самостоятельно сдает задачи в тестирующую систему и получает результат в виде количества баллов по задаче.

▪ Учащиеся сдают решения учителю, а учитель после окончания олимпиады сдает в тестирующую систему решения учащихся и получает полный протокол проверки, включая тестовые данные и результаты работы программы (выходные данные).

В системе автоматической проверки будут доступны следующие компиляторы: Delphi, Free Pascal, GNU C/C++, Java, PHP, Perl, Python (2 и 3), Ruby.

Для того, чтобы решение можно было проверить автоматически, программа должна строго соблюдать формат входных и выходных данных – не выводить никаких лишних сообщений, вводить данные строго в заданном порядке и т.п. При этом если программа не удовлетворяет этим требованиям, например, выводит ненужный текст, то проверяющий может перед отправкой внести в команды ввода-вывода необходимые исправления, не меняя содержания алгоритма. Часто оказывается сделать это быстрее, чем вручную проверять программу на всех тестах.

Ссылка для входа в систему автоматической проверки для учителей является секретной (известна только организаторам олимпиады) и не должна быть известна учащимся. Для учащихся, желающих воспользоваться тестирующей системой предназначена ссылка olympiads.ru/olymp.

Замечания и комментарии по предложенным задачам вы можете отправить в городскую методкомиссию по e-mail [email protected]

Задача «Сокращаем перемены»

Требуется подсчитать, на сколько минут раньше будет заканчиваться k-й урок, если все перемены сократить на 5 минут.

Формат ввода

Вводится одно натуральное число k, не превосходящее 7.

Формат вывода

Выведите одно натуральное число — время в минутах.

Пример

Задача «Шестеренки»

Даны две сцепленные шестеренки. У одной шестеренки N зубцов, у другой – K. Требуется найти, какое минимальное число поворотов на один зубчик требуется сделать, чтобы шестеренки вернулись в исходное состояние.

Формат ввода

В единственной строке даны два натуральных числа N и K, каждое из которых не превосходящих 10 миллионов.

Формат вывода

Выведите искомое количество зубчиков. Гарантируется, что оно не более миллиарда.

Примеры

Задача «Инопланетянин»

Во время эксперимента Накодиллы было случайно получено сообщение инопланетян, содержащее формулу вида A + B = C.

Общественности стало интересно, какую же систему счисления используют инопланетяне. Так как внеземная цивилизация была достаточно развита, чтобы отправить межпланетное сообщение, Накодилла предположил, что основание системы счисления довольно мало. Требуется написать программу, которая находит минимальное основание системы счисления, при котором данное равенство выполняется.

Формат ввода

В единственной строке входных данных содержится три числа A, B и C. Числа состоят из цифр от 0 до 9 и заглавных латинских букв от А до Z.

Формат вывода

Требуется вывести единственное число – искомое основание системы счисления. Если такой системы счисления не существует, то вывести -1. Гарантируется, что ответ не превышает 36.

Пример

Задача «Распаковка строчки»

Будем рассматривать только строчки, состоящие из заглавных латинских букв. Например, рассмотрим строку AAAABCCCCCDDDD. Длина этой строки равна 14. Поскольку строка состоит только из латинских букв, повторяющиеся символы могут быть удалены и заменены числами, определяющими количество повторений. Таким образом, данная строка может быть представлена как 4AB5C4D. Длина такой строки 7. Описанный метод мы назовем упаковкой строки.

Напишите программу, которая берет упакованную строчку и восстанавливает по ней исходную строку.

Формат ввода

Входной файл содержит одну упакованную строку. В строке могут встречаться только конструкции вида nA, где n — количество повторений символа (целое число от 2 до 99), а A — заглавная латинская буква, либо конструкции вида A, то есть символ без числа, определяющего количество повторений. Максимальная длина строки не превышает 80. Входная строка обязательно заканчивается символом перевода строки.

Формат вывода

В выходной файл выведите восстановленную строку. При этом строка должна быть разбита на строчки длиной ровно по 40 символов (за исключением последней, которая может содержать меньше 40 символов).

Примеры

Задача «Жизнь в квадрате»

В некоторых клетках квадрата N x N живут микроорганизмы (не более одного в одной клетке). Каждую секунду происходит следующее:

– все микроорганизмы, у которых менее 2-х соседей, умирают от скуки (соседями называются микроорганизмы, живущие в клетках, имеющих общую сторону или вершину);

– все микроорганизмы, у которых более 3-х соседей, умирают от перенаселенности;

– на всех пустых клетках, у которых ровно в трех соседних клетках жили микроорганизмы, появляются новые микроорганизмы.

Все изменения происходят одновременно, то есть для каждой клетки сначала выясняется ее судьба, а затем происходят изменения сразу во всех клетках.

Требуется по данной конфигурации определить, во что она превратится через T секунд.

Формат ввода

В первой строке вводятся два натуральных числа – N (1 ≤ N ≤ 10) и T (1 ≤ T ≤ 100).

Далее записано N строчек по N чисел, описывающих начальную конфигурацию (0 – пустая клетка, 1 – микроорганизм). Числа в строках разделены пробелами.

Формат вывода

Требуется вывести N строк по N чисел – описание конфигурации через T секунд (в том же формате, как и во входных данных).

Примеры