Fişierul intrare/ieşire:soricel.in, soricel.outSursăONI 2017 clasa a 6-a
AutorFlavius BoianAdăugată defrancuCristian Francu francu
Timp execuţie pe test0.6 secLimită de memorie8192 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise

Ș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 Cij 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 ≤ Cij ≤ 108
  • 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 109;
  • 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 ≤ Cij ≤ 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

soricel.insoricel.outExplicaţie
1
5 4 1
2 6 5 10
25 16 0 5
100 17 67 3
20 104 8 13
53 13 55 47
19
5
La finalul primei zile, depozitul va arăta astfel:
 
0 5 0 0
24 15 0 0
99 0 66 2
19 103 7 12
52 12 54 46
 
deoarece Remy a mâncat câte un cubuleţ din fiecare cameră şi apoi John
a golit camerele în care numărul de cubuleţe rămase era pătrat perfect.
Urmând aceleaşi etape, în fiecare zi Remy va putea să mănânce timp de
19 zile din depozit (după 19 zile toate camerele sunt goale deoarece
toate numerele au ajuns să fie pătrate perfecte sau valori nule).
În ziua 1 John va fura caşcavalul din 5 camere, cele care au
coordonatele: (1,1), (1,3), (1,4), (2,4), (3,2).
2
5 4 1
2 6 5 10
25 16 0 5
100 17 67 3
20 104 8 13
53 13 55 47
6
4
În ziua a 4-a John va goli 6 camere, cele cu coordonatele: (4,4),
(4,3), (4,2), (4,1), (5,1) şi (5,2). Aceasta este cea mai lungă
secvenţă de camere consecutive golite în aceeaşi zi.
Trebuie sa te autentifici pentru a trimite solutii. Click aici