Sankt-Peterburgskie Olimpiady po Informatike

Zadachi mezhdunarodnoj olimpiady 1993 goda

Pervyj tur: [Busy] [Sovladel'cy] [Cvetnye prjamougol'niki]
Vtoroj tur: [Kanadskie avialinii]

Zadacha 'Busy'

Maksimal'naja ocenka: 20 ballov
Ogranichenie vremeni na test: 5 minut

Imejutsja busy, sostojaschie iz N (N<=100) businok, nekotorye iz kotoryh krasnogo ili golubogo cveta, a ostal'nye - belye. Na ris. 1 i ris. 2 privedeny dva primera bus dlja N=29 (ciframi otmecheny pozicii pervoj i vtoroj businok). 

       1 2                 1 2

     o x x o             x o o x
    o       x           x       x
   o         o         x         o
  o           o       @           o
 x             o     @             @
x               x   o               o
x               x   x               x
x               x   o               x
 o             o     x             o
  x           o       o           o
   x         o         o         o
    o       o           o       x
      o x o               o o @

      Ris. 1              Ris. 2

o - krasnaja businka
h - golubaja businka
@ - belaja businka

Konfiguracija bus zadaetsja posledovatel'nost'ju cvetov businok ("b" - golubaja, "r" - krasnaja, "w" - belaja), nachinaja s businki nomer 1. Naprimer, busy na ris. 1 zadajutsja posledovatel'nost'ju:

brbrrrbbbrrrrrbrrbbrbbbbrrrrb

Porvem busy i zatem nachnem snimat' businki odnogo cveta s pervogo konca, poka ne vstretitsja businka drugogo cveta. To zhe samoe prodelaem so vtorym koncom (businki, snjatye s raznyh koncov, mogut byt' raznogo cveta). Trebuetsja opredelit' tochku takogo razryva dannyh bus, pri kotorom summarnoe kolichestvo businok, sobrannyh s oboih koncov, maksimal'no. Naprimer, dlja bus na ris. 1 tochka razryva mozhet nahodit'sja mezhdu 24 i 25 businkami ili mezhdu 9 i 10 businkami; pri jetom summarnoe kolichestvo businok v oboih sluchajah ravnjaetsja 8.

Pri snjatii businok s kazhdogo iz koncov belaja businka rassmatrivaetsja kak businka golubogo ili krasnogo cveta po situacii, to est' mozhet snimat'sja kak s golubymi, tak i s krasnymi.

Napishite programmu, kotoraja:

  1. Vvodit dannye iz vhodnogo ASCII-fajla s imenem NECK- LACE.DAT, kazhdaja stroka kotorogo soderzhit konfiguraciju bus, zadannuju v vide posledovatel'nosti cvetov i zapisyvaet vhodnye dannye v vyhodnoj ASCII-fajl s imenem NECKLACE.SOL. Primer vhodnogo fajla NECKLACE.DAT:
    brbrrrbbbrrrrrbrrbbrbbbbrrrrb
bbwbrrrwbrbrrrrrb
  2. Dlja kazhdoj konfiguracii bus opredeljaet M - maksimal'noe chislo sobrannyh businok i polozhenie odnoj iz optimal'nyh tochek razryva.
  3. Vyvodit v kachestve rezul'tata v vyhodnoj fajl s imenem NECKLACE.SOL chislo M i tochku razryva. Otvety dlja raznyh konfiguracij otdeljajutsja pustoj strokoj. Primer vyhodnogo fajla NECKLACE.SOL: 
    brbrrrbbbrrrrrbrrbbrbbbbrrrrb
8 between 9 and 10

bbwbrrrwbrbrrrrrb
10 between 16 and 17

Zadacha 'Sovladel'cy'

Maksimal'naja ocenka: 30 ballov
Ogranichenie vremeni na test: 5 minut

Nekotorye kompanii javljajutsja sovladel'cami drugih kompanij, tak kak priobreli chast' ih akcij. Naprimer, kompanija Forda vladeet 12% akcij kompanii Mazda. Govorjat, chto kompanija A kontroliruet kompaniju V, esli imeet mesto po men'shej mere odno iz sledujuschih uslovij:

  1. A=V.
  2. A vladeet > 50% akcij V.
  3. A kontroliruet K (K1) kompanij S(1), E, S(K) takih, chto kompanija S(i) vladeet sootvetstvenno H(i)% akcij kompanii V (dlja vseh i ot 1 do K), i H(1)+H(2)+ E +H(K)>50.

Zadacha, kotoruju nado reshit', zakljuchaetsja v sledujuschem:

Dana posledovatel'nost' troek chisel (i,j,p), oznachajuschih, chto kompanija i vladeet p% akcij kompanii j. Trebuetsja opredelit' vse pary chisel (h,s), pri kotoryh kompanija h kontroliruet kompaniju s. Obschee chislo kompanij ne prevyshaet 100.

Napishite programmu, kotoraja:

  1. Chitaet iz vhodnogo ASCII-fajla s imenem COMPANY.DAT posledovatel'nost' troek (i,j,p), gde i, j i p - polozhitel'nye celye chisla. V fajle mogut soderzhat'sja posledovatel'nosti troek chisel dlja neskol'kih testov. Razlichnye testovye posledovatel'nosti razdeleny pustoj strokoj.
  2. Nahodit vse pary chisel (h,s) takie, chto kompanija h kontroliruet kompaniju s.
  3. Zapisyvaet v vyhodnoj ASCII-fajl s imenem COMPANY.SOL vse obnaruzhennye pary chisel (h,s), v kotoryh h otlichaetsja ot s. Pary (h,s) nado zapisat' v posledovatel'nyh strokah v porjadke vozrastanija h (kazhdaja para zapisyvaetsja v otdel'noj stroke). Reshenija dlja razlichnyh testovyh naborov dannyh dolzhny razdeljat'sja pustoj strokoj.

Primer:

COMPANY.DATCOMPANY.SOL
2    3    25
1    4    36
4    5    63
2    1    48
3    4    30
4    2    52
5    3    30

1    2    30
2    3    52
3    4    51
4    5    70
5    4    20
4    3    20
 
4   2
4   3
4   5

2   3
2   4
2   5
3   4
3   5
4   5

Zadacha 'Cvetnye prjamougol'niki'

Maksimal'naja ocenka: 50 ballov
Ogranichenie vremeni na test: 5 minut

N prjamougol'nikov razlichnyh cvetov raspolagajutsja na belom prjamougol'nom liste bumagi, imejuschem razmery A sm v shirinu i V sm v dlinu. Storony prjamougol'nikov parallel'ny krajam lista, a sami prjamougol'niki ne vyhodjat za predely lista. V rezul'tate obrazujutsja razlichnye odnocvetnye figury. Esli dva prjamougol'nika odnogo cveta imejut hotja by odnu obschuju tochku, to oni javljajutsja chastjami odnoj figury. Zadacha sostoit v vychislenii ploschadi kazhdoj iz vidimyh odnocvetnyh figur dlja kazhdogo cveta. A i V - chetnye polozhitel'nye celye chisla, ne prevoshodjaschie 30.

Nachalo sistemy koordinat nahoditsja v centre lista, a osi parallel'ny krajam lista.

Nabory dannyh dlja neskol'kih testov zapisany vo vhodnom ASCII-fajle s imenem RECTANG.DAT sledujuschim obrazom:

A, V i N nahodjatsja v pervoj stroke kazhdogo nabora dannyh i razdeleny probelom.

V kazhdoj iz sledujuschih N strok nahodjatsja:

Porjadok strok sootvetstvuet porjadku, v kotorom prjamo- ugol'niki razmeschalis' na liste ot pervogo do poslednego. Nabory dannyh dlja razlichnyh testov razdeleny pustoj strokoj (sm. primer).

Napishite programmu, kotoraja:

  1. Chitaet ocherednoj nabor dannyh iz vhodnogo fajla s imenem RECTANG.DAT.
  2. Vychisljaet ploschad' kazhdoj iz odnocvetnyh figur (sm. primer).
  3. Zapisyvaet v vyhodnoj ASCII-fajl s imenem RECTANG.SOL cvet i ploschad' kazhdoj odnocvetnoj figury, kak pokazano nizhe v primere. Jeti rezul'taty dolzhny zapisyvat'sja v porjadke vozrastanija nomera cveta. Rezul'taty dlja razlichnyh testov razdeljajutsja pustoj strokoj.

Primer:

RECTANG.DATRECTANG.SOL
20 12 5
-7 -5 -3 -1  4
-3 -3  5  3  2
-4 -2 -2  2  4
 2 -2  3 -1 12
 3  1  7  5  1

30 30 2
 0  0  5 14  2
10 -7  0 13 15
 1 177 2 39 4 23 12 1 1 630 2 70 15 200

Zadacha 'Kanadskie avialinii'

Maksimal'naja ocenka: 50 ballov
Ogranichenie vremeni na test: 5 minut

Vy pobedili v sorevnovanii, organizovannom Kanadskimi avialinijami. Priz - besplatnoe puteshestvie po Kanade. Puteshestvie nachinaetsja s samogo zapadnogo goroda, v kotoryj letajut samolety, prohodit s zapada na vostok, poka ne dostignet samogo vostochnogo goroda, v kotoryj letajut samolety. Zatem puteshestvie prodolzhaetsja obratno s vostoka na zapad, poka ne dostignet nachal'nogo goroda. Ni odin iz gorodov nel'zja poseschat' bolee odnogo raza za iskljucheniem nachal'nogo goroda, kotoryj nado posetit' rovno dvazhdy (v nachale i v konce pu- teshestvija). Vam takzhe nel'zja pol'zovat'sja avialinijami drugih kompanij ili drugimi sposobami peredvizhenija. Zadacha sostoit v sledujuschem: dan spisok gorodov i spisok prjamyh rejsov mezhdu parami gorodov; najti marshrut, vkljuchajuschij maksimal'noe kolichestvo gorodov i udovletvorjajuschij vyshenazvannymi uslovijam. Neskol'ko naborov vhodnyh dannyh pomescheny v ASCII-fajl C:\IOI\ITIN.DAT. Kazhdyj nabor soderzhit:

Razlichnye nabory vhodnyh dannyh razdeleny pustoj strokoj. Posle poslednego nabora dannyh pustoj stroki ne budet. Primer fajla vhodnyh dannyh C:\IOI\ITIN.DAT: 

8 9
Vancouver
Yellowknife
Edmonton
Calgary
Winnipeg
Toronto
Montreal
Halifax
Vancouver Edmonton
Vancouver Calgary
Calgary Winnipeg
Winnipeg Toronto
Toronto Halifax
Montreal Halifax
Edmonton Montreal
Edmonton Yellowknife
Edmonton Calgary

5 5
C1
C2
C3
C4
C5
C5 C4
C2 C3
C3 C1
C4 C1
C5 C2

Vhodnye dannye korrektny, i ih proverka ne trebuetsja. Reshenija, poluchennye dlja kazhdogo nabora vhodnyh dannyh, dolzhny byt' posledovatel'no zapisany v vyhodnoj ASCII-fajl C:\IOI\ITIN.SOL sledujuschim obrazom:

  • v pervoj stroke - obschee kolichestvo gorodov iz vhodnogo fajla;
  • v sledujuschej stroke - chislo M, ravnoe kolichestvu razlichnyh gorodov, poseschaemyh na marshrute;
  • v sledujuschih M+1 strokah - nazvanija gorodov po odnomu v stroke v porjadke ih poseschenija.

Obratite vnimanie, chto ishodnyj gorod dolzhen byt' takzhe vyveden poslednim. Esli dlja nabora vhodnyh dannyh ne suschestvuet reshenija, to dlja jetogo nabora v vyhodnom fajle C:\IOI\ITIN.SOL dolzhny byt' tol'ko dve zapisi: obschee kolichestvo gorodov i soobschenie "NO SOLUTION" (net reshenija). Reshenija dlja raznyh naborov vhodnyh dannyh dolzhny razdeljat'sja v vyhodnom fajle pustoj strokoj. Obrazec vyhodnogo fajla C:\IOI\ITIN.SOL dlja privedennogo vyshe primera: 

8
7
Vancouver
Edmonton
Montreal
Halifax
Toronto
Winnipeg
Calgary
Vancouver

5
NO SOLUTION

Pomestite vashu programmu-reshenie v ASCII-fajl s imenem C:\IOI\DDD.xxx. Rasshirenie .xxx ravno .BAS dlja QBasic, .LCN dlja LOGO, .C dlja C, .PAS dlja PASCAL.

Используются технологии uCoz