Fişierul intrare/ieşire:robinson.in, robinson.outSursăONI 2005 clasa a 6-a
AutorDan GrigoriuAdăugată defrancuCristian Francu francu
Timp execuţie pe test0.1 secLimită de memorie2048 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise

Robinson (clasa a 6-a)

Robinson are un teren de forma pătrată, ca un tablou bidimensional, cu latura de m unităţi (cu m2 parcele). O parcelă este un pătrat elementar al tabloului. Liniile şi coloanele sunt numerotate de la 1 la m: liniile de sus în jos, iar coloanele de la stânga la dreapta.

El a semănat grâu şi s-a rugat să aibă o recoltă bogată. Ruga i-a fost ascultată şi grâul a răsărit astfel: în parcelele din prima linie, recoltele au fost de la stânga spre dreapta: n, n+1, n+2, … boabe de grâu şi în parcelele de pe prima coloană, recoltele au fost de sus în jos: n, n+1, n+2, … boabe de grâu.

Apoi, dacă parcurgem celelalte parcele linie cu linie începând cu a doua linie, iar în cadrul unei linii, începând cu coloana a doua, atunci recolta din linia i şi coloana j a fost egală cu suma recoltelor de pe poziţiile (i-1,j) şi (i,j-1).

Dacă aceste sume depăşesc 999, atunci ele vor fi înlocuite cu numerele formate din ultimele 3 cifre ale sumei respective (de exemplu, dacă suma=1234, se va reţine numărul 234).

Odată cu împlinirea rugii, Robinson a avut un vis în care, pentru a avea noroc şi anul viitor, i se cerea ca în prima zi să culeagă grâul astfel: să plece de la o poziţie dată (linia l şi coloana c), de unde va culege toate boabele de pe acea poziţie. Apoi, el va calcula restul împărţirii la 4 a numărului de boabe de pe acea poziţie. Poziţia următoare pentru cules va fi cea vecină din Nord, dacă restul este 0, cea vecină din Est, dacă restul este 1, cea vecină din Sud, dacă restul este 2, sau cea vecină din Vest, dacă restul este 3.

Drumul acesta pe care l-a visat se va opri fie când la poziţia următoare este în afara terenului, fie când poziţia următoare este una de pe care s-a cules deja recolta.

Cerinţă

Scrieţi un program care să citească numerele m, n, l şi c şi care să determine:

a) recoltele de pe fiecare parcelă;
b) succesiunea parcelelor vizitate, în ordinea în care s-a cules grâul în drumul visat;

Date de intrare

De pe prima linie a fişierului de intrare robinson.in se citesc numerele m n l c în această ordine, separate de câte un spaţiu; l şi c indică o poziţie corectă din tablou.

Date de ieşire

Pe prima linie a fişierului de ieşire robinson.out se va afişa valoarea a[m][m]. Următoarele linii vor conţine câte două numere naturale separate de un spaţiu indicând coordonatele fiecărei parcele din drumul parcurs: primul număr indică linia iar al doilea număr coloana parcelei vizitate.

Restricţii

  • m, n, l, c sunt numere naturale,
  • 1 ≤ m ≤ 20
  • 1 ≤ n ≤ 100
  • Pentru determinarea corectă a valorii a[m][m] se acordă 30% din punctaj.
  • Pentru indicarea corectă a drumului parcurs se acordă încă 70% din punctaj.

Exemplu

robinson.inrobinson.outExplicaţii
4 55 1 3
130
1 3
1 4
2 4
2 3
a) m=4, adică tabloul pătrat are latura de 4 unităţi. n=55, deci prima linie este:
55, 56, 57 şi 58. La fel şi prima coloană: 55, 56, 57, 58, de sus în jos. Apoi linia
a doua se completează astfel: a[2,2]=a[1,2]+a[2,1]=56+56=112, apoi
a[2,3] = a[1,3]+a[2,2]=57+112=169 ; apoi a[2,4]=a[1,4]+a[2,3] etc. Linia a treia,
se va completa astfel: a[3,2]=a[2,2]+a[3,1]; apoi a[3,3]=a[2,3]+ a[3,2], apoi
a[3,4]= a[2,4]+ a[3,3] etc.
 
Atentie: a[4,4]=a[3,4]+a[4,3]=565+565=1130 şi se reţine a[4,4]=130, adică numărul
format din ultimele 3 cifre ale lui 1130.
 
b) Poziţia de plecare: a[1;3]=57, cu rest 1, deci direcţia este Est. Aici avem a[1,4]=58,
care are rest 2, deci direcţia este Sud. Aici a[2,4]=227, cu rest 3, deci direcţia este
Vest, unde avem a[2,3]=169. Acesta are restul 1 şi direcţia este Est, şi ar trebui să se
revină pe poziţia (2,4) pe care a mai fost. S-au afişat poziţiile (1;3),(1;4),(2,4) şi (2;3).
Dacă în loc de l=1 şi c=3 am fi avut l=3 şi c=4, atunci a[3,4] = 565, cu rest 1, deci
direcţia Est şi ar trebui să iasă din teren. Drumul acesta ar avea un pas.
Trebuie sa te autentifici pentru a trimite solutii. Click aici