5 ol (sąlygos)

Penktoji moksleivių informatikos olimpiada

Pirmojo etapo uždavinių sąlygos

45. STANDARTINIAI NUMERIAI. Leidyklų išleistos knygos turi tarptautinės standartų knygos numerį ISBN (International Standard Book Number). Pavyzdžiui, informatikos vadovėlis turi numerį ISBN 5-430-01218-1. Numerį sudaro 10 skaitmenų, suskirstytų į grupes, kurios atskirtos viena nuo kitos brūkšneliu. Pirmieji skaitmenys žymi valstybę, tolesni – leidyklą ir knygos numerį toje leidykloje. Paskutinis skaitmuo kontrolinis. Jis gaunamas šitaip: pirmasis numerio skaitmuo padauginamas iš vieneto, antrasis iš dvejeto ir taip iki devintojo. Visos sandaugos sudedamos, o suma padalijama iš 11. Liekana ir yra kontrolinis skaitmuo. Jeigu liekana lygi 10, tai vietoj skaitmens rašoma raidė X.

Jeigu kurio nors skaitmens numeryje trūktų, tai jį būtų galima rasti pasinaudojus kontroliniu skaitmeniu.

Parašykite algoritmą šiam uždaviniui spręsti.

Pradinis duomuo – knygos numeris, pavaizduotas 10 elementų simboliniu masyvu. Trūkstamas skaitmuo pažymėtas raide T.

Rezultatas – trūkstamas masyvo simbolis (vietoj raidės T). Jeigu tokio simbolio rasti neįmanoma, tai rezultatas lygus N.

46. SUDĖTIS STULPELIU. Galvosūkių knygose galima rasti ne vieną uždavinį, kai pateikiama sudėtis (atimtis, daugyba) stulpeliu ir dalis skaitmenų praleista, pavyzdžiui:

+128*2*
1*514
1*1743
Parašykite algoritmą trūkstamiems skaitmenims rasti.

Pradiniai duomenys: trys natūralieji skaičiai, pavaizduoti simbolių (skaitmenų) eilutėmis. Trečiasis skaičius yra pirmųjų dviejų suma. Nežinomi skaitmenys pavaizduoti žvaigždutėmis.

Rezultatas (jei yra sprendinys) – trys skaičiai su rastaisiais skaitmenimis. Jei galimi keli variantai, pakanka pateikti vieną.

47. ŽIRGO KELIAS. Begalinėje šachmatų lentoje duotos dviejų langelių koordinatės (sveikaisiais skaičiais koordinačių plokštumoje). Parašykite algoritmą nustatyti, kiek ėjimų tektų padaryti žirgui, kol iš pirmojo duoto langelio pasiektų antrąjį, jei einama trumpiausiu keliu.

48. SKLYPAS. Sklypas suskirstomas kvadratėliais ir jame statomas pastatas, kuris užima sveikąjį skaičių kvadratėlių (pastatą sudarantys kvadratėliai būtinai turi liestis bent viena kraštine). Pastačius pastatą, aplink jį apibrėžiamas toks žemės sklypas, kad pastatas atsidurtų stačiakampiame žemės plote (stačiakampis minimalus, tačiau palei pastatą turi būti bent po vieną kvadratėlį žemės).

Parašykite algoritmą, kuris rastų, kokio ploto žemės sklypą gali gauti savininkas, kai jo pastatą sudaro n kvadratėlių. Raskite visus galimus variantus. Pavyzdžiui, kai n = 5, tai rezultatai bus 20, 21, 24, 25.

Antrojo etapo uždavinių sąlygos

49. LYGYBĖ. Simbolių eilute pavaizduotas reiškinys, sudarytas iš natūraliųjų skaičių, sudėties ir atimties ženklų (tarpų niekur nėra). Reiškinio pabaigoje užrašytas lygybės ženklas ir rezultatas. Tačiau kai kurių skaitmenų trūksta – vietoj kiekvieno jų įrašytas klaustukas.

Parašykite programą, kuri rastų trūkstamus skaitmenis ir kompiuterio ekrane pateiktų (išspausdintų) visą lygybę. Jei galimi keli sprendimo variantai, reikia pateikti visus. Jei sprendinio nėra, spausdinkite pranešimą LYGYBĖJE YRA KLAIDŲ.

Pradiniai duomenys – lygybė, įrašyta į vieną tekstinės bylos eilutę.

*Pavyzdys*
Pradiniai duomenys	Rezultatai
`150-10?+?+3-47+4=13`	`150-106+9+3-47+4=13` `150-105+8+3-47+4=13` `150-104+7+3-47+4=13` `150-103+6+3-47+4=13` `150-102+5+3-47+4=13` `150-101+4+3-47+4=13` `150-100+3+3-47+4=13`

50. LAUŽTĖ. Languoto popieriaus lapo linijomis nubrėžta uždara, pati savęs nekertanti laužtė, kurios visų atkarpų ilgiai yra sveikieji skaičiai (langelio kraštinės ilgis lygus vienetui). Laužtė nusakoma jos lūžio taškų koordinatėmis (x, y); x >= 0, y >= 0.

Parašykite algoritmą gautos figūros plotui apskaičiuoti.

Pradiniai duomenys – koordinatės, surašytos į tekstinę bylą po du skaičius (x, y) į vieną eilutę ir pateiktos laužtės apėjimo prieš laikrodžio rodyklę kryptimi. Pirmoji ir paskutinė koordinatės sutampa – laužtė uždara.

Laikykite, kad pradiniai duomenys teisingi.

Rezultatą rašykite kompiuterio ekrane.

*Pavyzdys*
Pradiniai duomenys	Rezultatai
`2 4` `2 3` `1 3` `1 1` `2 1` `2 2` `5 2` `5 1` `6 1` `6 4` `2 4`	`11`

Trečiojo etapo uždavinių sąlygos

51. ATSISKAITYMAS SKOLOMIS. Įmonės įsiskolinusios viena kitai. Jeigu įmonė turėtų pinigų, ji galėtų skolas sumokėti. Tačiau jų neturi. O neturi todėl, kad jai negrąžina skolų kitos įmonės. Kitos įmonės negali sumokėti savų skolų dėl tos pačios priežasties – jos negauna pinigų iš joms skolingų įmonių. Susidaro uždaras ratas. Tačiau jį galima pralaužti. Pasirodo, skolas galima sumokėti ... skolomis.

Sakykime, įmonė A yra skolinga 100 litų įmonei B, įmonė B – 50 litų įmonei C ir įmonė C – 75 litus įmonei A. Šis sąrašas yra uždaras. Todėl bendra skolų suma gali būti sumažinta, pertvarkius skolų sąrašą taip: įmonė A skolinga 50 litų įmonei B ir įmonė C skolinga 25 litus įmonei A. Įmonės C skola įmonei A gali būti laikoma netiesiogine įmonės C skola įmonei B per įmonę A, todėl galutinis skolų sąrašas yra toks: įmonė A skolinga 25 litus įmonei B ir įmonė C skolinga 25 litus įmonei B.

Parašykite programą, kuri išanalizuotų įmonių skolas ir jas pertvarkytų taip, kad bendra visų įmonių skolų suma būtų mažiausia.

Pradiniai duomenys – tekstinė byla, kurioje įrašytas skolų sąrašas. Kiekvienas sąrašo elementas įrašytas atskiroje eilutėje ir išreiškiamas trejetu:
a b x
čia a ir b – įmonių kodai, x – įmonės a skola įmonei b.

Pradiniai duomenys tenkina reikalavimus:

1) įmonių kodai yra sveikieji skaičiai iš intervalo [1..10000];
2) skolos išreiškiamos teigiamais realiaisiais skaičiais;
3) sąrašo gale yra įrašas, sudarytas iš trijų nulių.

Rezultatų byloje turi būti įrašyta tokia informacija:

1) bendra pradinė skolų suma;
2) bendra galutinė skolų suma;
3) skolų sąrašas, gautas pertvarkius skolas; jo elementai turi būti sudaryti iš trijų skaičių taip pat, kaip ir pradinių duomenų sąraše;

Pavyzdys
Sakykime, įmonės A kodas yra 11, įmonės B – 22, įmonės C – 33.

Pradiniai duomenys	Rezultatai
`11 22 100.00` `22 33 50.00` `33 11 75.00` `0 0 0.00`	PRADINĖ SKOLŲ SUMA: `225.00` GALUTINĖ SKOLŲ SUMA: `50.00` GALUTINIS SKOLŲ SĄRAŠAS: `11 22 25.00` `33 22 25.00`

52. PASKALIO TRIKAMPIS. Daugumai gerai žinomas Paskalio trikampis
     1
    1 1
   1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
. . . . . . . .
nepraranda savo žavumo ir galima sugalvoti vis naujų uždavinių.

Pradiniai duomenys – tekstinė byla, kurioje įrašyti natūralieji skaičiai, vienas nuo kito atskirti tarpais. Reikia nustatyti, ar iš jų galima sudaryti kurią nors Paskalio trikampio eilutę (galima pavartoti tik dalį skaičių rinkinio).

Rezultatas – rastoji eilutė arba žodis NEGALIMA, rašomi į tekstinę bylą. Jeigu galima sudaryti kelias eilutes, turi būti pateikta ilgiausia.

53. METAGRAMA. Metagrama – žodis, gautas iš kito žodžio, pakeitus vieną raidę. Iš kelių žodžių galima sudaryti metagramų grandinę, pavyzdžiui:

BALDAS – BALNAS – KALNAS – KALTAS – PALTAS – PULTAS – GULTAS

Pradiniai duomenys – tekstinė byla, kurioje surašyti žodžiai po vieną į eilutę. Reikia surasti ilgiausią metagramų grandinę (jei yra kelios, pateikite vieną iš jų).

Rezultatai – iš eilės einantys metagramų grandinės žodžiai, surašomi tekstinėje byloje po vieną žodį į eilutę.

54. KRYŽIAŽODIS. Parašykite programą, kuri rastų bent vieną duoto kryžiažodžio sprendimą.

Pradiniai duomenys: dvi tekstinės bylos: PAV.DAT ir ŽOD.DAT. Byloje PAV.DAT – kryžiažodžio paveikslas, byloje ŽOD.DAT – žodynas.

Kryžiažodžio paveikslas – tai stačiakampis, sudarytas iš kvadratėlių. Kvadratėliai, į kuriuos turi būti įrašytos raidės, vaizduojami tarpais, o visas kitas plotas užpildytas simboliais x.

Kryžiažodžio paveikslas tenkina šiuos reikalavimus:

1. Yra stačiakampis, ne didesnis kaip 40 x 40 simbolių.
2. Stačiakampio perimetras sudarytas vien iš simbolių x (t. y. žodžiai nesiekia stačiakampio kraštų.
3. Vienoje eilutėje arba viename stulpelyje galima įrašyti tik vieną žodį. Pavyzdžiui, šis kryžiažodžio fragmentas
ABCD
EFG
HI
skirtas šešiems žodžiams (ABCD, EFG, HI, BEI, CF, DG).
4. Žodžiai negali liestis.
5. Žodžio ilgis nuo 2 iki 10 raidžių.
6. Žodžiai rašomi iš kairės į dešinę arba iš viršaus į apačią.

Žodynas – tai aibė žodžių, kurie gali būti rašomi į kryžiažodį. Kiekvienas žodis į kryžiažodį gali būti įrašytas ne daugiau kaip vieną kartą. Žodžiai sudaryti vien iš didžiųjų lietuviškos abėcėlės raidžių. Vienoje bylos eilutėje – vienas žodis. Paskutinė eilutė tuščia.

Laikykite, kad pradiniai duomenys teisingi.

Rezultatai rašomi į tekstinę bylą KRYŽ.REZ. Tai kryžiažodžio paveikslai, paimti iš pradinių duomenų bylos, į kurių tuščius kvadratėlius įrašytos raidės, sudarančios žodžius, paimtus iš žodyno. Sprendinyje nebūtinai turi būti panaudoti visi žodžiai. Jei uždavinys neturi nė vieno sprendinio – į bylą rašoma frazė:
KRYŽIAŽODIS SPRENDINIO NETURI

*Pavyzdys*
Kryžiažodžio paveikslas – byla PAV.DAT	Žodynas – byla ŽOD.DAT	Rezultatas
`xxxxxxxxxxxx` `xxxxxxxxx xx` `xxxxxxxxx xx` `xxxxxxxxx xx` `xxx xx xx xx` `xxx x x` `xxx xx xx xx` `x x x xxx` `xxx xx x xxx` `xxx x xx` `xxx xx x xxx` `xx xxxx` `xxx xx xxxxx` `xxx xxxxxxxx` `xxxxxxxxxxxx` `xxxxxxxxxxxx`	ARKLYS ASILAS BEBRAS BEGEMOTAS ELNIAS KROKODILAS LAPĖ LOKYS OŽYS OŽKA TIGRAS	`xxxxxxxxxxxx` `xxxxxxxxxAxx` `xxxxxxxxxSxx` `xxxxxxxxxIxx` `xxxKxxBxxLxx` `xxxRxBEBRASx` `xxxOxxGxxSxx` `xO`Ž`KA``xExOxxx` `xxxOxxMx`Ž`xxx` `xxxDxLOKYSxx` `xxxIxxTxSxxx` `xxELNIASxxxx` `xxxAxxSxxxxx` `xxxSxxxxxxxx` `xxxxxxxxxxxx` `xxxxxxxxxxxx`

55. ŠALIGATVIAI. Stačiakampis laukas padalintas į šaligatvio plytelės dydžio kvadratus, kurie žymimi x ir y koordinatėmis. Ant kvadratų galima dėti plyteles ir iš jų nutiesti takus. Taką sudaro šonais besiliečiančios plytelės. Tako plotis – viena plytelė.

Yra pažymėti keturi kvadratai A, B, C ir D (t. y. duotos jų koordinatės).

Parašykite programą, kuri nustatytų, ar galima nutiesti du nesikertančius kelius, kurių vienas jungia kvadratą A su kvadratu B, kitas – kvadratą C su kvadratu D.

Pradiniai duomenys – surašyti į tekstinę bylą po du skaičius (x, y) į vieną eilutę. Pirmoje eilutėje nurodytas lauko dydis x_max ir y_max (1 <= x_max, y_max <= 500), keturiose kitose eilutėse – keturios kvadratų, žyminčių kelių galus, koordinatės x, y (1 <= x <= x_max, 1 <= y <= y_max).

Rezultatą, išreikštą žodžiu GALIMA arba NEGALIMA reikia parodyti kompiuterio displėjuje.

*Pavyzdys*
Pradiniai duomenys	Rezultatas
`10 8` `2 7` `10 1` `6 6` `4 2`	`GALIMA`

56. TELEVIZIJOS LAIDOS. (Vykdymo laikas – 50 s.) Yra televizorius ir videomagnetofonas. Buvo sudarytas vienos paros televizijos laidų, kurias reikia įrašyti į videokasetes, sąrašas. Laidos turi būti įrašytos taip, kad reikėtų kuo mažiau kasečių.

Kiekviena laida trunka ne mažiau kaip 10 minučių ir ne ilgiau kaip valandą. Laidos pradžioje 1 minutę rodoma reklama (reklamos laikas įeina į laidos laiką), kurios įrašinėti nereikia. Todėl reklamos metu galima pakeisti kasetę. Vienoje kasetėje telpa 1 valandos trukmės įrašas.

Parašykite programą, kuri rastų ir spausdintų mažiausią reikalingų kasečių skaičių.

Pradiniai duomenys – tekstinė byla, kurios kiekvienoje eilutėje yra keturi skaičiai: laidos pradžios ir pabaigos laikas valandomis ir minutėmis. Pradiniai duomenys teisingi: persidengiančių laikų nėra. Per parą parengiama ne daugiau kaip 30 laidų.

Rezultatas pateikiamas displėjaus ekrane.

*Pavyzdys*
Pradiniai duomenys	Rezultatas
`10 0 10 20` `9 15 10 0` `11 15 12 5` `12 5 12 35` `13 0 13 33`	`4`

57. SUSIJUSIOS SRITYS. Duotas m x n langelių (1 <= m <= 50, 1 <= n <= 50) dydžio popieriaus lapas, kuriame raidėmis J ir B sužymėti juodi ir balti langeliai.

Vientisa sritimi vadinsime tokią, kuri sudaryta iš vienos spalvos langelių, besiliečiančių vienas su kitu vertikaliomis arba horizontaliomis kraštinėmis.

Parašykite procedūrą, kuri rastų, kiek langelių sudaro didžiausią vientisą juodą ir didžiausią vientisą baltą sritis atskirai, bei tų sričių padėtį (bet kurio vieno jų langelio koordinates).

Procedūrą įjunkite į programą, kuri rezultatus pateiktų kompiuterio displėjuje.

Pradiniai duomenys – pateikiami tekstinėje byloje. Pirmojoje eilutėje įrašyti skaičiai m ir n. Tolesnėse m eilučių yra po n raidžių (J ar B).

Rezultatai: turi būti spausdinami du pranešimai:

tekstas DIDŽIAUSIA JUODOJI SRITIS, ją sudarančių langelių skaičius ir kurio nors langelio koordinatės (du skaičiai);
tekstas DIDŽIAUSIA BALTOJI SRITIS, ją sudarančių langelių skaičius ir kurio nors langelio koordinatės (du skaičiai);

Langeliai žymimi iš kairės į dešinę nuo 1 iki n ir iš viršaus į apačią nuo 1 iki m.

*Pavyzdys*
Pradiniai duomenys	Rezultatai
`3 4` `JJBB` `BJBJ` `JJBJ`	DIDŽIAUSIA JUODOJI SRITIS: `5; 1, 1`DIDŽIAUSIA BALTOJI SRITIS: `4; 3, 1`