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

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

HotLog


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

Задачи олимпиады "Четвертая командная олимпиада"

Задача A. Крестные отцы

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

Два главы крупных кланов дон Ромарио Магдини и дон Вито Демидетти встретились в центре затихшего города, чтобы выяснить раз и навсегда, кому он принадлежит. «Этот город тесен для нас двоих» – сказал Вито. «Давайте решим вопрос относительно мирным путём, дорогой дон. Предлагаю сыграть в игру. Кто проиграет, тот уходит из города» – сказал Ромарио. После небольшой паузы, Вито сказал: «Я знаю как Вы, дорогой дон, хорошо играете, и даже знаю Вашу любимую игру. Предлагаю немного изменить её правила». «Хорошо, но тогда я хожу первым» – сказал Ромарио.

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

Определите, кто выиграет при оптимальной игре обоих сторон, если дон Ромарио ходит первым.

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

Входной файл INPUT.TXT содержит целое десятичное число, состоящее не более чем из 104 цифр, возможно, с ведущими нулями.

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

В выходной файл OUTPUT.TXT выведите «Romario», если выиграет дон Ромарио, или «Vito», если выиграет дон Вито.

Примеры

INPUT.TXTOUTPUT.TXT
11Romario
210Vito
311Vito

Задача B. Гирлянда

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

Гирлянда состоит из N лампочек на общем проводе. Один её конец закреплён на заданной высоте A мм (H1 = A). Благодаря силе тяжести гирлянда прогибается: высота каждой неконцевой лампы на 1 мм меньше, чем средняя высота ближайших соседей (Hi = (Hi-1 + Hi+1) / 2 - 1 для 1 < i < N).

Требуется найти минимальную высоту второго конца B (B = HN) при условии, что ни одна из лампочек не должна лежать на земле (Hi > 0 для 1 ≤ i ≤ N).

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

Входной файл INPUT.TXT содержит два числа N и A (3 ≤ N ≤ 1000 - целое, 10 ≤ A ≤ 1000 - вещественное).

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

В выходной файл OUTPUT.TXT выведите одно вещественное число B с двумя знаками после запятой.

Примеры

INPUT.TXTOUTPUT.TXT
18 159.75
2692 532.81446113.34

Задача C. Шары и коробки - 2

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

По кругу стоит N коробок. Каждая коробка имеет одного правого и одного левого соседа. В i-ой коробке находится Ai шаров. Известно, что общее количество шаров во всех коробках не превосходит N. За один ход разрешается переложить один шар из коробки в соседнюю. Какое наименьшее количество ходов придется совершить, чтобы в каждой коробке находилось не более одного шара?

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

Первая строка входного файла INPUT.TXT содержит целое число N (1 ≤ N ≤ 1000). Во второй строке определена последовательность N целых чисел A1, A2, ... , AN (0 ≤ Ai ≤ N). Сумма всех значений Ai не превосходит N.

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

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

Пример

INPUT.TXTOUTPUT.TXT
17
1 0 0 0 2 3 1
7

Задача D. Одежда

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

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

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

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

Первая строка входного файла INPUT.TXT содержит число N - количество жителей города, которых видит путешественник (1 ≤ N ≤ 104). Вторая строка теста содержит N натуральных чисел, разделенных пробелами. Каждое число сi – это цвет одежды i-го жителя (1 ≤ ci ≤ 100).

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

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

Примеры

INPUT.TXTOUTPUT.TXT
16
1 2 5 2 1 2
2
24
5 5 4 4
0

Задача E. Прыжки в длину

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

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

По имеющемуся протоколу соревнований требуется определить тройку победителей.

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

Первая строка входного файла INPUT.TXT содержит целое N – количество участников соревнований (1 ≤ N ≤ 100). Далее следует N строк, каждая из которых представляет результаты выступления отдельного спортсмена в следующем формате:

CNT Name Surname N1 N2 N3 N4 N5 N6

Первые параметры определяют страну, имя и фамилию участника – строки из английских символов, каждая из которых не превышает 80 символов. Ni – значения прыжков в метрах, записанные с двумя знаками после точки (0 ≤ Ni ≤ 8.95, 1 ≤ i ≤ 6) в случае успешной попытки, либо обозначенные символом «x» (ASCII 120) в противном случае. Все параметры строки разделены пробелами (до 80 пробелов между двумя параметрами). Гарантируется, что в протоколе нет спортсменов с зачетными попытками и равными результатами.

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

В выходной файл OUTPUT.TXT выведите тройку победителей согласно приведенному в примерах формату (лишние пробелы допускаются). Если победителей 1 или 2, следует вывести только их. Спортсменов без зачетных попыток следует проигнорировать. Если невозможно выявить ни одного победителя, то следует вывести «No results.».

Примеры

INPUT.TXTOUTPUT.TXT
18
GER Christian Reif 8.18 x 8.22 8.12 8.12 7.96
RSA Godfrey Mokoena 8.00 7.91 7.87 7.93 8.01 8.10
BRA Mauro Silva x x 8.09 8.05 8.23 8.24
MEX Luis Rivera 7.92 8.16 8.17 8.03 8.27 x
ESP Eusebio Caceres 8.09 8.25 8.17 x 8.26 8.20
RUS Aleksandr Menkov 8.14 7.96 8.52 8.43 8.56 x
JAM Damar Forbes 8.02 7.89 x x 8.00 x
NED Ignisious Gaisah 8.09 8.15 8.17 8.29 x 8.16
1) RUS Aleksandr Menkov 8.56
2) NED Ignisious Gaisah 8.29
3) MEX Luis Rivera 8.27
23
USA John Smith 8.25 8.14 8.01 7.99 7.23 6.92
RUS Evgeny Kuznetsov 8.25 8.14 8.02 7.15 x 6.93
FRA Lucas Martin x x x x x x
1) RUS Evgeny Kuznetsov 8.25
2) USA John Smith 8.25
32
USA Freddy Krueger x x x x x x
RUS Fedya Krukov x x x x x x
No results.

Задача F. Игра в зачеркивание

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

Бумажная полоска разделена на N клеток. Двое играющих по очереди выбирают и зачёркивают ровно K пустых смежных клеток. Выигрывает сделавший последний ход. Оба игрока придерживаются правильной стратегии. Дана ситуация игры. Требуется определить, кто выиграет.

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

Первая строка входного файла INPUT.TXT содержит числа N и K (1 ≤ K ≤ N ≤ 40), во второй строке записаны N символов: английская заглавная O – пустая клетка, английская заглавная X – зачёркнутая клетка.

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

В выходной файл OUTPUT.TXT выведите одно число: 1, если выиграет первый, сделавший ход; 2, если выиграет второй; 0, если ход сделать нельзя (ничья).

Примеры

INPUT.TXTOUTPUT.TXT
14 2
OOOO
1
25 2
OOOOO
2
37 2
OXXOXXO
0

Задача G. Угадай число

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

Это интерактивная задача.

Программа жюри загадывает целое число N (1 ≤ N ≤ 109), которое ваша программа должна будет отгадать не более чем за 100 попыток. Вы можете делать запросы путем вывода числа из возможного диапазона целых чисел. В ответ на каждый запрос программа жюри будет сообщать результат сравнения загаданного числа с числом в запросе.

Протокол взаимодействия

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

< : загаданное число строго меньше числа в запросе (N < X);

> : загаданное число строго больше числа в запросе (N > X);

= : загаданное число совпадает с числом в запросе (N = X), при получении такого ответа ваша программа должна немедленно завершиться.

Ваша программа должна произвести не больше 100 запросов.

Пример

стандартный вводстандартный вывод
1 >
<
<
=
3
10
8
6
 

Примечание

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

  • В языке Pascal: flush(output)
  • В С/С++: fflush(stdout) или cout.flush()
  • В Java: System.out.flush()
  • В Python: sys.stdout.flush() из библиотеки sys
  • В C# и Basic: Console.Out.Flush()

Задача H. Доказательство теоремы

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

Преподаватель читает курс лекций, в рамках которого обычно доказывается N различных теорем. Некоторые теоремы могут ссылаться в доказательстве друг на друга. Более точно, каждая теорема Ti зависит от некоторого набора из Ci других теорем; доказать ее можно лишь доказав не менее половины теорем из данного набора. При этом структура курса такова, что нет такой теоремы, от которой зависели бы две или более различных теоремы, а также нет цепочки теорем (Ti1,Ti2, . . . , Tis) такой, что Ti1 зависит от Ti2, Ti2 зависит от Ti3, …, Tis−1 зависит от Tis, а Tis – от Ti1.

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

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

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

В первой строке входного файла INPUT.TXT записано число N (1 ≤ N ≤ 10 000) – количество теорем. Каждая из следующих N строк описывает теоремы, от которых зависит Ti−1, где i – номер этой строки во входном файле. Эти строки имеют вид Ai,1 Ai,2 ... Ai,Ci 0; здесь Ai,j – номер теоремы, от которой зависит Ti−1. Среди всех чисел Ai,j во входном файле нет двух одинаковых. Основная теорема имеет номер 1. Все числа во входном файле целые.

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

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

Примеры

INPUT.TXTOUTPUT.TXT
12
2 0
0
2
2
1
26
2 3 6 0
4 0
0
0
0
5 0
4
4
3
2
1
33
0
1 0
2 0
1
1


Красноярский краевой Дворец пионеров, (c)2006 - 2017, ICQ: 151483