Fişierul intrare/ieşire:	lost.in, lost.out	Sursă	Romanian Open Contest, TIMUS 2001
Autor	Mugurel Ionut Andreica	Adăugată de	Mugurel-Ionut Andreica •mugurelionut
Timp execuţie pe test	0.15 sec	Limită de memorie	20480 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Lost

Un astronaut al ASR (Agentia Spatiala Romana) a fost "uitat" pe al N-lea nivel al unei statii spatiale romanesti. El vrea sa coboare pana la nivelul 1, unde sunt localizate dispozitivele de comunicatie, pentru a putea contacta o nava spatiala care sa-l recupereze. Din nefericire, astronautul nu stie cat de mult timp i-ar lua navei spatiale pentru a ajunge la statie; de aceea, astronautul vrea sa adune cat mai multa mancare spatiala inainte de a chema nava spatiala.

Fiecare nivel al statie spatiale contine 16 camere, aranjate sub forma unei matrice cu 4 linii si 4 coloane (liniile sunt numerotate de la 1 la 4; la fel si coloanele). Fiecare camera contine o cantitate de mancare spatiala. Astronautul se poate deplasa liber in interiorul statiei spatiale, dar nu poate vizita aceeasi camera de 2 ori. Mai mult, o data ce a coborat la un nivel inferior, el nu mai poate urca pe un nivel de deasupra. In fiecare zi, din camera in care se afla, astronautul se poate muta ori in camera localizata la nord, la sud, la est sau la vest fata de camera curenta (pe acelasi nivel) sau in jos, pe nivelul de dedesubt, in camera de pe aceeasi linie si coloana ca si camera curenta. Deplasarea in jos este permisa numai daca exista o usa catre nivelul de dedesubt in camera curenta. Pentru fiecare nivel, astronautul are la dispozitie o harta care ii arata ce camere au usi catre nivelul de dedesubt. Astronautul nu sta 2 zile la rand in aceeasi camera si in fiecare zi se muta doar o singura data.

De fiecare data cand intra intr-o camera, astronautul ia cantitatea de mancare spatiala aflata in camera respectiva. Ratia de mancare a unui astronaut este definita ca raportul dintre cantitatea totala de mancare spatiala adunata in timpul plimbarii sale prin statie si numarul de zile petrecute in interiorul statiei spatiale inainte de a chema nava spatiala. Se considera ca astronautul petrece prima zi in camera unde isi incepe calatoria, pe nivelul N, si ca ia cantitatea de mancare din camera respectiva.

Determinati o secventa de mutari ale astronautului care sa il aduca din camera unde se afla initial, pe nivelul N, pana intr-o camera de pe nivelul 1. Aceasta secventa de mutari trebuie sa ii maximizeze ratia de mancare. Plimbarea astronautului prin statie nu trebuie sa se incheie automat in momentul in care ajunge intr-o camera de pe nivelul 1. El se poate plimba prin mai multe camere de pe nivelul 1 inainte de a-si incheia plimbarea si a chema nava spatiala.

Date de intrare

Prima linie a fisierului de intrare lost.in contine un singur numar intreg N, reprezentand numarul de nivele ale statiei spatiale. Urmeaza apoi descrierile celor N nivele, in ordine, de la nivelul N la nivelul 1. Pentru fiecare nivel, vor exista 8 linii in fisierul de intrare. Primele 4 linii contin cate 4 numere intregi, separate prin cate un spatiu, reprezentand cantitatea de mancarea spatiala disponibila in fiecare camera de pe nivelul respectiv (al j-lea numar de pe a i-a linie dintre cele 4 va reprezenta cantitatea de mancare din camera de pe linia i si coloana j). Urmatoarele 4 linii vor contine cate 4 numere intregi, separate prin cate un spatiu, avand valorile 0 sau 1. 1 inseamna ca exista o usa din camera respectiva catre nivelul de dedesubt, iar 0 inseamna ca nu exista usa. Nivelul 1 va avea numai valori 0 pe aceste 4 linii. Ultima linie a fisierului contine 2 numere intregi, l si c, reprezentand linia si coloana camerei de pe nivelul N in care se afla initial astronautul.

Date de iesire

Pe prima linie a fisierului de iesire lost.out veti afisa ratia maxima de mancare pe care o poate obtine astronautul, cu 4 cifre zecimale. Pe a doua linie veti afisa lungimea drumului sau (afisati 0 daca astronautul nu iese din camera in care se afla initial). Daca lungimea drumului sau este L (L > 0), atunci pe a treia linie veti afisa L caractere din multimea {'N','E','S','W','D'}, fiecare caracter corespunzand unei directii de miscare (nord, est, sud, vest si jos). Daca exista mai multe drumuri cu aceeasi ratie maxima de mancare, puteti afisa oricare din ele.

Restrictii

• 1 ≤ N ≤ 16
• 1 ≤ cantitatea de mancare spatiala dintr-o camera ≤ 255
• Daca L este lungimea drumului astronautului, atunci el petrece L+1 zile in interiorul statiei spatiale inainte de a chema o nava spatiala.
• Pentru fiecare test astronautul va putea ajunge din camera unde se afla initial intr-o camera de pe nivelul 1.

Exemplu

Cum se trimit solutii?