Aštuntosios Baltijos šalių informatikos olimpiados uždavinių sąlygos

1. Greičio limitai(Vykdymo laikas – 2 sek.) Šiuolaikiniame pasaulyje, dažniausiai renkamės ne trumpiausią kelią, o kelią, kuriame užtrunkame mažiausiai laiko. Taigi, važiuojant automobiliu, greičio ribojimai yra svarbūs. Įsivaizduokite, kad kai kurie greičio ribojimo ženklai keliuose paslaptingai dingo. Kadangi negalima tikėtis iš vairuotojo, kad jis viską prisimins, peršasi vienintelė logiška išvada: pravažiavęs vietą, kur anksčiau buvo kelio ženklas, vairuotojas laikysis to paties greičio ribojimo, kokio jis laikėsi prieš atvažiuodamas į tą vietą. Duotas kelių tinklo aprašas. Paprastumo dėlei laikykite, kad kelių tinklas susideda iš kelių ir sankryžų. Visi keliai yra vienpusiai, jungia lygiai dvi sankryžas ir juose yra ne daugiau vieno greičio ribojimo ženklo, kuris yra (jei yra) pačioje kelio pradžioje. Iš sankryžos A į sankryžą B gali eiti ne daugiau kaip vienas kelias. Laikykite, kad greitis pakinta akimirksniu ir nėra jokių kitų veiksnių, kurie gali daryti įtaką Jūsų kelionei. Ir, žinoma, jokiu būdu negalima važiuoti greičiau, negu leidžia paskutinysis Jūsų pravažiuotas ženklas.

UžduotisParašykite programą, kuri surastų mažiausiai laiko reikalaujantį maršrutą, pasinaudodama tuo, kad kai kurie ženklai yra dingę.

Pradiniai duomenysPradiniai duomenys įrašyti byloje speed.in. Pirmoje eilutėje yra trys sveikieji skaičiai N, M ir D. Čia N (2<=N<=150) – sankryžų skaičius. Jos numeruojamos nuo 0 iki N – 1. M yra kelių skaičius, o D žymi sankryžą, į kurią Jums reikia patekti iš nulinės sankryžos. Kiekvienoje tolesnių M eilučių aprašytas vienas kelias. Kelią aprašanti eilutė sudaryta iš keturių sveikųjų skaičių A (0<=A 0, priešingu atveju T = L/Vsen, kur Vsen yra greičio ribojimas, kurio laikėtės iki tol, kol atvažiavote į šią sankryžą.

Atkreipiame dėmesį, kad operacijos turėtų būti atliekamos su slankaus kablelio skaičiais, kad būtų išvengta nereikalingo apvalinimo. Pradiniu momentu esate sankryžoje 0 ir laikotės 70 vienetų greičio ribojimo.

RezultataiRezultatų bylą speed.out turi sudaryti viena eilutė. Joje reikia išvardinti sankryžas, per kurias reikia važiuoti, norint kelyje iš sankryžos 0 į sankryžą D sugaišti mažiausiai laiko. Sankryžos turi būti surašytos tiksliai tokia tvarka, kokia per jas yra važiuojama. Taigi pirmoji sankryža turėtų būti 0, o paskutinioji – D. Pradiniai duomenys tokie, kad kelias, kuriame užtrunkama trumpiausiai, bus tik vienas.

Pradinių duomenų ir rezultatų pavyzdžiaiPradiniai duomenys Rezultatai Paaiškinimas(speed.in) speed.out 6 15 1 0 1 25 68 0 2 30 50 0 5 0 101 1 2 70 77 1 3 35 42 2 0 0 22 2 1 40 86 2 3 0 23 2 4 45 40 3 1 64 14 3 5 0 23 4 1 95 8 5 1 0 84 5 2 90 64 5 3 36 40 0 5 2 3 1 Kelionėje sugaištas laikas šiuo atveju yra lygus 2,628.

2.Tenisas(Vykdymo laikas – 2 sek.) Norėdamas susirasti naujų narių teniso klubas suorganizavo Teniso savaitę. Žaisti parodomuosiuose susitikimuose buvo pakviesta daug teniso žvaigždžių. Kiekvienas pakviestasis žaidėjas nurodė, kiek žaidimų jis sutinka sužaisti. Kad pakviestiesiems žaidėjams nebūtų nuobodu, organizatoriai nutarė sudaryti tokį žaidimo tvarkaraštį, kad bet kurie du žaidėjai tarpusavyje susitiktų ne daugiau kaip vieną kartą.

UžduotisParašykite programą, kuri suskirstytų pakviestus žaidėjus į poras taip, kad kiekvienas žaidėjas žaistų tiek žaidimų, kiek jis sutiko žaisti ir su jokiu žaidėju nežaistų daugiau kaip vieną kartą. Suprantama, žaidėjas negali žaisti pats su savimi.

Pradiniai duomenysPirmoje pradinių duomenų bylos tennis.in eilutėje įrašytas žaidėjų skaičius N (2<=N<=1000). Likusiose N eilučių įrašyta po vieną skaičių: kiek žaidimų Gi (1<=Gi0). Trikampio viršūnės yra taškai (x; y), (x+m; y) ir (x; y+m). Parašykite programą, kuri suskaičiuotų bendrą visų trikampių užimamą plotą.

Pradiniai duomenysPradiniai duomenys įrašyti byloje tr.in. Pirmoje eilutėje įrašytas vienas sveikasis skaičius n (n<=2000).

Likusiose n bylos eilučių įrašyta po tris tarpais atskirtus sveikuosius skaičius (vienam trikampiui skirta viena eilutė): xi, yi ir mi, (1<=i<=n, -107<=xi<=107, -107<=yi<=107, 02->4; (mokestis 4, trukmė 5); • 1->3->4 (mokestis 4, trukmė 5); • 1->2->3->4 (mokestis 6, trukmė 4) • 1->3->2->4 (mokestis 4, trukmė 10).

Maršrutai 1->3->4 ir 1->2->4 yra geresni už 1->3->2->4. Yra dvi minimalių maršrutų mokesčio-trukmės poros: mokestis 4, trukmė 5 (maršrutai 1->2->4 ir 1->3->4) ir mokestis 6, trukmė 4 (maršrutas 1->2->3->4). Rinkdamiesi maršrutą turėsime nuspręsti, ar labiau norėtume keliauti greičiau, bet mokėti brangiau (maršrutas 1->2->3->4), ar sutiksime daugiau laiko praleisti kelionėje, bet sumokėti mažiau (maršrutas 1->3->4 arba 1->2->4).

UžduotisParašykite programą, kuri nustatytų kiek egzistuoja skirtingų minimalių maršrutų, jungiančių pradinį ir galinį miestus. Jei dviejų (ar daugiau) maršrutų laikas ir mokestis sutampa, tai jie skaičiuojami kaip vienas maršrutas, t.y. mus domina skirtingos minimalių maršrutų mokesčio–laiko poros, o ne patys maršrutai.

Pradiniai duomenysPirmoje pradinių duomenų bylos bic.in eilutėje įrašyti keturi sveikieji skaičiai: miestų skaičius n (jie numeruojami nuo 1 iki n), 1<=n<=100, kelių skaičius m, 0<=m<=300, pradinis ir galinis maršruto miestai s ir e atitinkamai, 1<=s,e<=n,s<>e. Toliau yra m kelius aprašančių eilučių. Vienam keliui skiriama viena eilutė. Kiekvienoje eilutėje įrašyti keturi sveikieji skaičiai: du miestai, kuriuos jungia tas kelias, p ir r, 1<=p,r<=n, p<>r, važiavimo mokestis c, 0<=c<=100, ir važiavimo laikas t,

0<=t<=100. Du tuos pačius miestus gali jungti daugiau nei vienas kelias.

RezultataiPirmoje ir vienintelėje rezultatų bylos bic.out eilutėje įrašykite vieną sveikąjį skaičių – skirtingų mokesčio–laiko porų, atitinkančių minimalius maršrutus iš e į s, skaičių.

Pradinių duomenų ir rezultatų pavyzdžiaiPradiniai duomenys Rezultatai Paaiškinimas(bic.in) (bic.out) 4 5 1 4 2 1 2 1 3 4 3 1 2 3 1 2 3 1 1 4 2 4 2 4 2 Pavyzdys atitinka pateiktąjį sąlygoje.

5. L-Žaidimas ©Edward de Bono(Vykdymo laikas – 30 sek.) L žaidimą sukūrė Edvardas de Bono, kuriam patinka žaisti stalo žaidimus ir kuris nemėgsta žaidimų su daug figūrų. Jis ketino sukurti kuo paprastesnį žaidimą, kuriam žaisti reiktų didelio meistriškumo. L žaidimas ir yra šių ketinimų rezultatas. Abu žaidėjai turi po vieną L figūrą. Dar yra dvi neutralios (t.y. nepriklausančios nė vienam žaidėjui) šaškės. Lentos išmatavimai: 4*4. Žaidimo tikslas: įstumti priešininką į tokią poziciją, kad jis negalėtų pajudinti savo L figūros. Duota kažkokia pradinė pozicija, kai abiejų žaidėjų L figūros ir abi šaškės išdėstytos lentoje. Žaidėjas, kurio eilė paeiti, pirmiausia paeina su L figūra. Ėjimas su L figūra reiškia, kad žaidėjas pakelia figūrą ir ją padeda bet kurioje kitoje laisvoje vietoje. Prieš dedant, figūrą galima apversti (t.y. pakeisti L orientaciją). Padėta figūra privalo užimti keturis langelius. Paėjęs su L figūra, žaidėjas gali perkelti bet kurią vieną (tik vieną) šaškę į bet kurį laisvą lentos langelį. Atkreipkite dėmesį, kad paeiti su šaške nebūtina!

Paveikslėliuose pateiktos trys pradinės situacijos. Iš bet kurios pateiktos situacijos žaidėjas, kuriam priklauso languota L figūra, gali paeiti su L figūra į dvi skirtingas pozicijas (tos pozicijos parodytos dvejuose likusiuose paveikslėliuose). Paėjęs L figūra, žaidėjas gali paeiti bet kuria šaške į bet kurį iš likusių laisvų 6 langelių arba visai nejudinti šaškės. Viso yra 2*(6+6+1) galimi ėjimai.

Žaidėjas laimi, jei priešininkas nebegali paeiti savo L figūra. Jeigu žemiau pateiktame pavyzdyje atėjo eilė paeiti žaidėjui su languota figūra, jis pralaimi, nes negali paeiti su L figūra.

Žaidimas paprastas ir kartu sudėtingas, nes yra labai daug ėjimų. Iš viso yra daugiau nei 18,000 variantų, kaip išdėstyti L figūras ir šaškes šioje mažoje lentoje, ir bet kuriuo žaidimo momentu gali būti iki 195 galimų skirtingų ėjimų, iš kurių tik vienas bus sėkmingas. UžduotisDuota tam tikra situacija lentoje, taip pat žinoma, kuris žaidėjas turi paeiti. Pavadinkime šį žaidėją pirmuoju, o likusį žaidėją – priešininku. Parašykite programą, kuri nuspręstų, ar tas žaidėjas turi laimintį ėjimą, ir, jei taip, jį surastų. Jei egzistuoja keli laimintys ėjimai, reikia išvesti bet kurį vieną. Jei laiminčio ėjimo nėra, programa turi nuspręsti, ar žaidimas baigsis lygiosiomis (laikant, kad abu žaidėjai žaidžia optimaliai), ar pirmasis žaidėjas pralaimės. Ėjimas vadinamas laiminčiu, jei pirmajam žaidėjui atlikus šį ėjimą ir toliau optimaliai žaidžiant, jo priešininkas būtinai pralaimės, nepriklausomai nuo to, kaip priešininkas žais. Pirmasis žaidėjas pralaimės, jeigu nesvarbu kaip jis žaistų, jo optimaliai žaidžiantis priešininkas laimės. Jeigu nei viena iš dviejų aukščiau aprašytų sąlygų neišpildoma (t.y. nė vienas žaidėjas negali užsitikrinti, kad optimaliai abiems žaidžiant, laimės), laikoma, kad žaidimas baigsis lygiosiomis. Pradiniai duomenysPradiniai duomenys įrašyti byloje lgame.in. Pradinių duomenų byloje įrašytos keturios eilutės, turinčios po keturis simbolius. Jos apibūdina situaciją žaidimo lentoje. Taškas „.“ atitinka tuščią lentos langelį, „x“ žymi neutralią šaškę, „#“ žymi pirmojo (jo eilė paeiti) žaidėjo L figūrą, „*“ žymi priešininko L figūrą. Duota situacija bus korektiška ir tokia, kad pirmasis žaidėjas galės padaryti bent vieną ėjimą.

RezultataiRezultatus įrašykite į bylą lgame.out. Jei egzistuoja laimintis ėjimas, išveskite jį tokiu pat formatu kaip pradiniu duomenų byloje. Priešingu atveju pirmoje rezultatų bylos eilutėje išveskite No winning move. Antroje eilutėje išveskite arba Draw, jei žaidimas baigsis lygiosiomis (laikant, kad abu žaidėjai žaidžia optimaliai), arba Losing, jei pirmasis žaidėjas pralaimės. Pradinių duomenų ir rezultatų pavyzdžiaiPradiniai duomenys Rezultatai(lgame.in) (lgame.out).*** #*.x ###. x… .*** x*#x ###. ….(lgame.in) (lgame.out)…x ###. #*** x..* No winning move Draw(lgame.in) (lgame.out).### x#*x ***. …. No winning move LosingVertinimasBalai už testus, kuriuose neegzistuoja laimintis ėjimas bus skiriami tik tada, jei programa surinks bent pusę taškų už testus, kuriems egzistuoja laimintis ėjimas.

6. Judantys Robotai(Vykdymo laikas – 10 sek.) Yra keletas robotų, kurie gali judėti visoje dvimatėje plokštumoje. Plokštuma padalinta į vienetinius kvadratėlius, turinčius sveikąsias koordinates (x, y). Roboto būseną apibūdina jo padėtis ir judėjimo kryptis. Padėtis nusakoma sveikųjų skaičių pora (x, y), o kryptis – laipsniais. Yra keturios galimos kryptys – 0, 90, 180 ir 270 laipsnių. Robotai gali vykdyti dviejų rūšių – posūkio ir žingsnio – komandas. Posūkio komanda turi vieną parametrą D, kurio galimos reikšmės yra 90, 180 ir 270. Ši komanda pakeičia roboto kryptį per D laipsnių: jei dabartinė roboto kryptis yra C, tai ji pakeičiama į (C + D) mod 360. Žingsnio komanda parametrų neturi. Ją atlikdamas robotas pajuda per vieną žingsnį jo judėjimo kryptimi. Vienas žingsnis 0 laipsnių kryptimi pakeičia roboto padėtį (pakeičia atitinkamas koordinates) per (1, 0), 90 laipsnių kryptimi – per (0, 1), 180 laipsnių kryptimi – per (-1, 0), o 270 laipsnių kryptimi – per (0, -1). Kiekvienas robotas turi jam skirtą baigtinio ilgio komandų seką ir tas komandas atlieka iš eilės. Kai visos komandos atliktos, robotas sustoja savo galutinėje padėtyje. Roboto judėjimas visiškai nepriklauso nuo kitų robotų, tą pačią padėtį (langelį) plokštumoje gali užimti bet koks skaičius robotų.

Prieš pradedant robotams judėti, valdymo centras gali įsakyti pašalinti tam tikras komandas iš kai kurių robotų komandų sekos. Taip valdymo centras gali keisti robotų judėjimo trajektorijas bei galutines padėtis. Valdymo centras nusprendė, kad visi robotai turi susirinkti į vieną vietą (langelį) apžiūrai, taigi reikia, kad visų robotų galutinės padėtys sutaptų. Taip pat centras nori, kad tai būtų įgyvendinta pašalinus kuo mažiau komandų. UžduotisTurime R robotų. Kiekvienas robotas turi pradinę padėtį, pradinę judėjimo kryptį ir jam paskirtą komandų seką. Parašykite programą, kuri nustatytų, kiek mažiausiai komandų iš visų robotų komandų sekų reikia pašalinti, kad visų robotų galutinės padėtys sutaptų (šią padėtį pavadinkime bendra galutine padėtimi) bei rastų bendrą galutinę padėtį. Jeigu galima parinkti kelias bendras galutines padėtis, pakanka nurodyti bet kurią. Pradiniai duomenysPradiniai duomenys įrašyti byloje robots.in. Pirmoje eilutėje įrašytas robotų skaičius R (2<=R<=10 ). Toliau seka R grupių eilučių – po vieną grupę kiekvienam robotui. Pirmoje grupės eilutėje yra keturi tarpu atskirti skaičiai: pradinė roboto padėtis (x, y), pradinė roboto judėjimo kryptis C (C = 0, 90, 180 arba 270) ir roboto komandų sekos ilgis n (1<=n<=50 ). Toliau grupėje yra n eilučių, aprašančių roboto komandų seką. Kiekvienoje eilutėje yra po vieną komandą. Žingsnio komandai skirtoje eilutėje įrašytas vienintelis simbolis – raidė S. Posūkio komandai skirtoje eilutėje įrašyta raidė T ir posūkio parametras D (D = 90, 180 arba 270). Raidę T nuo posūkio parametro skiria tarpas. RezultataiRezultatus įrašykite į bylą robots.out. Jeigu neįmanoma robotų surinkti į tą pačią galutinę padėtį (langelį), į vienintelę rezultatų bylos eilutę įrašykite skaičių (minus vienas). Priešingu atveju, į pirmą eilutę įrašykite mažiausią skaičių komandų, kurias reikia pašalinti. Antroje eilutėje tuomet įrašykite du tarpu atskirtus skaičius: bendros galutinės padėties koordinates x ir y.

Pradinių duomenų ir rezultatų pavyzdžiaiPradiniai duomenys Rezultatai Paaiškinimai(robots.in) (robots.out) 2 2 0 270 5 S T 180 S S S 1 -1 0 8 S S T 90 S T 270 S T 90 S 2 2 1 Turime du robotus. Pirmojo pradinė padėtis yra (2, 0), judėjimo kryptis 270, jam duotos 5 komandos. Antrojo pradinės padėties koordinatės yra (1, -1), judėjimo kryptis 0, jam duotos 8 komandos. Mažiausias skaičius komandų, kurias reikia pašalinti, yra lygus 2. Tuomet robotų galutinės padėtys sutaps ir bendros galutinės padėties koordinatės bus (2, 1). Tai galima gauti, pvz., pašalinus pirmojo roboto 3-ąją komandą ir antrojo roboto 5-ąją komandą.