El robot passejador P78712

Statement

html

Un robot es troba inicialment al punt (0, 0) d’un mon pla infinit que té n obstacles. Podeu considerar tant el robot com els obstacles com a punts. El robot té escrits en ordre els passos de longitud 1 que ha d’intentar fer, cadascun cap al nord, sud, est o oest. Si en un moment es troba a la posició (x, y), això vol dir sumar 1 a y, restar 1 a y, sumar 1 a x, o restar 1 a x, respectivament. Si, quan intenta fer un pas, el punt on hauria d’anar està ocupat per un obstacle, el robot no es mou de lloc en aquell torn.

Donades la posició dels obstacles i les instruccions donades al robot, podeu decidir en quina posició acabarà?

Entrada

L’entrada consisteix en diversos casos, cadascun amb una paraula amb les instruccions per al robot: entre 1 i 100 caràcters triats entre ‘N’, ‘S’, ‘E’, i ‘O’. A continuació ve n, seguida d’n parells diferents (x_i, y_i). Podeu suposar 0 ≤ n ≤ 10⁴, que cap obstacle es troba al (0, 0), i que totes les coordenades donades són més petites que 1000 en valor absolut.

Sortida

Per a cada cas, escriviu una línia amb la posició final del robot.

Observació

Algunes solucions molt poc eficients poden obtenir 15 punts, i altres parcialment eficients en poden obtenir 70, dels 100 punts totals.

Public test cases

Input

NN
4  1 0  -1 0  0 -1  23 42
SSOE
2  0 -2  -1 -1
O
0

Output

(0, 2)
(1, -1)
(-1, 0)

Information

Author: Salvador Roura
Language: Catalan
Official solutions: C++
User solutions: C++