Nosaukums
Lokomotīves (loko)
Laika limits
1.00s
Atmiņas limits
256.0 MB
Grūtība
84%

Definīcija

Uz bezgalīgi gara taisna sliežu ceļa vienādos attālumos viena no otras atrodas N lokomotīves. Katrai lokomotīvei ir unikāls numurs – naturāls skaitlis no 1 līdz N. Lokomotīves numurs norāda tās maksimālo kustības ātrumu kilometros stundā. Visas lokomotīves vienlaicīgi sāk kustēties uz priekšu (zīmējumā – pa labi) ar maksimālo iespējamo ātrumu. Ja kāda lokomotīve panāk priekšā braucošu lēnāku lokomotīvi, tā samazina kustības ātrumu un turpina braukt ar priekšā braucošās lokomotīves ātrumu. Pēc kāda laika visas lokomotīves ir sadalījušās grupās, kas turpmāk vairs nemainās.

Piemēram, sākumā sešas lokomotīves var būt izvietotas šādi:

Tad pēc kāda laika pēc kustības uzsākšanas tās sadalīsies trīs grupās, kas katra pārvietojas ar vienu noteiktu ātrumu:

Ievērojiet, ka grupā var būt arī tikai viena lokomotīve!

Uzrakstiet programmu, kas dotam sākotnējam lokomotīvju novietojumam nosaka, cik pastāvīgās grupās tās sadalīsies!

 


Ievaddatu raksturojums

Pirmajā rindā dots naturāls skaitlis N (lokomotīvju skaits, N ≤ 1 000 000). Otrajā datnes rindā doti N dažādi naturāli skaitļi robežās no 1 līdz N - lokomotīvju numuri tādā secībā, kādā tās atrodas uz sliežu ceļa, sākot ar braukšanas virzienā pēdējo. Starp katriem diviem blakusesošiem skaitļiem ir viena tukšumzīme.

 


Izvaddatu raksturojums

Vienīgajā rindā jāizvada viens naturāls skaitlis - grupu skaits, kādā sadalīsies lokomotīves.

 


Piezīmes

loko.dat loko.rez  
6
6 2 1 4 3 5
3
Piemērs atbilst dotajam zīmējumam.
   
loko.dat loko.rez  
6
1 2 3 4 6 5
5
 

 
Uzdevums izmantots Latvijas 22. informātikas olimpiādē 2009. gadā.


Uzdevums tiek aizsargāts ar autortiesībām un tā kopēšana vai neatļauta izmantošana ir aizliegta.