Всероссийские олимпиады

 

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

17-22 марта 1989 года, Красноярск

Теоретический тур

 

1. Прямоугольник ABCD задан координатами своих вершин. На проти­вопо­ложных сторонах AB и CD заданы последовательности R1 и R2 из N то­чек разбие­ния, а на сторонах BC и AD - R3 и R4 из M точек разбиения. Ну­мерация элементов последовательностей R1 и R2 начинается соответственно от точек A и D, а R3 и R4 - от точек B  и  A. Соединив отрезками точки с одинаковыми номерами в разбиениях R1 и R2, а затем в разбиениях R3 и R4, получим разбиение Q прямоугольника ABCD на множество четырехугольни­ков.

Построить алгоритм, определяющий четырехугольник разбиения Q с наиболь­шей площадью, при условии, что отрезки, соединяющие точки раз­биений R1 и R2 параллельны стороне AD.

Последовательности R1, R2, R3 и R4 задаются как массивы из длин от­резков разбиения соответствующих сторон прямоугольника.

2. Построить алгоритм, моделирующий на экране дисплея движение с постоян­ной скоростью V двух окружностей радиуса R внутри прямоугольной области, за­данной координатами своих вершин. В момент начала движения координаты цент­ров окружностей - (X1,Y1) и (X2,Y2), а углы между траекто­риями движения и верти­кальной осью координат - A1 и A2. Столкновения окружностей между собой и с гра­ницами области - упругие.

3. Данные N косточек домино по правилам игры выкладываются в пря­мую це­почку начиная с косточки, выбранной произвольно, в оба конца до тех пор, пока это возможно.

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

4. Имеются два одинаковых диска. На каждом из них есть круглое отвер­стие радиуса R, касающееся границы диска. Диски расположены горизон­тально, плотно прижаты друг к другу и скреплены общей осью, проходящей через их центр враще­ния. Верхний диск неподвижен, а нижний равномерно вращается с заданной угловой скоростью W2. Вдоль границы верхнего диска катятся с постоянной угловой ско­ростью W1 N шаров радиуса R. Шары рас­положены  плотно друг за другом и про­нумерованы цифрами от 1 до N. Если при совпадении отверстий на дисках шар про­валивается, то плотность цепоч­ки шаров "мгновенно" восстанавливается.

Построить алгоритм, позволяющий определить номера первых M шаров, вы­павших при совпадении отверстий на дисках, если в момент начала движе­ния угол между центрами отверстий верхнего и нижнего дисков был равен A1, а угол между центрами отверстия верхнего диска и первым шаром  цепоч­ки - А2. Угол сектора, по дуге которого расположена цепочка шаров, равен А3.

 

Практический тур

 

1. На интервале (1000; 9999) найти все простые числа, каждое из которых обла­дает тем свойством, что сумма первой и второй цифры записи этого чис­ла равна сумме третьей и четвертой цифр.

2. Найти все цифры десятичной записи числа .

 

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

Нальчик, 1990 год

Теоретический тур

 

1. На двумерной плоскости задано N точек с координатами (X1, Y1), (X2, Y2), ..., (XN, YN). Построить алгоритм, позволяющий из этих точек выделить вершины квадрата, содержащего максимальное число заданных точек.

Примечание: предполагается, что точки, расположенные на сторонах квадрата, принадлежат ему.

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

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

3. В городе имеется n автобусных остановок, обозначенные числами 1, 2, 3, ..., n. Проложено r автобусных маршрутов, заданных последовательностями соседних остановок при движении автобуса в одном направлении:

M1= ( i11, i12, ..., i1m1),

M2= ( I21, i22, ..., i2m2),

..........................,

Mr= ( ir1, ir2, ..., irmr),

где ijk из множества чисел от 1 до n.

Построить алгоритм, который по заданным номерам остановок i и j оп­ределяет наиболее быстрый путь перемещения пассажира от остановки i до остановки j с ис­пользованием имеющихся маршрутов автобусов и при усло­вии, что время движения между соседними остановками у всех маршрутов одинаково и в 3 раза меньше вре­мени однократного изменения маршрута. Кроме того, автобусы движутся в обоих направлениях.

4. На квадратном поле размером 3*3 с помощью датчика случайных чи­сел рас­ставлены 8 фишек с номерами от 1 до 8 (рис.1). Построить алгоритм расстановки фишек по возрастанию их номеров так, как показано на рис.2. Передвигать фишки можно только на соседнюю свободную позицию.

 

1

7

3

 

1

2

3

 

6

5

2

 

4

5

6

 

8

4

 

 

7

8

 

 

Рис. 1

 

Рис. 2

 

Практический тур

 

1. Заданы 121 натуральных чисел - 1, 2, 3, ..., 121.

Составить программу, которая расположит эти числа в 11 групп так, что одно­временно будут выполняться следующие условия:

1) каждая группа содержит точно 11 чисел;

2) каждое число принадлежит только одной группе;

3) сумма чисел в каждой отдельной группе одинакова для всех групп.

2. Составить программу, которая в полной записи числа 77! (77 факто­риал) укажет в порядке убывания номера разрядов, содержащих цифру 7.

Примечание: разряды числа нумеруются в следующем порядке: разряд единиц имеет номер 1, десятков - 2, сотен -3 и т.д.

 

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

Красноярск, 1991 год,

Теоретический тур

 

1. "Черный ящик". (Степанов В.И.) На вход "черного ящика" подается любая таблица, содержащая символы латинского алфавита. На выходе полу­чается 3 строки результата. Например:

а)  ,         б)  .

Опишите алгоритм, по которому мог бы работать этот "черный ящик".

2. "Караван". (Шостак Г.А.) Географическая карта местности задана квад­рат­ной сеткой определенного масштаба. В узлах сетки известна высота над уровнем моря. Между соседними узлами высота меняется плавно. Караван перемещается только  по линиям сетки. (Перемещение по диагонали запре­щается). Путь между двумя соседними точками с углом наклона больше 45 градусов считается непрохо­димым.

Провести караван из точки А(X1, Y1) в точку В(X2, Y2) по  пути с наи­меньшим перепадом высоты или сообщить об отсутствии решения.

Примечание: Перепадом высот на маршруте называется разность высот между самой высокой и самой низкой точками маршрута.

3. "Царевна". (Шепелевский А.С.) В одной из клеток поля n*n  (n>1) Кощей Бессмертный спрятал Марью Царевну, создав еще неизвестное число m (1<m<п*n) ее двойников в различных свободных клетках. И царевна, и ее двойники одинаково на­дежно укрыты и невидимы.

Отправившийся на поиски царевны Иванушка-дурачок попросил у бла­говоля­щей к нему щуки датчик биосигналов. Известно, что и Марья Царевна и ее двойники испускают незатухающие направленные биолучи, распростра­няющиеся параллельно сторонам и диагоналям поля.

Иванушка-дурачок также знает, что интенсивность биолуча Марьи Ца­ревны в m раз выше интенсивности биолучей двойников. Иванушка может установить свой датчик в любую клетку поля и получить величину суммарной интенсивности биолу­чей, приходящих в клетку.

Помогите Иванушке определить местонахождение настоящей царевны.

4. "Часы". (Сенокосов А.И.) Фирма "Школьник" предлагает разработать для электронных часов младших школьников режимы работы и трехкнопоч­ную систему управления ими.

Опишите режимы работы часов, содержание отображаемой информации в каждом из режимов, функции кнопок.

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

 

Практический тур

 

1. "Удав". (Жданов С.А.) Прямоугольная область задана своими коорди­натами:  (X1,Y1) - левая верхняя вершина и (X2,Y2) - правая нижняя верши­на. По границе об­ласти ползет удав длины L со скоростью V. Внутри области движется точка со ско­ростью V1. Точка начинает движение вниз от границы области на заданном расстоя­нии S от ее верхнего левого угла и под углом A к нижней линии области. Точка дви­жется, отражаясь от стенок до тех пор, пока не столкнется с удавом. Объекты начи­нают движение одновременно.

Составить программу, вычисляющую количество отражений точки от границ области и время до столкновения с удавом. Если при стократном от­ражении точка не столкнулась с удавом, программа прекращает работу, сооб­щив об этом событии.

2. "Полоска". (Ватолин Д., Прохоров В.В.) Расположенную вертикально прямо­угольную бумажную ленточку с закрепленным нижним концом стали складывать следующим образом:

- на первом шаге ее согнули пополам так, что верхняя половина легла на ниж­нюю либо спереди (П - сгибание) либо сзади (З - сгибание),

- на последующих  n-1 шагах выполняли аналогичное действие с полу­чающейся на предыдущем шаге согнутой ленточкой, как с единым целым.

Затем ленточку развернули , приведя ее в исходное состояние. На ней остались сгибы - ребра от перегибов, причем некоторые из ребер оказались направленными выпуклостью к нам (К - ребра), а некоторые - от нас (О -ребра). Ребра пронумеро­вали сверху вниз числами от 1 до 2n-1 .

А. Составить программу, запрашивающую:

- строку символов из прописных букв "П" и "З", определяющую последо­ватель­ность типов сгибаний,

- номер ребра, и сообщающую тип этого ребра, получившийся после за­данной последовательности сгибаний.

Б. Составить программу, запрашивающую строку символов из прописных  букв "О" и "К", где нахождение на i-том месте символа "О" или "К" определя­ет тип ребра на расправленной полоске, и выдающую строку из прописных "П" и "З", определяю­щих последовательность типов сгибаний, посредством которых получена ленточка с исходной последовательностью ребер. Если та­кой строки не существует, сообщить об этом.

 

 

IV Всероссийская олимпиада

22-27 марта 1992 года, Троицк Московской области

 

Задача I тура (автор В.В.Прохоров)

 

Пусть W-множество всех замкнутых односвязных ломанных на коорди­натной плоскости xOy, удовлетворяющих условиям:

а) каждые два соседних звена ломанной взаимно  перпендикулярны;

б) каждое звено ломанной параллельно одной из осей координат;

в) отсутствуют самопересечения или самокасания ломанной;

г) (x1, y1), ..., (хN, yN)- целочисленные координаты всех точек, где ло­манная претерпевает излом (порядок нумерации произволен и неизвестен), N- количество изломов.

Требуется:

А. Написать по взможности оптимальные (по времени исполнения) про­граммы с обоснованием алгоритмов), которые по задаваемым N и (x1, y1),..., (xN, yN) выда­вали бы и отображали на экране монитора:

1) какую-либо ломанную из множества W;

2) ломанную из множества W, имеющую наибольшую длину, и значение этой длины;

3) ломанную  из множества W, ограничивающую наибольшую площадь, и зна­чение этой площади;

4) количество ломанных в множестве W.

Б.Решить задачу А, исключив пункт б) из определения W.

ПРИМЕЧАНИЕ. Односвязной называется ломанная, из любой точки ко­торой можно попасть в любую другую ее точку, двигаясь по этой ломанной.

 

Задача II тура (авторы Е.В.Андреева и А.П.Марченко)[7, 92 г., 5-6]

 

В билете пассажира оказалось пробито отверстий больше, чем штырей в ком­постере. Пассажир утверждал, что пользовался только одним компосте­ром, но слу­чайно нажал его несколько раз. Контролеру требуется определить, могло ли быть получено заданное расположение отверстий одним и тем же компостером, если билет можно пробивать с обеих сторон неограниченное число раз и произвольно переме­щать и поворачивать относительно компосте­ра. Пробитые отверстия не выходят за пределы билета. В билете было проби­то N (N<10) отверстий.

Требуется:

А. Для компостера с двумя штырями (S=2) составить программу, которая:

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

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

3) При K=0 (см. пункт 2) находит компостер, с помощью которого мож­но про­бить наибольшее количество из заданных отверстий.

4) Находит минимальное число нажатий, требуемое для пробивки задан­ной конфигурации отверстий, для каждого компостера из пункта 2.

Б. Решить задачу А для компостеров с числом штырей S (S>2).

Примечания. Все исходные данные - натуральные числа. Компостеры, дающие при однократном нажатии совпадающие конфигурации отверстий, считаются оди­наковыми. Относительное расположение отверстий в билете и штырей в компостере вводятся либо с клавиатуры, либо из файла с именем COMP.DAT. Структура вводи­мой информации: {N, x1, y1, ..., xN, yN, S, u1, v1, ..., uS, vS}, где xi, yi- коодинаты от­верстий в билете, ui, vi - координаты штырей в компостере. Нажатие компостера следует моделировать клавишей "Пробел". При выводе конфигурации на экран сле­дует изображать координат­ную сетку. При этом программа должна осуществлять подходящее масштабирование.

 

V Всероссийская олимпиада

1993 год, г. Троицк Московской области

 

Задача I тура (автор А.А.Суханов)

 

Компьютерная сеть состоит из связанных между собой двусторонними кана­лами связи N компьютеров, номера которых от 1 до N. Эта сеть предна­значена для распространения сообщения от центрального компьютера всем остальным. Компью­тер, получивший сообщение, владеет им и может распро­странять его дальше по сети. Запрещается передавать сообщение на один и тот же компьютер дважды. Время пе­редачи сообщения по каналу связи зани­мает одну секунду, при этом передающий и принимающий компьютеры заня­ты на все время передачи данного сообщения. На рис. приведен возможный вариант такой сети.

Рис.

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

Для сети, показанной на рис.1, возможный порядок распространения со­обще­ния от центрального компьютера с номером 6 приведен в примере.

ПРИМЕР.

Секунда 1:         6->4

Секунда 2:         4->3

                           6->7

Секунда 3:         3->1

                           4->5

Секунда 4:         3->2

Написать программу, которая:

а) вводит описание сети, проверяет корректность этого описания и, в случае его некорректности, печатает соответствующее сообщение, заканчивая работу;

б) определяет и печатает какой-либо порядок распространения сообще­ния;

в) определяет и печатает порядок передачи сообщения за минимальное время (порядок распространения сообщения для сети на рис., приведенный в примере 1, яв­ляется оптимальным).

ТЕХНИЧЕСКИЕ ТРЕБОВАНИЯ

1) N не превосходит 50, а количество каналов связи не превосходит N+5.

2) Программа должна запрашивать имя входного файла; в крайнем случае до­пускается ввод данных с клавиатуры.

3) Сеть задается набором из N+2 строк в следующем формате:

строка 1:                        число компьютеров в сети (N);

строка 2:                        список всех соседей компьютера 1 (представляется                                             набором чисел, разделенных пробелами);

строка 3:                        список всех соседей компьютера 2;

...

строка N+1:       список всех соседей компьютера N;

строка N+2:       номер центрального компьютера.

Так, приведенная на рис.1 сеть может быть представлена следующим об­разом:

7

2 3

1 3

1 4 2

6 5 3

4

7 4

6

6

4) Вывод результатов на экран должен быть таким, как в примере 1.

РАЗБАЛЛОВКА

1. Организация диалога с пользователем:                 - 5 баллов.

2. Пункт А:                                                                                            - 25 баллов.

3. Пункт Б:                                                                                            - 25 баллов.

4. Пункт В:                                                                                            - 30 баллов.

5. Выполнение технических требований:                             - 15 баллов.

 

Задача II тура (автор А.П.Овсянников)

 

Дан автобусный билет с номером, состоящим из N цифр. Расставить ме­жду цифрами знаки арифметических операций ('+', '-', '/', '*') и скобки таким образом, чтобы значение полученного выражения было равно 100. Можно об­разовывать мно­гозначные числа из стоящих рядом цифр.

Выражение должно быть корректным с точки зрения арифметики. Допус­тимы лишние скобки, не нарушающие корректности выражения.

Требуется написать программу, решающую эту задачу.

Примечания

1. Знаки операций означают:

   '+' -сложение;

   '-' -вычитание (унарный минус не допускается!);

   '*' -умножение;

   '/' -деление нацело.

2. Используется стандартный приоритет операций, т.е. выражение

6*5/7+5-1/3

интерпретируется так

((((6*5)/7)+5)-(1/3))

3. Число цифр N в номере билета не больше 6.

4. При возникновении затруднения в решении задачи допустимо частное реше­ние, использующее не все знаки арифметических действий и/или скоб­ки.

 

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

1. Программа вводит номер с клавиатуры с приглашением: Номер:

2. Программа выводит полученное выражение как это показано ниже:

0+(19+1)*5+0=100

3. Если для введенного номера решение найти не удается, программа должна пе­чатать:

123456=?

4. Предполагается, что все вводимые данные корректны.

 

РАЗБАЛЛОВКА

 

1. Организация диалога с пользователем                                         -  2

2. Полное решение                                                                                          - 33

Частные решения:

- не используется '/'                                                                                         - 28

- не используется '/ ,'*'                                                                                     - 10

- не используются скобки                                                                   - 11

- не используются скобки и '/'                                                                        - 10

- не используются скобки, '*', '/'                                                                     -  5

3. Удаление из выражения лишних скобок                           -  5

 

Задача II тура (автор В.В.Прохоров)

 

Существует 2 основные формы информационных описаний - текстовая и гра­фическая.

Текстовым представлением оператора присваивания будем считать запись вида

<Имя переменной>:=<Формула>

Здесь <Формула> состоит из целых десятичных констант, имен перемен­ных, имен произвольных функций одного аргумента, а также знаков арифме­тических опе­раций ('+', '-', '*', '/') и круглых скобок. Ограничимся случаем, когда имена функций, переменных и константы - только односимвольные.

Графическим представлением оператора присваивания будем считать схему, со­стоящую из элементов вида

и соединяющих их линий. Количество "входов" у элемента ровно количеству аргу­ментов соответствующей операции или функции, <Имя> - знак арифме­тической опе­рации или имя функции.

ПРИМЕР. Оператору присваивания "а:=S((b+c)*(d+e))" можно сопоста­вить та­кую схему:

ТРЕБУЕТСЯ. Разработать диалоговую программную среду для преобразо­ва­ния вводимых с клавиатуры текстовых представлений операторов присваи­вания в графические, отображаемые на экране монитора.

Примечания

1. Считать, что схема, соответствующая вводимому оператору, при разум­ном выводе заведомо помещается на экран дисплея.

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

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

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

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

2. Интерфейс по возможности должен обеспечивать:

   - удобный ввод;

   - удобную диагностику ошибок с возможностью их оперативного ис­правле­ния;

   - композиционное и цветовое оформление выводимой на экран инфор­мации;

   - наличие на экране необходимых для работы подсказок.

РАЗБАЛЛОВКА

Программа, выдающая схему:

   - для произвольного оператора присваивания                             - 25

   - только при ограничеии из Примечания 3                                    - 20

Диагностика ошибочного ввода                                                                    - 10

Интерфейс                                                                                                                    -  5

 

Дополнительные баллы жюри на обе задачи                       - 20 баллов.

 

Командное первенство

 

1. Перевести число, записанное в системе счисления с основанием p в число, за­писанное в системе счисления с основанием q. При этом 1<p<37 и 1<q<37. В систе­мах счисления с основаниями, большими 10, для обозначения остальных цифр ис­пользуются прописные буквы латинского алфавита, анало­гично шестнадцатиричной системе. Так, в любой системе счисления с осно­ванием, большим 10, цифра, обозна­чающая 10 кодируется символом "A", а в системе с основанием 36 использованы все 26 букв латинского алфавита, то есть цифра, соответствующая 36 обозначается бук­вой Z.

Числа для перевода ваша программа должна считывать из текстового файла task1.dat. Каждая строка файла состоит из десятичного числа p, обозна­чающего основание исходной системы счисления, пробела, числа, записанно­го в системе счис­ления с основанием p, которое необходимо перевести в дру­гую систему, пробела и десятичного числа, обозначающего новую систему счисления.

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

2 1010100 8

7 32105 20

16 1AB03 5

Программа должна выдавать на экран копию считанного файла, добавляя в конец каждой строки, после числа q, пробел и результат перевода. Предпо­лагается, что все данные в файле корректны, а исходные числа для перевода не превосходят 2 000 000 000 (в десятичной системе).

2. Нить Ариадны. Тезею из лабиринта Минотавра помог выйти клубок ниток. Вы можете вместо клубка использовать персрнальный компьютер.

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

Маршрут Тезея вводится из файла task2.dat, где он представлен строкой, со­стоящей из букв: N, S, W, E.

Буквы означают:

N - один "шаг" на север,

S - один "шаг" на юг,

W - один "шаг" на запад,

E - один "шаг" на восток.

Например, если файл task2.dat содержит строку EENNESWSSWE то про­грамма должна выдать обратный путь NWW.

3. Весь графический экран вашего компьютера должен представлять со­бой таб­лицу 15*15, состоящую из одинаковых прямоугольников. Каждый пря­моугольник ваша программа должна заполнить случайным образом одним из 16 цветов, так чтобы в каждой строке и каждом столбце таблицы оказалось не менее 4 различных цветов.

Далее, на каждое нажатие пользователем клавиши "пробел", программа может закрасить один столбец или одну строку таблицы цветом, которым за­крашены по крайней мере два прямоугольника этой строки (столбца). Назо­вем это одним шагом работы программы.

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

4. Билли Бонс положил в сундук некоторое количество золотых монет. На вто­рой год он вынул из сундука сколько-то монет. Начиная с третьего года он добавлял столько монет, сколько было в сундуке два года назад. Сколько монет было в сун­дуке в первый и во второй года, если через X лет в сундуке оказалось ровно Y монет?

Пояснение: Если в первый год положить 5, а во второй вынуть 3 монеты, то на­чиная с первого года в сундуке будет 5, 2, 7, 9, 16, 25, ... монет.

Программа должна запрашивать с клавиатуры два числа X и Y на одной строке, разделенных пробелами. Пример ввода: 25 144, то есть X=25, Y=144.

 

VI Всероссийская олимпиада

1994 год, г. Троицк Московской области

 

Задача 1. БОЛЬНИЦА (автор В.В.Прохоров)

 

В процедурном кабинете N кушеток. Каждый из M пациентов должен принять на каждой кушетке процедуру. Некоторые пациенты могут иметь некоторое (одно и то же) кожное заболевание (кто именно - неизвестно, но их не более К). Некоторые из N кушеток являются источником этого заболевания (таковых наверняка не больше L). При соприкосновении с такой кушеткой пациент заражается.

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

Необходимо исключить инфицирование здоровых пациентов и увеличение количества зараженных кушеток после принятия процедур.

Для решения проблемы можно использовать стерильные простынки, поскольку сквозь ткань данная инфекция не передается. Из-за дефицитности  простынок ТРЕБУЕТСЯ определить алгоритм их перестилания на кушетках, обеспечивающий выполнение указанных требований при минимально возможном  расходе простынок. Разрешается стелить на кушетку друг на друга не более  Р простынок.

Компьютерная программа должна:

- запрашивать параметры M, N, К, L, Р;

- выдавать минимальное требуемое количество простынок;

- выдавать оптимальный в указанном смысле процесс застилания кушеток и принятия процедур, где

<Процесс>::=<Процедура>,<Процедура>, ...

<Процедура>::=<Номер пациента> /<Простынка> /<Простынка> /.../ <Номер кушетки>

<Простынка>::=<Номер простынки><Ориентация простынки>

Здесь <Ориентация простынки> - "a", если простынка лежит лицевой стороной вверх, и  "b"- в противном случае.

Пример. При M=1, N=З, K=0, L=1, P=2 программа должна выдавать  минимальное количество "2" и, например, последователъность 1/1а/1, 1/2а/2, 1/2а/1b/З.

 Примечания.

1. Контакт больного пациента с зараженной поверхностью ни к каким неприятным последствиям не приводит.

2. Общее время проведения процедур, их очередность, время ожидания пациентами очереди значения не имеют.

Оценка задачи

Максимальное количество баллов - 50.

 

Задача 2. ПАРКЕТ (автор С.Г.Волченков)

 

Комнату размером N*M единиц требуется покрыть одинаковыми плитками паркета размером 2*1 единиц без пропусков и наложений (M<=20, N<=8, M,N - целые). Пол можно покрыть паркетом различными способами. Например, для М=2, N=З все возможные способы укладки приведены на рисунке:

Задание:

Требуется определить количество всех возможнмх способов укладки паркета для конкретных значений M<=20, N<=8. Решением задачи является таблица, содержащая 20 строк и 8 столбцов.

Элементом таблицы является число, являющееся решением задачи для соответствующих M и N. На месте не найденных результатов должен стоять символ "*".

На рисунке приведен пример требуемой таблицы:

 

1

2

3

4

5

6

7

8

1

0

1

0

*

*

*

*

*

2

1

2

3

*

*

*

*

*

3

*

*

*

*

*

*

*

*

...

...

...

...

...

...

...

...

...

20

*

*

*

*

*

*

*

*

 

Таблица должна быть выровнена по столбцам и помещена в текстовый (АSCII) файл с именем "имя.RЕS", который обязательно сдается вместе с остальными файлами  данного тура.

Примечание.

Результат решения задачи будет оцениваться по содержимому файла  "имя.RES".

Оценка задачи:

Максимальное количество баллов - 50.

Чем больше правильно заполненных элементов таблицы, тем выше результат.

 

Задача З. БУКВОЕД (автор Е.В.Андреева)

 

Во входном файле содержится закодированное изображение электронного табло, состоящего из 25 строк и 80 столбцов лампочек. Известно, что на табло высвечивалась одна или несколько заглавных печатных букв: А, В, Ж, Л, М, О, С, Ф, Ю. Символы, отличные от перечисленных букв, на табло отсутствовали.

Две горящие лампочки, соседствующие на табло по горизонтали, вертикали или диагонали, принадлежат одной и той же букве. Буквы могут быть любого размера, толщины, начертания ("рукописные" буквы не допустимы). Буквы расположены вертикально. Изображения букв не касаются и не пересекаются. "Линии", образующие буквы, не имеют разрывов и полостей

 

Задание.

Написать программу, которая

1) запрашивает имя входного файла и выводит на экран монитора в текстовом режиме изображение электронного табло, представляя горящие лампочки символами '*';

2) решает задачу распознавания букв в предположении, что на табло изображена только одна буква;

3) решает задачу распознавания для произвольного количества букв.

Описание входных данных

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

Первое число в файле - общее количество серий. Далее следуют тройки чисел, задающие серии. Числа в файле разделены пробелами или концами строк. Сначала в файле описаны все серии первой строки табло слева направо, затем второй, третьей и т.д. строк.

Описание вывода результата

После каждого нажатия клавиши 'пробел' в изображении одной из букв, выведенных на экран,  символы '*' следует  заменить  на символ,  соответствующий этой букве, например, 'А' для буквы А или 'Ю' для Ю, до тех пор пока все буквы на экране не будут разпознаны.  В случае неоднозначного распознавания 6уквы вашей программой допустимо после нажатия клавиши 'пробел' заменить символы '*' в изображении этой буквы на два или даже три символа (например, на 'О','А' и 'Л'), распределяя их  по изображению буквы.

Если вашей программе не удалось распознать ту или иную букву, то символы '*' в ее изображении следует заменить на символ '?'.

 

Примечания:

1. Все исходные данные корректны.

2. Строки табло пронумерованы сверху вниз.

З. В крайнем случае считывание данных можно организовать и с клавиатуры.

4. Вместо замены '*' на экране на соответствующие символы в крайнем случае ответ можно выдать в следующем  виде: для каждой буквы в новой строке напечатать номер строки и столбца первой лампочки первой серии этой буквы и соответствующий ей символ (символы).

5. Если на вашем компьютере нет русских букв, используйте латинские буквы A, B, J, L, M, O, C, F.

6. Файл данных для пункта (З) описывает произвольное количество букв, причем каждая из перечисленных букв может как встречаться несколъко раз, в том числе и в различных модификациях, так и отсутствовать.

Подсказка

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

Оценка задачи

1. Ввод данных из файла и изображение их на экране                    10 баллов

2. Всего за распознавание букв                                                          от 0 до 70 6аллов

   Однозначное распознавание буквы (одним символом)   З балла за каждую

   Распознавание буквы с помощью двух символов             2 балла за каждую

   Распознавание буквы с помощью трех символов              1 балл  за каждую

   Замена символов '*' в букве на символ '?'                                      0 баллов

   Неверное распознавание буквы                                                      -1 балл  за каждую

3. Работа с файлом, описывающим более одной буквы      20 6аллов

Всего                                                                                                     100 баллов

 

VII Всероссийская олимпиада

1995 год, г. Троицк Московской области

 

Задача 1

РАМКИ

Имеется текстовый экран из M строк и N столбцов (3£M,N£100). Первоначально экран заполнен символом “•” (ASCII-код 249). На этом экране одна за другой рисуются прямоугольные рамки толщиной в один символ. Каждая рамка рисуется при помощи своего символа, являющегося заглавной буквой латинского алфавита. При рисовании рамки ее символы замещают на экране ранее изображенные. Рамки нарисованы таким образом, что у каждой рамки видна хотя бы одна пара противолежащих углов. Требуется по данному изображению на экране определить, возможно ли однозначно восстановить последовательность рисования рамок и 1) если восстановление однозначно, определить требуемую последовательность; 2) если восстановление неоднозначно, определить две различные возможные последовательности рисования рамок.

Исходные данные программы расположены в текстовом ASCII-файле, имя которого вводится с клавиатуры. Первая строка исходного файла содержит размеры экрана M и N. Далее расположено M строк по N символов в каждой, задающих изображение на экране.

Результат работы программы выводится одновременно на экран и в текстовый ASCII-файл с именем OUTPUT.TXT. Первая строка содержит одну из возможных последовательностей рисования рамок, заданную перечислением имен рамок без пробелов. Вторая строка повторяет первую, если восстановление однозначно, либо содержит другую возможную последовательность,  если восстанвление неоднозначно.

Примечания: Заданное во входном файле изображение заведомо можно получить последовательным рисованием рамок. Каждая сторона рамки состоит не менее, чем из 3 символов. Рамки не могут рисоваться за пределами экрана. Исходные данные корректны, и их проверка не требуется.

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

            6          4

                                            

                       A         A         A

            W        W        W        A

            W        A         W        A

            W                   W       

            W        W        W       

 

Пример выходного файла OUTPUT.TXT для приведенного примера:

AW

AW

 

Максимальная оценка задачи — 30 баллов

Задача 2

ЧТО ТУТ СЧИТАТЬ?

Задано натуральное десятичное число N (N£1.000.000.000). Написать программу вычисления количества принадлежащих диапазону от 1 до N чисел, в двоичном представлении которых содержится ровно K значащих нулей. Например, для N=18 и K=3 таких чисел — 3 (8, 17, 18).

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

- ввод чисел N и K осуществляется с клавиатуры,

- полученный результат выводится на экран.

Технические ограничения:

- корректность входных данных не проверяется,

- время тестирования ограничено

 Максимальная оценка задачи — 30 баллов

 

 

Задача 3

ДЕТЕКТИВ

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

Музей состоит из цепочки залов с номерами от 1 до n (n£10). Алмаз находился в зале k. Посетители (их не более 10) проходили по залам в соответствии с их номерами, не возвращаясь назад. Размеры залов таковы, что посетитель затрачивал на проход зала не меньше минуты. В некоторых залах находились смотрители (их не более 10), которые не могли похитить камень. В зале, где находился алмаз, смотрителя не было. Смотрители замечали не всех посетителей, которые проходили по залу, но уж если смотритель заметил посетителя, то он обязательно запоминал время, когда он его увидел, с точностью до минуты. Посетители музея, разглядывая экспонаты, не всегда обращали внимание на остальных посетителей, но уж если посетитель обращал на кого-то внимание, то он запоминал время и место (номер зала) его нахождения.

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

С этой целью майор Пронин допросил смотрителей и посетителей и составил протокол, содержащий информацию о том, кто, кого, когда и где видел.

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

Входные данные

Входные данные вводятся из файла в следующей последовательности:

n k                            - количество залов, номер зала, где был алмаз

t1 t2                          - промежуток времени, когда произошло похищение

m                              - число смотрителей

имя_смотрителя_1

имя_смотрителя_2

...

имя_смотрителя_m

p                           - число последующих строк в файле

кто_1         кого_1       когда_1     номер_зала_1

кто_2         кого_2       когда_2     номе_рзала_2

...

кто_p         кого_p       когда_p     номер_зала_p

 

Имена смотрителей и посетителей записываются русскими буквами.

Длина имен не превышает 20 символов.

 

Пример файла

4 2

9:20 10:30

1

БабаНастя

5

БабаНастя ПоручикРжевский 10:15 1

АгентСидоров ИностранныйШпион 11:21 1

АгентСидоров ИностранныйШпион 11:22 2

АгентСидоров ИностранныйШпион 11:22 3

АгентСидоров ИностранныйШпион 11:24 4

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

Максимальная оценка задачи — 40 баллов

 

Задача 4.

Лягушка и Комар

Лесное болото разделено на 88 одинаковых клеток. В некоторых клетках болота находятся кочки, а все остальные клетки с водой. На одной из кочек сидит лягушка, а над какой-то другой клеткой болота летает комар. Лягушка хочет съесть комара, а комар старается от нее улететь. Перемещаются лягушка и комар по очереди, первый ход - за лягушкой. За один прыжок лягушка перемещается на любую из кочек по горизонтали, вертикали или диагонали. Комар за один перелет перемещается на одну из 8 соседних клеток. Если лягушка в прыжке пролетает через клетку, над которой находится комар (или прыгает на клетку, над которой летает комар), то она съедает комара. Съев комара в последнем прыжке, лягушка может оказаться как в воде, так и на кочке.

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

Входные данные

1.  Входные данные программы расположены в текстовом ASCII-файле, имя которого вводится с клавиатуры.

2.  В первых 8 строках файла находится матрица размером 88, задающая схему расположения кочек в виде нулей и единиц (0 -  клетка с водой, 1 - кочка). Элементы матрицы в каждой строке записываются без пробелов. Далее содержится строка с координатами лягушки (X1, Y1) и комара (X2, Y2), где Xi - номер строки, Yi - номер столбца.

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

11111111

11111011

11101111

11111011

11110111

11011111

10111101

11111111

2 1 1 8

Выходные данные

Выходной текстовый ASCII-файл с именем OUTPUT.TXT должен содержать сначала минимальное количество шагов, а затем первый возможный ход лягушки, задаваемый координатами кочки, на которую прыгает лягушка. Если комара съесть невозможно, то выходной файл должен содержать одну строку с сообщением “Невозможно”.

Пример выходного файла  OUTPUT.TXT для приведенного примера:

2

2 7

Примечания:

1.  В выходном файле должен содержаться только один из возможных первых ходов лягушки.

2.  Лягушка перемещается только с кочки на кочку, т.к. при попадании в воду она теряет комара из вида.

3.  Исходные данные корректны, и их проверка не требуется.

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

5.  Время тестирования каждого теста ограничено одной минутой.

Максимальная оценка задачи - 40 баллов

 

Задача 5.

Параллельные вычисления

Задана программа, состоящая из N операторов присваивания (1N15). Каждый оператор записывается в следующем виде:

X=YopZ

где X, Y, и Z -            идентификаторы, состоящие из одной заглавной латинской       буквы;

op                   -            символ одной из арифметических операций: “+” (сложение),     “-” (вычитание), “*” (умножение) и “/” (деление)

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

Каждый оператор выполняется за один такт работы процессора. Чтобы синхронизировать работу процессоров введена команда “NOP”, которая задерживает работу процессора на один такт. В процессе одновременной работы двух процессоров выполняемые операторы могут использовать только такие общие переменные, которые находятся в правых частях операторов присваивания (например, операторы “A=B+C“ и “M=A+K“ не могут выполняться одновременно).

Входные данные

1.  Входные данные расположены в текстовом ASCII-файле, имя которго вводится с клавиатуры.

2.  Каждый оператор находится на отдельной строке; файл не содержит пробелов и пустых строк; в конце последней строки файла символов конца строки нет.

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

W=A+B

F=A+P

B=W/F

W=B*C

Выходные данные

1.  Результат работы обязательно помещается в выходной текстовый ASCII-файл с именем OUTPUT.TXT.

2.  В первую строку файла записывается искомое минимальное число тактов P.

3.  Далее следуют P строк, в которых в две колонки выписаны программы для каждого процессора; колонки должны быть выровнены по левому краю.

4.  Пример выходного файла OUTPUT.TXT для приведенного примера:

W=A+B        F=A+P

NOP             B=W/F

W=B*C        NOP

Примечания:

1.   Исходные данные корректны, и их проверка не требуется.

2.   Время тестирования каждого теста ограничено одной минутой.

Максимальная оценка задачи - 30 баллов

Задача 6.

Рандеву

Локаторы дальней космической связи замечают летящий в плоскости орбиты Земли неизвестный астероид с координатами (x,y). Астероид летит с постоянной скоростью, векторное значение которой равно (Vx, Vy). С Земли из точки с координатами (0,0) немедленно стартует ракета с радиусом действия R (R>0). Ракета летит по прямой с постоянной скоростью в пределах от 0 до W.

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

Входные данные

1.  Входные данные расположены в текстовом ASCII-файле, имя которого вводится с клавиатуры.

2.  В начале файла содержится число N - количество наборов исходных данных (тестов).

3.  Далее расположены N наборов исходных данных; каждый набор - шесть вещественных чисел: X, Y, Vx, Vy, W, R.

4.  Все числа в исходном файле разделяются пробелами и (или) символами перевода строки.

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

2

5.3 2.8 10.6 5.6 11.0 50.0

3.0 -4.0 -3.0 4.0 5.0 10.0

Выходные данные

1.  Результат работы помещается в выходной текстовый ASCII-файл с именем OUTPUT.TXT.

2.  Для каждого набора исходных данных вывести с новой строки вектор скорости (Ux,Uy) и минимальное время встречи, либо сообщение “Встреча невозможна”.

Пример выходного файла OUTPUT.TXT для приведенного примера:

Встреча невозможна

3.0 -4.0 0.5

Примечания:

1.  Результат решения задачи должен быть вычислен с погрешностью не более 0.01.

2.  Влиянием Земли и всех космических объектов пренебречь.

3.  Ракета и астероид двигаются в одной плоскости.

4.  Исходные данные корректны, и их проверка не требуется.

5.  Общее время тестирования ограничено тремя минутами.

Максимальная оценка задачи - 30 баллов

 

VIII Всероссийская олимпиада

1996 год, г. Троицк Московской области

 

Задача 1. Пестрые числа

-значное () число называется пестрым, если все его цифры различны. При этом ноль не может быть первой цифрой.

Требуется.

Написать программу, которая для заданного :

·      находит максимально длинную цепочку пестрых -значных чисел, в которой каждое следующее число в два раза больше предыдущего;

·      находит все такие цепочки максимальной длины.

Входные данные.

Число  вводится с клавиатуры.

Выходные данные.

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

Примечание.

Задача оценивается из 20 баллов.

Время тестирования программы - не более 1 мин.

Задача 2. Транслятор

Рассматриваются два алгоритмических языка: Beta  и Psi (описания языков прилагаются ниже). Требуется перевести программу с языка Beta на язык Psi. Результирующая программа на языке Psi  должна реализовывать тот же самый алгоритм, что и исходная программа на языке Beta.

Пример возможного перевода:

Программа на языке Beta

Одна из соответствующих ей
программ на языке Psi

10 N=5

20 SUM=SUM+N

35 N=N-1

40 IF N>0 THEN WALKTO 20

70 TYPE Sum

999 END

DEF N, Var, C;

START

Var := 0; c := 1;

WHILE c < 6 DO

IF c = 1 THEN N:= 5; c:=c+1; FI;

IF c = 2 THEN Var:=Var+N; c:=c+1;

FI;

IF c = 3 THEN N:=N-1; c := c+1; FI;

IF c = 4 THEN

IF N>0 THEN c := 1; FI; c:=c+1;

FI;

IF c = 5 THEN Print (Var);

c := c+1;

FI;

OD;

FINISH

Примечания

Текст исходной программы состоит не более, чем из 100 строк, а каждая строка содержит не более 80 символов.

В каждом из языков имена переменных не совпадают с ключевыми словами в операторах.

Текст исходной программы не содержит синтаксических ошибок.

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

Текст исходной прогаммы вводить из файла INPUT.TXT. Результат выводить в файл  OUTPUT.TXT

Задача оценивается из 40 баллов. Решения задачи для случая, когда в исходной программе отсутствуют операторы WALKTO, будут оцениваться.

Время тестирования программы ограничено.

Описание языка Beta

Программа на языке Beta состоит из последовательности операторов; каждый оператор располагается в отдельной строке и ему всегда предшествует метка (натуральное число £ 10000).

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

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

Исполнение программы начинается с первого оператора. Последним в тексте программы всегда является оператор END.

Значения переменных, константы и значения выражений в языке являются целочисленными и находятся в диапазоне от -32768 до 32767.

В начале работы программы значения всех переменных равны нулю.

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

Операторы языка перечислены в таблице 1.

Таб.1

Название оператора

Форма записи
 оператора

Комментарии

Оператор

присваива­ния

переменная =
выражение

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

Оператор перехода

WALKTO метка

Оператор передает управление оператору, начинающемуся с указанной метки. Метка задается константой и не может содержать арифметических операций.

Условный оператор

IF условие THEN оператор присваивания  или оператор перехода

Условие – это два выражения, разделенные одним из знаков сравнения: =, <, >, <> (не равно). Оператор проверяет условие, и, если оно истинно, то выполняется оператор, следующий за словом THEN в этой же строке.

Оператор печати

TYPE выражение

Оператор выводит с новой строки значение выражения.

Оператор завершения

END

Всегда записывается последним оператором в программе и завершает ее исполнение.

Описание языка Psi

Программы на языке Psi состоит из описания переменных и тела программы.

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

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

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

Программа может содержать пустые строки и лишние разделительные пробелы.

Имена переменных, имена операторов, метки и константы записываются без пробелов. Переменные в начале работы программы принимают случайные значения.

Операторы языка Psi

Название операторов

Форма записи оператора

Комментарии

Оператор

присваивания

переменная := выражение

Оператор присваивает переменной из левой части значение выражения.

Условный оператор

IF условие  THEN оператор;...;
оператор;
FI

Оператор проверяет условие, и, если оно истинно, то выполняются операторы, находящиеся между словами THEN и FI. Между THEN и FI может находиться и один оператор.

Оператор печати

PRINT (выражение)

Выводит с новой строки значение выражения.

Оператор цикла

WHILE условие  DO
оператор;,...;оператор; OD

Повторяет выполнение операторов, находящихся между словами DO и OD, пока истинно условие. Между DO и OD может находиться и один оператор.

Задача 3. ШЛАН­ГИ

Установка состоит из устройств A и B, со­еди­нен­ных между собой ле­жа­щими на земле шлан­гами. Ка­ж­дое устройство име­ет N патрубков, пронумерованных от 1 до N как изображено на рис. 1. Каждый из шлангов соединяет пат­ру­бки обоих устройств с одинаковыми номерами. Шланги могут располагаться друг относительно друга произвольным образом с единственным ограничением: при перемещении точки вдоль любого шланга от А к В расстояние от нее до А только возрастает. Номер шланга совпадает с номером патрубка устройства A.

рис. A.

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

Для этого об­ход­чику поручили записать ин­фор­ма­цию о то­ч­ках пе­ре­се­че­ний шлангов по направлению движения от устройства A к устройству B. Для ка­ж­до­го оче­ред­но­го пе­ре­се­че­ния обходчик за­пи­сал пары чисел: но­мер шланга, ле­жа­ще­го сни­зу, и но­мер шланга, рас­по­ло­жен­но­го свер­ху, соответственно (в ка­ж­дой то­ч­ке пе­ре­се­ка­ют­ся не бо­лее двух шлангов.

рис. 2.

Тре­бу­ет­ся

Написать программу, которая по заданным  (считать) и произвольной последовательно­сти пересечений шлангов определяла бы:

(а)   нет ли заведомых ошибок в записи обходчика;

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

Входные данные

 Входные данные располагаются в файле INPUT.TXT. В первой строке этого файла находится число , во второй — записанные через пробел вышеназванные пары натуральных чисел.

 Данные во входном файле всегда соответствуют описанному формату файла INPUT.TXT.

 Для рис.1 входные данные в файле INPUT.TXT имеют вид:

3

2 1 3 1 2 3 3 2 1 3 1 2

Выходные данные

Результаты решения должны выводиться на экран монитора. При этом допустимы следующие со­общения:

(а) Uncorrect input data         — при обнаружении заведомых ошибок в записи обходчика;

(б) Correct input data — при отсутствии заведомых ошибок в записи обходчика;

(в) Solvable                 — при возможности обеспечить непересечение шлангов;

(г) Unsolvable             — при невозможности обеспечить непересечение шлангов.

Для приведенного выше примера файла INPUT.TXT программа должна выдать сообщения:

Correct input data

Unsolvable

Примечания

 Задача оценивается из 40 баллов

 Оценка осуществляется, исходя из двух уровней сложности: для N=2 и для N=3.

 Время тестирования программы - не более 1 мин.

 

Задача 4. Коллекции

В городе открылся клуб филателистов, членами которого стремятся стать M человек. На каждом заседании в клуб принимают одного нового филателиста. Чтобы быть принятым, каждый претендент должен предъявить свою коллекцию марок, в которой нет одинаковых экземпляров и которая хоть чем-то отличается от коллек­ций членов клуба. Для этого каждый новый претендент идет в магазин, где прода­ются  видов почтовых марок () по ценам  (, ), и покупает соответствующий набор марок, стараясь потратить минимальную сумму денег.

Например, при ассортименте из 5 марок по ценам 3, 4, 6, 10, 15 коллекционеры будут покупать их в представленном ниже порядке:

коллекционер

купленные марки

затраченная сумма денег

первый

первая

3

второй

вторая

4

третий

третья

6

четвертый

первая и вторая

3+4

пятый

первая и третья

3+6

шестой

четвертая

10

седьмой

вторая и третья

4+6

восьмой

первая, вторая и третья

3+4+6

девятый

первая и четвертая

3+10

десятый

вторая и четвертая

4+10

...

...

...

Требуется

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

Входные данные

Входные данные задаются в файле INPUT.TXT в следующем порядке: в первой строке - N, во второй - M, в последующих N строках указываются цены марок в неубы­вающем порядке.

Выходные данные

Результат решения задачи записывается в файл с именем OUTPUT.TXT. Каждая из M строк этого файла содержит соответствующую искомую сумму затраченных денег для каждого коллекционера. Эти М сумм должны располагаться в неубывающем порядке.

Пример входного файла и соответствующего ему выход­ного файла приведен ниже:

INPUT.TXT

OUTPUT.TXT

5

10

3

4

6

10

15

3

4

6

7

9

10

10

13

13

14

Примечания:

1)  - натуральные числа. ;

2) Тестирование задачи будет осуществляться автоматически, так что никаких отсту­плений от данного формата ввода/вывода быть не должно;

3) Время тестирования не более 30 сек;

4) Задача оценивается в 34 балла.

Задача 5. Детская игра со спичками

N спичек () на плоскости образует фигуру как, например, изображено на рис. 1

рис. 1

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


Очевидно, для любой заданной фигуры можно построить симметричную ей, переложив некоторые спички. В процессе перекладывания спички ломать нельзя. Накладывание спичек друг на друга не приводит к нарушению условия их располо­жения на плоскости. Например, из фигуры рис. 1. могут быть получены фигуры, изображенные на рис. 2 и рис. 3.

                                               рис. 2                 рис. 3

Требуется

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

Входные данные

Исходное расположение спичек задается в файле с именем INPUT.TXT. Первая строка файла содержит число N, далее следуют N строк, содержащих координаты кон­цов каждой спички:

Выходные данные

Результат работы программы записывается в файл с именем OUTPUT.TXT, содержащий в первой строке количество переложенных спичек, далее следуют N строк с коорди­натами концов спичек в результирующей фигуре.

Например, для фигуры на рис.1 решением является фигура на рис. 2. Соответст­вующие им файлы INPUT.TXT и OUTPUT.TXT приведены ниже:

INPUT.TXT

OUTPUT.TXT

3

1 0 1 5

2 4 5 0

5 0 8 4

 

1

9 0 9 5

2 4 5 0

5 0 8 4

 

Примечание

1.   Заведомо известно, что координаты концов спичек исходной и результирующей фи­гуры - целые числа ()

2.   Время тестирования ограниченно 1 минутой.

3.   Задача оценивается в 33 балла.

Задача 6. Стена

Стена для рекламных щитов состоит из M рядов по N одинаковых кирпичей в ка­ждом. Каждый последующий ряд смещен относительно предыдущего на 1/2 кирпича (см. рис. 1). Четные ряды сверху смещаются влево, а нечетные – вправо. Конфигурация из кирпичей является устойчивой, если каждый кирпич опирается, по крайней мере, на один кирпич в нижележащим ряду (кирпичи нижнего ряда лежат на земле).  Очевидно, что из заданной конструкции можно удалить некоторые кирпичи без потери ее устойчивости. На рис. 2 изображен пример возможной конструкции для стены на рис. 1.

Требуется

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

Программа должна выдать количество оставшихся в конструкции кирпичей и ее кон­фигурацию.

Входные данные

Входной файл с именем INPUT.TXT содержит количество рядов M и ширину
 стены N.

Выходные данные

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

Пример файла исходных данных INPUT.TXT для рис. 1:

4 5

Пример выходного файла OUTPUT.TXT см. рис. 2:

13

1 2 3 4 5 0

2 4 5 0

2 3 5 0

3 5 0

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

рис. 1

 

рис. 2

Примечание

Задача оценивается в 33 балла.

Программы, выдающие правильные, но не оптимальные решения также будут оцени­ваться.

Время тестирования ограничено 1 минутой.

 

 

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

Санкт-Петербург, 2-9 апреля 1997 года

Задача 1.  Текст на заборе

Мэр города Речуйска распорядился штрафовать за употребление нежелательных слов и обнародовал список этих слов с размером штрафа за каждое. Все эти слова состоят из букв "I", "N", "W".

Некто строит незамкнутый забор длиной N  досок. Имеются доски, на каждой из которых написана одна из букв "I", "N" или "W". Получившийся забор будет содержать надпись из вышеназванных букв. За каждое нежелательное слово, образуемое какими-либо последовательно стоящими буквами (при прочтении слева направо), придется заплатить штраф, причем столько раз, сколько раз оно встречается на заборе.

Например, если запрещенными словами являются IN — штраф 1 рубль и WIWI — штраф 100 рублей, то за построение забора WIWIWINI будет назначен штраф 201 рубль.

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

Ограничения

*     Штрафы выражаются в рублях Речуйска и представляются целыми числами от 1 до 100.

*     Количество запрещенных слов £ 50.

*     Длины запрещенных слов £  6 символов.

Входные данные

Первая строка файла входных данных INPUT.TXT содержит длину забора N, вторая — количество слов в списке мэра M. В каждой из последующих M строк записано нежелательное слово и через пробел — соответствующий штраф. Все слова попарно различны, состоят только из больших букв латинского алфавита "I", "N" или "W".

Входные данные корректны.

Выходные данные

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

Пример файла INPUT.TXT:

Пример файла OUTPUT.TXT:

8

8

W 10

I 10

N 30

WI 1

WW 10

II 11

WIW 2

IWI 3

98

IWIWIWIW

 

Система оценок

Максимальная оценка за задачу — 40 баллов.

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

 

Время тестирования —  20 секунд на каждый тест.

Задача 2.  Числообменник

Числа от 1 до N выписаны подряд в строку. Разрешается менять местами любые два числа, между которыми в строке стоят ровно  или  чисел (числа    заданы).

Например, пусть . Тогда после перестановки чисел в позициях 1 и 4 (между ними стоят 2 числа) и чисел в позициях 1 и 5 (между ними стоят 3 числа) получится последовательность 5, 2, 3, 1, 4.

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

Ограничения:

*     ;

*     ;

*     Для всех i выполняется .

Входные данные

Файл исходных данных INPUT.TXT содержит (в указанном порядке): N, M, . Все числа в файле разделяются пробелами и (или) символами перевода строки.

Входные данные корректны.

Выходные данные

В выходном файле OUTPUT.TXT  должно находиться  искомое число.

Пример файла INPUT.TXT:

Пример файла OUTPUT.TXT:

5

2

3 2

24

Система оценок

Максимальная оценка за задачу — 35 баллов.

Частичные решения задачи (количество перестановок £ 2 147 483 648) будут оцениваться исходя из 15 баллов.

 

Время тестирования —20 секунд на каждый тест.

 

Задача 3.  Простые гири

Имеются гири с массами: 1 г, 2 г, ..., N г  (N£500000). Написать программу,  распределяющую эти гири на максимально возможное количество пар так, чтобы суммарный вес гирь в каждой паре выражался простым числом.

Входные данные

Входной файл INPUT.TXT содержит число N.

Входные данные корректны.

Выходные данные

В выходной файл OUTPUT.TXT выводится список найденных пар. Все числа в выходном файле разделяются пробелами и (или) символами перевода строки.

Пример файла INPUT.TXT:

Пример файла OUTPUT.TXT:

7

1 6

7 4

5 2

Система оценок

Максимальная оценка за задачу —  25 баллов.

 

Время тестирования —20 секунд на каждый тест.

 

Задача 4. INTERNETомания

       Компания “Новые русские сети” разработала электронную энциклопедию “Мир Internet”, состоя­щую из L одинаковых по объему томов, и желает распространить ее на все N серверов сети Internet. Передача данных по каналам связи начинается с сервера компании и может осуществляться с любого сервера отдельными томами в произвольном порядке. Каждый из M имеющихся каналов связи соединяет два сервера и имеет заданную пропускную способность, одинаковую в обоих направлениях и определяемую временем передачи по нему одного тома. Между любой парой серверов может быть не более одного канала. Информация на любом сервере становится доступной для считывания другими серверами через T минут после окончания приема всей энциклопедии. Возможна как одновре­менная передача произвольных томов сразу нескольким серве­рам, так и одновременное считывание различных томов сразу с нескольких серверов. На рисунке приведен пример возможной сети для N = M = 3, L = 3, T = 1.

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

     Входные данные

       Входные данные расположены в файле с именем INPUT.TXT в следующем порядке:

·         N — число серверов в сети (); серверы нумеруются числами от 1 до N, сервер компании “Новые русские сети” имеет номер 1.

·         M число каналов связи

·         L — количество томов в энциклопедии ()

·         T время задержки

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

       Время задержки T и время передачи задаются вещественными числами. Все числа во входном файле разделяются пробелами и (или) символами перевода строки в соответствии с представленным ниже примером. Все входные данные корректны.

     Выходные данные

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

       Ниже приведен пример файлов INPUT.TXT и OUTPUT.TXT для сети, изображенной на рисунке. Пунктирными стрелками показано направление передачи данных.

Пример файла INPUT.TXT:

Пример файла OUTPUT.TXT:

3 3 3 1.0

1 2 3.0

2 3 3.0

3 1 6.0

13.00

3

 

                                                  Максимальная оценка за задачу — 33 балла.

                                                  Время тестирования — 20 секунд на каждый тест.

 

Задача 5. Энциклопедия

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

Каждый том справочника содержит одну или несколько словарных статей. Статья — это одна строка неограниченной длины, начинающаяся с имени статьи, за которым после пробела следует ее тело. Имя статьи — последовательность больших и маленьких русских и латинских букв (не более 32-х). Все статьи в одном томе имеют  различные имена. В теле статьи могут употребляться любые печатные символы.

Таким образом, каждый том имеет вид:

<Имя_статьи><Пробел><Тело_статьи>

<Имя_статьи><Пробел><Тело_статьи>

. . .

<Имя_статьи><Пробел><Тело_статьи>

В теле словарной статьи могут встречаться ссылки на другие статьи вида:

<Разделитель><Имя_статьи><Пробел>"(см."[<Имя_тома>]")"

Здесь <Разделитель> — это любой печатный символ, не являющийся буквой.

Примечание. В определениях использованы следующие обозначения: (а) текст, заключенный в кавычки, должен находиться во входных и выходных данных в том же виде; (б) конструкции <…> замещаются соответствующими значениями; (в) запись [...] означает, что соответствующие элементы могут отсутствовать.

Требуется

Разработать диалоговую систему ЭНЦИКЛОПЕДИЯ, автоматизирующую работу со справочником. Система должна удовлетворять следующим требованиям.

1. Ввод команд осуществляется из командной строки, которая отделяется сверху от остального текста на экране пустой строкой. Приглашение для ввода команды выдается после запуска системы и после исполнения любой команды (кроме команды выхода из системы ). Приглашение состоит из имени текущего тома и символа “>”; сразу после запуска системы текущий том — это первый из перечисленных в файле INPUT.TXT.

2. Система должна выполнять следующие команды:

Формат команды

Описание

"DIR"

Вывести список томов справочника

"VOLUME"<Пробел><Имя_тома>

Сменить текущий том

"LIST"[<Пробел><Имя_тома>]

Вывести оглавление тома

"TYPE"<Пробел>[<Имя_тома>":"]<Имя_статьи>

Вывести статью на экран

"REF"<Пробел><Номер_ссылки>

Вывести статью по номеру ссылки

"CLS"

Очистить экран

"VERIFY"

Проверить корректность системы ссылок

"EXIT"

Завершить работу

Если имя тома опущено, то команда выполняется для текущего тома. Никакая команда, кроме VOLUME, не меняет текущего тома.

По команде TYPE система должна вывести на экран текст статьи с разбивкой на строки длиной не более 80 символов каждая; разбиение производится по пробелам. Строки должны быть максимально возможной длины. Наличие пробела в первой позиции строки не допускается.

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

"1."<Пробел><Имя_статьи>[","<Пробел>"том"<Пробел><Имя_тома>]

"2."<Пробел><Имя_статьи>[","<Пробел>"том"<Пробел><Имя_тома>]

. . .

По команде LIST выводится пронумерованный список всех статей тома в том порядке, в котором они встречаются в томе. Формат вывода списка такой же, как для команды TYPE (раздел вывода имени тома отсутствует.

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

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

"Все ссылки корректны"

В противном случае выдать список несуществующих статей, на которые есть ссылки, с именами статей, в которых эти ссылки имеются. Формат вывода списка:

"Есть ссылки на несуществующие статьи:"

"1. Из "<Имя_тома>":"<Имя_статьи>" ссылка на "<Имя_тома>":"<Имя_статьи>"

"2. Из "<Имя_тома>":"<Имя_статьи>" ссылка на "<Имя_тома>":"<Имя_статьи>"

. . .

Здесь после "Из " указывается  статья, в которой имеется некорректная ссылка, а после "ссылка на " – то, на что эта ссылка указывает.

3. Все тома, перечисленные в файле INPUT.TXT, существуют и находятся в текущем каталоге DOS.

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

"Нет такой команды"

"Том не найден"

"Статья не найдена"

"Неверный номер ссылки"

4. При входе в систему и по окончании работы необходимо выводить приветствия и прощания "Привет!" и "До свидания." соответственно.

5. В названиях команд (DIR, VOLUME, ...) и именах томов большие и маленькие буквы неразличимы (в отличие от всех других ситуаций). Регистр букв при выводе имен томов, приглашений и сообщений об ошибках выберите по своему усмотрению.

6. Размеры всей энциклопедии не превышают 10Кбайт.

7. Текст статьи со списком ссылок заведомо целиком помещается на экран компьютера.

Примеры

Пример файла INPUT.TXT:

Computer

English

Пример тома COMPUTER (файл COMPUTER.TXT):

компьютер -устройство для обработки информации. Основные части: процессор (см.), память (см.), монитор (см.), клавиатура (см.Computer), винчестер (см.),дисковод (см.).

процессор - основная микросхема (см.), мозг компьютера.

память - устройство для хранения временных данных.

клавиатура - устройство для ввода информации, имеет свой процессор (см.).

Также клавиатура (см.Music).

монитор - устройство для изображения текстовой и графической информации.

микросхема - маленькая, но умная железка.

винчестер - устройство для хранения данных. Также оружие-winchester (см.English).

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

Пример тома ENGLISH (файл ENGLISH.TXT):

animal - a living thing that can feel and move about (dog, bear (см.), fish).

amoeba (pl. -bae) - a very simple form of living found in the water.

amour - a secret (см.) love (см.) affair.

bear - a large, heavy animal (см.) with rough hair.

love - a feeling of affection, passion (см.) or desire between the sexes.

passion - strong feeling or enthusiasm.

passionate - easily giving way to strong feelings (e.g. love (см.)).

Winchester - Oliver F. Winchester (1810-1880), US gun manufacturer.

(смысл приведенных в примерах текстов не имеет для решения никакого значения).

Пример сеанса работы

Ниже приведен один из вариантов диалога с системой для нашего справочника, заданного файлами INPUT.TXT, COMPUTER.TXT и ENGLISH.TXT. Пример является иллюстративным и не исчерпывает все возможные ситуации.

 

Привет!

 

Computer>DIR

Computer

English

 

Computer>VOLUME English

 

English>list

1. animal

2. amoeba

3. amour

4. bear

5. love

6. passion

7. passionate

8. Winchester

 

English>TyPe amoeba

amoeba (pl. -bae) - a very simple form of living found in the water.

 

English>TYPE animal

animal - a living thing that can feel and move about (dog, bear (см.), fish).

 

1. bear

 

English>REF 2

Неверный номер ссылки

 

English>REF 1

Неверный номер ссылки

 

English>LIST computer

1. компьютер

2. процессор

3. память

4. клавиатура

5. монитор

6. микросхема

7. винчестер

 

English>TYPE Computer:винчестер

винчестер - устройство для хранения данных. Также оружие - winchester (см.English).

 

1. winchester, том English

 

English>VOLUME COMPUTER

 

Computer>TYPE компьютер

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

память (см.), монитор (см.), клавиатура (см.Computer), винчестер (см.),дисковод

(см.).

 

1. процессор

2. память

3. монитор

4. клавиатура

5. винчестер

6. дисковод

 

Computer>REF 4

клавиатура - устройство для ввода информации, имеет свой процессор (см.). Также

клавиатура (см.Music).

 

1. процессор

2. клавиатура, том Music

 

Computer>REF 2

Том не найден

 

Computer>VERIFY

Есть ссылки на несуществующие статьи:

1. Из Computer:винчестер ссылка на English:winchester

2. Из Computer:клавиатура ссылка на Music:клавиатура

3. Из Computer:винчестер ссылка на English:winchester

4. Из English:amour ссылка на English:secret

5. Из Computer:компьютер ссылка на Computer:дисковод

 

 

Computer>EXIT

До свидания.

Система оценок

Жюри независимо оценивает реализацию отдельных команд в системе.

Максимальная оценка за задачу    34 балла.

 

Задача 6. Подсветка фонтана

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

Входные данные

Исходные данные записаны в файле INPUT.TXT в следующей последовательности:

·      в 1-ой строке — число вершин N  (N£100);

·      в каждой из последующих N строк — пара чисел через пробел, являющихся координатами вершин x1  y1  x2  y2  ¼ xN  yN  в порядке обхода ломаной против часовой стрелки, где 1,2,...,N - номера вершин;

·      в последней строке — номера соединяемых вершин  k и l  (1£k<l£N).

Координаты вершин являются вещественными числами.

Все входные данные корректны.

Выходные данные

Результат  вывести в виде числа в файл OUTPUT.TXT. Результат проверяется с точностью  до шести значащих цифр. Результирующее число может быть как с фиксированной точкой, так и в нормализованном виде.

Пример файла INPUT.TXT:

Пример файла OUTPUT.TXT

7

2 0

5 0

6 3.5

5 6

4 2

3 7

0 5

3 7

7.5

Система оценок

Максимальная оценка за задачу — 33 балла.

Время тестирования - 20 секунд на один тест.

 

 

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

Санкт-Петербург, апрель 1998 года

 

Задача 1. Хеш-функция

имя входного файла:

hash.in

имя выходного файла:

hash.out

время на один ход:

20 секунд

максимальный балл:

34

 

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

 

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

 

На время тура вам предоставляется файл words.txt, содержащий перечисленные в алфавитном порядке 10 000 слов. Слова из этого файла будут использоваться при тестировании вашего решения. Это означает, что во всех тестах слова будут выбираться только из этого множества. Во время тестирования файл words.txt будет вашей программе недоступен.

 

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

 

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

 

 

Входные данные

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

 

Выходные данные

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

 

Пример входного файла hash.in

мертвые

души

кому

на

Руси

жить

хорошо

герой

нашего

времени

 

Пример выходного файла hash.out

8

5

5

3

5

5

7

6

7

8

 

Примечание

Оценка хеш-функции в приведенном примере равна четырем.

 

 

Задача 2. Разделяй и властвуй

имя входного файла:

divide.in

имя выходного файла:

divide.out

время на один ход:

20 секунд

максимальный балл:

33

 

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

 

Подпись: xПодпись: OПодпись: yТридесятое государство имеет форму прямоугольника, стороны которого тянутся с запада на восток и с севера на юг. Картограф изобразил карту государства в виде прямоугольника на системе координат с центром O, совпадающим с юго-западным углом страны и осями, параллельными осям координат. Засеки на карте изображены в виде отрезков различной длины, параллельных осям координат. При этом оказалось, что никакие два отрезка не пересекаются и не лежат на одной прямой.

 

 

 

Для удобства управления своей страной царь Салтан повелел разделить ее на непересекающиеся прямоугольные области с соблюдением следующих условий:

 

1)      каждая засека входит полностью в границы областей

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

 

Напишите программу, помогающую картографическому приказу построить искомое разбиение.

 

Входные данные

В первой строке входного файла находятся координаты северо-восточного угла страны, Во второй строке указано количество засек N (N≤1000). Каждая из следующих N строк содержит описание одной из засек в виде четверки числе x1, y1, x2, y2, что соответствует отрезку с концевыми точками (x1, y1)  и (x2, y2). Все координаты являются неотрицательными целыми и не превосходят 10000.

 

Выходные данные

В первую строку выходного файла выведите количество областей M в найденном разбиении. В последующих M строках должны находиться целочисленные координаты юго-западного и северо-восточного углов для каждой из областей разбиения. Числа внутри строки разделять пробелами.

 

Пример входного файла divide.in

5 5

3

4 1 2 1

2 2 2 3

2 4 0 4

 

Пример выходного файла divide.out

4

2 0 5 1

2 1 5 5

0 4 2 5

0 0 2 4

 

 

Задача 3. Приватизация

имя входного файла

rail.in

имя выходного файла:

rail.out

время тестирования

20 секунд

максимальный балл:

33

 

Железнодорожная сеть состоит из отдельных участков, соединяющих города попарно. Этими участками каждый из N имеющихся городов соединен с тремя другими городами. Две компании собираются приватизировать все эти участки, но антимонопольный комитет настаивает на том, чтобы из каждого города выходили дороги разных компаний.

 

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

 

Входные данные

В первой строке входного файла содержится натуральное число N — количество городов (N≤5000) Далее для каждого города i (i=1,…,N) записана тройка различных чисел — номера тех городов, с которыми он связан. Соединение городов i и j, если оно существует, отражено в соответствующих строках. Между любыми двумя городами может проходить не более одной дороги.

 

Выходные данные

В выходной файл требуется вывести список участков, предназначенных для приватизации одной из компаний (все остальные участки приватизируются другой компанией). Каждый участок задается в отдельной строке двумя числами — номерами тех городов, которые он соединяет. Числа должны разделяться пробелами. Если решения не существует, выходной файл должен содержать единственную строку NO SOLUTION.

 

Пример входного файла rail.in

6

6 5 3

6 4 3

4 1 2

5 3 2

6 4 1

2 1 5

 

Пример выходного файла rail.out

1 6

2 4

3 4

5 6

 

Задача 4. Игра “Просто Филя”

имя входного файла:

filya.in

имя выходного файла:

filya.out

время на один ход:

5 секунд

максимальный балл:

50

 

Дано прямоугольное клеточное поле 41´45 клеток. Каждая клетка покрашена в один из шести цветов. Цвета пронумерованы от 1 до 6. Левая верхняя и правая нижняя клетки поля имеют различный цвет. В результате поле разбивается на некоторое количество одноцветных областей. Две клетки одного и того же цвета, имеющие общую сторону, принадлежат одной и той же области.

 

Правила игры

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

 

3

4

4

5

6

6

6

 

3

3

5

5

6

6

1

 

4

3

5

6

2

4

6

 

2

6

5

6

5

4

6

 

2

4

3

2

6

5

6

 

3

6

6

1

1

1

1

 

 

 

 

 

 

 

 

 

 

 

5

4

4

5

6

6

6

 

5

5

5

5

6

6

1

 

4

5

5

6

2

4

6

 

2

6

5

6

5

4

6

 

2

4

3

2

6

5

6

 

3

6

6

1

1

1

1

 

 

 

 

 

 

 

 

 

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

 

Задание

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

·    по данным входного файла ваша программа выбирает номер цвета, записывает его в выходной файл  и заканчивает свою работу;

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

·    ваша программа будет запускаться до тех пор, пока тестовая игра не завершится;

·    в случае некорректного хода вашей программы тестовая игра завершается досрочно.

 

Критерии оценки

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

 

Входные данные

Входной файл filya.in содержит 41 строку по 45 цифр в каждой без пробелов. Первая цифра файла соответствует цвету левой верхней клетки игрового поля. Вам предоставляется пример входного файла.

 

Выходные данные

Выходной файл filya.out содержит номер цвета хода.

 

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

5

 

Примечание

Для отладки своей программы вы можете воспользоваться программой filya.exe, правила работы с которой описаны в файле read.me.

 

 

Задача 5. Поезда

имя входного файла

train.in

имя выходного файла:

train.out

время тестирования

20 секунд

максимальный балл:

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

  3 2 2

4 3

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

3 2

3 0

P(4,3)

 
0 2

3 4

0 0

  O

 
0 4

6 2

 

 

 

 

Задача 2. Новый алхимик

имя входного файла:

input.txt

имя выходного файла:

output.txt

ограничение времени на каждом тесте:

10 сек

баллы

33

 

Счастливый день!  могу сегодня я

В шестой сундук (сундук еще не полный)

Горсть золота накопленного всыпать.

Немного, кажется, но понемногу

Сокровища растут.

А. С. Пушкин

 

Алхимик Петя изобрел философский камень, с использованием которого можно проводить некоторое множество алхимических реакций по превращению одних веществ в другие. Масса каждого вещест

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

  3 2 2

4 3

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

3 2

3 0

P(4,3)

 
0 2

3 4

0 0

  O

 
0 4

6 2

 

 

 

 

Задача 2. Новый алхимик

имя входного файла:

input.txt

имя выходного файла:

output.txt

ограничение времени на каждом тесте:

10 сек

баллы

33

 

Счастливый день!  могу сегодня я

В шестой сундук (сундук еще не полный)

Горсть золота накопленного всыпать.

Неnd;200). Далее следуют M строк, каждая из которых содержит описание одного из элементов в базе набора гармоний в виде последовательности составляющих ее номеров нот, записанных через пробел. В следующей строке находится целое число L — количество заданных аккордов (1Изначально у Пети имеется один грамм свинца. С помощью философского камня Петя может превратить свой свинец в другие вещества, на которые он потом также сможет воздействовать философским камнем. Выполняя одну за другой алхимические реакции, Петя стремится получить как можно больше золота.

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

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

В первой строке записано целое число K(1£K£6) — количество различных веществ, участвующих и образующихся в алхимических реакциях.

Вторая строка  содержит список этих веществ, разделенных пробелом (в списке обязательно есть свинец и золото). Названия веществ не длиннее 10 букв.

В третьей строке записано целое число L(1£L£100) — количество типов реакций, выполняемых философским камнем.

Далее в файле идут L описаний этих реакций. Каждое описание реакции состоит из двух строк:

·        в первой строке – названия веществ, вступающих в реакцию,

·        во второй строке – названия веществ, получающихся в результате реакции.

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

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

Ниже приведены примеры входного и выходного файлов для представленных на рисунке алхимических реакций, выполняемых философским камнем.

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

5

свинец золото сера ртуть медь

5

свинец

золото сера ртуть

свинец

золото медь ртуть

ртуть золото

сера

ртуть медь

ртуть сера золото

сера ртуть

золото

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

3

 

 

Задача 3. ПЕСНЬ

имя входного файла:

input.txt

имя выходного файла:

output.txt

ограничение времени на каждом тесте:

10 сек

баллы

34 балла

…Звуки умертвив,

Музыку я разъял, как труп. Проверил

Я алгеброй гармонию...

А. С. Пушкин

 

В традиционной музыке используются музыкальные звуки из некоторого набора, именуемого звукорядом. Звуки звукоряда принято группировать в октавы, в каждой из которых 12 звуков. Порядковый номер звука в пределах одной октавы назовем нотой. Таким образом, каждый звук можно задать парой чисел – номером октавы и номером ноты. Номер октавы К – произвольное целое число, номер ноты N  принимает значение из интервала [01,12]. Звуки можно обозначать этими двумя числами, записанными рядом без пробелов (второе число всегда двузначное). Эту запись назовем кодом Q.  Например, Q = –108 для (–1)-й октавы, восьмой ноты. Значение Z, определяемое по формуле  Z = K×12 +N  назовем абсолютным номером Z звука в звукоряде (для приведенного выше примера Z = – 4).

Набор всех звуков, ноты которых принадлежат заданному подмножеству P номеров нот, назовем гармонией G. Это означает, что любой звук с абсолютным номером Z = K×12 +n, где n – номер ноты из P, принадлежит этой гармонии при любом значении K. Отсюда следует, что гармония однозначно определяется указанием P. Две гармонии назовем эквивалентными, если при прибавлении некоторого одного и того же целого числа ко всем абсолютным номерам звуков первой гармонии получаются все элементы второй гармонии. Ограничимся рассмотрением только таких наборов гармоний, в которые наряду с каждой из гармоний входят и все эквивалентные ей. Для описания набора такого вида достаточно указать из каждой совокупности эквивалентных по одной гармонии Gi или соответствующему ей подмножеству Pi. Базой B набора гармоний назовем совокупность всех таких Pi.

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

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

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

Задание

Пусть даны: база B набора гармоний, последовательность аккордов A и начальный звук Q. Требуется написать программу, находящую наименее кучерявую из всех благозвучных мелодий, начинающихся с этого звука.

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

В первой строке записано целое число M — количество заданных элементов в базе набора гармоний (1£ M &pouo-bidi-font-size:10.0pt'>. Строки схемы, соответствующие рифмующимся строкам стихотворения, помечаются одинаковыми числами. Для любого стихотворения его схема строится однозначно. Ниже представлен пример четверостишья и его схемы:

Мой дядя самых честных правил,
Symbol'>£
L£200). Каждая из последующих L строк содержит описание одного из аккордов в виде последовательности кодов составляющих его звуков, записанных через пробел. Описания аккордов следуют в порядке их исполнения. Последняя строка входного файла содержит код начального звука Q. Все значения кодов звуков записываются тремя цифрами.

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

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

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

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

3

1 5 8 11

1 5 8 12

1 6 8

5

101 106

010 112

-101 004

201 202

110 111

102

4

102 104 104 106 106

 

Задача 4. Хлопоты многодетного купца

имя входного файла:

input.txt

имя выходного файла:

output.txt

ограничение времени на каждом тесте:

10 сек

максимальный балл:

30

 

 

Среди заботливых купцов…

А.С. Пушкин

 


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

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

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

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

Первая строка входного файла содержит целое число N — количество дочерей (1£N£100).

В следующей строке файла задано целое число K — количество имеющихся у ювелира видов камней (1£K£100).

Далее следуют K строк. Каждая строка содержит название вида камня и его цену, разделенные пробелом. Название вида камня — слово, длина которого не превышает 10 букв, цена камня — целое число, не превышающее 32767.

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

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

Если решения найти не удается, выходной файл должен содержать единственное слово “NO”.

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

2

3

янтарь 1

изумруд 2

алмаз 3

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

алмаз 1 янтарь 2

изумруд 2 янтарь 1

 

Задача 5. Микрофония

имя входного файла:

input.txt

имя выходного файла:

output.txt

ограничение времени на каждом тесте:

10 сек

максимальный балл:

35

Театр уж полон…

А.С. Пушкин

 

В драматическом театре им. Пушкина к юбилею Александра Сергеевича решили поставить оперу «Евгений Онегин». Артисты театра обладают красивыми, но не очень сильными голосами. По этой причине руководство театра дало указание приобрести радиомикрофоны.

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

Очередность выходов артистов на сцену и их уходов за кулисы указывается в режиссерском плане. Кроме того, в этом плане указывается, через какие кулисы выходит (или уходит) артист и поет ли он в данном выходе.

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

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

Первая строка входного файла содержит натуральное число N — количество артистов, участвующих в спектакле (1£N£1000).

Во второй строке записано натуральное число K — количество выходов артистов на сцену (1£K£3000).

Далее идут 2K строк, описывающих режиссерский план спектакля. Каждая из них содержит четверку Ai Bi Ci Di (1£i£2K):

·        Ai — символ +, если в данный момент артист выходит на сцену, или символ -, если артист со сцены уходит;

·        Bi — номер артиста (целое число от 1 до N);

·        Ci — символ Л, если артист выходит (уходит) через левые кулисы, или символ П, если он выходит (уходит) через правые кулисы;

·        Di — символ Д, если артист поет в данном выходе (пел перед данным уходом), или символ Н, если он не поет (не пел).

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

Первая строка выходного файла должна содержать два целых числа. Первое число — количество микрофонов перед началом оперы с левой стороны, второе число — количество микрофонов с правой стороны. В каждой из последующих K строк необходимо вывести 1 или 0 в зависимости от того, берет ли с собой микрофон очередной выходящий на сцену артист (1 – берет, 0 – не берет).

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

3

4

+ 1 Л Д

– 1 Л Д

+ 2 Л Н

+ 3 Л Н

– 3 П Н

+ 1 П Д

– 1 Л Д

– 2 П Н

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

1 0

1

0

1

1

 

Задача 6. Стихоплет


имя входного файла:

input.txt

имя выходного файла:

output.txt

ограничение времени на каждом тесте:

10 сек

максимальный балл:

35

 

Четырехстопный ямб мне надоел:
Им пишет всякий. Мальчикам в забаву
Пора б его оставить. Я хотел
Давным-давно приняться за октаву.
А в самом деле: я бы совладел
С тройным созвучием. Пущусь на славу!
Ведь рифмы запросто со мной живут;
Две придут сами, третью приведут.

А.С. Пушкин

Любому стихотворению можно поставить в соответствие его схему по следующим правилам. Каждый ударный слог заменяется на символ апостроф «, а безударный — на символ тильда «~». В схеме сохраняется пунктуация (знаки препинания: «,», «;», «:», «.», «?», «!»)Примечание

Будут также оцениваться частичные решения для случая прямоугольного царства.

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

4

9 10

20 40

40 40

51 10

2

21 30

 

4 ~'~'~'~'~,
1 ~'~'~~~',
4 ~~~'~'~'~
1 ~'~'~~~'
.

Будем считать, что в стихотворении действует следующее правило рифмовки: две строки рифмуются, когда в них совпадают все буквы от последней ударной гласной до последней буквы в строке. Если же ударная гласная — последняя буква в строке, то для рифмы необходимо совпадение двух последних букв рифмующихся строк. При этом рифма может порождаться как частью одного слова, так и несколькими подряд идущими словами. Например,

А подбирать союзы да наречья;
                       ,

Мне рифмы нужны; все готов сберечь я.

Отдельные строки стихотворения могут как рифмоваться со всеми строками стихотворения, так и вообще не иметь рифмующихся с ними строк.

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

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

Формат входного файла

В первой строке входного файла находится целое число N — количество строк в стихотворении (1£N£20).

В следующих N строках расположены в произвольном порядке слова соответствующих строк стихотворения. В каждой из них содержится не более 20 слов, разделенных пробелами. Под словом понимается последовательность прописных русских букв (за исключением «ё») и, при необходимости, знака дефис «-». Длина слова не превышает 30 символов. Если слово состоит более чем из одного слога, то перед ударной гласной стоит символ «'».

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

Формат выходного файла

Выходной файл должен содержать любой вариант восстановленного стихотворения с сохранением пунктуации. Слова одной строки должны быть отделены друг от друга одним пробелом. Между знаком препинания и предшествующим ему словом должен отсутствовать пробел.

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

4

д'ядя мой пр'авил с'амых ч'естных

в занем'ог когд'а не ш'утку

заст'авил он себ'я уваж'ать

в'ыдумать и л'учше мог не

4 ~'~'~'~'~,

1 ~'~'~~~',

4 ~~~'~'~'~

1 ~'~'~~~'.

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

мой самых дядя честных правил,

в когда не шутку занемог,

он уважать себя заставил

не лучше выдумать и мог.

Примечания.

1.      Будут оцениваться и такие решения, в которых соблюдены порядок чередования ударных/безударных слогов и пунктуация оригинала, а рифмы нет.

2.      Пример входного файла находится на вашем диске.

 

 

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

Троицк Московской области, март 2000 г.

 

1. Коррозия металла

Входной файл:                       INPUT.TXT

Выходной файл:                     OUTPUT.TXT

Ограничение времени:         5 секунд на тест

Максимальная оценка:          25 баллов

 

Для хранения двух агрессивных жидкостей A и B используется емкость с многослойной перегородкой, которая изготавливается из имеющихся N листов. Для каждого листа i (i = 1,…,N) известно время его растворения жидкостью Aai  и жидкостью Bbi. Растворение перегородки каждой из жидкостей происходит последовательно лист за листом, с постоянной скоростью по толщине листа. Требуется спроектировать такую перегородку, время растворения которой было бы максимальным.

Входные данные

В первой строке входного файла записано число N (1£N£256). В каждой из последующих N строк содержатся два положительных вещественных числа ai и bi, разделенные пробелом.

Выходные данные

В первую строку выходного файла записать время растворения перегородки с точностью до 3 цифр после десятичной точки. В следующую строку файла записать номера листов в порядке их расположения от жидкости A к жидкости B, разделяя числа пробелами.

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

4

1 2

1 2

0.5 1.5

7 3.5

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

6.000

4 2 1 3

 

2. UP

Входной файл:                       INPUT.TXT

Выходной файл:                     OUTPUT.TXT

Ограничение времени:         10 секунд на тест

Максимальная оценка:          35 баллов

 

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

Уровень подготовки программиста по каждой из перечисленных тем оценивается своим индексом UP по L-балльной шкале от 1 до L. Для каждой из задач определены минимальные UP программиста по каждой из тем, необходимые для того, чтобы он смог решить данную задачу. Определены также UP, которых программист достигнет, решив ее. Если при этом по какой-то из тем он уже имел более высокий UP, то этот уровень не понизится. На решение задачи, повышающей хотя бы один из UP, программист тратит 2 часа, в противном случае — 1 час.

Требуется разработать учебный план, занимаясь по которому не более T часов, начинающий программист  (UP=1 по всем темам) достиг бы уровня подготовки L по всем темам, прорешав за это время как можно больше различных задач.

Входные данные

В первой строке входного файла задано число T — количество часов, которыми располагает претендент для подготовки к собеседованию. Во второй строке записано число L (2 £ L £ 16), а в третьей строке — количество задач M (1 £ M £ 500, T £ 2×M). Каждая из последующих M строк содержит 8 чисел, описывающих одну из задач. Первые четыре числа определяют UP претендента по всем темам, необходимые для того, чтобы он мог решить эту задачу. Следующие четыре числа задают UP, до которых в результате решения этой задачи повысятся те уровни подготовки претендента, которые были ниже.

Выходные данные

При возможности достижения уровня подготовки L по всем темам в выходной файл вывести сначала максимальное количество задач в учебном плане, а затем — последовательность номеров задач, которые должен решить претендент. Задачи нумеруются в том порядке, в каком они описаны во входном файле, ни одна задача не может быть указана более одного раза. Если с помощью указанного во входном файле набора задач за время T начинающий программист не сможет достигнуть UP, равного L по всем темам, вывести в выходной файл одно число 0.

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

7

5

6

2 1 1 1 2 4 5 5

1 1 1 1 3 1 1 1

3 3 3 3 3 3 3 3

1 3 1 1 5 5 5 5

2 2 2 2 2 2 2 2

1 2 3 4 2 3 4 5

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

4

2 1 4 3

 

 

3. Раздел царства

Входной файл:                       INPUT.TXT

Выходной файл:                     OUTPUT.TXT

Ограничение времени:         10 секунд на тест

Максимальная оценка:          40 баллов

 

Царство царя Гороха представляет собой выпуклый N-угольник, внутри которого расположены K селений. Царь решил завещать двум своим сыновьям по полцарства, одинаковые по площади и с равным количеством селений. Для этого он требует разделить царство одной прямолинейной границей.

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

Входные данные

Первая строка входного файла содержит количество вершин многоугольника N (3£N£50). В следующих N строках заданы координаты вершин многоугольника, перечисленные в порядке обхода контура по часовой стрелке. В (N+2)-ой строке указано количество селений K (0£K£100), а в последующих K строках заданы координаты селений. Все координаты — целые числа, не превосходящие по модулю 106. Размерами селений следует пренебречь.

Выходные данные

В выходной файл н=36 valign=top style='width:26.7pt;padding:0cm 5.4pt 0cm 5.4pt'>

 

 

1

40 20

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

30.000000 35.000000

30.000000 15.000000

 

 

4.     Аппликатура

Входной файл:                       INPUT.TXT

Выходной файл:                     OUTPUT.TXT

Ограничение времени:         5 секунд на тест

Максимальная оценка:          30 баллов

 

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

 

Пронумеруем пальцы пианиста слева направо натуральными числами от 1 до P, клавиши инструмента также пронумеруем слева направо натуральными числами от 1 до K. Тогда запись звуков мелодии можно представить в виде последовательности N номеров клавиш, которые следует нажимать для ее исполнения, где N — длина мелодии.

 

Пусть для каждой пары пальцев с номерами i и j заданы целые числа aij и bij, такие, что если палец i нажимает клавишу X, то следующей клавишей пальцем j может быть нажата лишь клавиша из диапазона [X+aij, X+bij]. Этот набор чисел aij, bij, 1£i£P, 1£j£P, зависит от особенностей пианиста и его исполнительской техники. Заметим, что не каждая мелодия может быть сыграна конкретным пианистом при указанных выше ограничениях.

 

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

Входные данные

В первой строке входного файла содержится число P — количество пальцев у пианиста (1£P£20). Во второй строке записано число K — количество клавиш у инструмента (1£K£10000). В третьей строке указаны целые числа a11 b11 a12 b12a1P b1P a21 b21 a22 b22a2P b2PaP1 bP1 aP2 bP2aPP bPP, разделенные пробелами (–K £ aij £ bij £ K). В четвертой строке находится число N — длина мелодии (1£N£1000). Пятая строка содержит N чисел X1 X2 X3XN — последовательность разделенных пробелами номеров клавиш для исполнения  мелодии.

Выходные данные

В первой строке выходного файла должно содержаться либо число L — количество перекладываний пальцев в оптимальной аппликатуре, либо число –1 при невозможности сыграть мелодию. Вторая строка при наличии решения должна содержать N чисел Y1YN — последовательность разделенных пробелами номеров пальцев при исполнении мелодии.

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

3

10

0 0 -2 -2 -5 1 2 3 8 10 0 1 2 10 -2 -2 -1 -1

9

4 5 7 7 7 6 8 7 5

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

3

2 3 1 1 3 3 1 3 2

 

 

5.     Выскажись!

Входной файл:                       INPUT.TXT

Выходной файл:                     OUTPUT.TXT

Ограничение времени:         10 секунд на тест

Максимальная оценка:          40 баллов

 

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

  1. Всероссийская олимпиада по информатике проводится весной (истинно).
  2. 5 в квадрате меньше нуля (ложно).

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

 

Сложным высказыванием назовем два и более простых высказывания, соединенные союзами И, ИЛИ, оборотами ЕСЛИ …, ТО … и … ТОГДА И ТОЛЬКО ТОГДА, КОГДА … . Назовем эти союзы и обороты вместе с частицей НЕ логическими операциями, обозначив их следующим образом:

 

НЕ …

 !…

… И …

 …&…

… ИЛИ …

 …|…

ЕСЛИ …, ТО …

 …=>…

… ТОГДА И ТОЛЬКО ТОГДА, КОГДА …

 …<=>…

 

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

 

A

!A

 

A

B

A&B

A|B

A=>B

A<=>B

0

1

 

0

0

0

0

1

1

1

0

 

0

1

0

1

1

0

 

0

1

0

0

1

0

0

 

 

 

1

1

1

1

1

1

 

В сложном высказывании операции имеют следующие приоритеты в порядке от высшего к низшему: !, &, |, =>, <=>. Например, в выражении A<=>!B=>C|D&E операции будут выполняться в таком порядке: (A<=>((!B)=>(C|(D&E)))). Здесь и далее в качестве имен высказываний будем использовать большие буквы латинского алфавита.

 

Рассмотрим следующую последовательность описаний.

а)  Сначала идут описания простых высказываний вида:

<имя>=<простое высказывание>

В каждом <простом высказывании> определяющее слово заключается в круглые скобки.

б)  Затем из описанных ранее высказываний с помощью логических операций строятся сложные высказывания по одному из следующих двух правил:

<имя>=!<имя>

<имя>=<имя><логическая операция><имя>

При использовании второго правила операция ! (НЕ) не может использоваться в качестве <логической операции>.

 

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

Требуется

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

2.      Изменить полученное в пункте 1 логическое выражение так, чтобы операции ! (НЕ) стояли только перед именами простых высказываний, а не перед скобками, и истинность результирующего высказывания при этом не изменилась. Скобки можно как оставлять, так и раскрывать, используя приоритеты операций. Заметим, что в измененном логическом выражении возможно появление любых из перечисленных выше логических операций, отличных от имевшихся в исходном логическом выражении. (20 баллов)

3.      Построить результирующее высказывание на русском языке согласно полученному в пункте 2 выражению, опуская круглые скобки у определяющих слов в простых высказываниях и круглые скобки в логическом выражении. (10 баллов)

Входные данные

В первой строке входного файла содержится число N, задающее количество описаний в последовательности. В последующих N строках записаны описания по определенным выше правилам, каждое описание — в отдельной строке. Простые высказывания обозначаются буквами из диапазона от A до J и имеют длину не более 50 символов. Сложные высказывания обозначаются буквами из диапазона от K до T, пробелы в их определениях отсутствуют. В конце файла может содержаться одна или несколько пустых строк.

Выходные данные

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

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

6

A=(шел) дождь

В=асфальт (мокрый)

C=(хочется) гулять

K=А&B

L=!К

М=L=>C

 

Пример 1 возможного выходного файла к приведенному примеру входного файла

((!(A&B))=>C)

((!A|!B)=>C)

ЕСЛИ НЕ шел дождь ИЛИ асфальт НЕ мокрый, ТО хочется гулять

Пример 2 возможного выходного файла к тому же примеру входного файла

((!(A&B))=>C)

C|A&B&!C

хочется гулять ИЛИ шел дождь И асфальт мокрый И НЕ хочется гулять

 

Примечания

Если в выходном файле вторая строка пустая, то ответ на пункт 3 оцениваться не будет.

На жестком диске вашего компьютера находятся два примера входных файлов, один из которых совпадает с примером, приведенным в условии, и соответствующие им возможные выходные файлы. С помощью данных файлов вы можете определить коды символов, использующихся для обозначения логических операций, а также правильное написание логических операций на русском языке. Файлы называются INРUT1.TXT и OUTРUT1.TXT, INРUT2.TXT и OUTРUT2.TXT.

 

6.     УМНОжение

Входной файл:                       INPUT.TXT

Выходной файл:                     OUTPUT.TXT

Ограничение времени:         5 секунд на тест

Максимальная оценка:          30 баллов

 

Известный ученый Яков Трахтенберг разработал систему быстрого счета для нахождения произведения двух натуральных чисел. Так, вычисление произведения 23 и 14 давало в качестве промежуточного результата последовательность чисел  12  11  2, называемую набором Трахтенберга. Далее по этому набору получался конечный результат, равный 322.

Приведем еще несколько примеров таких наборов:

     241304   ´      32  =>    8   12     6   11   11   16     6   =>   7721728

           527   ´    463  =>  21   48   55   38   20                 =>     244001

         3214   ´  5643  =>  12   19   34   43   29   28   15   => 18136602

         1245   ´        8  =>  40   32   16     8                        =>         9960

 

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

Входные данные

Во входном файле в одной строке записана последовательность чисел, разделенных пробелом, задающих некоторый набор Трахтенберга. Количество чисел в наборе не более 50.

Выходные данные

Выведите в выходной файл искомые пары сомножителей и их произведения в формате:

<множимое>*<множитель>=<результат произведения>

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

Примечание

Старшие цифры сомножителей и результата произведения не могут равняться нулю.

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

8 12 6 11 11 16 6

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

241304*32=7721728

 

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

Екатеринбург,  март 2001 года

 

Задача 1. Бизнес-классики

Входной файл                                         class.in

Выходной файл                                      class.out

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

Максимальная оценка                            35  баллов

 

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

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

Входные данные

В первой строке входного файла с именем class.in записано натуральное число N (1£N£80). В каждой из последующих трех строк находится N чисел  (0 или 1), описывающих расположение рублей в клетках первой, второй и третьей строки игрового поля соответственно. Единица обозначает наличие рубля в клетке, ноль – его отсутствие. Числа в каждой из этих трех строк входного файла расположены через пробел.

Выходные данные

Выходной файл с именем class.out должен содержать 2 строки. В первой строке должен находиться номер строки игрового поля (1, 2 или 3), с которой играющему следует начать игру. Вторая строка файла должна описывать последовательность прыжков. Каждый прыжок в этой последовательности нужно обозначить одним из следующих символов:

 

 

·         U – если в результате прыжка номер строки, на которой находится играющий, уменьшился на 1;

·         D – если номер строки увеличился на 1;

·         L – если номер столбца уменьшился на 1;

·         R – если номер столбца увеличился на 1.

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

 

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

4

1 1 1 0

1 1 1 0

1 1 1 1

 

Пример выходного файла для приведенного примера входного файла

1

DDRUURDDRUU

 

 

 

 


Задача 2. Оппозиция.

Входной файл                                         org.in

Выходной файл                                      org.out

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

Максимальная оценка                            30 баллов

 

В некоторой стране полиция выявила разветвленную сеть оппозиционной  партии.

Партия сильно законспирирована и состоит из рядовых членов и руководителей различных уровней. Во главе партии  стоит один главный руководитель — лидер партии. До начала арестов приказ лидера может быть доведен до любого члена партии. Все члены партии пронумерованы от 1 до N.

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

Естественно, что с началом арестов членов партии, она распадется на мелкие, не связанные друг с другом группы. Например, с арестом члена партии №2 (см. рис.1), партия разваливается на 4 группы.

Полицмейстер уверяет, что группа, состоящая из менее, чем К членов партии, идеологически вырождается и не представляет угрозы для государства.

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

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

Входные данные

Входной файл с именем org.in содержит три строки. В первой  записано число K (1£K£10000), во второй строке — число N (1£N£10000), определяющее количество членов партии. Третья строка содержит набор из N–1 числа. В этой строке для каждого члена партии, кроме лидера, задается номер его непосредственного руководителя. Номер руководителя всегда меньше, чем номер подчиненного. При этом первое число задает номер руководителя второго члена партии, второе — третьего и так далее. Числа в строке разделяются одним пробелом.

Выходные данные

Выходной файл с именем org.out состоит из двух строк. В первую строку необходимо поместить количество арестов, а во вторую - номера членов партии, подлежащих аресту. Эти номера разделяются одним пробелом. При наличии нескольких решений выведите одно из них.

Пример входного файла для структуры партии, представленной на рис.1

3

14

1 1 2 2 3 2 3 6 6 6 7 4 7

                      Рис. 1

Пример выходного файла для приведенного входного файла

4

6 2 7 8

 

Задача 3. Телеметрия

Входной файл:                                       tele.in
Входной файл:                                       tele.out
Ограничение по времени:                      5 секунд на тест
Максимальная оценка:                          35 баллов

Для космического корабля сконструирована телеметрическая система, содержащая N  (1£N£1000) групп датчиков. Каждая из этих групп включает Pi (1<Pi) датчиков. Группе датчиков соответствует свой канал связи, к которому в конкретный момент времени может быть подключен только один датчик этой группы, который назовем активным.

С центрального пульта на систему могут подаваться команды управления. Каждая команда управления имеет вид: {<номер группы>, «следующий / предыдущий»}. При этом номер активного датчика в соответствующей группе увеличится или уменьшится на единицу. Попытка установить номер активного датчика в группе вне пределов [1..Pi] ведет к аварийному останову контроллера.

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

Для комплексной проверки корабля требуется проводить съем показаний для всех возможных комбинаций активных датчиков, причем повторять уже использованные ранее комбинации активных датчиков запрещается. Общее количество комбинаций активных датчиков не превосходит 10000.

После окончания проверки система должна оказаться в исходном состоянии.

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

Входные данные

Входной файл с именем tele.in содержит следующие три строки. Первая строка содержит число N – количество групп датчиков. Вторая строка содержит N чисел P1, P2, … , PN, каждое из которых задает количество датчиков в соответствующей группе. Третья строка содержит N исходных номеров активных датчиков в группах. Числа во второй и третьей строках разделены пробелом.

Выходные данные

Выходной файл с именем tele.out должен содержать следующие строки. В первую строку выводится сообщение “Yes” или “No” в зависимости от того, возможно или нет реализовать управление контроллером, осуществляющее требуемую схему съема данных. При выводе сообщения “Yes” в последующих строках выдается последовательность команд управления. Каждая строка содержит по одной команде вида: <номер группы> <пробел> <знак “+” или “–“>. При этом знак “+” соответствует увеличению на 1, а знак “–” – уменьшению на 1 номера активного датчика в этой группе.

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

2

2 3

2 1

 

Пример выходного файла, соответствующего приведенному входному файлу

Yes

1 –

2 +

2 +

1 +

2 –

2 –

 

Примечание. Будут отдельно оцениваться решения для частных случаев N=1, N=2, N=3.

 

Задача 4. Лесной пожар

Входной файл                                         fire.in

Выходной файл                                      fire.out

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

Максимальная оценка                            35 баллов

 

В МЧС поступило сообщение о возможном лесном пожаре в заданном квадрате тайги. Для поиска места возгорания было послано N самолетов. Однако ни один из экипажей пожар не обнаружил.

Известно, что с самолета видна полоса тайги, границы которой находятся на расстоянии 50 км справа и слева от той линии на поверхности Земли, над которой пролетает самолет (см. рисунок), причем точки, находящиеся на расстоянии ровно 50 км от этой линии, все еще видны. Донесение с каждого самолета содержало информацию о том, в каких двух различных точках (xb, yb) и (xeye) самолет входил в заданный квадрат и покидал его соответственно. Между этими точками самолет двигался строго по прямой.

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

Входные данные

Входной файл с именем fire.in состоит из N +2 строк.

В первой строке записано натуральное число L – размер заданного квадрата тайги в километрах (0<L£1000). Во второй строке – натуральное число N (1£N£100) – количество самолетов. В каждой из последующих N строк записано донесение с самолета – четыре вещественных координаты xb, yb, xe, ye. Координаты заданы в километрах. Стороны квадрата тайги параллельны осям координат, его левый нижний угол находится в точке с координатами (0, 0), а правый верхний – в точке (LL).

Выходные данные

Выходной файл с именем fire.out должен содержать одну строку. Если заданный квадрат был просмотрен полностью, то эта строка должна состоять из слова OK, написанного заглавными латинскими буквами. В противном случае в этой строке должны быть записаны через пробел координаты x и y какой-либо точки, которая не попала ни в одну из просмотренных полос. Координаты нужно выводить в километрах с ошибкой не более одного метра*).

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

245

1

26.1 0 193.568 245

Пример выходного файла для приведенного примера входного файла

155.123 100

Примечание

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

 

Задача 5. Замок

Входной файл                                         castle.in

Выходной файл                                      castle.out

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

Максимальная оценка                            32  балла

 

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

Между двумя комнатами замка не более одной двери. Общее количество дверей не превосходит 5000.

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

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

 

Входные данные

Во входном файле castle.in содержится план замка.

В первой строке входного файла находится натуральное число N (1<N<1000) – количество комнат.

Во второй строке входного файла содержится натуральное число K (1£K£N) – номер комнаты, в которой принц и гувернантка завтракали.

В последующих N строках содержатся списки смежных комнат: в i-й строке перечислены через пробел номера комнат, смежных с i комнатой. Каждая такая строка заканчивается нулем.

Выходные данные

Выходной файл с именем castle.out должен содержать следующую информацию. Если принц не сможет избежать наказания, в единственной строке файла выводится сообщение No. В противном случае, в первой строке файла выводится сообщение Yes, во второй строке – количество дверей, закрытых принцем, а в третьей строке – последовательность номеров комнат, разделенных пробелами, в которых побывал принц.

 

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

4

1

2 4 0

4 1 3 0

2 4 0

1 2 3 0

 

Пример выходного файла для приведенного примера входного файла

Yes

3

1 4 2 3

 

Примечание

Будут отдельно оцениваться решения для частного случая N£100.

 

Задача 6. Олимпиада

 

Входной файл                         olymp.in

Выходной файл                      olymp.out

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

Максимальная оценка            33 балла

 

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

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

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

Известно, что i-й делегат тратит на проход через пункт контроля ti секунд. Для прохода одной пары делегатов требуется время, равное времени прохода менее расторопного из этой пары.

Для каждого члена делегации время, требуемое для выхода из здания, такое же, как и для входа.

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

Входные данные

В первой строке входного файла olymp.in задается натуральное число N (2£N£1000).

В последующих N строках находятся натуральные числа t1, t2, ... , tN (по одному в строке) – времена прохода членов делегации через пункт контроля в секундах, 1£ti£10000.

Выходные данные

В первой строке выходного файла olymp.out необходимо выдать наименьшее возможное время (в секундах), через которое вся делегация окажется во Дворце молодежи.

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

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

3

5

5

10

Пример выходного файла  для приведенного примера входного файла

20

1 2 2

2 3

 



*) В одном километре 1000 метров.