Задания олимпиады по информатике – 2014

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

Виртуальный кабинет

Каждая команда или индивидуальный участник получает после регистрации доступ к Виртуальному кабинету.
С помощью Виртуального кабинета команда/индивидуальный участник:

• публикует свою Визитную карточку
• узнает новости проекта, уточняет ключевые даты
• подает ответы на задания Интернет-олимпиады
• отправляет письма координатору
• оставить свои отзывы и пожелания организаторам проекта

 

Ключевые даты

Этапы выполнения заданий 1 тура	Дата получения (начала выполнения) задания	Дата окончания выполнения задания
Подготовка Визитки команды и загрузка файла через Виртуальный кабинет	после подтверждения регистрации	11-00 (мск) 10 ноября 2014 г.
Выполнение заданий проекта, загрузка работ через Виртуальный кабинет	11-00 (мск) 10 ноября 2014 г.	17-00 (мск) 19 ноября 2014 г.
Публикация итогов проекта		11-00 (мск) 2 декабря 2014 г.
Команды отправляют отзыв о проекте из Виртуального кабинета.	3 декабря 2014	4 декабря 2014 г.

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

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

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

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

Задача 1. Числа

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

Задача 2. Золотой песок

Грабитель пробрался на завод по производству золотого песка. Он обнаружил, что склад завода заполнен тремя видами золотого песка. Один килограмм золотого песка первого вида на черном рынке стоит A₁ у.е., второго – A₂ y.e., а третьего – А₃ у.е. К несчастью, у грабителя есть только три сумки: первая рассчитана на В₁ килограмм, вторая – на В₂ килограмм, третья – на В₃ килограмм. В силу ряда причин, грабитель не может смешивать песок (т. е. помещать в одну сумку два вида песка) и размещать песок одного вида более чем в одной сумке.

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

Задача 3. Алгоритм

В представленной ниже блок-схеме описан рекурсивный алгоритм F с целым неотрицательным параметром n и целым неотрицательным параметром-переменной a.

Определите, что делает данный алгоритм, и опишите нерекурсивный алгоритм, который делает то же самое. Операция "/" – операция целочисленного деления (получение неполного частного от деления: например, 11/4 = 2).

Задача 4. Плохие лотерейные билеты

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

Требуется посчитать, сколько билетов нужно будет купить обществу трискайдекафобов, если известно, что лотерейные билеты имеют серийные номера от 0 до 10^N-1.

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

Задача 5. Двапалиндром

Болезнь – это здоровая реакция организма на нездоровый наш образ жизни.
Л. Сухоруков.

В современном мире очень много психических заболеваний. Кто-то страдает шизофренией, у кого-то тяжелая форма зависимости от интернета. Но в начале 2013 года стала набирать обороты новая болезнь, которая называется двапалиндромия. Заболевшие начинают превращать все слова в двапалиндромы. Скорее всего, вам известен термин «двапалиндром», но, возможно, кто-то его не знает, поэтому для них мы дадим определение двапалиндрома. Двапалиндром – это строка, которая является палиндромом, и каждая половина этой строки так же является палиндромом. Напомним, что палиндром – это строка, которая читается одинаково в обоих направлениях. Кстати, самое длинное употребительное слово-палиндром в мире – saippuakauppias. Но вернемся к нашим двапалиндромам. Примером двапалиндрома может служить слово «abbaabba». Для лечения двапалиндромии компания «Бугл» придумала специальные очки «БуглБлаз». Больной, надевавший эти очки, видел не просто слова, а слова-двапалиндромы. Через 26 дней ношения таких очков больной выздоравливал.

Доктором физико-математических наук, профессором Шмаковым из Лифляндского государственного университета, было установлено, что излечиться можно гораздо быстрее, если слова будут превращаться в двапалиндромы минимальным количеством изменения букв в исходном слове. Для подтверждения этой гипотезы он провел восемь экспериментов. Теперь многоуважаемый профессор хочет исправить программу в очках «БуглБлаз» таким образом, чтобы она превращала слова в двапалиндромы за минимальное количество изменений символов. Но существует одна проблема: профессор совершенно не умеет программировать, так как это очень просто.

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

Задача 6. Сортировка

Вам дана перестановка из n чисел (последовательность из n чисел, все элементы которой различны и принимают значения от 1 до n: например, 3 2 4 1 – перестановка, а 3 1 5 2 – нет). Вы можете делать с ней следующее: 1) выбрать отрезок перестановки четной длины; 2) поменять половины отрезков местами. Опишите алгоритм, сортирующий перестановку по возрастанию её элементов за минимальное количество действий. Числа в перестановке можно сравнивать между собой.

Пример:

Рассмотрим перестановку 3 1 2

Возьмём отрезок перестановки [1,2], т. е. возьмём элементы с номерами от 1 до 2 включительно. Поменяем половины местами. Получим 1 3 2. Теперь возьмём отрезок перестановки [2,3], поменяем местами его половины. Получим 1 2 3. Итак, перестановка отсортирована по возрастанию.

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

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

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

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

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

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

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

Задача 1. Счастливые билетики по–ярославски

Есть счастливые билетики по–московски, есть счастливые билетики по–питерски, но мало кто слышал про счастливые билетики по–ярославски. В ярославском общественном транспорте номера билетиков состоят из 2N цифр. Билетик называется счастливым, если ярославская сумма первых N цифр равна ярославской сумме последних N цифр. Требуется найти количество счастливых билетиков по–ярославски для заданного N. На первый взгляд, задача простая, но что же такое «ярославская сумма»? Для заданного числа k найдем сумму его цифр, если получившееся число состоит из двух и более цифр, то найдем сумму цифр этого числа и т. д., пока не получим число, состоящее из одной цифры. Такая сумма цифр называется «ярославской суммой цифр». Билетики нумеруются от 00…000 до 99…999.

Вход: файл input.txt, в первой строке которого записано натуральное число N.

Ограничения: 1 ≤ N ≤ 1000

Выход: файл output.txt, содержащий одно число – количество счастливых билетиков по модулю10⁹+7 (т.е. остаток от деления количества счастливых билетиков на 10⁹+7)

Примеры

input.txt	output.txt
1	10
6	110888113

Задача 2. Замощение улицы

Новый мэр Эль-Пасо Авраам Гарфилд решил замостить главную улицу города и для этой работы нанял бригаду рабочих во главе с Джорджем Шерманом. Улица представляет собой полосу длиной 4*N метров. Бригада Джорджа будет покрывать её плитками размера 1*2 метра. Плитки можно укладывать как горизонтально, так и вертикально. Шермана интересует, сколькими способами он может замостить главную улицу Эль-Пасо. Так как это число может быть очень большим, то от вас требуется найти число замощений по модулю 10⁹+7 (т.е. найти остаток от деления количества замощений при делении на 10⁹+7).

Вход: файл input.txt, в первой строке которого записано натуральное число N (ширина дороги в Эль-Пасо).

Ограничения: 0 < N < 113

Выход: файл output.txt, содержащий одно число – количество различных способов замостить улицу плитками 1*2 по модулю 10⁹+7 (т.е. остаток от деления количества способов замостить улицу на 10⁹+7).

Примеры

input.txt	output.txt
2	5
3	11
7	781

Пояснение к примерам

Улицу длиной 4*2 метра (первый тест из примеров) можно замостить 5 следующими способами:

Задача 3. Упаковка печенья

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

В любой момент ваша линия производства выпускает новые печеньки, которые хранятся в печенькохранилище, ожидая упаковки. Время от времени поступают запросы с конвейера по упаковке – отправить из печенькохранилища ту печеньку, которую нужно упаковать. Перед поступлением в хранилище, диаметр каждой печеньки измеряется с точностью до 1 нанометра. На упаковку отправляется печенька, являющаяся медианой среди всех печенек. Что такое медиана? Если мы отсортируем печеньки по возрастанию диаметров, то, если печенек нечетное количество c, то на упаковку идёт печенька на позиции (c+1)/2 в отсортированной последовательности. Если же c – четное число, то печенька на c/2+1 в отсортированной последовательности. Если печеньку отправляют на упаковку, то она пропадает со склада. Ваша задача – промоделировать работу системы упаковки печенек.

Вход: файл input.txt, в каждой входной строке которого содержится либо положительное число d, означающее, что в хранилище поступает новая печенька диаметром d нанометров, либо символ '#', означающий запрос с конвейера по упаковке.

Ограничения: 1 ≤ d ≤ 300 000 000; количество строк ввода не более 600 000; также следует считать, что хранилище пусто до тех пор, пока туда не поступит первая печенька.

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

Примеры

input.txt	output.txt
1 2 3 4 # # # #	3 2 4 1
1 # 2 # 3 # 4 #	1 2 3 4