El tresor P39415

Statement

Donades les coordenades $(x, y)$ d’un tresor, volem saber si la trajectòria d’un robot situat a la posició (0, 0), i que segueix les instruccions que li donem, passa per la ubicació on es troba el tresor.

up $p$ : es desplaça $p$ passes cap amunt.
down $p$ : es desplaça $p$ passes cap avall.
right $p$ : es desplaça $p$ passes cap a la dreta.
left $p$ : es despaça $p$ passes cap a l’esquerra.

Per exemple, si el robot està a la posició inicial $(0, 0)$ , la instrucció right $2$ farà que el robot passi per les coordenades $(1, 0)$ i $(2, 0)$ . Si la següent instrucció és up 1 el robot anirà a la posició $(2, 1)$ .

Entrada

L’entrada consisteix en dos enters $x$ , $y$ (mai no seran tots dos iguals a $0$ ), que representen les coordenades d’un tresor. Li segueix una seqüència de parells $m$ $p$ a on $m$ és un string que representa un moviment (només pot ser "up", "down", "right", "left"), i $p$ és un enter no negatiu que representa número de passes.

Sortida

Cal escriure el mínim número d’instruccions i de passes necessàries perquè un robot situat a l’origen de coordenades $(0, 0)$ arribi al tresor seguint les instruccions de l’entrada. Si el robot no arribés mai al tresor, s’ha de donar el missatge “not found” seguit del total d’instruccions i passes fetes.

Observació

Un solució en la què el robot avanci pas a pas es donarà com a bona.

Public test cases

Input

4 0
right 2
left 1
up 0
right 15
left 30

Output

4 6

Input

-5 10
right 3
up 20
down 10
left 4
left 5
down 0
left 0
up 9

Output

5 41

Input

-2 10

Output

not found 0 0

Input

-2 -10
left 2
up 10

Output

not found 2 12

Information

Author: Emma Rollón
Language: Catalan
Official solutions: Python
User solutions: Python