Elektroniskā pasta ziņojumi

ID: epasts
Grūtība: 3/5
Laika limits: 1

Uzdevums

Arčibalds ir pierakstījies uz vairākām vēstkopām, no kurām pienāk elektroniskā pasta ziņojumi par noteiktām tēmām. Lai varētu apstrādāt šos ziņojumus, Arčibalds ir izveidojis vairākas elektroniskas mapītes, kur katra atbilst kādai no tēmām. Pirms lasīt kādu ziņojumu, Arčibalds pārnes ziņojumu tam atbilstošajā mapītē. Pasta programma vienas operācijas laikā ļauj attiecīgajā mapītē no visa ienākušo jauno ziņojuma saraksta pārnest

Pārnešana nav noteikti jāsāk no jauno ziņojumu saraksta sākuma. Pirms ziņojumu lasīšanas Arčibaldam visi ziņojumi jāpārnes uz tiem paredzētajām mapītēm. Protams, ka viņš vēlas izdarīt to ar pēc iespējas maz operācijām.

Pieņemsim, ka Arčibalds būtu parakstījies uz anekdotēm, jautriem notikumiem, sporta vēstīm un laika prognozi. Ja jauno ziņojumu sarakstā kādu dienu ziņojumi ir sekojošā kārtībā:

Pārnest ziņojumus var sekojoši: vispirms divus "Jautro notikumu" ziņojumus, tad laika prognozi, tad anekdotes un, visbeidzot, visas sporta vēstis. Kopumā būs veiktas četras operācijas.

Uzrakstiet programmu, kas nosaka mazāko operāciju skaitu, kāds nepieciešams, lai pārnestu visus ziņojumus uz tiem paredzētajām mapītēm!

 

Ievaddati

Teksta faila epasts.in vienīgā rinda satur naturālu skaitli N 0 <N < 200, kas apzīmē jauno ziņojumu skaitu un N veselus skaitļus, kas norāda tiem atbilstošo tēmu numurus. Tēmu numuri var būt diapazonā no -32768 līdz 32767. Katri divi blakus skaitļi ievaddatos ir atdalīti ar tukšumsimbolu.

 

Izvaddati

Teksta faila epasts.out vienīgajā rindā jāizvada naturāls skaitlis - mazākais operāciju skaits, kāds nepieciešams, lai pārnestu visus ziņojumus uz tiem paredzētajām mapītēm.

 

Piemērs

epasts.inepasts.out
7 1 3 4 3 2 2 3
4

Piemērā dotie dati atbilst uzdevuma tekstā aplūkotajam piemēram, ja anekdotēm atbilst numurs 1, jautriem stāstiņiem - 2, sporta vēstīm - 3 un laika prognozei - 4.

 

Atsauces

Uzdevums izmantots Ukrainas XIII informātikas olimpiādē 2000.gadā.
© 2001-2002 olimps! http://www.lio.lv/olimps/