Муниципальное общеобразовательное учреждение

средняя общеобразовательная школа №4

Территориальный ресурсный центр

Тверская область, г. Нелидово, ул. Карбышева 14А

Областная олимпиада по информатике

2005 года

Задачи I тура

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

Сотрудники завода по производству золотого песка из воздуха решили поправить свое финансовое положение. Они пробрались на склад завода, где хранился золотой песок трех видов. Один килограмм золотого песка первого вида они смогли бы продать за А₁ рублей, второго вида — за А₂ рублей, а третьего вида — за А₃ рублей. Так получилось, что у сотрудников оказалось с собой только три емкости: первая была рассчитана на В₁ килограмм груза, вторая на В₂ килограмм, а третья на В₃ килограмм. Им надо было заполнить полностью все емкости таким образом, чтобы получить как можно больше денег за весь песок. При заполнении емкостей нельзя смешивать песок разных видов, то есть, в одну емкость помещать более одного вида песка, и заполнять емкости песком так, чтобы один вид песка находился более чем в одной емкости.

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

Технические требования:

Имя входного файла: INPUT.TXT Имя выходного файла: OUTPUT.TXT

Ограничение по времени тестирования: 1 секунда на один тест.

Формат входных данных:

Входной файл INPUT.TXT . В первой строке записано число N, равное количеству тестов.

В каждой следующей строке (N строк) содержится по 6 натуральных чисел А₁, А₂, А₃, В₁,В₂, В₃. записанных через пробел. Все числа не превосходят 100.

Формат выходных данных:

Выходной файл OUTPUT.TXT должен содержать N строк, содержащих ответы на соответствующие тесты.

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

Пример файлов входных и выходных данных:

INPUT.TXT

OUTPUT.TXT

2 12 3 3 2 1 1112 2 2

Задача 2. "Расшифровка"

Компания по защите интеллектуальной собственности решила повысить уровень защищенности своих операционных систем путем шифрования всех сообщений, передаваемых внутри ее локальных сетей. Любое допустимое в компании сообщение представляет собой строку S = S₁,S₂...S_n состоящую исключительно из букв латинского алфавита. Шифрование сообщения осуществляется в К фаз. На каждой фазе строка X заменяется строкой, в которой сначала располагаются все буквы строки S, стоящие на позициях с номерами, являющимися простыми числами (первый блок), а затем - все остальные буквы (второй блок). Напомним, что число называется простым, если оно -натуральное и имеет ровно два натуральных делителя. Относительный порядок букв в каждом из двух блоков остается неизменным. Например, строка S = abcdefgh на первой фазе шифруется в строку S = bcegadfh. Если осуществляется вторая фаза шифрования, то строка S примет вид S = ceafbgdh. После передачи зашифрованного сообщения по сети оно должно быть дешифровано, чтобы получатель смог прочитать исходную запись.

Требуется написать программу, осуществляющую дешифрование заданной строки, являющейся результатом шифрования строки S после К фаз.

Технические требования:

Имя входного файла: INPUTn.TXT Имя выходного файла: OUTPUTn.TXT

Ограничение по времени тестирования: 1 секунда на один тест

Формат входных данных: В первой строке входного файла INPUTn.TXT содержится натуральное число К (1<К<100), вторая строка содержит сообщение 5 после К фаз шифрования, состоящее из я ( 1<п<255) как прописных, так и строчных букв латинского алфавита. Регистр букв в процессе шифрования остается неизменным.

Формат выходных данных: Выходной файл OUTPUTn.TXT должен содержать только одну дешифрованную строку S.

Пример файлов входных и выходных данных:

INPUT1.TXT	OUTPUT1.ТХТ
2 CEAFBGDH	ABCDEFGH
INPUT2.TXT	OUTPUT2.ТХТ
1 ВААААСВ	АВАСАВА

Задача 3. «Корпорация»

Структура некоторой корпорации такова, что каждый служащий, кроме служащих нижнего звена, является непосредственным начальником не менее чем одного другого служащего (возможно, служащего нижнего звена). Во главе компании стоит Президент, которому подчиняются либо непосредственно, либо по должностной иерархии все остальные служащие. Каждый служащий (разумеется, кроме Президента) имеет одного непосредственного начальника. Все служащие в этой структуре имеют индивидуальные номера от 1 до N (2<N<10001). Пример описания такой структуры приведен на рисунке, где сотрудник с номером 3 является Президентом и непосредственным начальником сотрудников с номерами 1 и 4, а сотрудник с номером 4 является непосредственным начальником сотрудника с номером 2. Структура корпорации является корпоративной тайной и строго охраняется.

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

Требуется написать программу, которая по сведениям, доступным на сайте, восстанавливает структуру корпорации.

Технические требования:

Имя входного файла: INPUTn.TXT

Имя выходного файла: OUTPUTn.TXT

Ограничение по времени тестирования: 1 секунда на один тест.

Формат входных данных:

Во входном файле INPUTn.TXT на одной строке содержится последовательность чисел, определяющая все пути следования писем от Президента до каждого служащего нижнего звена. Каждый путь описывается соответствующими номерами служащих, разделенными пробелами. Например, для приведенной на рисунке структуры таких путей будет два: 3 4 2 и 3 1. Пути в последовательности указываются в произвольном порядке. Гарантируется, что заданная последовательность корректна, то есть существует корпорация, ей соответствующая.

Формат выходных данных:

Выходной файл OUTPUTn.TXT должен содержать N строк. В каждой i-й строке (1≤i≤N должны располагаться в порядке увеличения номеров все номера служащих, непосредственно подчиненных i-му служащему. Все числа в строке разделены пробелом. Последним в каждой строке должно быть число 0. Если решений несколько, необходимо вывести любое.

Пример файлов входных и выходных данных:

INPUT1.ТХТ	OUTPUT1.ТХТ
3 4 2 3 1	0 0 14 0 2 0

2 тур

Задача 4. “Долина Золотоискателей” (50 баллов)

В долине Золотоискателей находятся N ярко выраженных мест добычи золота, каждое из которых представляет собой квадрат размером 1x1, причем никакие два квадрата не пересекаются. Каждое такое место характеризуется величиной A_i – средним годовым доходом от продажи добытого золота.

Американский миллионер Дж. Скрудж хочет приобрести в долине Золотоискателей квадратный участок, на территории которого находился бы такой набор мест добычи золота, чтобы их суммарный средний годовой доход был не менее величины . Конечно, искомый участок должен иметь минимальную площадь.

Требуется написать программу, с помощью которой можно найти расположение искомого участка.

Технические требования:

Имя входного файла: INPUTn.TXT

Имя выходного файла: OUTPUTn.TXT

Ограничения по времени тестирования: 5 секунд на каждый тест

Формат входных данных:

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

Формат выходных данных:

Стороны искомого квадратного участка должны быть параллельны осям координат. В выходном файле OUTPUTn.TXT в единственной строке должна содержаться фраза NO SOLUTION, если искомый участок не существует, или располагаться через пробел четыре целых числа – координаты левой верхней и правой нижней вершин искомого участка соответственно.

Пример входных и выходных данных

INPUT1.TXT

OUTPUT1.TXT

4 5

1 1 1

3 4 4

3 1 4

2 2 3

2 1 4 3

Задача 5. Игра "Перевертыши" (30 баллов)

Имеется полоска, состоящая из М квадратов (М £ 100),. На каждом квадрате есть кнопка и лампочка. Лампочка может светиться одним из трех цветов: красным, зеленым или синим. При нажатии на кнопку, расположенную на какой-либо клетке, меняется цвет лампочки в этой клетке и во всех клетках, имеющих с данной общую сторону. Смена цвета лампочек всегда осуществляется по правилу: красный меняется на зеленый, зеленый на синий, а синий на красный.

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

Технические требования:

Имя входного файла: INPUTn.TXT

Имя выходного файла: OUTPUTn.TXT

Ограничение по времени тестирования: 5 секунд на каждый тест

Формат входных данных:

В строке входного файла INPUTn.TXT содержится описание начального состояния поля. Строка представляет собой последовательность символов, задающих цвета лампочек. Символ «R» обозначает красный цвет, «G» - зеленый, а «B» - синий.

Формат выходных данных:

Выходной файл OUTPUTn.TXT должен содержать единственное целое число -наименьшее количество нажатий кнопок, необходимое, чтобы лампочки на всей полоске засветились одним цветом. Если решения не существует, в ответе – NO