Олимпиада по информатике школьников Республики Татарстан Зональный тур, 9 декабря 2010 г.

5:05 дп | Программирование Автор: prepod

Выкладываю для интересующихся оригинал прошлогоднего олимпиадного задания по Республике Татарстан.

Уважаемый участник олимпиады!

В связи с автоматизированной проверкой работ, жюри убедительно просит соблюдать следующие технические требования:
Программы следует сохранять в файлах с именами заданного формата: длина имени — шесть символов, из них первый символ — Z, второй символ — номер зоны, третий и четвёртый символы — регистрационный номер участника, пятый — символ _ подчеркивания, шестой символ — номер задачи. Расширение имени файла — .PAS или .BAS, в зависимости от используемой среды программирования. Например, участник зонального тура в пятой зоне, зарегистрированный под номером №9, Pascal-программу решения первой задачи должен сохранить в файле с именем Z509_1.PAS
Имена дисковых файлов, содержащих входные и выходные данные, в программе следует записывать без указания диска и пути по каталогам, то есть должно быть записано только собственное имя файла: INPUT.TXT или OUTPUT.TXT.
Следует строго соблюдать предписанный в заданиях формат вывода результатов.
Ограничение по времени тестирования задано в расчете на использование процессора с тактовой частотой не менее 800 Мгерц.

1. Кубики (20 баллов)

Фабрика по производству настольных игр собирается изготовить N игральных кубиков. В ходе их изготовления необ­ходимо тщательно обработать поверхность кубиков. Для этого кубики укладываются в один слой на лоток (не более M штук за один раз), и шлифовальный круг, вращающийся в горизонтальной плоскости, в течение одной минуты шлифует верхние грани всех уложенных кубиков одновременно. Затем на лоток укладывается новая порция кубиков (или те же самые переворачиваются другой гранью кверху), и снова включается шлифовальный круг. Для уменьшения износа шлифовального круга желательно минимизировать время его работы.
Требуется составить программу, определяющую минимальное время, которое необходимо для обработки всех кубиков.
Технические требования:
Входной файл: INPUT.TXT.
Выходной файл: OUTPUT.TXT.
Ограничение по времени тестирования: 1 секунда на один тест.
Формат входных данных:
Входной файл INPUT.TXT содержит два разделённых пробелом целых числа: N (0 <= N <= 1000000) — количество кубиков и M (1 <= M <= 1000000) — вместительность лотка.
Формат выходных данных:
Выходной файл OUTPUT.TXT содержит одно целое число – минимальное время работы шлифовального круга в минутах.

Примеры файлов
входных данных:
Примеры файлов
выходных данных:
20 30 6
6 4 9

2. Торт (25 баллов)

На день рождения Васи Пупкина мама испекла торт и украсила его поверхность ягодами разных сортов. Торт был испечен в форме прямоугольника размером M x N. Каждый квадратный участок торта размером 1 x 1 был украшен только одной ягодой. Угощая друзей, Вася задумался, на какое минимальное количество кусков можно разрезать торт так, чтобы каждый кусок был украшен только одним из двух сортов ягод.
Требуется составить программу, вычисляющую это минимальное количество K.
Замечание. Два участка торта могут принадлежать одному куску, если они имеют общую горизонтальную или вертикальную границу.

Технические требования:
Входной файл: INPUT.TXT.
Выходной файл: OUTPUT.TXT.
Ограничение по времени тестирования: 1 секунда на один тест.
Формат входных данных:
Первая строка входного файла INPUT.TXT содержит два разделенных пробелом натуральных числа M, N, не превосходящих 10 000. Последующие M строк содержат описание поверхности торта, украшенного различными сортами ягод. Каждая строка состоит из N разделенных пробелами символов «1» и «2», соответствующих сортам ягод.
Формат выходных данных:
Выходной файл OUTPUT.TXT содержит одно число K.

Пример файла
входных данных:
Пример файла
выходных данных:
4 5
1 2 1 2 2
1 1 2 1 2
2 1 2 1 1
2 1 1 1 2
7

Пояснение к примеру. На рисунке показан пример разрезания торта на семь кусков, каждый из которых украшен одним сортом ягод.

1 2 1 2 2
1 1 2 1 2
2 1 2 1 1
2 1 1 1 2

3. Медианты (25 баллов)

Мориц и Ахилл вырастили дерево, на ветки которого по­местили рациона­льные числа. Более точно, это выглядело так. Начав с двух дробей {  ,  }, они повторяли необходимое количество раз следующую операцию: между двумя соседними дробями и вставляли медианту – новую дробь  . К примеру, первая операция добавляет новую дробь между дробями   и  :? ,  ,  . Следую­щий шаг добавляет две новых дроби:  ,  ,  ,  ,  . Последую­щий шаг добавляет четыре:  ,  ,  ,  ,  ,  ,  ,  ,  , и так далее. Совокупность вставок можно изобразить в виде бесконечного дерева, вер­хние уровни которого выглядят так:
Воспользуемся символами L и R для обозначения левой и правой ветви при продвижении вниз по дереву от корня к некоторой определенной дроби. Тогда строка символов L и R будет однозначно определять местонахождение дроби в этом дереве. Так, RLRR означает продвижение вправо от к  , затем вниз влево от к  , затем вправо к  , и наконец, еще раз вправо к . Строку RLRR можно рассматривать как представ­ление дроби .
Требуется составить программу, которая для данной положительной рациональной дроби находит ее представление в виде строки символов L и R.

Технические требования:
Входной файл: INPUT.TXT.
Выходной файл: OUTPUT.TXT.
Ограничение по времени тестирования: 1 секунда на один тест.
Формат входных данных:
Входной файл INPUT.TXT содержит два разделенных пробелом натуральных числа M, N, не превосходящих 32 000.
Формат выходных данных:
Выходной файл OUTPUT.TXT содержит число 0, если требуемую дробь получить невозможно. Если решение существует, выходной файл OUTPUT.TXT содержит строку символов L и R, соответствующую движению по дереву от корня к дроби  .

Примеры файлов
входных данных:
Примеры файлов
выходных данных:
3 1 RRR
8 6 RRLL

4. Игры с числами (30 баллов)

Имеется последовательность из N различных целых чисел A1, A2, … , AN. Разрешается выбрать любые из них и увеличить на 1. Если после этого преобразования появятся равные числа, в последовательности оставляют только одно из них.
Это преобразование можно применить последовательно K раз, чтобы оставить в последовательности минимальное количество чисел.
Требуется составить программу, вычисляющую минима­льное количество P чисел, оставшихся в последовательности.
Технические требования:
Входной файл: INPUT.TXT.
Выходной файл: OUTPUT.TXT.
Ограничение по времени тестирования: 1 секунда на один тест.
Формат входных данных:
Первая строка входного файла INPUT.TXT содержит два целых числа N и K (0 < N< 50 000, 0 < K < 1 000 000). В последующих строках записаны разделенные пробелами и/или символами новой строки N целых чисел: A1, A2, … , AN из интервала (?32 000; 32 000).
Формат выходных данных:
Выходной файл OUTPUT.TXT содержит одно число P.

Пояснение к примеру. На первом шаге увеличим на единицу числа 7 и 1. Новая последовательность 8, 2, 15, 8, 3 содержит равные числа 8, поэтому оставляем только одно из них: 8, 2, 15, 3. На втором шаге увеличим на единицу число 2 и из получившегося набора 8, 3, 15, 3 удаляем одно из повторяющихся чисел. Окончательный набор 8, 3, 15 содержит три числа.

VN:F [1.9.22_1171]
Rating: 9.0/10 (2 votes cast)
VN:F [1.9.22_1171]
Rating: 0 (from 0 votes)
Олимпиада по информатике школьников Республики Татарстан Зональный тур, 9 декабря 2010 г., 9.0 out of 10 based on 2 ratings

No related posts.