Taisnleņķa koordinātu sistēmā ir uzzīmēts telpas sānskats. Grīda ir attēlota ar nogriezni, kas sākas punktā (0,0) un beidzas punktā (N,0). Griesti ir attēloti kā lauzta līnija, kuras sākumpunkta x-koordināta ir 0, bet beigu punkta x-koordināta ir N. Tā sastāv no horizontāliem un vertikāliem posmiem, kuru garumi ir veseli skaitļi (pēc horizontāla posma vienmēr seko vertikāls posms un otrādi). Zināms, ka katras lauztās līnijas virsotnes x-koordināta ir lielāka vai vienāda ar iepriekšējās virsotnes x-koordinātu. Visu virsotņu y-koordinātas ir naturāli skaitļi. Pirmais un pēdējais lauztās līnijas posms ir horizontāls.
Jebkura griestu horizontālā posma punktos ar veselām koordinātām (ieskaitot tā galapunktus) iespējams novietot punktveida lampu. Lampa izstaro gaismu uz leju 45° leņķī uz kreiso un labo pusi.
Zīmējumos parādīti divi atšķirīgi visas grīdas apgaismošanas varianti, izmantojot trīs lampas (grīda un griesti iezīmēti ar biezāku līniju). Zīmējumā pa kreisi lampas novietotas punktos ar koordinātām (2,2), (5,1) un (9,3), un apgaismotie grīdas segmenti ir attiecīgi [0;4], [4;6] un [6;10] (uzskatām, ka kādas lampas apgaismotais grīdas segments vienmēr ietver abus galapunktus). Zīmējumā pa labi lampas novietotas punktos ar koordinātām (0,3), (4,5) un (8,3). Apgaismotie grīdas segmenti ir attiecīgi [0;3], [2⅓;5¼], [5;10]. Redzam, ka abos variantos ar šādi novietotām trim lampām visa grīda (nogrieznis [0; 10]) tiek apgaismota.
Uzrakstiet programmu, kas dotai griestu konfigurācijai atrod mazāko iespējamo lampu skaitu, kāds nepieciešams, lai varētu apgaismot visu grīdu!
Teksta faila lampas2.dat pirmajā rindā dots vesels pozitīvs skaitlis N (N ≤ 100 000) - grīdas garums. Nākamajā rindā doti N naturāli skaitļi. i-tais skaitlis apzīmē griestu augstumu segmentā [i-1;i] katram i (1 ≤ i ≤ N). Neviena skaitļa vērtība nepārsniedz 20 000. Katri divi blakusskaitļi atdalīti ar tukšumzīmi.
Teksta faila lampas2.rez vienīgajā rindā jāizvada vesels skaitlis - mazākais iespējamais lampu skaits, kāds nepieciešams, lai varētu apgaismot visu grīdu.
| lampas2.dat | lampas2.rez |
10 3 2 2 5 5 1 2 3 3 3 |
3 |
| lampas2.dat | lampas2.rez |
2 3 1 |
1 |
| lampas2.dat | lampas2.rez |
4 1 1 1 1 |
2 |