0732 - Robot 1

O echipă de cercetători a construit un robot pentru realizarea de operaţiuni industriale în medii greu accesibile. Robotul este acţionat de un motor electric alimentat de un acumulator cu proprietatea de a se autoîncărca folosind energia mediului ambiant.

Pentru testele preliminare s-a construit o suprafaţă de testare de formă pătrată, compusă din N*N pătrate de dimensiune unitate, pentru fiecare pătrat cunoscându-se cantitatea de energie, posibil egală cu zero, pe care o poate acumula robotul dacă ajunge în poziţia respectivă. Robotul se va deplasa conform unui şir de comenzi codificat prin caracterele N, E, S, V (N-deplasare cu o poziţie către nord, E-deplasare cu o poziţie către est, S-deplasare cu o poziţie către sud, V-deplasare cu o poziţie către vest). Şirul de comenzi este corect, adică robotul nu va trece de mai multe ori prin aceeaşi poziţie şi nu va depăşi marginile suprafeţei de testare.

Iniţial, acumulatorul robotului este descărcat complet, dar acesta se găseşte cu siguranţă într-o poziţie de unde poate acumula energie. Deplasarea robotului dintr-o poziţie în alta consumă o unitate de energie. Cantitatea de energie ce poate fi stocată în acumulator este nelimitată.

Robotul se opreşte când a efectuat toate comenzile din şirul dat sau când ajungând într-o poziţie energia acumulatorului devine zero, iar în respectiva poziţie nu poate acumula energie.

Cerința

Cunoscând dimensiunea suprafeţei de testare, cantitatea de energie din fiecare poziţie, poziţia iniţială şi succesiunea de comenzi determinaţi poziţia unde se opreşte robotul.

Date de intrare

Fişierul robot1.in are următoarea structură:

• Pe prima linie se află numerele naturale N, M, L, C separate prin câte un spaţiu, cu semnificaţia: N-dimensiunea suprafeţei de testare, M-numărul comenzilor, L şi C-coordonatele poziţiei iniţiale (linia, respectiv coloana);
• Pe a doua linie se găsesc M caractere din mulţimea {‘N’, ‘E’, ‘S’, ‘V’}, separate prin câte un spaţiu reprezentând şirul de comenzi;
• Pe următoarele N linii se află câte N valori naturale, separate prin câte un spaţiu, reprezentând numărul unităţilor de energie disponibile în fiecare poziţie a suprafeţei de testare.

Date de ieșire

Fişierul robot1.out va conţine două numere naturale X şi Y, scrise pe prima linie din fişier, separate printr-un spaţiu, reprezentând numărul liniei şi respectiv numărul coloanei unde robotul se opreşte.

Restricții și precizări

• 2 ≤ N ≤ 1000
• 2 ≤ M ≤ 5000
• pentru 30% dintre teste N ≤ 100
• Cantitatea de energie dintr-o poziţie este un număr natural mai mic sau egal cu 1000000
• Liniile şi coloanele suprafeţei de testare se consideră numerotate de sus in jos, respectiv de la stânga la dreapta, începand cu valoarea 1.

Exemplu:

robot1.in

5 4 1 1
S S S E
2 2 3 4 5
0 0 3 0 1
1 4 4 4 4
0 0 5 5 5
0 1 1 0 0

robot1.out

4 1

Încărcare soluție

Lipește codul aici

​def P(n, c):

    vec = []

    nr = 0

    while n:

        if n % 10 != c:

            vec.append(n % 10)

            nr += 1

        n = n // 10

    for i in range(1, nr+1):

        nr -= 1

        n = 10*n + vec[nr]