Задачи личного первенства по спортивному программированию
1. Безумство Одиссея
Ограничения: время – 500ms/1000ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
> Муж тот, о ком ты спросил, - Лаэртид Одиссей многоумный.\
Он в каменистой стране, на Итаке на острове вырос,\
В хитростях всяких искусный, во всяких решениях мудрый.\
`\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ ` Илиада, песнь 3
Одиссей спокойно жил на Итаке и совершенно не хотел ехать на войну с Троей. Поэтому перед приехавшими к нему послами ахейцев он
сделал вид, что совершенно безумен: сеял в поле соль и бормотал бессмыслицу. Но изображать безумие не так легко, как кажется.
Попробуйте, например, придумать текст вообще без осмысленных слов!
В первой строке ввода указаны два целыых числа: длина строки `L`, которую нужно придумать (`1<=L<=10`), и количество слов `N` (`1<=N<=10`).
В следущей строке перечислены в алфавитном порядке и без разделителей от 1 до 5 строчных латинских букв, которые можно использовать.
Затем идут `N` строк длиной не более `L` каждая - слова, которых не должно быть в строке. Слова состоят только из разрешенных букв.
Выведите единственную строку, состоящую ровно из `L` разрешенных букв и не содержащую подстрок,
совпадающих с запрещенными словами. Если таких строк существует несколько, выведите лексикографически минимальную из них.
Если ни одной подходящей строки не существует, выведите -1.
```sample Пример ввода 1
5 2
abc
a
bb
```
```sample Пример вывода 1
bcbcb
```
```sample Пример ввода 2
10 4
ab
aa
ab
ba
bb
```
```sample Пример вывода 2
-1
```
2. Лагерь ахейцев
Ограничения: время – 500ms/2500ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение 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`).
Выведите единственное целое число -- минимальную суммарную высоту надстроек.
```sample Пример ввода
5 2
1 4 0 1 1
1 2
2 5
```
```sample Пример вывода
6
```
Пояснение: участки стены после надстройки будут иметь высоты 2, 4, 2, 3, 2.
Соответственно, общая высота надстроек равна 1 + 0 + 2 + 2 + 1 = 6.
3. Игра с драхмами
Ограничения: время – 250ms/500ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение 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.
```sample Пример ввода 1
1
1
```
```sample Пример вывода 1
Ajax
```
```sample Пример ввода 2
3
1 2 5
```
```sample Пример вывода 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 или стандартный вывод
Послать решение 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)` одновременно, выведите любой из них.
```sample Пример ввода
2
4 0 0 10
2 12 9 10
```
```sample Пример вывода
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 или стандартный вывод
Послать решение 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)` однозначно определена для любого натурального аргумента.
```sample Пример ввода
5
```
```sample Пример вывода
5
```
6. Пещера Полифема
Ограничения: время – 1s/2s, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
> Был в этом стаде баран, меж всех остальных наилучший.\
За спину взявшись его, соскользнул я барану под брюхо\
И на руках там повис...\
Хозяин... глупец, не заметил,\
Что привязано было под грудью баранов шерстистых.\
`\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ ` Одиссея, песнь 9
Сбежать из пещеры циклопа Полифема -- нелегкая задача, ведь вход завален огромным камнем. Циклоп убирает камень только для того,
чтобы выпустить своих баранов из пещеры на пастбище снаружи. Одиссею пришла в голову отличная идея: пусть
каждый из его спутников спрячется под шкурой какого-нибудь из баранов, тогда циклоп их не заметит. Однако, не
любой баран подойдет: некоторые из них слишком малы, чтобы скрыть могучего ахейца. Под каждым бараном должно прятаться не больше
одного ахейца, и рост каждого ахейца должен быть не больше, чем размер скрывающего его барана. К счастью для Одиссея, в
пещере спрятано еще и немного бараньего корма. Если скормить `X` порций корма барану, то его размер увеличится на `X`. Порции
можно распределять между одним или несколькими баранами как угодно. Помогите Одиссею понять, какое
максимальное количество спутников удастся вывести из пещеры благодаря его идее.
В первой строке ввода указаны три целых числа: `N` -- число баранов, `M` -- число ахейцев, `С` -- количество порций
корма (`1<=N,M<=10^5`, `0<=C<=100`).
Во второй строке перечислены `N` целых чисел от 1 до `10^9` включительно -- размеры каждого из баранов.
Во второй строке перечислены `M` целых чисел от 1 до `10^9` включительно -- рост каждого из ахейцев.
Выведите одно целое число -- максимальное количество ахейцев, которые могут одновременно спрятаться под баранами.
```sample Пример ввода 1
4 3 1
7 2 2 1
6 6 3
```
```sample Пример вывода 1
2
```
```sample Пример ввода 2
1 3 5
1
10 10 10
```
```sample Пример вывода 2
0
```
Пояснение к первому примеру.
Первый или второй ахейцы ростом 6 могут спрятаться под
первым бараном размера 7 (но не оба одновременно). Ни под каким другим бараном (даже после откармливания 1 порцией корма) спрятаться
они не могут. Второму или третьему барану можно скормить
единственную доступную порцию корма, тогда он вырастет от размера 2 до размера 3 и сможет скрыть третьего ахейца.
7. Песня сирен
Ограничения: время – 500ms/1000ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение 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.
```sample Пример ввода 1
3 4 2 8
aab
abaa
```
```sample Пример вывода 1
14
```
```sample Пример ввода 2
3 1 4 4
abc
c
```
```sample Пример вывода 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 или стандартный вывод
Послать решение 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.
Путь может иметь произвольную форму (не обязательно прямую), но не должен выходить за пределы пролива. Путь
не может проходить внутри чудовищ либо касаться их.
```sample Пример ввода 1
10 1 8 3
0 1
3 4
5 3
3 2
5 2
1 1
6 -4
0 -1
```
```sample Пример вывода 1
0
```
```sample Пример ввода 2
2 1 3 1
0 10
1 11
0 12
```
```sample Пример вывода 2
50
```
Пример безопасного пути для случая 1 изображен на рисунке
Во втором случае любой путь, не выходящий за пределы пролива, пролегает на расстоянии 1 или меньше от Харибды.
9. В гостях у Алкиноя
Ограничения: время – 250ms/500ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
> Царь Алкиной, между всех феакийских мужей наилучший!\
...Я — Одиссей Лаэртид. Измышленьями хитрыми славен\
Я между всеми людьми. До небес моя слава доходит.\
`\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ ` Одиссея, песнь 9
Потерпевшего кораблекрушение Одиссея приютил у себя во дворце царь Алкиной. Герой не прочь задержаться в гостях подольше,
ведь всё, что от него требуется -- это лишь каждый вечер рассказывать какую-нибудь историю про свои прошлые подвиги. Всего
Одиссей совершил `N` подвигов, а за один вечер успевает рассказать историю про `M` из них. Упоминать один и тот же подвиг
дважды в течение одной истории (то есть, в тот же вечер) недостойно героя, но уже на следующий день про тот же подвиг
можно рассказывать снова, в следующей истории. Более того, даже если две истории состоят из
описаний одних и тех же подвигов, но в разном порядке -- Алкиной все равно радостно послушает их обе. И лишь
повторять дважды полностью одинаковую историю (те же подвиги в том же порядке) Одиссею не позволит гордость. Помогите
хитроумному Одиссею подсчитать, сколько вечеров он сможет провести в гостях, пока его героические истории
не начнут повторяться и не наскучат Алкиною.
В первой строке ввода содержится два целых числа: общее число подвигов Одиссея `N` и количество подвигов
в одной истории `M` (`1<=M<=N<=10^5`).
Выведите одно целое число -- количество различных историй, которые Одиссей сможет рассказать. Число может быть очень большим,
поэтому выведите остаток от его деления на 1000000007.
```sample Пример ввода
3 2
```
```sample Пример вывода
6
```
Пояснение к примеру. Из трех подвигов A, B и C можно составить истории: AB, BA, AC, CA, BC, CB.
10. Хитрость Пенелопы
Ограничения: время – 3s/6s, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
> Кроме того, против нас и другую придумала хитрость:\
Ткань начала она ткать, станок у себя поместивши,\
Тонкую, очень большую и нам объявила при этом:\
-- Вот что, мои женихи молодые (ведь умер супруг мой),\
Не торопите со свадьбой меня, подождите, покамест\
Савана я не сотку...\
`\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ ` Одиссея, песнь 2
Пока Одиссей странствует по дальним краям, его дворец и все имущество оберегает верная супруга Пенелопа. Чтобы отделаться от
назойливых женихов, она заявила каждому из них следующее: ежедневно она будет ткать новое прямоугольное полотно с целочисленными
сторонами и площадью от `L` до `R` включительно. Пока полотна не будут повторяться, Пенелопа продолжит ждать Одиссея, и женихам не
на что рассчитывать. Помогите сыну Одиссея Телемаху оценить, сколько различных полотен сможет соткать Пенелопа для каждого
из женихов -- а значит, сколько дней у него осталось на поиски отца.
В первой строке ввода содержится одно целое число `N` -- количество женихов, которым Пенелопа
дала обещание (`1<=N<=10^5`). В каждой из следующих `N` строк указано по два целых числа `L` и `R` (`1<=L<=R<=10^7`) -- минимальная
и максимальная площадь полотна, которое обещала соткать Пенелопа.
Выведите `N` целых чисел, по одному на строке. Каждое число -- общее количество различных прямоугольников с целыми сторонами, имеющих
площадь от `L` до `R` включительно. Прямоугольники, получающиеся друг из друга поворотом, считаются различными.
```sample Пример ввода
3
1 2
3 4
6 6
```
```sample Пример вывода
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 или стандартный вывод
Послать решение 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` или меньше от любого другого острова.
```sample Пример ввода 1
6 5 1
0 4
2 5
3 3
3 0
4 4
6 4
```
```sample Пример вывода 1
2
```
```sample Пример ввода 2
2 1 1
0 0
1 1
```
```sample Пример вывода 2
-1
```
Пояснение к примеру 1. С острова 1 можно плыть к островам 2, 3 и 4. Остров 6 слишком далеко, а путь до острова 5 находится слишком близко (на расстоянии ровно 1) к острову 2.
С островов 2 и 3 прямой переход к острову 6 невозможен, так как он будет пролегать слишком близко к острову 5. Но с острова 4 до острова 6 добраться можно. Получаем единственный путь из двух переходов: 1->4->6.
Начало
Соревнования
Рекурсивный перебор