apraksts uzdevumi suutiit jauns statuss rezultati helps apraksts

serials Seriāls diskos 5 sek.


 Uzdevums

Vecmāmiņai Aldai mīļākais seriāls ir “Mīlestības bedre”. Šim seriālam ir S sērijas. Katrai sērijai ir savs garums sekundēs. Aldas mazdēls Andris ir dabūjis visas “Mīlestības bedres” sērijas un grib iepriecināt vecmāmiņu, tai uzdāvinot visu sēriju ierakstus DVD diskos, lai vecmāmiņa varētu labi pavadīt laiku no rīta līdz vakaram un lai nejaušas iesnaušanās (kas Aldai gadās) neradītu satraukumu par neredzētām sērijām. Andrim ir pietiekams daudzums vienādu DVD matricu, lai ierakstītu visas sērijas. Katrā matricā var ierakstīt X sekundes.

Andris grib ievērot šādus principus:

  1. Katrai sērijai ir jāaizņem minimālais disku skaits (piemēram, ja sērijas ierakstam vajag 10 diskus, bet tās fragmentus gribas ierakstīt 12 dažādos diskos, tad to nedrīkst darīt);
  2. Sērijas jāieraksta diskos hronoloģiskā secībā, t.i., to secību nedrīkst mainīt.

Uzrakstiet programmu, kas aprēķina mazāko iespējamo disku skaitu, kādā var ierakstīt visas seriāla sērijas, ievērojot Andra principus!

 
 Ievaddati

Teksta faila serials.dat pirmajā rindā doti divi naturāli skaitļi S (S ≤ 106 ) un X (X ≤ 106), kas atdalīti ar tukšumzīmi. Katrā no nākamajām S faila rindām dots naturāls skaitlis, kas nepārsniedz 106, - vienas seriāla sērijas garums sekundēs. Ievaddatu (i+1)-ajā rindā ir dots i-tās sērijas garums.

 
 Izvaddati

Teksta faila serials.rez vienīgajā rindā jāizvada viens naturāls skaitlis - mazākais disku skaits, kādā var ierakstīt visas seriāla sērijas.

 
 Piemērs

serials.datserials.rez
4 5
3
4
2
1
3
Vienīgais variants ir – pirmajā diskā ierakstīt pirmo sēriju, otrajā – otro, bet trešajā – trešo un ceturto sēriju.
  
serials.datserials.rez
2 5
7
7
3
Piemēram, pirmajā diskā var ierakstīt pirmās sērijas pirmās piecas sekundes. Otrajā diskā – pirmās sērijas atlikušās divas sekundes, kā arī pirmās divas sekundes no otrās sērijas. Trešajā diskā – otrās sērijas atlikušās piecas sekundes.

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

Drukāšanai

 

Copyright © 2001 Girts Folkmanis, LIIS