El robot passejador P78712


Statement
 

pdf   zip

thehtml

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 (xi, yi). Podeu suposar 0 ≤ n ≤ 104, 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++