Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 
[Положение] [Расписание] [Архив] [Содержание] [Задачи] [Рейтинг]

Задачи олимпиады "Пятнадцатая командная олимпиада"

Задача A. Расписание

(Время: 1 сек. Память: 16 Мб)

Каждый день в университете проходит следующим образом. В 00:00 наступает утро, которое длится до начала первой пары. Затем проходят 6 пар, разделенных переменами. Наконец, наступает вечер, который продолжается до 23:59 включительно. Зная текущее время и расписание звонков, определите, идет ли сейчас пара, и если идет, то какая. Пара включает в себя минуту своего начала, но не включает минуту своего окончания. Расписание звонков приведено в таблице:

Номер парыВремя началаВремя окончания
18:309:55
210:1011:35
311:5013:15
413:4515:10
515:2516:50
617:0518:30

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

Входной файл INPUT.TXT содержит текущее время в формате hh:mm (с ведущими нулями). Гарантируется, что hh от 00 до 23, mm от 00 до 59.

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

В выходной файл OUTPUT.TXT выведите:

  • «MORNING», если сейчас утро;
  • «EVENING», если сейчас вечер;
  • «BREAK», если сейчас перемена;
  • целое число (номер пары), если сейчас пара.

Примеры

INPUT.TXTOUTPUT.TXT
111:202
207:00MORNING

Задача B. Олимпиада

(Время: 1 сек. Память: 16 Мб)

Трое студентов, пятикурсник, третьекурсник и первокурсник, живут в одной комнате общежития и любят участвовать в соревнованиях по программированию по правилам ACM. У каждого из них свой подход к решению задач. Пятикурсник решает все задачи строго по порядку - сначала первую, затем вторую, и так до последней. Третьекурсник решает задачи строго в обратном порядке – сначала последнюю, затем предпоследнюю, и так до первой. А первокурсник сначала решает самую простую задачу, затем – самую простую из оставшихся задач, и так до самой сложной. Сложность задачи определяется временем, необходимым для её решения. Для решения одной и той же задачи наши студенты тратят одинаковое количество времени.

Ваша задача – по описанию соревнований по программированию определить, кто из студентов победит. Напомним, что по правилам ACM побеждает участник, за 300 минут решивший больше всего задач, а при равенстве количества задач – набравший меньше штрафного времени.

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

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

Входной файл INPUT.TXT содержит натуральное число N (N ≤ 10) – количество задач. Во второй строке записаны N натуральных чисел – количество минут, необходимое для решения каждой задачи. Время решения задачи не превосходит 300 минут.

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

В выходной файл OUTPUT.TXT выведите номер курса студента, одержавшего победу в олимпиаде.

Примеры

INPUT.TXTOUTPUT.TXT
13
40 30 60
1
24
10 20 30 40
1

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

В первом тесте пятикурсник набрал 240 штрафных минут (40 + 70 + 130), третьекурсник – 280 (60 + 90 + 130), первокурсник - 230 минут (30 + 70 + 130).

Во втором тесте третьекурсник набрал 300 минут, а первокурсник и пятикурсник – 200 минут. Но пятикурсник уступил первокурснику.


Задача C. Шоколадки

(Время: 1 сек. Память: 16 Мб)

Рома играет сам с собой в очень интересную игру. Для нее нужна коробка конфет, в которой конфеты расположены прямоугольником n×m штук. В игре участвуют конфеты из темного и белого шоколада. Сначала коробка заполняется конфетами произвольным образом. Далее Рома повторяет следующие операции. Он находит три конфеты одного цвета, лежащие рядом (в ряд, или в виде буквы «Г»), съедает их и заполняет освободившиеся места новыми конфетами произвольным образом. Если же он не находит трех конфет одного цвета, лежащих рядом, то игра заканчивается.

Посчитайте, сколько различных комбинаций может остаться на доске (то есть, в коробке) после окончания игры. Например, если n = 2, m = 3, то может остаться восемь различных комбинаций:

(здесь символами «B» и «W» обозначены конфеты из темного и белого шоколада соответственно)

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

Входной файл INPUT.TXT содержит два целых числа - n и m. (1 ≤ n, m ≤ 1000).

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

В выходной файл OUTPUT.TXT выведите одно число - ответ на вопрос задачи.

Пример

INPUT.TXTOUTPUT.TXT
12 38

Задача D. Экзамен - 2

(Время: 1 сек. Память: 16 Мб)

Экзамен по берляндскому языку проходит в узкой и длинной аудитории. На экзамен пришло N студентов. Все они посажены в ряд. Таким образом, позиция каждого человека задается координатой на оси Ox (эта ось ведет вдоль длинной аудитории). Два человека могут разговаривать, если расстояние между ними меньше или равно D. Какое наименьшее количество типов билетов должен подготовить преподаватель, чтобы никакие два студента с одинаковыми билетами не могли разговаривать? Выведите способ раздачи преподавателем билетов.

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

В первой строке входного файла INPUT.TXT содержится два целых числа N, D (1 ≤ N ≤ 104; 0 ≤ D ≤ 106). Вторая строка содержит последовательность различных целых чисел X1, X2, ... , XN, где Xi (0 ≤ Xi ≤ 106) обозначает координату вдоль оси Ox i-го студента.

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

В первую строку выходного файла OUTPUT.TXT выведите Q – наименьшее количество типов билетов, необходимых для проведения экзамена. Во вторую строку выведите последовательность N целых чисел от 1 до Q, i-ое число этой последовательности обозначает номер типа билета i-го студента. Если ответов несколько, выведите любой.

Примеры

INPUT.TXTOUTPUT.TXT
14 1
11 1 12 2
2
1 1 2 2
24 0
11 1 12 2
1
1 1 1 1

Задача E. Домашняя работа

(Время: 1 сек. Память: 16 Мб)

Витя наконец-то прошёл последний уровень своей любимой игры "Прострели мне колено". На часах было уже полдвенадцатого, а он до сих пор не сделал домашнюю работу по математике. Прочитав задание, Витя сказал: "О, какое же оно скучное, посчитать сумму прогрессии... Вот посчитать сумму остатков - это весело!". Витя написал в тетрадке

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

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

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

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

В выходной файл OUTPUT.TXT выведете единственное число - ответ на задачу.

Примеры

INPUT.TXTOUTPUT.TXT
15 514
210 19

Задача F. Пушка

(Время: 1 сек. Память: 16 Мб)

В начале координат установлена пушка, стреляющая шариками для пинг-понга. На некотором расстоянии R от нее, параллельно оси ОХ, находится кирпичная стена бесконечной длины. Между стеной и осью OX расположена точечная цель с координатами (X,Y). Требуется нацелить пушку так, чтобы шарик ударился сначала о стену, а затем попал в цель. Определите кратчайшее расстояние от оси OY до точки соударения шарика со стеной.

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

Во входном файле INPUT.TXT содержится три целых числа R, X и Y (-10 ≤ X ≤ 10, 0 ≤ Y< R ≤ 10), разделенных пробелами.

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

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

Примеры

INPUT.TXTOUTPUT.TXT
110 5 53.33
210 10 56.67

Задача G. Экзамен

(Время: 1 сек. Память: 16 Мб)

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

N-арное дерево – это дерево, степень каждого узла которого не превосходит N. Бинарные (двоичные) деревья – это частный случай n-арного дерева при n=2.

Существует красивый способ представить любое n-арное дерево с помощью бинарного. Речь идет о так называемом (FC-NS)-представлении (First Child – Next Sibling). Каждый узел такого дерева слева ссылается на потомка (или на NIL), а справа ссылка осуществляется на брата (узел с общим предком). Пусть Par(N) – функция, возвращающая предка для N, либо NIL в том случае, когда N – корень. Таким образом, узлы N и S – братья, если Par(N)=Par(S).

Будем обозначать узлы дерева ASCII-символами '0'-'9', 'a'-'z', 'A'-'Z'. Пусть Val(N) – функция, возвращающая ASCII-код символа, обозначающего узел. Определим также функцию FC(N), возвращающую первого потомка для N (либо NIL при отсутствии такового). Аналогично определим функцию NS(N), которая будет возвращать следующего брата за узлом N.

FC(N) – это потомок Сi с наименьшим значением Val(Ci) для всех потомков,

NS(N) – такой брат Si, с наименьшим Val(Si) для всех Val(Si)>Val(N).

Ниже рассмотрим пример 3-арного дерева и его бинарного (FC-NS)-представления, полученное в результате вышеупомянутых рассуждений:

                      1                                           1
                     /|\                                          |
                    / | \                                         2-3-4
                   /  |  \                                        |   |
                  2   3   4                                       5-6 7
                 / \       |                                          |
                5   6      7                                          8-9
                          / \								
                         8   9								

                3-арное дерево	                      Бинарное (FC-NS)-представление

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

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

Первая строка входного файла INPUT.TXT содержит P – количество узлов заданного множества деревьев (их может быть более одного). Далее следуют P строк, содержащие пары ASCII-символов ('0'-'9', 'a'-'z', 'A'-'Z'), разделенные пробелом. Первый из них – узел потомка, второй – узел предка. Родительский узел корневого узла обозначен символом '-'. Никакие узлы не повторяются дважды. Различные узлы обозначаются различными символами.

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

В выходной файл OUTPUT.TXT выведите заданное множество деревьев в бинарном (FC-NS)-представлении. Первая строка должна содержать корневые узлы деревьев, следующие в порядке возрастания ASCII-кодов по одному из нижеизложенных правил построения:

  1. Корневой узел первого дерева должен располагаться в первой строке, в самой левой позиции.
  2. FC(N) (если не NIL) должен печататься под узлом N, разделяясь вертикальной линией '|'.
  3. NS(N) (если не NIL) должен печататься справа от узла N, разделяясь одним или несколькими символами '-'.
  4. Узлы одного уровня (с равным расстоянием от корня) всегда должны располагаться в одной строке.
  5. Никакие два символа не должны соприкасаться, они должны отделяться либо горизонтальной, либо вертикальной линией.
  6. Никакие два символа не должны пересекаться (печататься один на другом), все должны быть видимыми.
  7. Количество символов при выводе должно быть минимальным (не должно быть лишних пробелов и лишних пропусков с использованием линий).

Просим учесть, что утверждение 7 не следует из примеров, приведенных ниже.

Примеры

INPUT.TXTOUTPUT.TXT
19
1 -
2 1
3 1
4 1
5 2
6 2
7 4
8 7
9 7
1
|
2-3-4
|   |
5-6 7
    |
    8-9
21
A -
A

Примечание

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


Задача H. Хоккей

(Время: 1 сек. Память: 16 Мб)

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

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

Входной файл INPUT.TXT содержит натуральное число N (N≤104) – количество команд.

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

В выходной файл OUTPUT.TXT выведите единственное число – искомое количество способов награждения участников.

Примеры

INPUT.TXTOUTPUT.TXT
136
2206840


Красноярский краевой Дворец пионеров, (c)2006 - 2018, ICQ: 151483, E-mail: admin@acmp.ru