eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Лорд Бредли на северном полюсе

Лорд Бредли на северном полюсе

Начинался полярный рассвет. Лорд Брэдли стоит точно на Северном полюсе, лицом в сторону своего далекого дома в Гринвиче. Со всех сторон Земли на него движутся сердитые белые медведи чтобы отомстить. У лорда Брэдли есть только его верная винтовка. Он никогда не промахивается, и может сделать выстрел (или любое количество выстрелов) в любой период времени. Винтовка имеет необычную линию огня - она может поразить цель на любом расстоянии, вплоть до Южного полюса. Единственная проблема заключается в изменении направления выстрела: для сохранения своей совершенной концентрации лорд Бредли всегда поворачивается со скоростью одной арксекунды (\textbf{1}'' = \textbf{1}/\textbf{3600} * \textbf{1}° за одну секунду). Удастся ли ему пострелять всех медведей, или он сам станет их завтраком? Предположим, что Земля является совершенной сферой, длина экватора составляет в точности \textbf{40 320} км, а все медведи двигаются прямо на Бредли с константной скоростью \textbf{28} км/ч. Медведь может быть убит даже в упор (в момент достижения им Северного Полюса), однако направление ружья должно совпадать с направлением откуда пришел медведь. Зная начальные географические координаты всех медведей, определите, сможет ли выжить лорд Бредли. \InputFile Первая строка содержит количество тестов \textbf{t}. Первая строка каждого теста содержит количество медведей \textbf{n} (\textbf{1} ≤ \textbf{n} ≤ \textbf{1 000}). В следующих \textbf{n} строках заданы координаты медведей (широта и долгота, используя * для градусов, ' для минут и " для секунд как показано в примере). Ни градусы, ни минуты, ни секунды не могут быть пропущены. Все числа являются неотрицательными целыми. Как и обычно, через \textbf{N} обозначается северное полушарие, через \textbf{S} южное, \textbf{E} - восток от Гринвича, \textbf{W} - запад. \OutputFile Для каждого теста вывести в отдельной строке одно слово: \textbf{ALIVE} если Бредли сможет победить медведей или \textbf{EATEN} иначе.
Ліміт часу 3 секунди
Ліміт використання пам'яті 64 MiB
Вхідні дані #1
3
2
87*0'0"N 4*0'0"E
88*0'0"N 6*0'0"W
2
86*0'0"N 4*0'0"E
87*59'59"N 6*0'0"W
1
89*59'59"N 0*0'4"W
Вихідні дані #1
EATEN
ALIVE
ALIVE
Джерело 2013 Petrozavodsk Winter Training Camp, Jagiellonian University Contest, Январь 25, Задача L