Fișierul intrare/ieșire	cartofi.in, cartofi.out	Sursă	OJSEPI 2021 clasa a 8-a
Autor	Flavius Boian	Adăugată de	Mircea Rebengiuc • mircea_007
Timp de execuție pe test	0.1 sec	Limită de memorie	65536 KB
Scorul tău	N/A	Dificultate	2.25

Poți vedea testele pentru această problemă accesând atașamentele .

Vezi soluțiile trimise | Statistici

Cartofi (clasa a 8-a)

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).

Cerințe

Scrieți un program care citește numerele N și M (cu semnificația din enunț), iar apoi determină:

1. numărul plantelor din teren care nu au produs niciun cartof;
2. numărul maxim de cartofi care pot fi produși de plantele dintr-o suprafață pătratică din terenul fermierului;
3. pentru fiecare dintre cele Q perechi de numere (A, B) citite, numărul cartofilor produși de plantele aflate în zonele pătratice situate între coloanele cu numerele A și B, inclusiv acestea.

Date de intrare

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.

Date de ieșire

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.

Restricții

• 2 ≤ N ≤ 5·10⁸
• 3 ≤ M ≤ 10⁹
• 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

Observații:

• Șirul Fibonacci este definit astfel: f₁ = 1, f₂ = 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}.

Exemplu