ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

Чемпионат УрГУ 2005

Описание     Задачи     Отправить на проверку     Состояние проверки     Результаты
Соревнование завершено

F. Мобильная жизнь

Ограничение времени: 2.0 секунды
Ограничение памяти: 64 МБ
Цветочный город живёт в ногу со временем. Еще совсем недавно здесь наладили сотовую связь, а Винтик и Шпунтик уже изобрели свой сотовый телефон со встроенным передатчиком положения телефона. Теперь-то точно никто из коротышек (а в особенности Незнайка) не потеряется, ведь если с ним будет такой телефон, то Винтик и Шпунтик всегда смогут узнать его местоположение. Осталось только этот телефон протестировать. Решили сделать это следующим образом: пусть Шпунтик ездит по городу с телефоном и последовательно записывает все его показания на бумажку, а Винтик в это время сидит в мастерской и следит за передвижением Шпунтика на большом экране. Когда Шпунтик вернется обратно, то останется только лишь сравнить записи Шпунтика и Винтика. Хотя как же их сравнить, ведь у Шпунтика — список строк с показаниями телефона, а у Винтика — список чисел, описывающих передвижение Шпунтика по городу? Напишите программу, которая по списку Винтика генерирует список, который должен был бы получиться у Шпунтика, если вся система работает без ошибок.
Сотовый телефон Винтика и Шпунтика имеет цветовой индикатор мощности сигнала и показывает идентификатор текущей соты. Цветовой индикатор может принимать семь различных значений (по цветам радуги, столь любимой коротышками). Фиолетовый цвет говорит о самом высоком уровне сигнала, а красный о том, что сигнала практически нет, и не нужно удивляться, если телефон вдруг перестанет работать.
Для каждой базовой станции известно расстояние, ближе которого сигнал всегда будет идеальным (то есть индикатор на телефоне будет гореть фиолетовым цветом). Известно также, что при удалении от передающей станции дальше этого расстояния, индикатор станет сначала синим, потом голубым и т. д., пока не станет красной, которая уже не меняется при дальнейшем падении мощности. Винтик уверяет, что цветовая индикация изменяется на одно деление при падении мощности сигнала на 2 децибела. Он также уверен, что мощность сигнала зависит только от расстояния до базовой станции, и падает пропорционально этому расстоянию, т. е. при росте расстояния в два раза мощность сигнала падает тоже в два раза.
Телефон Винтика и Шпунтика выбирает базовую станцию по следующим правилам:
  1. При включении телефон выбирает базовую станцию с самым мощным сигналом, если таких несколько, то предпочтение отдается станции с меньшим (лексикографически) именем соты.
  2. Телефон остается в соте пока индикатор не станет красным, после чего переходит в режим поиска новой соты.
  3. Если индикатор горит красным, то телефон находится в постоянном поиске новой соты и автоматически переключается на неё, если только сигнал от новой станции будет достаточен для того, чтобы индикатор имел любой цвет, кроме красного. Если таких сот несколько, действует то же правило выбора соты, что и при включении телефона.
Шпунтик записывает сообщения в следующем формате:
  1. Power on. CELL_ID:<имя_соты>, SIGNAL_LEVEL:<цвет_индикатора>
    — телефон включён.
  2. Cell changed. CELL_ID:<имя_соты>, SIGNAL_LEVEL:<цвет_индикатора>
    — сменилась базовая принимающая станция.
  3. Signal changed. SIGNAL_LEVEL:<цвет_индикатора>
    — изменилась цветовая индикация сигнала.
Даже если телефон мгновенно переключился на новую соту, то Шпунтик всё равно запишет строчку о появлении красной индикации в старой соте.
Комментарий для незнакомых с децибелами: Децибелл — логарифмическая величина, характеризующая отношение величин. Если сигнал A имеет мощность Wa, а сигнал B — Wb, то мощность сигнала B отличается от мощности сигнала A на 10 · log10(Wb/Wa) децибел. Если сравнивают не мощность, а, скажем, напряжение, то используют формулу 20 · log10(Ub/Ua), но Винтик и Шпунтик используют первую формулу.

Исходные данные

В первой строке находится число N — число базовых сотовых станций в Солнечном городе (1 ≤ N ≤ 100). Далее следует N строк с описанием сот. Строка с описанием соты содержит 3 целых числа: Xc, Yc, Rc — координаты базовой станции и расстояние, на котором сигнал от станции равен базовому и строку без пробельных символов, длиной не больше 50: Sc — название соты.
(N+2)-я строка содержит число M — количество прямолинейных участков движения Шпунтика. Последние M строк содержат по 4 целых числа: Xs, Ys, Xe, Ye — координаты начала и конца отрезка движения. (−10000 ≤ Xc, Yc, Xs, Ys, Xe, Ye ≤ 10000, 0 < Rc ≤ 10000, 1 ≤ M ≤ 1000).
Гарантируется, что движение Шпунтика является непрерывным, то есть конец каждого отрезка совпадает с началом следующего. Кроме того, для простоты будем считать, что в момент перехода с одного отрезка на другой Шпунтик никогда не находился на границе смены уровня сигнала или смены соты и что он никогда не проходил по касательной к этой границе.

Результат

Корректный список Шпунтика.

Пример

исходные данныерезультат
4
0 0 1 Romashka
0 10 1 Lutik
10 10 2 Znaika
10 0 1 Children
2
5 5 -5 -5
-5 -5 5 5
Power on. CELL_ID:Znaika, SIGNAL_LEVEL:GREEN
Signal changed. SIGNAL_LEVEL:YELLOW
Signal changed. SIGNAL_LEVEL:ORANGE
Signal changed. SIGNAL_LEVEL:RED
Cell changed. CELL_ID:Romashka, SIGNAL_LEVEL:YELLOW
Signal changed. SIGNAL_LEVEL:ORANGE
Signal changed. SIGNAL_LEVEL:YELLOW
Signal changed. SIGNAL_LEVEL:GREEN
Signal changed. SIGNAL_LEVEL:BLUE
Signal changed. SIGNAL_LEVEL:INDIGO
Signal changed. SIGNAL_LEVEL:VIOLET
Signal changed. SIGNAL_LEVEL:INDIGO
Signal changed. SIGNAL_LEVEL:BLUE
Signal changed. SIGNAL_LEVEL:GREEN
Signal changed. SIGNAL_LEVEL:YELLOW
Signal changed. SIGNAL_LEVEL:ORANGE
Автор задачи: Евгений Крохалев
Источник задачи: Чемпионат Уральского государственного университета, 29 октября 2005
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 1415. Мобильная жизнь