Fișierul intrare/ieșire	soricel.in, soricel.out	Sursă	ONI 2017 clasa a 6-a
Autor	Flavius Boian	Adăugată de	Cristian Frâncu • francu
Timp de execuție pe test	0.6 sec	Limită de memorie	8192 KB
Scorul tău	N/A	Dificultate	4

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

Vezi soluțiile trimise | Statistici

Șoricel (clasa a 6-a)

Notă: datele de ieșire vor fi afișate diferit față de enunțul original al problemei.

Șoricelul Remy dorește să depoziteze cubulețele de cașcaval pe care le-a adunat. El a construit un depozit pe o suprafață dreptunghiulară și l-a compartimentat în N*M camere identice. În fiecare cameră șoricelul a depozitat o cantitate de cubulețe de cașcaval (ca în Figura A) și a stabilit că va mânca în fiecare zi câte un cubuleț de cașcaval din fiecare cameră în care există cașcaval. Planul său este stricat de John, șoricelul leneș din casa vecină, căruia nu-i place să-și strângă singur cașcaval, așa că s-a hotărât să fure din depozitul lui Remy. Pentru că John este pasionat de matematică s-a hotărât ca în fiecare seară, după ce vecinul său a terminat de mâncat, să se plimbe prin depozit și să fure tot cașcavalul din camerele în care găsește un număr pătrat perfect de cubulețe de cașcaval. John intră în depozit prin camera din colțul stânga sus, de coordonate (1,1), parcurge prima linie de la prima la ultima coloană, apoi a doua linie de la ultima coloană, până la prima și așa mai departe, până când termină de vizitat toate camerele (ca în Figura B).

Cerințe

Scrieți un program care să determine:

1. Numărul de zile în care se va goli depozitul lui Remy și câte camere va goli John în ziua K.
2. Numărul maxim de camere consecutive golite de acesta într-o zi și ziua în care se va întâmpla acest lucru.

Date de intrare

Fișierul de intrare soricel.in conține pe prima linie numărul natural P reprezentând cerința din problemă care trebuie rezolvată. Pe a doua linie vor fi cele trei numere naturale nenule N, M și K, separate prin câte un spațiu, cu semnificațiile din enunț. Pe fiecare dintre următoarele N linii se află câte M numere naturale separate prin câte un spațiu, reprezentând numărul de cubulețe de cașcaval C_ij depozitate în camera de coordonate (i,j).

Date de ieșire

Dacă valoarea lui P este 1, fișierul de ieșire soricel.out va conține cele două valori conform cerinței 1, astfel: pe prima linie numărul de zile în care se va goli depozitul, iar pe a doua linie numărul de camere golite de John în ziua K.

Dacă valoarea lui P este 2, fișierul de ieșire soricel.out va conține cele două valori conform cerinței 2, astfel: pe prima linie numărul maxim de camere consecutive golite de John într-o zi, iar pe a doua linie numărul zilei în care se va întâmpla acest lucru.

Restricții

• 1 ≤ N, M ≤ 200
• 0 ≤ C_ij ≤ 10⁸
• 1 ≤ K ≤ numărul de zile până când depozitul va fi gol;
• există cel puțin o cameră care conține mai mult de un cubuleț de cașcaval;
• numărul total de bucăți de cașcaval furate din camere consecutive într-o zi nu va depăși 10⁹;
• ziua în care începe să mănânce Remy este considerată ziua 1;
• dacă există două sau mai multe zile în care John golește un număr egal de camere consecutive, se va afișa ziua în care a mâncat cele mai multe cubulețe de cașcaval într-o secvență de camere consecutive, iar dacă și aceste cantități sunt egale, se va afișa numărul zilei cu valoarea cea mai mare;
• considerăm că liniile se numerotează de sus în jos începând cu 1, iar coloanele de la stânga la dreapta începând cu 1;
• pentru rezolvarea corectă a cerinței 1 se acordă 40 de puncte, iar dacă pentru fiecare test se afișează corect doar prima valoare, se acordă jumătate din punctajul aferent testului respectiv;
• pentru prima cerință vor exista și teste în valoare de 20 de puncte, pentru care 0 ≤ C_ij ≤ 1000, iar N, M ≤ 30;
• pentru rezolvarea corectă a cerinței 2 se acordă 60 de puncte, iar dacă pentru fiecare test se afișează corect doar prima valoare, se acordă două treimi din punctajul aferent testului respectiv.

Exemple