Fişierul intrare/ieşire:furnica.in, furnica.outSursăOJI 2007, clasa a 6-a
AutorDoru Popescu AnastasiuAdăugată defrancuCristian Francu francu
Timp execuţie pe test0.1 secLimită de memorie2048 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise

Furnica (clasa a 6-a)

Pe o tablă de şah cu n linii şi n coloane se află firimituri de pâine şi o furnică. Pentru fiecare pătrăţel, inclusiv cel în care se găseşte furnica, aflat pe linia i şi coloana j, cantitatea de firimituri de pâine este egală cu restul împărţirii lui i+j la 6. Astfel pentru n=4 tabla de şah conţine următoarele cantităţi de firimituri:

Furnica (notată cu F în figură) se poate deplasa din pătrăţelul unde se găseşte în toate cele opt pătrăţele vecine, numerotate ca mai jos:

Furnica se deplasează, pornind din pătrăţica aflată în colţul din stânga sus, în una dintre pătrăţelele vecine, şi aşa mai departe. Pe drumul său furnica se hrăneşte cu toată cantitatea de firimituri din pătrăţelele prin care a trecut (după ce iese din pătrăţică catitatea de firimituri devine 0). Drumul furnicii este dat printr-un şir de k numere naturale (cuprinse între 1 şi 8) care precizează, la fiecare pas, următorul pătrăţel din drum.

Cerinţă

Scrieţi un program care pentru un drum dat determină cantitatea totală de firimituri mâncată de furnică, precum şi numărul pătrăţelelor prin care aceasta a trecut de cele mai multe ori.

Date de intrare

Fişierul de intrare furnica.in conţine pe prima linie numerele n şi k, separate între ele printr-un spaţiu, iar pe linia următoare k numere naturale (1, 2, 3, 4, 5, 6, 7 sau 8) separate prin câte un spaţiu, reprezentând următorul pătrăţel din drum pentru un pătrăţel curent.

Date de ieşire

Fişierul de ieşire furnica.out va conţine, pe prima linie, cantitatea totală şi numărul pătrăţelelor din cerinţă separate printr-un spaţiu.

Restricţii

  • 1 < n < 101
  • 0 < k < 201
  • Drumul furnicii nu iese din tablou.

Exemplu

furnica.infurnica.outExplicaţii
4 10
3 6 5 3 2 6 3 6 2 3
23 2
Drumul furnicii trece prin pătrăţelele (linie, coloană) următoare:
(1,1)->(1,2)->(2,1)->(3,1)->(3,2)->
(2,3)->(3,2)->(3,3)->(4,2)->(3,3)->(3,4).
Pe drum se mănâncă următoarea cantitate de firimituri: 2+3+3+4+5+5+0+0+0+0+1=23
Prin pătrăţelele de coordonate (3,2) şi (3,3) se trece de cele mai multe ori (de două ori).
Trebuie sa te autentifici pentru a trimite solutii. Click aici