apraksts uzdevumi suutiit jauns statuss rezultati helps apraksts

cards2 Kāršu kārtošana 1 sek.


 Uzdevums

Mazajam Maverikam patīk spēlēt kārtis, bet lielas raizes viņam sagādā kāršu sakārtošana rokā. Kad Maveriks ir pacēlis sev pienākošās kārtis, viņš vispirms tās sakārto grupās tā, lai katrā grupā būtu visas vienas krāsas kārtis. Pēc tam viņš sakārto kārtis katrā grupā pēc to vērtības - kārtij ar zemāku vērtību grupā jāatrodas vairāk pa kreisi. Protams, ka šo kārtošanu laikā visas kārtis jātur rokā.

Maveriks vēlas sakārtot kārtis cik ātri vien iespējams, t.i., izdarot pēc iespējas mazāk gājienu. "Gājiens" ir vienas kārts pārvietošana.

Uzrakstiet programmu, kas nosaka, kāds ir mazākais iespējamais gājienu skaits!

 
 Ievaddati

Teksta faila cards2.in pirmā rinda satur divu naturālu skaitļu C(dažādo krāsu skaits,1 ≤C≤4) un N(vienas krāsas kāršu skaits, 1≤N≤100) vērtības, kas atdalītas ar tukšumsimbolu.

Katra no nākošajām C*N faila rindām satur pa diviem naturāliem skaitļiem X un Y, 1≤X≤C, 1≤Y≤N, kas atdalīti ar tukšumsimbolu. Katrs šāds skaitļu pāris apzīmē vienas kārts krāsu (X) un vērtību(Y). Kāršu secība ir tāda, kādā kārtis Maveriks ir tās pacēlis.

Visas kārtis savā starpā ir dažādas.

 
 Izvaddati

Teksta faila cards2.out vienīgajā rindā jāizvada vesels skaitlis - mazākais gājienu skaits, kāds nepieciešams, lai kārtis sakārtotu.

 
 Piemērs

cards2.incards2.out
2 2
2 1
1 2
1 1
2 2
2
  
cards2.incards2.out
4 1
2 1
3 1
1 1
4 1
0
  
cards2.incards2.out
3 2
3 2
2 2
1 1
3 1
2 1
1 2
2

 
 Atsauces
Uzdevums izmantots Horvātijas informātikas olimpiādē 2001.gadā

Drukāšanai

 

Copyright © 2001 Girts Folkmanis, LIIS