XXIII Городская олимпиада школьников г. Петрозаводска по информатике - Условия

A. Письма счастья

Имя входного файла:	letters.in
Имя выходного файла:	letters.out
Ограничение по времени:	2 s
Ограничение по памяти:	256 megabytes

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

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

Помогите Васе написать программу, решающую поставленную задачу.

Формат входного файла

В первой строке входного файла находятся два числа n и m (1 ≤ n ≤ 10⁵, 0 ≤ m ≤ 10⁵) – количество пользователей в социальной сети и количество отправленных сообщений. Следующие m строк содержат по два положительных числа a_i, b_i (1 ≤ a_i, b_i ≤ n) – идентификаторы отправителя и адресата.

Формат выходного файла

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

Пример:

letters.in	letters.out
6 5 1 2 2 1 2 4 3 5 4 3	3
3 3 1 2 2 3 3 1	0

Примечание: в первом примере ``несчастливые'' пользователи имеют идентификаторы 1, 5 и 6.

Источник: XXIII Городская олимпиада школьников г. Петрозаводска по информатике
Автор: Денис Власов

Обсудить Отправить решение

B. Теплый шарф

Имя входного файла:	scarf.in
Имя выходного файла:	scarf.out
Ограничение по времени:	1 s
Ограничение по памяти:	256 megabytes

Малыш Илюша очень любит тепло одеваться. Так получилось, что сегодня у него День рождения и мама подарила ему тёплый шарф длиной K сантиметров и толщиной d cантиметров. Теперь Илюшу очень интересует вопрос: какое максимальное число раз он сможет полностью обмотать шарф вокруг своей шеи, представляющей из себя окружность радиуса R сантиметров, и какой длины останется не намотанная часть.

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

Формат входного файла

Входной файл состоит из одной строки, содержащей три вещественных числа, разделённых пробелами: K, d, R (1 ≤ K ≤ 10¹³, 0.000001 ≤ d ≤ 10⁶, 1 ≤ R ≤ 10⁶) – длина шарфа, толщина шарфа и радиус шеи. Все размеры даны в сантиметрах и имеют не более чем 6 знаков после запятой.

Формат выходного файла

В выходной файл выведите два числа разделённых пробелом – максимальное число полных оборотов шарфа вокруг шеи и длину остатка шарфа в сантиметрах c точностью не менее 8 знаков после запятой. Ваш ответ будет признан правильным, если относительная или абсолютная погрешность не превышает 10^-6.

Пример:

scarf.in	scarf.out
110 1 13	1 22.0354056995
10 0.001 1	1 3.7105315075
17.342 0.00342 1.14501	2 2.8889145016
123.456789 0.123456 1.234567	10 3.2233257581
31.415927 2 3	1 0.0000004641

Источник: VI Сетевая районная олимпиада Республики Карелия по информатике. 3 декабря 2011 г. XXIII Городская олимпиада школьников г. Петрозаводска по информатике
Автор: Владимир Басунков

Обсудить Отправить решение

C. Мониторы

Имя входного файла:	monitors.in
Имя выходного файла:	monitors.out
Ограничение по времени:	2 s
Ограничение по памяти:	256 megabytes

Чёрный Кот подрабатывает созданием сайтов на заказ. Одной из необходимых операций для создания сайта является вёрстка макета – когда макет дизайна, нарисованный в графическом редакторе, переводят в HTML, чтобы потом на основе этого HTML-документа создать шаблон для системы управления содержимым сайта.

Конечно, при вёрстке HTML-шаблона, Кот проверяет правильность его отображения в различных условиях: в разных браузерах, с разным разрешением экрана и т.п. Обычно всё проходит достаточно гладко, однако в этот раз заказчик хочет, чтобы сайт корректно отображался на очень широких мониторах (более 2000 пикселов по горизонтали). Однако у Кота нет такого широкого монитора и казалось бы, он не сможет протестировать сайт. Но Кот не был бы Котом, если бы не придумал решение. Он понял, что если подключить к компьютеру несколько мониторов и расположить их по горизонтали, можно получить достаточно широкий виртуальный экран, на котором уже можно будет протестировать сайт. Кот выписал разрешения всех мониторов, которые есть у него и его друзей и теперь хочет узнать, какое же максимальное разрешение по горизонтали он может получить, используя эти мониторы.

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

Формат входного файла

В первой строке входного файла находится единственное число N – количество мониторов, имеющихся у Кота и его друзей (1 ≤ N ≤ 100000). Далее в N строках следует по два числа w_i, h_i – разрешение очередного монитора по горизонтали и вертикали соответственно (1 ≤ w_i, h_i ≤ 10⁹).

Формат выходного файла

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

Пример:

monitors.in	monitors.out
3 1024 768 1024 768 1600 1200	2048
4 1024 768 1024 768 1600 1200 1600 1200	3200
3 640 480 800 600 400 768	800

Примечание: в первом примере Коту следует объединить два первых монитора. Третий монитор добавить к ним нельзя, поскольку у него другое разрешение по вертикали. Во втором примере можно объединить либо два первых монитора, либо два последних. Два последних объединить выгоднее. В третьем примере никакие два монитора объединить нельзя – Коту придётся просто использовать самый широкий монитор.

Источник: VI Сетевая районная олимпиада Республики Карелия по информатике. 3 декабря 2011 г. XXIII Городская олимпиада школьников г. Петрозаводска по информатике
Автор: Денис Денисов

Обсудить Отправить решение

D. Десант

Имя входного файла:	attack.in
Имя выходного файла:	attack.out
Ограничение по времени:	2 s
Ограничение по памяти:	256 megabytes

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

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

Введём в городе декартову прямоугольную систему координат. Тогда место высадки захватчиков и положения пилонов города можно обозначить парой целых чисел (x, y) – координатами в этой системе. Расстояние между точками (x₁, y₁) и (x₂, y₂) определяется как сумма модулей разности соответствующих координат (|x₁ - x₂| + |y₁ - y₂|).

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

Изначально нет работающих пилонов.

Формат входного файла

В первой строке входного файла находится число q (1 ≤ q ≤ 100000) – количество изменений в системе пилонов города. Следующие q строк содержат по три целых числа t, x, y (-10⁹ ≤ x, y ≤ 10⁹) – тип изменения и координаты точки нового пилона. Если t равно 1, то это значит, что пилон с координатами в точке (x, y) введен в эксплуатацию. Если t равно -1, то это значит, что пилон с коодинатами в точке (x, y) вышел из строя. Гарантируется, что перед тем, как пилон вышел из строя, он работал. Никакие два работающих пилона не будут находиться в одной точке. Гарантируется, что после каждого действия существует хотя бы один рабочий пилон.

Формат выходного файла

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

Пример:

attack.in	attack.out
3 1 1 1 1 1 2 -1 1 1	1 1 1 1 1 2
10 1 -6 3 1 10 -6 -1 10 -6 1 -10 4 1 4 -10 1 -2 7 1 -9 -1 1 -8 -3 1 2 9 1 -5 -7	-6 3 -6 -6 -6 3 -10 3 -6 3 -6 3 -6 3 -8 -1 -6 3 -6 -1

Источник: XXIII Городская олимпиада школьников г. Петрозаводска по информатике
Автор: Никита Иоффе

Обсудить Отправить решение

E. Топливо

Имя входного файла:	fuel.in
Имя выходного файла:	fuel.out
Ограничение по времени:	2 s
Ограничение по памяти:	256 megabytes

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

Пилл Баучер, председатель Ассоциации СуперМотоциклистов (далее – АСМ), стремясь прояснить ситуацию, немедленно обзвонил своих знакомых и выяснил числа f_i – имеющиеся количества топлива на каждой из n городских заправочных станций супермотоциклов (1 ≤ i ≤ n). Числа f_i измеряются в количествах полных баков. Расположение станций позволило Пиллу установить c_i – количество участников АСМ, которые с утра, ещё до открытия, займут очередь за топливом у станции с номером 1 ≤ i ≤ n.

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

Формирование групп происходит по следующим правилам:

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

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

Формат входного файла

Во входном файле в первой строке содержится одно целое число n – количество заправок (1 ≤ n ≤ 10⁵). Во второй строке содержится n чисел f_i, которые указывают начальные количества баков топлива на каждой заправке (1 ≤ f_i ≤ 10⁹). В третьей строке содержится n чисел c_i – первоначальное количество человек в очереди к каждой заправке (1 ≤ c_i ≤ 10⁹).

Информация о списках ближайших заправок занимает n строк, каждая из которых содержит целое число – количество ближайших заправок, за которым следуют номера ближайших заправок в порядке возрастания расстояния. Гарантируется, что суммарное количество заправок во всех списках не превосходит 10⁵.

Формат выходного файла

Выходной файл должен содержать n строк. В i–той из них должно быть записано единственное целое число – момент закрытия заправки с номером i.

Пример:

fuel.in	fuel.out
5 7 10 7 8 6 4 6 6 1 5 1 2 2 5 4 0 2 2 3 2 2 3	1 1 1 2 1
4 1 1 1 1 1 1 1 1 1 2 3 1 3 4 1 2 1 2	1 1 1 1
4 1 4 1 1 1 1 1 1 1 2 3 1 3 4 1 2 1 2	1 2 1 1
4 1 5 1 1 1 1 1 1 1 2 3 1 3 4 1 2 1 2	1 2 1 1
4 1 20 1 1 2 3 2 2 1 2 3 1 3 4 1 2 1 2	0 2 0 0

Источник: XXIII Городская олимпиада школьников г. Петрозаводска по информатике
Автор: Денис Денисов

Обсудить Отправить решение