bojenje
Nastavnik likovnog je dao zadatak ucenicima da oboje traku tkanine u odredenom dezenu. Da bi lakše objasnio dezen, on je na tabli nacrtao traku, podelio je vertikalnim crtama na N kvadratica i svakom kvadraticu dodelio neku boju. Mali Mica se dosetio da njegova baka ima mašinu za bojenje tkanine koja radi po sledecem principu: Ubaci se novcic; pozicionira se pocetak dela koji se boji; pozicionira se kraj dela koji se boji; izabere se boja; konacno, pretisne se dugme «Start» i mašina oboji deo tkanine od pocetnog do krajnjeg dela zadatom bojom, prekrivajuci pri tom sve boje koje su prethodno bile nanete na tom delu. Mali Mica želi da potroši što manje novcica, pa je vas zamolio da mu pomognete u tome.
Vaš zadatak je da napišete program koji za zadati dezen nalazi najmanji broj novcica sa kojima mali Mica može da obavi zadatak, kao i nacin na koji treba upravljati mašinom da bi se to ostvarilo. Pretpostavka je da se kvadratici numerišu s leva udesno brojevima od 1 do N, a boje se zadaju celim brojevima od 1 do K, gde je K broj korišcenih boja. Jedno bojenje je odredeno sa tri broja a, b i c koji redom predstavljaju pocetni i krajnji kvadratic i boju dela trake koji se boji. <br><br>
Ulaz: U prvom redu standardnog ulaza nalaze se dva cela broja N i K razdvojena blanko znakom (1 <= N ,K <= 300) koji predstavljaju dužinu tkanine u kvadraticima (broj kvadratica) i broj korišcenih boja, respektivno. U svakom od narednih N redova nalazi se po jedan ceo broj koji predstavlja boju odgovarajuceg kvadratica (posmatrano s leva na desno), onako kako je nastavnik zadao u dezenu. <br><br>
Izlaz: U prvi red standardnog izlaza ispisati ceo broj M koji predstavlja minimalan broj novcica potreban malom Mici. U svaki od narednih M redova ispisati tri broja a, b i c razdvojenih blako znakom, koji predstavljaju jedno bojenje. Bojenja moraju biti takva da, ako se redom primenjuju, daju zadati dezen. Ukoliko postoji više rešenja za niz bojenja, štampati bilo koje. <br><br>
Primer:
<br><br>
Ulaz: <br>7 3<br>1<br>2<br>3<br>
2<br>1<br>3<br>1<br><br>
Izlaz: <br>4<br>1 7 1<br>
2 4 2<br>3 3 3<br>6 6 3<br><br>
Objašnjenje: Prvo se cela traka ofarba bojom 1, potom se deo od 2-og do 4-og kvadratica (ukljucujuci i ta dva) ofarba bojom 2, zatim se 3-i kvadratic ofarba bojom 3 i na kraju se 6-i kvadratic ofarba bojom 3.
Vaš zadatak je da napišete program koji za zadati dezen nalazi najmanji broj novcica sa kojima mali Mica može da obavi zadatak, kao i nacin na koji treba upravljati mašinom da bi se to ostvarilo. Pretpostavka je da se kvadratici numerišu s leva udesno brojevima od 1 do N, a boje se zadaju celim brojevima od 1 do K, gde je K broj korišcenih boja. Jedno bojenje je odredeno sa tri broja a, b i c koji redom predstavljaju pocetni i krajnji kvadratic i boju dela trake koji se boji. <br><br>
Ulaz: U prvom redu standardnog ulaza nalaze se dva cela broja N i K razdvojena blanko znakom (1 <= N ,K <= 300) koji predstavljaju dužinu tkanine u kvadraticima (broj kvadratica) i broj korišcenih boja, respektivno. U svakom od narednih N redova nalazi se po jedan ceo broj koji predstavlja boju odgovarajuceg kvadratica (posmatrano s leva na desno), onako kako je nastavnik zadao u dezenu. <br><br>
Izlaz: U prvi red standardnog izlaza ispisati ceo broj M koji predstavlja minimalan broj novcica potreban malom Mici. U svaki od narednih M redova ispisati tri broja a, b i c razdvojenih blako znakom, koji predstavljaju jedno bojenje. Bojenja moraju biti takva da, ako se redom primenjuju, daju zadati dezen. Ukoliko postoji više rešenja za niz bojenja, štampati bilo koje. <br><br>
Primer:
<br><br>
Ulaz: <br>7 3<br>1<br>2<br>3<br>
2<br>1<br>3<br>1<br><br>
Izlaz: <br>4<br>1 7 1<br>
2 4 2<br>3 3 3<br>6 6 3<br><br>
Objašnjenje: Prvo se cela traka ofarba bojom 1, potom se deo od 2-og do 4-og kvadratica (ukljucujuci i ta dva) ofarba bojom 2, zatim se 3-i kvadratic ofarba bojom 3 i na kraju se 6-i kvadratic ofarba bojom 3.
Submit solution
Coming laterThe grading service will be connected in a later migration step. You can inspect the task and your previous results now.