== include(page="template/taskheader" task_id="cartofi") ==
Fermierul Feder cultivă cartofi pe un teren dreptunghiular de lățime *N* metri și lungime *M* metri, compartimentat în *N · M* zone pătratice identice de lungime *1* metru, dispuse alăturat, câte *N* pe lățime (pe *N* linii, numerotate de la *1* la *N*) și câte *M* pe lungime (pe *M* coloane, numerotate de la *1* la *M*). În fiecare zonă pătratică se află câte o plantă de cartofi. Parcurgând terenul de la prima linie către ultima, fiecare linie cu număr impar parcurgând-o de la coloana *1* către coloana *M*, iar fiecare linie cu număr par parcurgând-o de la coloana *M* către coloana *1*, fermierul (pasionat de matematică) a scris numerele cartofilor produși de fiecare plantă, în ordinea parcurgerii, și a constatat că aobținut șirul cifrelor unităților primilor *N · M* termeni ai șirului Fibonacci (vezi Figura *1* în care *N = 3* și *M = 6*).
Fermierul Feder cultivă cartofi pe un teren dreptunghiular de lățime *N* metri și lungime *M* metri, compartimentat în *N · M* zone pătratice identice de lungime *1* metru, dispuse alăturat, câte *N* pe lățime (pe *N* linii, numerotate de la *1* la *N*) și câte *M* pe lungime (pe *M* coloane, numerotate de la *1* la *M*). În fiecare zonă pătratică se află câte o plantă de cartofi. Parcurgând terenul de la prima linie către ultima, fiecare linie cu număr impar parcurgând-o de la coloana *1* către coloana *M*, iar fiecare linie cu număr par parcurgând-o de la coloana *M* către coloana *1*, fermierul (pasionat de matematică) a scris numerele cartofilor produși de fiecare plantă, în ordinea parcurgerii, și a constatat că a obținut șirul cifrelor unităților primilor *N · M* termeni ai șirului Fibonacci (vezi Figura *1* în care *N = 3* și *M = 6*).
!problema/cartofi?cartofi.jpeg!
h2. Cerințe
h2. Date de intrare
Fișierul de intrare $cartofi.in$ ...
Fișierul $cartofi.in$ conține pe prima linie un număr natural *C* reprezentând cerința din problemă care trebuie rezolvată ([*1*], *2* sau *3*). A doua linie a fișierului conține cele două numere naturale *N* și *M*, separate printr-un spațiu, cu semnificația din enunț. Dacă *C = 3*, atunci fișierul va mai conține pe a treia linie numărul natural *Q*, iar pe fiecare linie dintre următoarele *Q*, câte două numere naturale separate printr-un spațiu. reprezentând câte o pereche de numere *(A, B)* dintre cele *Q*.
h2. Date de ieșire
În fișierul de ieșire $cartofi.out$ ...
Fișierul $cartofi.out$ va conține:
* Dacă *C = 1*, pe prima linie un număr natural reprezentând răspunsul la cerința *1*.
* Dacă *C = 2*, pe prima linie un număr natural reprezentând răspunsul la cerința *2*.
* Dacă *C = 3*, *Q* linii, câte o linie pentru fiecare pereche *(A, B)* dintre cele *Q*. Linia corespunzătoare fiecărei perechi *(A, B)* va conține un număr natural reprezentând numărul cartofilor produși de plantele aflate în zonele pătratice situate între coloanele cu numerele *A* și *B*, inclusiv aceste valori, reprezentând răspunsul la cerința *3*.
h2. Restricții
* $... ≤ ... ≤ ...$
* $2 ≤ *N* ≤ 5·10[^8^]$
* $3 ≤ *M* ≤ 10[^9^]$
* $*N* ≤ *M*$
* $1 ≤ *A* ≤ *B* ≤ *M*$
* Pentru cerința *1* se acordă *20p*, iar pentru cerințele *2* și *3* se acordă câte *40p*.
* Pentru teste în valoare de *17 puncte*: *N* ≤ 50, *M* ≤ 100 și *Q* ≤ 20
* Pentru alte teste în valoare de *24 puncte*: *N* ≤ 100, *M* ≤ 1000 și *Q* ≤ 10000
* Pentru alte teste în valoare de *31 puncte*: *N* ≤ 1000, *M* ≤ 10000 și *Q* ≤ 100000
h2. Exemplu
h3. Observații:
table(example).
|_. cartofi.in |_. cartofi.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
* Șirul Fibonacci este definit astfel: f[~1~] = 1, f[~2~] = 1 și f[~n~] = f[~n-1~] + f[~n-2~], dacă n ≥ 3, (n este un număr natural nenul).
* O suprafață pătratică din teren este formată *K·K* zone pătratice alăturate dispuse câte *K* pe linie și câte *K* pe coloană, oricare ar fi 1 ≤ *K* ≤ min{N,M}.
h3. Explicație
h2. Exemplu
...
table(example).
|_. 1) |_. cartofi.in |_. cartofi.out |_. Explicații |
|| 1
3 6
| 1
| Se rezolvă cerința *1*.
*N* = 3, *M* = 6.
Primii *N·M* = 18 termeni ai șirului Fibonacci sunt:
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584.
Astfel, numerele cartofilor produși de fiecare plantă din teren sunt cele din Figura *1*.
În teren există o singură plantă care nu a produs niciun cartof (cea din linia 3, coloana 3) |
|_. 2) |_. cartofi.in |_. cartofi.out |_. Explicații |
|| 2
3 6
| 42
| Se rezolvă cerința *2*.
*N* = 3, *M* = 6.
Numerele cartofilor produși de fiecare plantă din teren sunt cele din
tabelul din Figura *1*. Plantele aflate în suprafața pătratică galbenă din
tabelul din Figura *2* au produs cel mai mare număr de cartofi.|
|_. 3) |_. cartofi.in |_. cartofi.out |_. Explicații |
|| 3
5 6
3
1 2
4 6
2 3
| 48
64
43
| Se rezolvă cerința *3*.
*N* = 5, *M* = 6, *Q* = 3.
Tabelul din Figura *3* conține numerele cartofilor produși de fiecare
plantă din teren sunt cele din Figura *3*.
Suma elementelor cuprinse între coloanele (1, 2), inclusiv 1 și 2, este 48.
Suma elementelor cuprinse între coloanele (4, 6), inclusiv 4 și 6, este 64.
Suma elementelor cuprinse între coloanele (2, 3), inclusiv 2 și 3, este 43. |
== include(page="template/taskfooter" task_id="cartofi") ==
