» » Технокубок: итоги финального раунда и разбор задач

 

Технокубок: итоги финального раунда и разбор задач

Автор: admin от 30-03-2017, 16:10, посмотрело: 268

Технокубок: итоги финального раунда и разбор задач


Пятого марта прошел финальный раунд Технокубка — олимпиады по программированию для школьников. В этом году в ней приняли участие 3000 человек, 400 из которых прошли в финал. Предлагаем вам взглянуть итоги финала и разбор задач:


A. Андрюша и носки
B. Место встречи изменить нельзя
C. Андрюша и разноцветные шарики
D. Иннокентий и футбольная лига
E. Подземная лаборатория
F. Аксель и Марстон в Битландии
G. Андрюша и живые барьеры
H. Автобусы и интранет


Что такое Технокубок? Это олимпиада по программированию для учащихся 8-11 классов, организуемая Mail.Ru Group совместно с МГТУ им. Баумана и МФТИ. Она состоит из трех этапов: ознакомительного (онлайн), отборочного (онлайн) и заключительного (очно).


Ознакомительные раунды — онлайн-раунды для знакомства с платформой Codeforces. На них предлагается решить по две простые задачи, чтобы разобраться в системе. Такие раунды проводятся перед каждым отборочным. Их результаты не влияют на итоговый рейтинг в олимпиадной сетке.


Отборочные раунды — онлайн-раунды на платформе Codeforces. По результатам на них лучшие программисты попадают в финал. На таких раундах предлагается решить по шесть задач. Чтобы попасть в заключительный этап, необходимо пройти отбор хотя бы в одном из таких раундов.


Заключительный раунд — очный этап олимпиады. Он проходит в Москве в марте 2017 года на базе МФТИ и МГТУ им. Баумана. Участникам предлагается решить задачи на компьютерах на платформе Codeforces.


Награждение. В 2017 году победители и призеры Технокубка получают при поступлении в вузы льготы олимпиады третьего уровня, особые условия при поступлении в МФТИ и МГТУ им. Баумана.


Все участники очного этапа получают памятные призы. Обычно это футболки с логотипом чемпионата. Для первых трех мест также предусмотрен ценный приз в виде техники Apple, а победителя ждет Технокубок. Награждение победителей проходит в офисе Mail.Ru Group, где ребята могут пообщаться с разработчиками и увидеть их рабочие места.


Технокубок: итоги финального раунда и разбор задач


Победители Технокубка 2017


В 2017-ом году победу в Технокубке одержала Александра Дроздова, г. Москва, ученица 11 класса СУНЦ МГУ, занявшая второе место годом ранее. На второй строчке в списке лидеров оказался Артур Петуховский, г. Витебск, а на третьей — Владимир Романов, г. Москва. Полную версию результатов можно посмотреть здесь. Поздравляем победителей!


Технокубок: итоги финального раунда и разбор задач


Разбор задач финального раунда


Участникам финала предложили решить 8 задач за 3 часа. Тройке лидеров удалось справиться с семью из них. Еще 17 человек одолели по 6 задач, а с 5 задачами справились 32 человека.


Технокубок: итоги финального раунда и разбор задач


A. Андрюша и носки


Ограничение по времени на тест — 2 секунды
Ограничение по памяти на тест — 256 мегабайт
Ввод — стандартный ввод
Вывод — стандартный вывод


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


Сегодня перед ним встала нелегкая задача — сложить в шкаф носки. У Андрюши есть n разных пар носков, которые изначально сложены в мешок. Пары носков пронумерованы от 1 до n. Андрюша хочет убрать носки в шкаф по парам. Для этого он по одному достает носки из мешка, и для каждого вытащенного носка смотрит, доставал ли он уже его пару. Если нет, что значит, что пара текущего носка все еще находится в мешке, то Андрюша кладет текущий носок на стол перед собой. Иначе он убирает текущий носок и его пару в шкаф.


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


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


В первой строке находится единственное целое число n (1 <= n <= 105) — число пар носков.


Во второй строке через пробел перечислены 2n чисел x1, x2, ..., x2n (1 <= xi <= n), которые описывают, в каком порядке Андрюша доставал носки из мешка. А именно, число xi означает, что i-м по порядку Андрюша достал носок из пары xi.


Гарантируется, что Андрюша достал ровно два носка из каждой пары.


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


В единственной строке выведите одно число — максимальное число носков, которые когда-либо лежали на столе перед Андрюшей.


Примеры


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


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


Входные данные
3
2 1 1 3 2 3


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


Примечание


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


Рассмотрим, что происходит во втором примере:



  • Сначала на столе ничего нет, Андрюша достает носок из пары номер 2.

  • На столе лежит носок (2). Андрюша достает носок из пары номер 1 и кладет его на стол.

  • На столе лежат носки (1, 2). Андрюша достает носок из пары номер 1, но такой носок уже есть на столе. Поэтому Андрюша убирает оба носка в шкаф.

  • На столе лежит носок (2). Андрюша достает носок из пары номер 3 и кладет его на стол.

  • На столе лежат носки (2, 3). Андрюша достает носок из пары номер 2, но такой носок уже есть на столе. Поэтому Андрюша убирает оба носка в шкаф.

  • На столе лежит носок (3). Андрюша достает носок из пары номер 3, но такой носок уже есть на столе. Поэтому Андрюша убирает оба носка в шкаф.


Таким образом, на столе единовременно лежало максимум два носка.



B. Место встречи изменить нельзя


Ограничение по времени на тест — 5 секунд
Ограничение по памяти на тест — 256 мегабайт
Ввод — стандартный ввод
Вывод — стандартный вывод


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


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


Перед вами стоит задача определить минимальное время, за которое все n друзей смогут встретиться в одной точке на главной улице. Обратите внимание, что точка, в которой встретятся друзья, не обязана иметь целочисленную координату.


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


В первой строке находится единственное целое число n (2 <= n <= 60 000) — количество друзей.


Во второй строке находятся n целых чисел x1, x2, ..., xn (1 <= xi <= 109) — текущие координаты друзей в метрах.


В третьей строке находятся n целых чисел v1, v2, ..., vn (1 <= vi <= 109) — максимальные скорости друзей в метрах в секунду.


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


Выведите минимальное время (в секундах), за которое все n человек смогут встретиться в одной точке.


Ваш ответ будет считаться правильным, если его абсолютная или относительная погрешность не превышает 10 - 6. Формально, пусть ваш ответ равен a, а ответ жюри — b. Ваш ответ будет считаться правильным, если Технокубок: итоги финального раунда и разбор задач.


Примеры


Входные данные
3
7 1 3
1 2 1


Выходные данные
2.000000000000
Входные данные
4
5 10 3 2
2 3 2 4


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


Примечание


В первом примере все друзья могут встретиться в точке 5 через 2 секунды. Для этого первый друг должен идти все время со своей максимальной скоростью на юг, а второй и третий должны идти со своими максимальными скоростями на север.



C. Андрюша и разноцветные шарики


Ограничение по времени на тест — 2 секунды
Ограничение по памяти на тест — 256 мегабайт
Ввод — стандартный ввод
Вывод — стандартный вывод


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


Парк состоит из n полянок, которые соединены между собой (n - 1) двусторонними дорожками, причем от каждой полянки можно дойти по дорожкам до любой другой.


Андрюша решил на каждой полянке повесить один цветной шарик. Цвета шариков задаются целыми положительными числами, начиная с 1. Чтобы парк стал более разнообразным, Андрюша решил выбирать цвета шариков по-особенному. А именно, он хочет развесить шарики так, чтобы для любых трех попарно различных полянок a, b и c таких, что a и b соединены дорожкой, и b и c соединены дорожкой, цвета шариков на этих полянках были попарно различными.


Чтобы не тратить много денег на покупку шариков, Андрюша хочет использовать как можно меньше различных цветов. Так как Андрюша не очень силен в программировании, он просит вас помочь ему решить эту задачу.


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


В первой строке находится одно целое число n (3 <= n <= 2•105) — число полянок в парке.


В каждой из следующих (n - 1) строк находятся два целых числа x и y (1 <= x, y <= n) — номера двух полянок, соединенных очередной дорожкой.


Гарантируется, что от любой полянки можно добраться до любой другой по дорожкам.


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


В первой строке выведите одно целое число k — минимальное количество цветов, которое необходимо использовать Андрюше.


Во второй строке выведите n целых чисел, i-е из которых равняется цвету шарика, который нужно повесить на i-й полянке. Каждое из чисел должно быть в пределах от 1 до k.


Примеры


Входные данные
3
2 3
1 3


Выходные данные
3
1 3 2


Входные данные
5
2 3
5 3
4 3
1 3


Выходные данные
5
1 3 2 5 4


Входные данные
5
2 1
3 2
4 3
5 4


Выходные данные
3
1 2 3 1 2


Примечание


В первом примере из условия парк состоит из трех полянок, которые последовательно соединены: 1 -> 3 -> 2. Значит, цвета шариков на каждой полянке должны быть попарно различны.


Технокубок: итоги финального раунда и разбор задач
Иллюстрация к первому примеру


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



  • 1 -> 3 -> 2

  • 1 -> 3 -> 4

  • 1 -> 3 -> 5

  • 2 -> 3 -> 4

  • 2 -> 3 -> 5

  • 4 -> 3 -> 5


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


Технокубок: итоги финального раунда и разбор задач
Иллюстрация ко второму примеру


В третьем примере есть следующие тройки:



  • 1 -> 2 -> 3

  • 2 -> 3 -> 4

  • 3 -> 4 -> 5


Это значит, что одного или двух цветов недостаточно, а для трех цветов ответ существует и приведен в примере.


Технокубок: итоги финального раунда и разбор задач
Иллюстрация к третьему примеру



D. Иннокентий и футбольная лига


Ограничение по времени на тест — 2 секунды
Ограничение по памяти на тест — 256 мегабайт
Ввод — стандартный ввод
Вывод — стандартный вывод


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


Название каждого клуба состоит из двух слов: названия команды и города, в котором располагается клуб, например, «DINAMO BYTECITY». Иннокентий не хочет сильно искажать название, поэтому он хочет выбрать сокращенное название для каждого из клубов таким образом, чтобы:


1) либо сокращенное название клуба совпадало с первыми тремя буквами названия команды, например, для вышеприведенный команды это «DIN»,
2) либо первые две буквы сокращенного названия клуба совпадали с первыми двумя буквами названия команды, а третья — с первой буквой города команды. Например, для вышеприведенный команды это «DIB».


Кроме этого, если для какой-то команды x выбран второй вариант названия, то не должно быть команды, у которой выбран первый вариант сокращенного названия, совпадающий с первым вариантом названия команды x. Например, если сокращенное название вышеприведенной команды это «DIB», то никакая команда, у которой выбран первый вариант сокращенного названия, не должна иметь сокращенного названия «DIN». При этом возможно, что какая-то команда получит название «DIN», где «DI» — первые две буквы названия команды, а «N» — первая буква города. Конечно, никакие две команды не должны иметь одинакового сокращенного названия.


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


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


В первой строке находится единственное целое число n (1 <= n <= 1000) — число футбольных клубов в лиге.


В каждой из следующих n строк находятся два слова — название команды и название города очередного клуба. И название команды, и название города состоят из заглавных букв латинского алфавита и имеют длину не менее 3 и не более 20.


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


Если выбрать сокращенные названия, удовлетворив требованиям Иннокентия, невозможно, выведите единственную строку «NO».


Иначе в первую строку выведите «YES». Далее выведите n строк, в каждой строке выведите выведите сокращенное название очередного клуба. Выводите клубы в том же порядке, в каком они заданы во входных данных.


Если возможных ответов несколько, выведите любой.


Примеры


Входные данные
2
DINAMO BYTECITY
FOOTBALL MOSCOW


Выходные данные
YES
DIN
FOO


Входные данные
2
DINAMO BYTECITY
DINAMO BITECITY


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


Входные данные
3
PLAYFOOTBALL MOSCOW
PLAYVOLLEYBALL SPB
GOGO TECHNOCUP


Выходные данные
YES
PLM
PLS
GOG


Входные данные
3
ABC DEF
ABC EFG
ABD OOO


Выходные данные
YES
ABD
ABE
ABO


Примечание


В первом примере можно выбрать первый вариант названия для обеих команд.


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


В третьем примере можно выбрать вторые варианты названий у первых двух команд, и первый вариант — у третьей команды.


В четвертом примере обратите внимание на то, что разрешается, чтобы выбранное название некоторой команды x совпадало с первым вариантом названия y, если первый вариант названия x не совпадает с первым вариантом названия y.



E. Подземная лаборатория


Ограничение по времени на тест — 1 секунда
Ограничение по памяти на тест — 256 мегабайт
Ввод — стандартный ввод
Вывод — стандартный вывод


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


Лаборатория представляет собой связный граф из n вершин и m ребер. В некоторых вершинах этого графа k клонов Андрюши начинают поиск выхода из лаборатории. В процессе поиска каждую секунду они переходят по ребру в соседнюю вершину, причем в каждой вершине может одновременно находиться сколько угодно клонов. Каждый клон может в некоторый момент времени остановиться и прекратить поиски, но он обязательно должен их начать, то есть посетить хотя бы одну вершину. Более того, выход может находиться в произвольном месте лаборатории, поэтому клоны должны обойти граф целиком, то есть каждая вершина графа должна быть посещена хотя бы одним клоном хотя бы один раз.


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


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


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


В первой строке находятся три целых числа n, m и k (1 <= n <= 2•105, n - 1 <= m <= 2•105, 1 <= k <= n) — число вершин в графе, число ребер в графе и количество клонов.


В каждой из следующих m строк находятся два целых числа xi и yi (1 <= xi, yi <= n) — номера двух вершин, соединенных очередным ребром. В графе могут быть петли и кратные ребра.


Гарантируется, что граф связный.


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


Выведите k строк. В начале i-й строки выведите целое число ci (Технокубок: итоги финального раунда и разбор задач) — количество вершин, которые посетит i-й клон, а затем выведите ci целых чисел — номера вершин, которые он посетит, в порядке их посещения. Выводите вершину каждый раз, когда клон ее посещает, даже если он посещал ее до этого.


Гарантируется, что ответ существует.


Примеры


Входные данные
3 2 1
2 1
3 1


Выходные данные
3 2 1 3


Входные данные
5 4 2
1 2
1 3
1 4
1 5


Выходные данные
3 2 1 3
3 4 1 5


Примечание


В первом тесте есть всего 1 клон, он посещает вершины в порядке (2, 1, 3), что укладывается в ограничение 6 посещенных вершин.


Во втором тесте есть 2 клона, они посещают вершины в порядке (2, 1, 3) и (4, 1, 5), что укладывается в ограничение 5 посещенных вершин.



F. Аксель и Марстон в Битландии


Ограничение по времени на тест — 5 секунд
Ограничение по памяти на тест — 256 мегабайт
Ввод — стандартный ввод
Вывод — стандартный вывод


Два друга Аксель и Марстон вместе путешествуют по Битландии. В Битландии n городов, некоторые пары из которых соединены однонаправленными дорогами. Дороги в Битландии бывают пешеходные и велосипедные. В Битландии может быть несколько дорог между каждой парой городов, и бывают даже дороги из города в него же. Однако, никакие две дороги в Битландии не могут иметь одинаковые начало, конец и тип одновременно.


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



  • Маршрут начинается с пешеходной дороги.

  • Пусть известное начало маршрута записано в виде строки s из букв П (пешеходная дорога) и В (велосипедная дорога). Тогда к маршруту s дописывается строка Технокубок: итоги финального раунда и разбор задач, где Технокубок: итоги финального раунда и разбор задач означает строку s, в которой тип каждой дороги заменен на противоположный (все пешеходные дороги на велосипедные, и наоборот).


Первые несколько шагов построения маршрута будут выглядеть так: П, ПВ, ПВВП, ПВВПВППВ, ПВВПВППВВППВПВВП, и так далее.


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


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


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


Первая строка содержит два целых числа n и m (1 <= n <= 500, 0 <= m <= 2n2) — количество городов и дорог в Битландии соответственно. Следующие m строк описывают дороги. В i-ой из этих строк записано три целых числа vi, ui и ti (1 <= vi, ui <= n, 0 <= ti <= 1), где vi и ui — номера городов, являющихся началом и концом i-ой дороги, а ti задает тип i-ой дороги (0 — пешеходная дорога, 1 — велосипедная дорога). Гарантируется, что для каждой пары различных чисел i, j, таких что 1 <= i, j <= m, либо vi? vj, либо ui ? uj, либо ti ? tj.


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


Если друзья могут найти подходящий путь длины строго большей, чем 1018, выведите одно число -1. В противном случае выведите максимальную длину подходящего пути, то есть наибольшее количество дорог, которое могут пройти друзья.


Примеры


Входные данные
2 2
1 2 0
2 2 1


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


Входные данные
2 3
1 2 0
2 2 1
2 2 0


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


Примечание


В первом примере путь длины 3 можно получить, пройдя один раз по дороге 1 из города 1 в город 2, после чего дважды по дороге 2 из города 2 в него же.


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



G. Андрюша и живые барьеры


Ограничение по времени на тест — 4 секунды
Ограничение по памяти на тест — 256 мегабайт
Ввод — стандартный ввод
Вывод — стандартный вывод


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


Кроме того, в некоторых строках автомата были расположены перегородки. Всего перегородок было n, и i-я из них располагалась в строке ui, занимая все клетки в столбцах с li по ri. Никакие две перегородки не находились в одной строке, Андрюша это точно запомнил. Кроме того, в каждой строке была хотя бы одна клетка, в которой не было перегородки.


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


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


Особенность автомата была в том, что иногда шарики проходили сквозь перегородки, как через свободные клетки. Это связано с тем, что перегородки были живыми и боялись шариков, падающих с большой высоты. А именно, если на перегородку номер i падал шарик, который перед этим падал более, чем si клеток (то есть шарик появился в строке с номером строго больше, чем ui + si), то перегородка пропускает этот шарик, как будто ее нет. Если шарик был брошен в автомат сверху, считайте, что он появился на высоте (h + 1).


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


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


В первой строке находятся три целых числа h, w и n (1 <= h <= 109, 2 <= w <= 105, 0 <= n <= 105) — число строк, число столбцов и число перегородок в автомате.


В каждая из следующих n строк находятся четыре целых числа. В i-й из этих строк находятся числа ui, li, ri, si (1 <= ui <= h, 1 <= li <= ri <= w, 1 <= si <= 109) — строка, в которой находится i-я перегородка. Столбцы, в которых находятся края этой перегородки, и максимальная высота, с которой перегородка не пропускает шарики. Гарантируется, что в каждой строке есть хотя бы одна клетка, в которой нет перегородки, а также то, что все ui различны.


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


Выведите единственное число — остаток от деления суммарного числа выпавших шариков на 109 + 7.


Примеры


входные данные
10 5 1
3 2 3 10


выходные данные
7


входные данные
10 5 2
3 1 3 10
5 3 5 10


выходные данные
16


входные данные
10 5 2
3 1 3 7
5 3 5 10


выходные данные
14


входные данные
10 15 4
7 3 9 5
6 4 10 1
1 1 4 10
4 11 11 20


выходные данные
53


Примечание


В первом примере один барьер: если бросить шарик во второй или третий столбец, то выпадет два шарика, иначе — один. Итого ответ 7.


Во втором примере количество выпавших шариков равно 2, 2, 4, 4, 4 при бросании шариков в столбцы слева направо соответственно.


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


В четвертом примере количество выпавших шариков равно 2, 2, 6, 6, 6, 6, 6, 6, 6, 1, 2, 1, 1, 1, 1 при бросании шариков в столбцы слева направо соответственно. Случай, когда шарик брошен в седьмой столбец, рассмотрен на рисунке ниже.



H. Автобусы и интранет


Ограничение по времени на тест — 10 секунд
Ограничение по памяти на тест — 256 мегабайт
Ввод — стандартный ввод
Вывод — стандартный вывод


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


Автобусы начинают движение по маршруту в первой вершине ломаной с равными промежутками. Пусть T — это время, за которое один автобус проезжает по кругу весь маршрут. Тогда автобус 1 начинает движение в момент времени 0, автобус 2 — в момент времени T / m, третий — в момент времени 2T / m, и т.д.; наконец, автобус m стартует в момент (m - 1)T / m. Таким образом, интервалы между всеми парами соседних автобусов (в том числе, между последним и первым) одинаковы.


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


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


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


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


В первой строке записано два целых числа n и m (2 <= n, m <= 105) — количество вершин ломаной и количество автобусов соответственно.


Следующие n строк описывают вершины ломаной в порядке ее обхода. Каждая из этих строк содержит два целых числа xi, yi( - 1000 <= xi, yi <= 1000) — координаты очередной вершины.


Гарантируется, что каждое звено ломаной (в том числе, между последней и первой вершиной) параллельно одной из осей координат. Кроме этого, никакие две последовательные вершины ломаной не совпадают. Ломаная может иметь самопересечения и проходить по одному отрезку несколько раз.


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


Выведите одно вещественное число — ответ на задачу. Ответ будет принят, если абсолютная или относительная погрешность не превосходит 10- 6.


Примеры


входные данные
4 2
0 0
0 1
1 1
1 0
выходные данные
1.000000000
входные данные
2 2
0 0
1 0
выходные данные
0.000000000


Примечание


Пусть все автобусы проезжают 1 единицу расстояния в секунду. В первом примере, через 0.5 секунды автобусы окажутся на расстоянии 1, поэтому можно выбрать D = 1.


Во втором примере, через 0.5 секунды оба автобуса окажутся в точке (0.5, 0), поэтому можно выбрать D = 0.


Технокубок: итоги финального раунда и разбор задач
Результат, если бросить шарик в седьмой столбец




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



Источник: Хабрахабр

Категория: Программирование

Уважаемый посетитель, Вы зашли на сайт как незарегистрированный пользователь.
Мы рекомендуем Вам зарегистрироваться либо войти на сайт под своим именем.

Добавление комментария

Имя:*
E-Mail:
Комментарий:
Полужирный Наклонный текст Подчеркнутый текст Зачеркнутый текст | Выравнивание по левому краю По центру Выравнивание по правому краю | Вставка смайликов Выбор цвета | Скрытый текст Вставка цитаты Преобразовать выбранный текст из транслитерации в кириллицу Вставка спойлера
Введите два слова, показанных на изображении: *