Задачи личного первенства по спортивному программированию

1. Безумство Одиссея

Ограничения: время – 500ms/1000ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Муж тот, о ком ты спросил, - Лаэртид Одиссей многоумный.
Он в каменистой стране, на Итаке на острове вырос,
В хитростях всяких искусный, во всяких решениях мудрый.
$\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \$ Илиада, песнь 3

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

В первой строке ввода указаны два целыых числа: длина строки $L$ , которую нужно придумать ( $1<=L<=10$ ), и количество слов $N$ ( $1<=N<=10$ ). В следущей строке перечислены в алфавитном порядке и без разделителей от 1 до 5 строчных латинских букв, которые можно использовать. Затем идут $N$ строк длиной не более $L$ каждая - слова, которых не должно быть в строке. Слова состоят только из разрешенных букв.

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

Пример ввода 1

5 2
abc
a
bb

Пример вывода 1

bcbcb

Пример ввода 2

10 4
ab
aa
ab
ba
bb

Пример вывода 2

-1

2. Лагерь ахейцев

Ограничения: время – 500ms/2500ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

С той стороны частокол заостренный над ним поднимался, –
Крепкий, высокий, который воздвигли ахейские мужи,
Чтобы служил им надежной защитою против троянцев.
$\ \ \ \ \ \ \ \ \ \ \ \ \ \$ Илиада, песнь 12

Ахейцы, высадившиеся под Троей, окружили свой лагерь стеной из $N$ последовательных участков разной высоты. Афина поведала своему любимцу Одиссею, что вскоре на лагерь нападут $M$ отрядов троянцев, каждый из которых имеет численность $K_i$ и силу $P_i$ . Отряд численностью $K_i$ атакует одновременно $K_i$ подряд идущих участков стены, и если суммарная высота этих участков окажется меньше $P_i$ – троянцы прорвутся в лагерь и сожгут ахейские корабли. Но даже Афина не может заранее предсказать, какие именно участки стены троянцы выберут для атаки. Поэтому Одиссею нужно срочно надстроить стену так, чтобы избежать поражения ахейцев в любом случае. Суммарная высота надстраиваемых частей должна быть минимальной, чтобы Одиссей как можно скорее закончил постройку и вернулся к привычным пирам и состязаниям.

В первой строке ввода указаны два целых числа: длина стены $N$ ( $1<=N<=10^4$ ) и количество атакующих отрядов $M$ ( $1<=M<=10^3$ ). Следующая строка содержит $N$ целых чисел $h_j$ : высоты последовательных участков стены ( $0<=h_j<=10^9$ ). Затем следуют $M$ строк, содержащих описания атакующих отрядов, по два целых числа в каждой: численность отряда $K_i$ ( $1<=K_i<=N$ ) и сила отряда $P_i$ ( $1<=P_i<=10^9$ ).

Выведите единственное целое число – минимальную суммарную высоту надстроек.

Пример ввода

Пример вывода

Пояснение: участки стены после надстройки будут иметь высоты 2, 4, 2, 3, 2. Соответственно, общая высота надстроек равна 1 + 0 + 2 + 2 + 1 = 6.

3. Игра с драхмами

Ограничения: время – 250ms/500ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Золота полуталант он последней назначил наградой.
После того поднялся и слово сказал аргивянам:
Встаньте, кто также и эту награду оспаривать хочет!
Так сказал Ахиллес. И Аякс поднялся Оилеев,
Встал Одиссей многоумный…
$\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \$ Илиада, песнь 23

После гибели Патрокла ахейцы устроили в его честь погребальные игры. В финал состязания по хитроумию вышли Аякс и (кто бы мог подумать) Одиссей.

В состязании используются монеты $N$ различных номиналов. Сначала перед игроками выложено по одной монете каждого номинала, и Одиссей ходит первым. За ход игрок может взять любую монету и разменять её, то есть заменить на произвольное количество монет более мелких номиналов так, чтобы их сумма была равна номиналу взятой монеты. Например, если в игре участвуют монеты в 1, 2 и 5 драхм, то монету в 5 драхм можно разменять на 5 монет по 1 драхме, либо на 1 монету в 2 драхмы и 3 монеты по 1 драхме, либо на 2 монеты по 2 драхмы и 1 монету в 1 драхму. Запас монет для размена не ограничен. Можно использовать любые номиналы из тех, что были доступны в начале игры (даже если в текущий момент соответствующих монет в игре уже нет), и только их. Проигрывает в состязании тот, кто не может сделать ход. Определите, кто из славных героев победит при правильной игре обоих.

В первой строке ввода указано целое число $N$ ( $1 <= N <= 50$ ) – количество номиналов монет, используемых в игре. Во второй строке перечислены в порядке возрастания $N$ натуральных номиналов $C_i$ ( $1 <= C_i <= 10^18$ ). Гарантируется, что минимальный номинал всегда равен 1 драхме, и каждый следующий номинал хотя бы в 2 раза больше предыдущего ( $C_{i+1} >= 2*C_{i}$ ).

Если в состязании победит первый игрок, выведите Ajax, если второй – выведите Odysseus.

Пример ввода 1

1
1

Пример вывода 1

Ajax

Пример ввода 2

3
1 2 5

Пример вывода 2

Odysseus

Пояснение к примеру 1: в начальной позиции нет ходов и Одиссей сразу же проигрывает.

Пояснение к примеру 2: первым ходом Одиссей может разменять монету в 5 драхм на монету в 2 и 3 монеты по 1 драхме. После этого в игре останутся 2 монеты по 2 и 4 монеты по 1 драхме. Аякс своим ходом обязан разменять одну из монет в 2 драхмы на 2 монеты по 1. Одиссей своим ходом разменяет оставшуюся монету в 2 драхмы и победит, т.к. разменивать дальше монеты в 1 драхму нельзя.

4. Троянский конь

Ограничения: время – 500ms/2500ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

С помощью девы Афины построен был конь деревянный,
Как его хитростью ввел Одиссей богоравный в акрополь,
Внутрь поместивши мужей, Илион разоривших священный.
$\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \$ Одиссея, песнь 8

Одиссею пришла в голову отличная идея: спрятать ахейских воинов в огромного деревянного коня, которого защитники Трои сами затащат в город. Главный вопрос: в какой цвет покрасить коня? У каждого из $N$ ахейских вождей есть любимый цвет, заданный в формате $(R_i,G_i,B_i)$ , и авторитет $K_i$ . Если Одиссей покрасит коня в цвет $(R,G,B)$ , а вождь с авторитетом $K_i$ предпочитает цвет $(R_i,G_i,B_i)$ , то возникнет вражда величиной $K * ((R-R_i)^2 + (G-G_i)^2 + (B-B_i)^2)$ . Помогите Одиссею выбрать цвет так, чтобы его суммарная вражда со всеми вождями была как можно меньше. Если есть несколько таких цветов, найдите цвет с минимальной суммой $(R+G+B)$ , ведь всю сэкономленную краску можно будет пустить на украшение собственного корабля героя!

В первой строке ввода содержится одно целое число $N$ – количество вождей $(1<=N<=10^5)$ . Затем следует $N$ строк по четыре целых числа в каждой: авторитет вождя $(1<=K_i<=100)$ и описание его любимого цвета $(0<=R_i,G_i,B_i<=65535)$ .

Выведите три целых числа – компоненты $R,G,B$ цвета, минимизирующего суммарную вражду с вождями. Если возможно несколько ответов, минимизирующих минимальную вражду и сумму $(R+G+B)$ одновременно, выведите любой из них.

Пример ввода

2
4 0 0 10
2 12 9 10

Пример вывода

4 3 10

Пояснение к примеру: суммарная вражда равна $4 * ((4-0)^2+(3-0)^2+(10-10)^2) + 2 * ((4-12)^2+(3-9)^2+(10-10)^2)$ . Можно показать, что для других ответов суммарная вражда будет больше.

5. В стране лотофагов

Ограничения: время – 250ms/500ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Гибели те лотофаги товарищам нашим нисколько
Не замышляли, но дали им лотоса только отведать.
Кто от плода его, меду по сладости равного, вкусит,
Тот уж не хочет ни вести подать о себе, ни вернуться.
$\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \$ Одиссея, песнь 9

Жители страны лотофагов гостеприимно встретили корабль Одиссея и накормили моряков своим любимым кушаньем – лотосами. К сожалению, вкусившие лотосов моряки тут же потеряли разум и забыли, кто они и куда плывут. Хитроумный Одиссей выяснил, что потеря памяти кратковременна: разум вернется через некоторое количество дней, зависящее от того, сколько лотосов съел пострадавший. Обозначим продолжительность безумия $M(N)$ , где $N$ – число съеденных лотосов. Проведя серию опасных экспериментов над собой и окружающими, Одиссей установил ряд соотношений, которым удовлетворяет $M(N)$ :
$M(1) = 1$
$M(3) = 3$
$M(2N) = M(N)$
$M(4N+1) = 2M(2N+1) - M(N)$
$M(4N+3) = 3M(2N+1) - 2M(N)$
Помогите Одиссею определить для каждого из моряков, как скоро он придет в себя.

В единственной строке ввода содержится натуральное число $N$ , не превосходящее $10^18$ .

Выведите одно целое число – значение $M(N)$ . Гарантируется, что $M(N)$ однозначно определена для любого натурального аргумента.

Пример ввода

Пример вывода

6. Пещера Полифема

Ограничения: время – 1s/2s, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Был в этом стаде баран, меж всех остальных наилучший.
За спину взявшись его, соскользнул я барану под брюхо
И на руках там повис…
Хозяин… глупец, не заметил,
Что привязано было под грудью баранов шерстистых.
$\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \$ Одиссея, песнь 9

Сбежать из пещеры циклопа Полифема – нелегкая задача, ведь вход завален огромным камнем. Циклоп убирает камень только для того, чтобы выпустить своих баранов из пещеры на пастбище снаружи. Одиссею пришла в голову отличная идея: пусть каждый из его спутников спрячется под шкурой какого-нибудь из баранов, тогда циклоп их не заметит. Однако, не любой баран подойдет: некоторые из них слишком малы, чтобы скрыть могучего ахейца. Под каждым бараном должно прятаться не больше одного ахейца, и рост каждого ахейца должен быть не больше, чем размер скрывающего его барана. К счастью для Одиссея, в пещере спрятано еще и немного бараньего корма. Если скормить $X$ порций корма барану, то его размер увеличится на $X$ . Порции можно распределять между одним или несколькими баранами как угодно. Помогите Одиссею понять, какое максимальное количество спутников удастся вывести из пещеры благодаря его идее.

В первой строке ввода указаны три целых числа: $N$ – число баранов, $M$ – число ахейцев, $С$ – количество порций корма ( $1<=N,M<=10^5$ , $0<=C<=100$ ). Во второй строке перечислены $N$ целых чисел от 1 до $10^9$ включительно – размеры каждого из баранов. Во второй строке перечислены $M$ целых чисел от 1 до $10^9$ включительно – рост каждого из ахейцев.

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

Пример ввода 1

4 3 1
7 2 2 1
6 6 3

Пример вывода 1

Пример ввода 2

1 3 5
1
10 10 10

Пример вывода 2

Пояснение к первому примеру. Первый или второй ахейцы ростом 6 могут спрятаться под первым бараном размера 7 (но не оба одновременно). Ни под каким другим бараном (даже после откармливания 1 порцией корма) спрятаться они не могут. Второму или третьему барану можно скормить единственную доступную порцию корма, тогда он вырастет от размера 2 до размера 3 и сможет скрыть третьего ахейца.

7. Песня сирен

Ограничения: время – 500ms/1000ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

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

Корабль Одиссея проплывает мимо скал, населенных сладкоголосыми сиренами. Сирены непрерывно и бесконечно поют свою песню, раз за разом повторяя одну и ту же последовательность нот длины $N$ . Несколько звучащих подряд нот могут образовать заклинание длины $M$ , которое лишает разума любого слушателя на время $T$ . То есть, если ноты с номерами от $i-M+1$ до $i$ включительно образуют заклинание, то во время звучания следующих $T$ нот (с $i+1$ по $i+T$ включительно) все гребцы Одиссея бросают весла и корабль не двигается. После окончания действия заклинания гребцы сразу же (в начале звучания ноты с номером $i+T+1$ ) приходят в себя и возвращаются к работе, если только не попадут под действие заклинание снова. Если в момент срабатывания заклинания гребцы уже лишены разума, заклинание все равно действует (см. пример). Чтобы пересечь опасный участок моря, на котором слышно пение сирен, нужно проработать веслами в общей сложности в течение времени $L$ . Определите, сколько времени на это потребуется кораблю Одиссея.

В первой строке ввода указано 4 натуральных числа: число нот в песне $N$ , число нот в заклинании $M$ ( $1<=N,M<=10^5$ ), время действия заклинания $T$ ( $1<=T<=10^10$ ) и необходимое время гребли L ( $1<=L<=10^10$ ). Время измеряется в единицах, равных продолжительности звучания одной ноты. Вторая строка содержит $N$ строчных латинских букв - ноты, содержащиеся в песне сирен. Третья строка содержит $M$ строчных латинских букв - ноты, образующие заклинание.

Выведите единственное целое число – время, которое потребуется кораблю для преодоления опасного участка. Если корабль попадет в плен к сиренам навечно, выведите -1.

Пример ввода 1

3 4 2 8
aab
abaa

Пример вывода 1

Пример ввода 2

3 1 4 4
abc
c

Пример вывода 2

-1

Пояснение к примеру 1. Песня будет звучать так: aabaabaabaabaab… Заклинание впервые сработает в конце 5-й ноты (т.к. символы со 2-го по 5-й равны "abaa"), поэтому в течение 6-й и 7-й нот гребцы бездействуют. Затем на 8-й ноте гребцы снова гребут, а на 9-й и 10-й бездействуют (из-за того, что ноты с 5-й по 8-ую вновь равны "abaa"). Затем заклинание будет срабатывать в конце 11-ой, 14-ой и т.д. нот. Гребцы будут грести в следующие ноты: 1, 2, 3, 4, 5, 8, 11, 14. В конце 14-ой ноты накопленная продолжительность гребли достигает 8, и корабль покидает опасный участок.

8. Между Сциллой и Харибдой

Ограничения: время – 1s/2s, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Узким проливом мы плыли, и в сердце теснились стенанья;
Сцилла с этого боку была, с другого Харибда,
Страх наводя, поглощала соленую воду морскую.
$\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \$ Одиссея, песнь 12

Корабль Одиссея плывет по длинному проливу постоянной ширины $W$ между Сциллой и Харибдой. Сцилла – многоглавое чудовище, живущее на западной стороне пролива – имеет форму многоугольника. А Харибда – опасный морской водоворот на восточной стороне пролива – имеет форму полукруга. Корабль Одиссея настолько мал по сравнению с ними, что можно считать его точкой. Если корабль пройдет на расстоянии $D$ или меньше от Сциллы, то она нападет и сожрет шестерых моряков из команды. Если же корабль окажется на расстоянии $D$ или меньше от Харибды, то его затянет в водоворот и все путники (их на корабле 50) погибнут. Помогите Одиссею определить минимальное количество людей, которое погибнет при прохождении пролива.

В первой строке ввода содержатся 4 целых числа: ширина пролива $W$ ( $2<=W<=10^4$ ), размер опасной зоны вокруг чудовищ $D$ ( $1<=D<=10^4$ ), количество углов в описании Сциллы $N$ ( $3<=N<=10^5$ ) и радиус Харибды $R$ ( $0<R<W$ ). С запада пролив ограничен вертикальной линией $x=0$ , с востока - линией $x=W$ . Центр Харибды находится в точке ( $W,0$ ). Далее находятся $N$ строк по два целых числа в каждой - координаты углов Сциллы ('0≤x≤W', '-10^4≤y≤10^4'). Гарантируется, что первая и последняя точки имеют x-координаты, равные 0. Точки образуют многоугольник, не обязательно выпуклый. Чудовища не выходят за пределы пролива, не пересекаются и не касаются.

Если от южного до северного края пролива существует путь, все точки которого находятся на расстоянии строго больше $D$ от обоих чудовищ, выведите 0. Иначе, если существует путь, все точки которого находятся на расстоянии строго больше $D$ от Харибды, выведите 6. Иначе, если любой путь обязательно содержит хотя бы одну точку на расстоянии $D$ или меньше от Харибды, выведите 50.

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

Пример ввода 1

Пример вывода 1

Пример ввода 2

Пример вывода 2

Пример безопасного пути для случая 1 изображен на рисунке

width:300px|Путь 1

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

9. В гостях у Алкиноя

Ограничения: время – 250ms/500ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Царь Алкиной, между всех феакийских мужей наилучший!
…Я — Одиссей Лаэртид. Измышленьями хитрыми славен
Я между всеми людьми. До небес моя слава доходит.
$\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \$ Одиссея, песнь 9

Потерпевшего кораблекрушение Одиссея приютил у себя во дворце царь Алкиной. Герой не прочь задержаться в гостях подольше, ведь всё, что от него требуется – это лишь каждый вечер рассказывать какую-нибудь историю про свои прошлые подвиги. Всего Одиссей совершил $N$ подвигов, а за один вечер успевает рассказать историю про $M$ из них. Упоминать один и тот же подвиг дважды в течение одной истории (то есть, в тот же вечер) недостойно героя, но уже на следующий день про тот же подвиг можно рассказывать снова, в следующей истории. Более того, даже если две истории состоят из описаний одних и тех же подвигов, но в разном порядке – Алкиной все равно радостно послушает их обе. И лишь повторять дважды полностью одинаковую историю (те же подвиги в том же порядке) Одиссею не позволит гордость. Помогите хитроумному Одиссею подсчитать, сколько вечеров он сможет провести в гостях, пока его героические истории не начнут повторяться и не наскучат Алкиною.

В первой строке ввода содержится два целых числа: общее число подвигов Одиссея $N$ и количество подвигов в одной истории $M$ ( $1<=M<=N<=10^5$ ).

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

Пример ввода

3 2

Пример вывода

Пояснение к примеру. Из трех подвигов A, B и C можно составить истории: AB, BA, AC, CA, BC, CB.

10. Хитрость Пенелопы

Ограничения: время – 3s/6s, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Кроме того, против нас и другую придумала хитрость:
Ткань начала она ткать, станок у себя поместивши,
Тонкую, очень большую и нам объявила при этом:
– Вот что, мои женихи молодые (ведь умер супруг мой),
Не торопите со свадьбой меня, подождите, покамест
Савана я не сотку…
$\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \$ Одиссея, песнь 2

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

В первой строке ввода содержится одно целое число $N$ – количество женихов, которым Пенелопа дала обещание ( $1<=N<=10^5$ ). В каждой из следующих $N$ строк указано по два целых числа $L$ и $R$ ( $1<=L<=R<=10^7$ ) – минимальная и максимальная площадь полотна, которое обещала соткать Пенелопа.

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

Пример ввода

Пример вывода

3
5
4

Пояснение к примеру:
Первое обещание, площадь от 1 до 2: прямоугольники $1 xx 1, 1 xx 2, 2 xx 1$ – всего 3.
Второе обещание, площадь от 3 до 4: прямоугольники $1 xx 3, 3 xx 1, 1 xx 4, 4 xx 1, 2 xx 2$ – всего 5.
Третье обещание, площадь 6: прямоугольники $1 xx 6, 6 xx 1, 2 xx 3, 3 xx 2$ – всего 4.

11. Возвращение на Итаку

Ограничения: время – 1s/2s, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

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

Эллада состоит из $N$ островов, пронумерованных от $1$ до $N$ . Одиссей спешит из Трои (остров 1) домой на Итаку (остров $N$ ). Из-за несовершенства методов древнегреческой навигации корабль Одиссея плавает только по прямым отрезкам, соединяющим острова, и за один переход преодолевает расстояние не больше $T$ . Если Одиссей останавливается на острове, то вынужден долгие недели пировать в гостях у местного царя и рассказывать ему о своих подвигах, поэтому желательно останавливаться как можно реже. Но если царь заметит, что Одиссей проплыл поблизости от его острова (на расстоянии $D$ или меньше) и не остановился, то это будет сочтено за величайшее оскорбление, за Одиссеем пошлют погоню, и домой он вообще не попадет. Помогите Одиссею предсказать, как скоро он сможет вернуться к любимой жене Пенелопе!

В первой строке входного файла указаны три целых числа: количество островов $N$ ( $1<=N<=1000$ ), максимальная дальность перехода $T$ ( $1<=T<=1000000$ ) и дальность обзора $D$ ( $1<=D<=1000$ ). Затем следует $N$ строк – описания островов. Каждая строка содержит два целых числа $x_i$ и $y_i$ – координаты соответствующего острова ( $-1000<=x_i,y_i<=1000$ ). Острова считаются точками. Гарантируется, что все острова расположены на расстоянии строго больше $D$ друг от друга.

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

Пример ввода 1

Пример вывода 1

Пример ввода 2

2 1 1
0 0
1 1

Пример вывода 2

-1

Пояснение к примеру 1. С острова 1 можно плыть к островам 2, 3 и 4. Остров 6 слишком далеко, а путь до острова 5 находится слишком близко (на расстоянии ровно 1) к острову 2. С островов 2 и 3 прямой переход к острову 6 невозможен, так как он будет пролегать слишком близко к острову 5. Но с острова 4 до острова 6 добраться можно. Получаем единственный путь из двух переходов: 1->4->6.

29/09/2024	Очный тур личного первенства по спортивному программированию ( 1)
30/09/2024	Дорешивание личных соревнований (2+ курсы) (проводит BOGAT) (A)
02/10/2024	Дорешивание личных соревнований (1 курс) (проводит BOGAT) (A)

29/09/2024	Очный тур личного первенства по спортивному программированию ( 2)
30/09/2024	Дорешивание личных соревнований (2+ курсы) (проводит BOGAT) (H)

29/09/2024	Очный тур личного первенства по спортивному программированию ( 3)
30/09/2024	Дорешивание личных соревнований (2+ курсы) (проводит BOGAT) (G)
17/03/2025	ЦОП2: Игры 1 (проводит BOGAT) (E)

29/09/2024	Очный тур личного первенства по спортивному программированию ( 4)
30/09/2024	Дорешивание личных соревнований (2+ курсы) (проводит BOGAT) (J)

29/09/2024	Очный тур личного первенства по спортивному программированию ( 5)
30/09/2024	Дорешивание личных соревнований (2+ курсы) (проводит BOGAT) (C)
02/10/2024	Дорешивание личных соревнований (1 курс) (проводит BOGAT) (C)

Назад

Подразделы

Другие разделы

Дата и время

Авторизация

Задачи личного первенства по спортивному программированию

1. Безумство Одиссея

2. Лагерь ахейцев

3. Игра с драхмами

4. Троянский конь

5. В стране лотофагов

6. Пещера Полифема

7. Песня сирен

8. Между Сциллой и Харибдой

9. В гостях у Алкиноя

10. Хитрость Пенелопы

11. Возвращение на Итаку