|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| Sankt-Peterburgskie Olimpiady po Informatike |
Zadachi mezhdunarodnoj olimpiady 1992 goda
| Pervyj tur: | Ostrova v more |
| Vtoroj tur: | Pokorenie vershiny |
|
Zadacha "Ostrova v more"
|
Raspolozhenie ostrovov v more predstavleno s pomosch'ju setki razmerom N*N. Kazhdyj ostrov oboznachaetsja simvolom "*" v uzle jetoj setki. Zadacha zakljuchaetsja v tom, chtoby vosstanovit' kartu morskih ostrovov po zakodirovannoj informacii o raspredelenii ostrovov po gorizontaljam i vertikaljam. Dlja illjustracii principa kodirovanija rassmotrim sledujuschuju kartu i sootvetstvujuschie ej kody:
* * * 1 2
* * * * 3 1
* * * 1 1 1
* * * * * 5
* * * * 2 1 1
* 1
1 1 4 2 2 1
1 2 3 2
1
Chisla sprava ot karty na jetom risunke javljajutsja kodami i predstavljajut porjadok i razmer grupp ostrovov v sootvetstvujuschih gorizontaljah setki. Naprimer, cifry "1 2" v pervoj stroke oznachajut, chto pervaja gorizontal' soderzhit gruppu iz odnogo ostrova, za kotoroj sleduet gruppa iz dvuh ostrovov. Sleva i sprava ot kazhdoj gruppy ostrovov raspolozheno more proizvol'noj protjazhennosti. Analogichno, posledovatel'nost' "1 1 1" v pervom stolbce pod kartoj ostrovov oznachaet, chto pervaja vertikal' soderzhit tri gruppy ostrovov, v kazhdoj iz kotoryh odin ostrov, i t.d.
Postanovka zadachi
Napisat' programmu, kotoraja vypolnjaet sledujuschie dejstvija (shagi) do teh por, poka dannyj vhodnoj fajl, soderzhaschij neskol'ko blokov informacii, ne budet prochitan polnost'ju:
- Schityvaet ocherednoj blok informacii iz vhodnogo ASCII fajla (struktura jetogo fajla privedena v primere 1) i otobrazhaet ego na jekrane. Kazhdyj blok informacii nachinaetsja s velichiny razmera kvadratnoj setki, za kotorym sleduet kodovaja informacija o gorizontal'nom i vertikal'nom raspredelenii ostrovov. Kod dlja kazhdoj otdel'noj gorizontali i vertikali javljaetsja otdel'noj strokoj fajla i predstavljaet soboj posledovatel'nost' chisel, razdelennyh probelami. Zakanchivaetsja kazhdaja stroka nulem. Pri jetom snachala idet informacija o vseh gorizontaljah, a zatem - o vertikaljah.
- Vosstanavlivaet kartu (ili vse karty v sluchae ne edinstvennogo reshenija kak v primere 4) i otobrazhaet ee (ih) na jekrane.
- Dobavljaet kartu (karty) v konec vyhodnogo ASCII fajla. Kazhdoe pustoe mesto v setke dolzhno byt' predstavleno dvumja probelami, a kazhdyj ostrov - simvolom "* " (zvezdochka i probel). V sluchae neodnoznachnogo reshenija razlichnye karty dolzhny byt' otdeleny drug ot druga pustoj strokoj. Esli kartu vosstanovit' nevozmozhno, v sootvetstvujuschej stroke vyhodnogo fajla napisat' " no map ". Reshenija, otnosjaschiesja k razlichnym blokam informacii vhodnogo fajla dolzhny byt' otdeleny v vyhodnom fajle strokoj s nadpis'ju " next problem ".
Tehnicheskie ogranichenija
- N dolzhno byt' ne men'she 1 i ne bol'she 8.
- Rezul'tirujuschaja programma dolzhna byt' pomeschena v tekstovyj ASCII fajl s imenem "C:\IOI\DAY-1\413-PROG.xxx". Rasshirenie .xxx dlja PASCAL - .PAS, dlja C - .C, dlja BASIC - .BAS, dlja LOGO - .LOG.
- Imja vhodnogo ASCII fajla dolzhno byt' "C:\IOI\DAY-1\413-SEAS.IN".
Primer 1:
6 1 2 0 <-- stroka dlja pervoj gorizontali 3 1 0 1 1 1 0 5 0 2 1 1 0 1 0 1 1 1 0 <-- stroka dlja pervogo stolbca 1 2 0 4 0 2 3 0 2 0 1 2 0
Primer 2:
Blok vhodnoj Reshenie: informacii 4 Stolbcy 1 2 3 4 0 Stroka 1 1 0 Stroka 2 * 2 0 Stroka 3 * * 0 Stroka 4 0 1 0 2 0 0
Primer 3:
2 0 0 2 0 2 0 Dlja jetih dannyh ne suschestvuet karty.
Primer 4:
2 1 0 1 0 1 0 1 0 Jetim dannym udovletvorjajut dve razlichnye karty.
|
Zadacha "Pokorenie vershiny"
|
Klub al'pinistov sostoit iz P chlenov, s nomerami ot 1 do P. Kazhdyj al'pinist podnimaetsja v goru s odnoj i toj zhe skorost'ju, a skorost' pod''ema ne otlichaetsja ot skorosti spuska. Al'pinist s nomerom i rashoduet C(i) edinic resursov v den' kak pri pod''eme, tak i pri spuske, i mozhet nesti v kazhdyj moment vremeni ne bol'she S(i) takih edenic. Vse C(i) i S(i) - celye chisla. Predpolagaetsja, chto al'pinist mozhet dostich' vershiny za N dnej pri polnoj obespechennosti resursami kak dlja pod''ema, tak i dlja spuska. Gora mozhet byt' tak vysoka, chto odin al'pinist ne mozhet iznachal'no nesti vse neobhodimye dlja pod'ema i spuska resursy. Pojetomu gruppa al'pinistov startuet v odnom i tom zhe meste i v odno i to zhe vremja, chtoby obespechit' voshozhdenie. Al'pinist mozhet nachat' spuskat'sja, ne dostignuv vershiny, otdav pri jetom vse nenuzhnye emu dlja spuska resursy drugim al'pinistam, kotorye dolzhny byt' v sostojanii ih vzjat'. Al'pinisty ne otdyhajut v techenie jekspedicii. Zadacha sostoit v sostavlenii raspisanija voshozhdenija dlja kluba al'pinistov. Po krajnej mere odin al'pinist dolzhen dostich' vershiny gory i vse al'pinisty, vkljuchennye v gruppu voshozhdenija, dolzhny vozvratit'sja v nachal'nuju tochku.
Postanovka zadachi
Napisat' programmu, kotoraja vypolnjaet sledujuschee:
- Vvodit s klaviatury chislo dnej N, trebuemoe dlja dostizhenija vershiny gory, chislo P chlenov kluba i chisla S(i), C(i), dlja vseh i ot 1 do P. Predpolagaetsja, chto vse vhodnye dannye celochislennye. Otvergnut' (povtorit' zapros) na vvod dannyh, kotorye ne imejut smysla.
- Opredeljaet raspisanie dlja voshozhdenija, a takzhe nomera al'pinistov a(1), a(2),..., a(k), obrazujuschih gruppu dlja voshozhdenija, i chisla M(j) (dlja vseh j ot 1 do k), kotorye oboznachajut kolichestvo edinic resursov, vzjatyh kazhdym a(j) al'pinistom na starte. Soobschaet, esli nel'zja sostavit' takogo raspisanija dlja zadannyh N, S(i) i C(i).
- Vyvodit sledujuschuju informaciju na jekran:
a) chislo k al'pinistov, dejstvitel'no uchastvujuschih v voshozhdenii (razmer gruppy voshozhdenija);
b) neobhodimoe dlja jetogo obschee kolichestvo edinic resursov;
c) nomera uchastvujuschih v voshozhdenii al'pinistov a(1),a(2),..., a(k);
d) dlja kazhdogo a(j) (1<=j<=k) kakoe kolichestvo edinic resursov on voz'met s soboj so starta;
e) dlja kazhdogo a(j) kolichestvo dnej, cherez kotoroe on nachnet spuskat'sja. - Pytaetsja najti pochti optimal'noe raspisanie. Raspisanie javljaetsja optimal'nym, esli:
a) chislo uchastvujuschih v voshozhdenii al'pinistov, neobhodimoe dlja dostizhenija vershiny odnim iz nih, minimal'no.
b) sredi vseh raspisanij dlja grupp, udovletvorjajuschih usloviju a), obschee kolichestvo edinic resursov, vzjatyh s soboj so starta, - minimal'no.
Tehnicheskie ogranichenija
- Pomestite vashu rezul'tirujuschuju programmu v tekstovyj ASCII fajl s imenem "C:\IOI\DAY-2\422-PROG.xxx". Rasshirenie .xxx dlja PASCAL - .PAS, dlja C - .C, dlja BASIC - .BAS, dlja LOGO - .LOG.
- Programma dolzhna otvergat' vhodnye dannye, esli N<1 ili N>100, a takzhe esli P<1 ili P>20.
Primer:
Vozmozhen sledujuschij dialog s vashej programmoj.
Chislo dnej, neobhodimoe dlja dostizhenija vershiny - 4 Chislo al'pinistov v klube - 5 Maksimal'nyj resurs dlja al'pinista 1 - 7 Ezhednevnyj rashod resursa dlja al'pinista 1 - 1 Maksimal'nyj resurs dlja al'pinista 2 - 8 Ezhednevnyj rashod resursa dlja al'pinista 2 - 2 Maksimal'nyj resurs dlja al'pinista 3 - 12 Ezhednevnyj rashod resursa dlja al'pinista 3 - 2 Maksimal'nyj resurs dlja al'pinista 4 - 15 Ezhednevnyj rashod resursa dlja al'pinista 4 - 3 Maksimal'nyj resurs dlja al'pinista 5 - 7 Ezhednevnyj rashod resursa dlja al'pinista 5 - 1 2 al'pinista trebuetsja dlja pokorenija vershiy. 10 edenic resursa v celom dlja jetogo neobhodimo. Vzbirat'sja budut al'pinisty 1,5. Al'pinist 1 voz'met 7 edinic resursa i nachnet spuskat'sja cherez 4 dnja. Al'pinist 5 voz'met 3 edinic resursa i nachnet spuskat'sja cherez 1 den'. Hotite splanirovat' voshozhdenie dlja drugogo al'pinistskogo kluba? (Y/N) - Y. Chislo dnej, neobhodimoe dlja dostizhenija vershiny - 2 Chislo al'pinistov v klube - 1 Maksimal'nyj resurs dlja al'pinista 1 - 3 Ezhednevnyj rashod resursa dlja al'pinista 1 - 1 Voshozhdenie nevozmozhno. Hotite splanirovat' voshozhdenie dlja drugogo al'pinistskogo kluba? (Y/N) - N. Do svidanija.