filmovi
Kako se mali Dragan?e iz tre?eg zadatka nije proslavio u matematici i programiranju, roditelji su mu smanjili džeparac. Zato je on rešio da iskoristi svoju veliku kolekciju DVD filmova i odlu?io da prodaje filmove po niskim cenama. Svaki film se nalazi na jednom DVD-u, a na Dragan?etovom hard disku može stati najviše k filmova. Procedura rezanja je slede?a: ukoliko se traženi film nalazi na hard disku, Dragan?e odmah po?inje sa rezanjem; u suprotnom on mora da na?e odgovaraju?i DVD i presnimi ga na hard disk. Ako na disku nema slobodnog prostora, on mora da obriše neki film. Traženje DVD-a i presnimavanje iziskuje puno vremena, i zato Dragan?e želi da smanji taj broj. Na po?etku je njegov disk prazan.<br><br>
On je napravio spisak poru?enih filmova i zna ta?no redosled n kupaca koji dolaze da nasnime omiljeni film. Dragan?e je uspeo da minimizira broj prebacivanja filmova na HDD (a samim tim i ?ekanje kupaca). Da li i vi možete da izra?unate koliko ?e najmanje puta Dragan?e ipak morati da presnimi neki film na hard disk?<br><br>
Ulaz:<br><br>
(Ulazni podaci se ucitavaju sa standardnog ulaza) U prvom se nalaze dva prirodna broja n i k. Broj n predstavlja broj naru?enih filmova, a broj k je broj filmova koji može da stane na disku. U slede?ih n redova nalaze se redni brojevi filmova a[i] koje kupci uzimaju, pore?ani po vremenu dolaska<br><br>
Izlaz:<br><br>
(Izlazne podatke ispisati na standardni izlaz) U prvom i jedinom redu štampati minimalan broj presnimavanja DVD-a na hard disk.<br><br>
Ograni?enja:<br><br>
* 1 ? n ? 10000<br>
* 1 ? k ? 500<br>
* 1 ? a[i] ? 10000<br>
<br>
Primeri:<br><br>
Ulaz:<br>
5 2<br>
1<br>
2<br>
2<br>
4<br>
1<br>
<br>
Izlaz:<br>
3<br>
<br>
Objašnjenje:<br>
<br>
lj Kako je hard disk na po?etku prazan, Dragan?e mora da presnimi film sa rednim brojem 1. Zatim, mora da presnimi film broj 2. Slede?i kupac naru?uje film koji se ve? nalazi na disku, tako da ga Dragan?e odmah nareže. Naredni kupac traži film 4, tako da Dragan?e briše film broj 2 i presnimava preko film broj 4. Poslednji film koji se traži je broj 1, tako da Dragan?e ne mora da ga traži, jer se na hard disku nalaze filmovi 4 i 1.
<br><br>
Ulaz:<br>
10 3<br>
2<br>
3<br>
2<br>
1<br>
5<br>
2<br>
4<br>
5<br>
3<br>
2<br>
<br>
Izlaz:<br>
6<br>
On je napravio spisak poru?enih filmova i zna ta?no redosled n kupaca koji dolaze da nasnime omiljeni film. Dragan?e je uspeo da minimizira broj prebacivanja filmova na HDD (a samim tim i ?ekanje kupaca). Da li i vi možete da izra?unate koliko ?e najmanje puta Dragan?e ipak morati da presnimi neki film na hard disk?<br><br>
Ulaz:<br><br>
(Ulazni podaci se ucitavaju sa standardnog ulaza) U prvom se nalaze dva prirodna broja n i k. Broj n predstavlja broj naru?enih filmova, a broj k je broj filmova koji može da stane na disku. U slede?ih n redova nalaze se redni brojevi filmova a[i] koje kupci uzimaju, pore?ani po vremenu dolaska<br><br>
Izlaz:<br><br>
(Izlazne podatke ispisati na standardni izlaz) U prvom i jedinom redu štampati minimalan broj presnimavanja DVD-a na hard disk.<br><br>
Ograni?enja:<br><br>
* 1 ? n ? 10000<br>
* 1 ? k ? 500<br>
* 1 ? a[i] ? 10000<br>
<br>
Primeri:<br><br>
Ulaz:<br>
5 2<br>
1<br>
2<br>
2<br>
4<br>
1<br>
<br>
Izlaz:<br>
3<br>
<br>
Objašnjenje:<br>
<br>
lj Kako je hard disk na po?etku prazan, Dragan?e mora da presnimi film sa rednim brojem 1. Zatim, mora da presnimi film broj 2. Slede?i kupac naru?uje film koji se ve? nalazi na disku, tako da ga Dragan?e odmah nareže. Naredni kupac traži film 4, tako da Dragan?e briše film broj 2 i presnimava preko film broj 4. Poslednji film koji se traži je broj 1, tako da Dragan?e ne mora da ga traži, jer se na hard disku nalaze filmovi 4 i 1.
<br><br>
Ulaz:<br>
10 3<br>
2<br>
3<br>
2<br>
1<br>
5<br>
2<br>
4<br>
5<br>
3<br>
2<br>
<br>
Izlaz:<br>
6<br>
Submit solution
Coming laterThe grading service will be connected in a later migration step. You can inspect the task and your previous results now.