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

robot1.out

4 1

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema Robot1:

#include <stdio.h>
#include <algorithm>

using namespace std;

#define DIMM 5010
#define DIM 1010

struct rec {
    int i;
    int j;
    int p;
    int v;
};

rec M[DIMM];
char S[DIMM];

int cmpij(rec x, rec y) {
    if (x.i == y.i)
        return x.j < y.j;
    else
        return x.i < y.i;
}

int cmpp(rec x, rec y) {
    return x.p < y.p;
}

int L, C, K, k, ri, rj, i, j, X, R, Sol;
char c;

int main() {
    FILE *f = fopen("robot1.in","r");
    FILE *g = fopen("robot1.out","w");
    fscanf(f, "%d",&L);
    fscanf(f, "%d",&K);
    fscanf(f, "%d %d\n",&ri,&rj);
//  fscanf(f,"%s",S+1);
    M[1].i = ri;
    M[1].j = rj;
    M[1].p = 1;
    for (k=1;k<=K;k++) {
        fscanf(f,"%c%c",&S[k],&c);
        M[k+1].p = k+1;
        if (S[k] == 'N') {
            M[k+1].i = M[k].i - 1;
            M[k+1].j = M[k].j;
        } else if (S[k] == 'S') {
            M[k+1].i = M[k].i + 1;
            M[k+1].j = M[k].j;
        } else if (S[k] == 'E') {
            M[k+1].i = M[k].i;
            M[k+1].j = M[k].j + 1;
        } else if (S[k] == 'V') {
            M[k+1].i = M[k].i;
            M[k+1].j = M[k].j - 1;
        }
    }
    sort(M+1, M+K+2, cmpij);
    k = 1;
    for (i=1;i<=L && k<=K+1;i++) {
        for (j=1;j<=L && k<=K+1;j++) {
            fscanf(f,"%d",&X);
            if (i==M[k].i && j==M[k].j) {
                M[k].v = X;
                k++;
            }
        }
    }
    fclose(f);
    
    sort(M+1, M+K+2, cmpp);
    R = M[1].v;
    k = 1;
    if (R == 0)
        Sol = 1;
    else
        for (k=2;k<=K+1;k++) {
            R+=(M[k].v-1);
            if (R == 0) {
                Sol = k;
                break;
            }
        }
    if (k == K+2)
        Sol = K+1;
    
    fprintf(g,"%d %d\n",M[Sol].i, M[Sol].j);
    
    return 0;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email .

Rezolvarea problemei #732 Robot1

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #732 Robot1 de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!

Rezolvare completă PbInfo #732 Robot1