Fişierul intrare/ieşire:	inundatie.in, inundatie.out	Sursă	ONI 2022, clasa a 6-a
Autor	Cristian Francu	Adăugată de	George Barbu •george.barbu
Timp execuţie pe test	0.6 sec	Limită de memorie	65536 kbytes
Scorul tău	N/A	Dificultate	4/5

Vezi solutiile trimise | Statistici

Inundație

Fie un şir de N coloane de ciment (poziţiile lor fiind numerotate de la 1 la N) de aceeaşi lăţime şi diverse înălţimi. Ele sunt încadrate la stânga (poziţia 0) şi la dreapta (poziţia N+1) de ziduri foarte înalte. Apa începe să curgă de deasupra primei coloane, câte o pătrăţică de apă pe secundă. Apa se acumulează dacă are pereţi în stânga şi în dreapta, altfel curge mai jos către dreapta. Deasupra fiecărei coloane de ciment se poate forma astfel o coloană de apă, cu înălţimea egală cu numărul de pătrăţele de la nivelul apei până la zona de contact cu coloana de ciment.

Cerinţe

• Care este înălţimea H a celei mai înalte coloane de apă după ce apa a ajuns peste tot la înălţimea celei mai înalte coloane de ciment?
• Care este numărul T de secunde în care apa ajunge să acopere coloana numărul P?
• Care este poziţia D a celei mai din dreapta coloane acoperită de apă după S secunde?
• Care este poziţia R a celei mai din stânga coloane pe care o putem reduce cu o unitate astfel încât apa să ajungă cât mai repede la coloana P?

Date de intrare

Fişierul de intrare inundatie.in conţine pe prima linie un număr natural C, reprezentând cerinţa ce trebuie rezolvată (1,2,3, sau 4).
Pe a doua linie numerele N, P şi S despărţite prin câte un spaţiu cu semnificaţia din enunţ.
Pe a treia linie se găsesc N numere naturale separate prin câte un spaţiu ce reprezintă înălţimile coloanelor.

Date de ieşire

În fişierul de ieşire inundatie.out va conţine un singur număr, astfel:

• Dacă C = 1: înălţimea H cu semnificaţia de mai sus.
• Dacă C = 2: timpul T cu semnificaţia de mai sus.
• Dacă C = 3: poziţia D cu semnificaţia de mai sus.
• Dacă C = 4: poziţia R cu semnificaţia de mai sus.

Restricţii

• C ∈ {1,2,3,4};
• 3 ≤ N ≤ 100.000
• 1 ≤ înălţimea oricărei coloane din şir ≤ 20.000
• 1 ≤ P ≤ N
• 1 ≤ S ≤ 100.000
• O coloană de înălţime h este acoperită de apă dacă apa a ajuns la înălţimea h.

Observaţii legate de distribuţia punctelor:

• Pentru cerinţa C = 1 se pot obţine 11 puncte;
• Pentru cerinţa C = 2 se pot obţine 25 puncte;
• Pentru cerinţa C = 3 se pot obţine 33 puncte;
• Pentru cerinţa C = 4 se pot obţine 31 puncte;

Exemple

inundatie.in	inundatie.out
1 32 15 45 8 5 5 4 3 3 7 5 4 3 3 5 4 3 4 5 6 5 4 4 3 4 5 4 3 2 1 2 3 4 5 9	8
2 32 15 45 8 5 5 4 3 3 7 5 4 3 3 5 4 3 4 5 6 5 4 4 3 4 5 4 3 2 1 2 3 4 5 9	21
3 32 15 45 8 5 5 4 3 3 7 5 4 3 3 5 4 3 4 5 6 5 4 4 3 4 5 4 3 2 1 2 3 4 5 9	29
4 32 15 45 8 5 5 4 3 3 7 5 4 3 3 5 4 3 4 5 6 5 4 4 3 4 5 4 3 2 1 2 3 4 5 9	7

Explicaţii

Toate exemplele se referă la figura de mai sus, diferă doar numărul cerinţei. În toate N = 32, P = 15 şi S = 45.
Primul exemplu: Linia portocalie de înălţime 9 este nivelul apei la momentul când toate coloanele devin acoperite de apă. Cea mai înaltă coloană de apă este cea cu numărul 27, având 8 pătrăţele de apă.
Al doilea exemplu: În imaginea de mai sus, liniile roşii arată nivelurile apei la momentul când apa acoperă coloana de la poziţia P = 15. Observăm că sunt 21 de pătrăţele de apă sub linie, deci este nevoie de 21 de secunde pentru a acoperi coloana 15.
Al treilea exemplu: Linia verde arată nivelul apei după 42 de secunde. Ea acoperă coloana numărul 29. Lăsând apa să curgă încă 3 secunde (până la cele S = 45 secunde) nivelul nu se ridică suficient pentru a ajunge la coloana 30 deoarece ar mai fi nevoie de 5 pătrăţele de apă, adică încă 5 secunde.
Al patrulea exemplu: Cea mai din stânga coloană pe care o vom reduce cu unu este coloana numărul 7. Astfel apa va ajunge cu 5 secunde mai devreme în coloana P = 15. Linia maro (linia de apă de înălţime 6 care se întinde de la coloana 2 la coloana 6) arată cele 5 pătrăţele cu care reducem timpul. Orice altă coloană am reduce nu va ajunge aşa repede.