[RTK-tekmovalci] Ogrevanje

Čet Mar 27 14:29:57 CET 2008

Pozdravljeni, tekmovalci!

Že to soboto bo šlo zares, zato smo samo za vas pripravili dve nalogi za
ogrevanje.
Svoje rešitve lahko pošljete do sobote na naslednji e-naslov:
nino.basic na gmail.com
Tiste ki boste poslali rešitve ogrevalnih nalog in boste prisotni na
tekmovanju
čakajo simbolične nagrade ;-)

----------------------------------------------------------------------------------

*** Izpis HTMLja ***

Mislimo si preprost dokument v jeziku HTML — poleg besedila vsebuje še
oznake
oblike <ime> in </ime>, pri čemer je "ime" ime enega od elementov jezika
HTML.
(Jezik HTML dovoli v oznakah sicer tudi še presledke in atribute, v besedilu
pa
komentarje, vendar predpostavimo, da v naših dokumentih teh reči ne bo.)

Napiši program, ki prebere s standardnega vhoda (ali pa datoteke) nek takšen
dokument v jeziku HTML, in za tisti del dokumenta, ki leži med oznakama
<body>
in </body>, izpiše vse besedilo (ne pa tudi oznak). Pri izpisu naj tudi
skoči v
novo vrstico na vsakem takem mestu, kjer se v vhodnem dokumentu pojavi
oznaka
<br> oziroma <br/>.

----------------------------------------------------------------------------------

*** Popravilo ograje ***

Odkar se je na Kranjskem razcvetel turizem in imajo zato veliko imenitnih
obiskovalcev iz tujine, Kranjci veliko bolj skrbijo za svojo samopodobo.
Obnovili
so že vsa pročelja hiš, sedaj pa so se lotili še cest. Med drugim bodo
zamenjali
zaščitno ograjo, ki je že precej poškodovana. Ker so nekoliko ekonomični
želijo
zamenjati samo poškodovane dele ograje.

Ograja je sestavljena iz deščic dolžine 1m, ki so druga za drugo pritrjene
na
stebričke ob cesti. Te deščice tvorijo eno dolgo neprekinjeno ograjo, zato
so jih
označili s števili od 1 do n. (k-ta deščica se tako na levem koncu stika s
(k − 1)-vo deščico, na desnem pa s (k + 1)-vo deščico. Izjemi sta le prva in
zadnja deščica, ki imata samo eno sosedo.)

Ograjo so natančno pregledali in naredili seznam oznak poškodovanih deščic.
Ko so
hoteli naročiti nove deščice, s katerimi bi zamenjali poškodovane, so
ugotovili,
da so v trgovini na voljo le deske dolžine k metrov (k > 1). Te sicer lahko
tudi
razrežejo, vendar bo od obeh kosov uporaben samo eden — tj. desko lahko
skrajšajo,
ne morejo je pa razdeliti na dve.

Ograjo bodo menjali tako, da bodo iz ograje odstranili l (l <= k) zaporednih
metrskih deščic (med njimi so lahko tudi nepoškodovane, ki bodo pri
ostranjevanju
žal uničene) in jih nadomestili z novo desko (ki jo bodo po potrebi
skrajšali
na l metrov). Zanima jih najmanjše število desk, ki jih morajo kupiti, da
bodo
obnovili celo ograjo.

Vhodna datoteka:
V prvi vrstici so tri cela števila, n, k in c, ločena s po enim presledkom.
Pri tem je n dolžina ograje, k dolžina nadomestnih desk, c pa število
poškodovanih
odsekov. Sledi c vrstic z oznakami poškodovanih odsekov (oznake so cela
števila od
1 do n in so podane v naraščajočem vrstnem redu).
Veljalo bo: 1 <= n <= 1.000.000, 1 < k <= 1.000.000 in 0 <= c <= n.

Izhodna datoteka:
Vanjo naj tvoj program izpiše eno število deščic, ki jih je potrebno kupiti.

Primer vhodne datoteke:
10 4 6
1
3
4
5
7
9

Pripadajoča izhodna datoteka:
3

Ograjo s tega primera lahko popravimo tako, da kupimo tri deske; prvo desko
skrajšamo na dolžino 1 in z njo zamenjamo odsek 1; drugo desko skrajšamo na
dolžino
3 in z njo zamenjamo odseke 3, 4 in 5; tretjo desko pa skrajšamo na dolžino
3 in z
njo zamenjamo odseke 7, 8 in 9 — odsek 8 sicer ni poškodovan, vendar s tem
ni nič
narobe. Le z dvema deskama dolžine 4 pa se ograje ne da obnoviti, čeprav je
poškodovanih samo 6 odsekov na ograji.

----------------------------------------------------------------------------------

No, tako, zdaj pa hitro programirat :-)
Z veseljem bomo odgovorili na kakršnakoli vaša vprašanja: rtk-info na ijs.si

Lep pozdrav,
  Moyca