apraksts uzdevumi suutiit jauns statuss rezultati helps apraksts

muris Mūra siena 1 sek.


 Uzdevums

Kādas senas celtnes mūra sienā gadu gaitā ir izveidojies caurums. Kodētā veidā to apraksta matrica no m rindām un n kolonnām, kur 1 apzīmē, ka šajā vietā siena ir saglabājusies, bet 0 - ka nav (mūrī ir caurums).

Piemēram (m=5, n=10):

1110000111
1100001111
1000000011
1111101111
1110000111

Sienā esošo caurumu aiztaisīšanai var izmantot dažāda augstuma blokus, kuru platums ir viena, bet augstums - k vienības, 1<=k<=m.
Uzrakstiet programmu, kas dotam sienas aprakstam nosaka, kāds mazākais skaits kāda augstuma bloku nepieciešams, lai aizmūrētu visus sienā esošos caurumus.

 
 Ievaddati

Teksta faila muris.in pirmā rinda satur divu naturālu skaitļu m (sienas augstums) un n (sienas platums) vērtības, kas atdalītas ar tukšumsimbolu. Zināms, ka 1<=m,n<=200.
Nākošajās m faila rindās ir dots sienas apraksts. Katrā rindā ir tieši n simboli (0 vai 1) bez atdalošajiem tukšumsimboliem.

 
 Izvaddati

Teksta failā muris.out jāizvada sienas aiztaisīšanai nepieciešamo bloku skaits to augstumu pieaugšanas secībā. Informācija par attiecīgā augstuma blokiem jāizvada tikai tad, ja šī augstuma bloki ir nepieciešami.Katrai faila rindai jāsatur divi naturāli skaitļi ki un pi, kas atdalīti ar tukšumsimbolu. ki ir attiecīgā garuma bloka augsums un pi - nepieciešamais šī augstuma bloku skaits.

 
 Piemērs

muris.inmuris.out
5 10
1110000111
1100001111
1000000011
1111101111
1110000111
1 7
2 1
3 2
5 1

 
 Atsauces
Uzdevums izmantots Rumānijas informātikas olimpiādē 2002.gadā.

Drukāšanai

 

Copyright © 2001 Girts Folkmanis, LIIS