printРабочее место участника

printЗадачи

2391. В поисках Принцессы

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

Конфетный город разделен перпендикулярными улицами на квадратные кварталы. На каждом перекрестке стоит банановый стражник. Финн хочет встретиться с Принцессой и расспрашивает стражников на перекрестках о её местонахождении. Стражники знают о местоположении Принцессы, но путаются с направлениями, поэтому могут показать на дорогу, ведущую в прямо противоположном направлении. Формально, если `|X_i\ -\ X_P|\ >\ |Y_i\ -\ Y_P|`, где `(X_i,\ Y_i)` – координаты стражника, `(X_P,\ Y_P)` – координаты Принцессы, то стражник может с равной вероятностью показать направление W (запад) или E (восток). Если `|X_i\ -\ "XP"|\ <\ |Y_i\ -\ Y_P|`, то стражник может показать направление N (север) или S (юг). Если `|X_i\ -\ X_P|\ =\ |Y_i\ -\ Y_P|`, то стражник может показать любое из четырех направлений. Стражники не меняют своих указаний.
Гарантируется, что в начальный момент `1\ ≤\ |X_F\ -\ X_P|\ +\ |Y_F\ -\ Y_P|\ ≤\ 300`, где `(X_F,\ Y_F)` – координаты Финна. Напишите программу, которая поможет Финну найти Принцессу, пройдя не более 2000 перекрестков.
Протокол взаимодействия
При старте программа получает строку, содержащую первое указание от стражника на местоположение принцессы. Программа должна вывести строку, содержащую один символ N, S, W или E — в каком направлении нужно идти дальше. После вывода программа должна сделать принудительную запись буфера вывода (в C++ это делает endl, в C нужно использовать fflush(stdout), в Pascal – flush(output)). После вывода программа получает указания от стражника на очередном перекрестке или сообщение "PRINCESS!", если Принцесса была обнаружена на этом перекрестке. При появлении такого сообщения программа должна завершить работу. Если программа не найдет Принцессу за 2000 перемещений, то программа получает вердикт WA "Неверный ответ".

Пример ввода

N
S
PRINCESS!

Вывод программы

S
S
loading