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ă si a drumului parcurs se acordă încă 70% din punctaj.
Exemple
robinson.in
robinson.out
Explicaţ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.