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

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

HotLog


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

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

Задача A. Портрет

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

У вас есть два портрета, выполненных в виде круга радиуса R. И большой набор круглых рам для таких портретов.

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

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

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

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

В выходной файл OUTPUT.TXT выведите найденный радиус рам. Если двух подходящих рам с одинаковым радиусом не найдется, следует вывести 0.

Примеры

INPUT.TXTOUTPUT.TXT
115 8
21 5 34 12 4 5 78 12
12
215 8
21 5 34 12 4 6 21 14
0

Задача B. Фатализм

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

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

Прайм создает лабиринт размера m×n клеток, огороженный со всех сторон стенами. Каждая клетка лабиринта – либо свободное пространство, либо стена. В начальный момент времени в некоторых клетках, где нет стены, стоят роботы и смотрят в одном из четырех направлений. Никакие два робота не стоят в одной клетке.

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

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

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

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

В первой строке входного файла INPUT.TXT заданы через пробел три числа m, n и k (1 ≤ m, n, k ≤ 100). В следующих n строках содержится ровно по m символов в каждой: i-ый символ в j-ой из этих строк равен «X» (икс большое), если соответствующая клетка (i, j) занята стеной, и «.» (точка), если эта клетка пуста. Далее идут k строк, описывающие роботов. Каждая из них имеет вид (xi,yi,zi), где xi и yi – координаты робота (1 ≤ xi ≤ m, 1 ≤ yi ≤ n), а zi – один из четырех символов направления: символ «U» (up) соответствует уменьшению координаты y, символ «L» (left) – уменьшению координаты x, символ «D» (down) – увеличению y, а символ «R» (right) – увеличению x. Все числа во входном файле целые.

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

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

Примеры

INPUT.TXTOUTPUT.TXT
15 1 2
X...X
3 1 L
4 1 R
2
24 4 4
X..X
....
....
X..X
1 3 R
3 4 U
4 2 L
2 1 D
1
34 5 3
....
....
....
....
....
1 4 R
3 5 U
4 5 U
4
43 6 5
.X.
.X.
.X.
...
...
.X.
1 4 R
2 5 U
3 5 U
1 6 R
3 6 L
5

Задача C. Волна

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

Поле размером N×M клеток заполнено целыми числами. Требуется найти на поле клетку, из которой волна, запущенная не более чем на K итераций, покроет площадь с максимальной суммой расположенных на ней чисел.

Пример распространения волны для поля размером 5 x 4. Волна запущена из клетки (3,3) и была остановлена после трех итераций. Белые клетки – клетки, не покрытые волной, серые и черные – клетки, покрытые волной. Клетки, покрытые волной на последней итерации, отмечены серым цветом.

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

Первая строка входного файла INPUT.TXT содержит натуральные числа N, M и K (N, M ≤ 15, K ≤ N + M). Следующие N строк содержат по M чисел, каждое из которых не превосходит 104 по абсолютной величине.

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

В выходной файл OUTPUT.TXT выведите четыре числа R, C, P и S, где R – номер строки, C – номер столбца, из которых следует запустить волну, P – количество итераций распространения волны, S – максимальная сумма чисел, покрытых волной. Если существует несколько вариантов ответа, вывести тот, в котором число P минимально. Если таких вариантов несколько, вывести вариант, в котором число R минимально, если и таких несколько, вывести вариант, в котором число С минимально.

Пример

INPUT.TXTOUTPUT.TXT
15 4 3
1 2 3 4
1 6 7 8
9 10 11 12
0 0 0 0
2 0 0 1
3 3 3 66

Задача D. Премия

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

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

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

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

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

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

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

Примеры

INPUT.TXTOUTPUT.TXT
128 28002800
230 1015

Задача E. Пирожные

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

Санта Клаус планирует принести подарки на новый год n ребятам. У него есть m пирожных, и он собирается подарить каждому ребенку несколько пирожных. Однако неожиданно возникла проблема. Детям не нравится, когда кому-то достается больше пирожных, чем ему.

Каждый ребенок характеризуется своей жадностью, жадность i-го ребенка равна gi. Если ai ребят получат больше пирожных чем i-й, то его неудовлетворенность будет равна gi∙ai.

Теперь у Санты проблема: надо поделить пирожные между ребятами так, чтобы суммарная неудовлетворенность была минимальна. Каждый ребенок должен получить хотя бы одно пирожное. Санта собирается раздать все m пирожных. Помогите ему распределить их между ребятами!

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

Первая строка входного файла INPUT.TXT содержит числа n и m (1 ≤ n ≤ 30, n ≤ m ≤ 5000). Вторая строка содержит n целых чисел g1, g2, ..., gn (1 ≤ gi ≤ 107).

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

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

Примеры

INPUT.TXTOUTPUT.TXT
13 20
1 2 3
2
2 9 9
24 9
2 1 5 8
7
2 1 3 3

Задача F. Поместье

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

И молвил тогда Король: «Ты храбро сражался, Рыцарь, и твой подвиг не будет забыт в веках. За доблесть твою я дарую тебе сей замок и земли вокруг него. Однако нарушен был тобой строжайший из запретов – все войны видели, как ты сражался без Шляпы на голове подобно дикарям, и их злые духи могли вселиться в тебя. Ты знаешь, что закон предков велит отправлять на небеса души подобных тебе, пока зло, которое могло укорениться в них, не вырвалось наружу. Но в моей воле пощадить тебя, ибо я вижу, что ты достаточно силен чтобы не позволить этому злу проникнуть в мысли и душу твои. Ты должен дать обет три месяца и три дня не покидать своей земли и каждый день три часа после захода солнца молить добрых духов о защите. Дела торопят меня, и не могу я препроводить тебя до замка. Поэтому я дарую тебе и дорогу от этого места до замка. А сейчас иди, и возвращайся по истечении срока.» - так записано в Зеленой Книге Лет.

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

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

Первая строка входного файла INPUT.TXT содержит два вещественных числа xk и yk – координаты места, в котором происходил диалог. Во второй строке записаны три вещественных числа xc, yc и rc – координаты замка и радиус окружности, ограничивающей дарованную вместе с ним землю. Все числа во входном файле по модулю не превосходят 104.

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

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

Пример

INPUT.TXTOUTPUT.TXT
12 5
2 1 1
5.69646

Пояснение

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


Задача G. Шкафчики

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

Тренажерный зал в течение суток планирует принять N клиентов, время прихода и ухода каждого из них определено с точностью до минуты. Находясь в тренажерном зале, клиент занимает один из M шкафчиков для раздевалок. Шкафчики в учреждении нумеруются целыми числами от 1 до M.

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

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

Первая строка входного файла INPUT.TXT содержит целые числа N и M – количество клиентов и шкафчиков соответственно. Каждая из последующих N строк содержит информацию о клиенте: фамилию, время прихода и время ухода, разделенные пробелом. Фамилия содержит от 1 до 10 символов английского алфавита. Время прихода строго меньше времени ухода. Каждое из времен имеет формат ЧЧ:ММ (1 ≤ N, M ≤ 105, 00:00 ≤ ЧЧ:ММ ≤ 23:59).

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

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

Примеры

INPUT.TXTOUTPUT.TXT
15 3
Ivanov 09:00 13:30
Petrov 05:30 10:00
Sidorov 09:30 14:00
Orlov 13:30 16:15
Frolov 13:00 17:00
Ivanov 2
Petrov 1
Sidorov 3
Orlov 2
Frolov 1
22 1
Kuznetsov 09:00 12:00
Bobrov 11:59 13:20
No solution

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

Решения для N ≤ M будут оцениваться в 20 баллов.

Решения для N ≤ 1000 будут оцениваться в 60 баллов.


Задача H. Финал ACM ICPC

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

Ежегодно в Санкт-Петербурге, Барнауле и некоторых городах ближнего зарубежья проходят соревнования по программированию. Эти соревнования проходят в рамках студенческого чемпионата мира по программированию, организованного одной из самых авторитетных ассоциаций ACM (Association for Computing Machinery). На этих соревнованиях проходит отбор команд с Северо-Восточного Европейского Региона NEERC (North-Eastern European Regional Contest).

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

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

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

В первой строке входного файла INPUT.TXT находится три натуральных числа: P – количество команд, принявших участие в полуфинале, N и K (N, K ≤ P ≤ 105).

В следующих P строках, по одному в строке перечислены названия университетов, команды которых заняли соответствующие места. Название университета содержит строчные и прописные английские буквы и пробелы. Длина названия университета не превышает 30 символов. В следующей строке перечислены номера команд соответствующих университетов. Таким образом, если название университета записано в i-ой строке (2 ≤ i ≤ P+1), то эта команда заняла i-1 место на полуфинале и имеет номер, записанный на i-1 месте в P+2 строке.

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

В выходной файл OUTPUT.TXT выведите названия команд, приглашенных к участию в финале чемпионата мира по программированию, упорядоченных по месту, занятому на полуфинале. В качестве названия команды выведите название университета и через пробел «#ID», где ID – номер команды.

Пример

INPUT.TXTOUTPUT.TXT
19 5 2
Fantasy University
Crazy University
Fantasy University
Fantasy University
Very Good U
Good U
Very Good U
Crazy University
Good U
1 1 2 3 2 1 1 2 2
Fantasy University #1
Crazy University #1
Fantasy University #2
Very Good U #2
Good U #1


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