Олимпиада по информатике 2010

ЗАДАНИЯ ОЛИМПИАДЫ

Решения задач загружаются в Виртуальном кабинете.

Задачи теоретической части

В предложенных задачах требуется дать словесное описание алгоритма решения предложенной задачи (если не оговаривается что-то другое). При проверке решений (алгоритмов) будут учитываться следующие параметры:

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

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

1. Игра "Даты"

Играют двое. Первый игрок сообщает какую-нибудь дату нашего столетия (например, 26 ноября 2010 года). Каждый игрок своим ходом называет более позднюю дату, увеличивая либо номер дня в месяце, либо месяц, либо год (только что-то одно). Опишите выигрышную стратегию, при которой:
а) игрок, назвавший 31 декабря 2200 года, выигрывает;
б) игрок, назвавший 31 декабря 2200 года, проигрывает.

2. Поиск

В каждой клетке большой прямоугольной таблицы размера N на M записано число, причём известно, что все числа равны натуральным степеням двойки, не превышающим 1024. Опишите алгоритм, определяющий количество прямоугольников 1x10 в таблице, в которых все числа различны.

3. Длинное число

Имеется K-значное число N.
а) Опишите алгоритм, позволяющий по заданному числу M найти наибольшее M-значное число, получающееся вычеркиванием цифр из N (предполагается, что M не больше K).
б) Опишите алгоритм, позволяющий найти наибольшее число W, для которого каждое натуральное число от 1 до W может быть получено вычеркиванием цифр из числа N.

4. Шайка

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

5. Сейф

Кодовый замок сейфа представляет собой n независимых рычагов, каждый из которых может находиться в одном из k положений. Таким образом, положение замка может быть описано n-значным числом, каждая цифра которого может принимать значения от 1 до k. За одну секунду можно перевести только один из рычагов в соседнее положение, что соответствует изменению одной из цифр на одну единицу. Грабители застают замок запертым в некотором положении. Определите, могут ли они перебрать все возможные положения замка, не теряя ни секунды (т.е. каждую секунду получать новую комбинацию), и как это сделать.

Задачи практической части

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

Для проверки принимаются только исходные тексты программ (файлы *.pas, *.c, *.cpp) в соответствии с техническими требованиями. Программы (исходные тексты) загружаются для проверки в Виртуальном кабинете, сразу компилируются и проверяются на наборе тестов, после чего участнику выдается результат. Допускается вносить изменения в программы произвольное количество раз и загружать программы для повторной проверки.

Внимание: загрузка работ будет возможна с 30 ноября. Загружается только исходный текст программы (файл *.pas, *.c, *.cpp) без архивирования.

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

Входные данные берутся из текстового файла input.txt, результат выполнения программы выводится в файл output.txt в установленном формате. Программа ничего не должна запрашивать для ввода с клавиатуры и не должна ничего выводить на экран.

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

1. Часы

Даны два числа ЧЧ и ММ, означающие начальное показание часов (часы и минуты соответственно, 0≤ЧЧ<12, 0≤ММ<60). Определите наименьшее время, округленное до минут, которое должно пройти до того времени, когда часовая и минутная стрелки на циферблате расположатся перпендикулярно друг другу. Считается, что стрелки движутся равномерно, "не прыгая".

Вход:файл input.txt, в котором записаны два целых числа, разделенных пробелом, означающие начальное показание часов: первое число – часы, второе – минуты.

Ограничения: в тексте задачи.

Выход: файл output.txt, содержащий единственное целое число (результат в минутах)

Пример:

2. Путь коня

На обычной шахматной доске стоит конь. Ему требуется перебраться на другую клетку, сделав ровно k ходов. Требуется написать программу, которая определяет, может ли конь это сделать, если да, то сколькими возможными способами, и выводит один из таких способов.

Вход:файл input.txt, в котором в первой строке входного файла указано начальное положение коня и через пробел – конечное положение коня в шахматной нотации (латинская буква от a до h и цифра от 1 до 8, при этом буква и цифра записаны слитно). Во второй строке входного файла указано число k.

Ограничения: 0≤k≤30.

Выход: файл output.txt, содержащий в первой строке целое число - количество путей коня из начальной клетки в конечную. В случаю, если это число больше нуля, то в следующей строке должен быть указан один из возможных путей.

Пример:

3. Словесный калькулятор

Имеется арифметическое выражение – натуральные числа, между которыми расставлены знаки сложения, вычитания и умножения (других знаков операций и скобок нет). Данное арифметическое выражение записано в словесной форме: каждое натуральное число записано на русском языке в форме числительного в именительном или винительном падеже, знаки сложения, вычитания и умножения записываются, соответственно, как плюс, минус и умножить на. Требуется вычислить значение выражения и представить результат также в словесной форме.

Вход:файл input.txt, в котором в первой строке встрочными (маленькими) буквами словесно записано арифметическое выражение.

Ограничения: каждое встречающееся в исходном выражении натуральное число не превосходит 1000000000.

Выход: файл output.txt, содержащий в первой строке записанный в словесной форме строчными буквами результат вычисления. Предполагается, что результат вычислений – целое число от –1000000000 до 1000000000.

Пример 1:

Пример 2: