Pirmojo etapo uždavinių sąlygos

114.  KAIP PASIEKTI LEMPUTĘ. Turime n dėžių, kurių briaunų a x b x c ilgiai yra žinomi. Dėžes galima guldyti ant bet kurio šono.

Kambaryje perdegė elektros lemputė. Atstumas nuo grindų iki jos yra t. Žmogus gali pasiekti tik aukštyje h kabančią lemputę.

Reikia rasti pirmąją iš duotų dėžių, kuria pasinaudojus galima įsukti naują lemputę. Kiek iš viso yra tam tinkamų dėžių?

115. SKLYPAS. Ūkininkas gavo žemės. Tačiau vietoj konkretaus sklypo jam buvo duota tvora, susidedanti iš n dalių (atkarpų), kiekviena po 10 metrų ilgio. Ūkininkui buvo pasakyta, kad sklypas, kurį jis apsitvers šia tvora, bus jo. Sklypo tvora turi būti laužtė, kurią sudarančios atkarpos eina dviem kryptimis: šiaurė–pietūs (arba pietūs–šiaurė) ir rytai–vakarai (arba vakarai–rytai). Kiekviena laužtės atkarpa sudaroma iš sveikojo tvoros dalių skaičiaus.

Parašykite programą, kuri nustatytų, kokio didžiausio ploto sklypą gali apsitverti ūkininkas. Sklypo dydį reikia išreikšti hektarais ir arais (1ha = 100a = 10000m²). 

116. ELEKTRONINIS LAIKRODIS. Skaitmenys elektroniniame laikrodyje yra sudaromi iš horizontalių ir vertikalių pagaliukų:
 

Duotas horizontalių ir vertikalių pagaliukų skaičius. Parašykite algoritmą, kuris nustatytų, kokį laiką galėjo rodyti elektroninis laikrodis. Pradiniai duomenys tokie, kad sprendinys būtinai egzistuoja.

117.  SKAIČIŲ KRIPTOGRAMA. (Vykdymo laikas – 1 min.) Žemiau pateiktoje kriptogramoje dauginami skaitmenys pažymėti žvaigždutėmis:

     ****
  x   ***
     ****
   *****
  *****
  *******

Parašykite programą, kuri rastų visus duotos kriptogramos sprendinius. Vieną sprendinį turi sudaryti trys skaičiai: dauginamasis, daugiklis ir sandauga.

118. DEŠIMTAINĖS TRUPMENOS KEITIMAS PAPRASTĄJĄ.  Parašykite programą, kuri dešimtainę trupmeną paverstų paprastąja ir išspausdintų formatu S/V, kur S – skaitiklis, V– vardiklis. Be abejo, trupmena turi būti suprastinta. 

119. KUBELIS SU SKAIČIAIS.  Ant stalo guli kubelis ir ant kiekvienos jo sienelės užrašyta po vieną sveikąjį skaičių. Ant viršutinės sienelės užrašytas skaičius a, ant apatinės – b, ant priekinės – c, ant užpakalinės – d, ant kairiosios – e, ant dešiniosios – f.

Yra keturios kubelio vartymo komandos: K – kubelis paverčiamas ant kairiojo šono, D – paverčiamas ant dešiniojo šono, P – paverčiamas ant priekinės pusės, A – paverčiamas ant galinės sienelės.

Duota kubelio vartymo komandos (raidžių be tarpų seka). Parašykite algoritmą nustatyti, koks skaičius bus matomas ant kubelio viršutinės sienelės, kai atliksime duotąją komandų seką.

120. SULTIS GERTI SVEIKA.  Kiekvienos savaitės pirmadienio rytą Jonas gauna k centų kišenpinigiams. Vienas butelis sulčių kainuoja s centų, o tušti buteliai superkami po b centų.
Kartą (tai buvo i-oji savaitės diena), iš viso turėdamas n centų, Jonas nusprendė kasdien (pradedant i-ąja diena) pirkti sulčių už visus turimus pinigus. Pinigai, gauti pardavus butelius, bus panaudojami kitą dieną sultims pirkti. Šitaip Jonas darys tol, kol jis įstengs nusipirkti bent vieną sulčių butelį.

Kiek butelių sulčių išgers Jonas?

Parašykite programą šiam uždaviniui spręsti. Pradiniai duomenys – natūralieji skaičiai k, s, b, n, i (1 <= i <= 7). Jei nusprendžiama sultis pirkti pirmadienį, tai iš karto gaunami kišenpinigiai (pasipildo turima pinigų suma). Už pirmadienį gautus kišenpinigius sultys perkamos pirmadienį.

121. SKAITMUO SEKOJE. Sakykime, kad turime seką, sudarytą iš paeiliui einančių Fibonačio skaičių (be tarpų):

1123581321345589144233...

Parašykite programą šios sekos k-ajam skaitmeniui rasti.

Fibonačio skaičių seka – tai tokia seka, kurios pirmasis ir antrasis nariai lygūs vienetui, o kiekvienas tolesnis yra lygus prieš jį einančių dviejų narių sumai.

122.  SKAIČIAUS SPĖJIMAS. Yra toks žaidimas, kai pirmasis žaidėjas sugalvoja sveikąjį skaičių (didesnį už nulį, bet mažesnį už maxint), o antrasis, sakydamas po vieną skaitmenį, bando atspėti sugalvotąjį skaičių.

Duotas sugalvotas skaičius ir šešių skaitmenų seka. Toji seka – tai antrojo žaidėjo spėti skaitmenys. Visi sekos skaitmenys skirtingi. Parašykite programą nustatyti, ar antrasis žaidėjas, pasakęs duotus šešis skaitmenis, atspėjo sugalvotąjį skaičių.

Jei skaičius nebuvo atspėtas, tai rezultatas – žodis NE ir skaičius, reiškiantis, kiek liko skirtingų neatspėtų skaitmenų.

123. ABĖCĖLĖ.   Laikant informatikos brandos egzaminą būna uždavinių, kai reikia rasti visus galimus duotos abėcėlės žodžius. Pavyzdžiui:

„Abėcėlė turi keturis simbolius: A, B, C, D. Parašykite visus galimus trijų ženklų žodžius, sudarytus iš šios abėcėlės simbolių.“

Parašykite programą apibendrintam uždaviniui spręsti. Duota n simbolių abėcėlė, kurią sudaro tik didžiosios lietuviškosios abėcėlės raidės. Reikia rasti visus galimus k ženklų žodžius, sudarytus iš šios abėcėlės simbolių.

124. NULIAI SKAIČIAUS GALE. Duotas dešimtainis natūrinis skaičius n. Parašykite programą rasti tokiai skaičiavimo sistemai, kuria užrašius duotąjį skaičių, gautume kuo daugiau nulių jo pabaigoje. Jei galimi keli variantai, užtenka pateikti vieną.

A, Ą
B
C
Č
D
E, Ę, Ė
F
G
H
I, Į, Y
J
K
L
M
N
O
P
R
S
Š
T
U, Ų, Ū
V
Z
Ž

Du žodžiai lyginami tokiu būdu: imamos jų pirmosios raidės, ir žiūrimi prioritetai. Jei jie nesutampa, tai žodyne pirmiau bus žodis, turintis didesnio prioriteto raidę. Jei prioritetai lygūs, tai pereiname prie antroje pozicijoje esančių simbolių ir kartojame tuos pačius veiksmus. Jei vienas žodis yra kito žodžio pradžia, tai pirmesnis turi būti trumpesnysis žodis.

Reikia parašyti programą, kuri iš tekstinės bylos perskaitytų žodžius, juos surūšiuotų ir sutvarkytą žodžių sąrašą įrašytų į tekstinę bylą.

126. ŠEŠIOLIKTAINIŲ SKAIČIŲ KODAVIMAS. (teorinis uždavinys). Šešioliktainiai skaitmenys yra 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F. Visi skaitmenys šešioliktainio skaičiaus užraše vienodai tikėtini. Nuliai skaičiaus pradžioje nerašomi.

Sveikojo teigiamo šešioliktainio skaičiaus užrašą reikia užkoduoti tik dešimtainiais skaitmenimis: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9.

1. Kiekvieną šešioliktainio skaičiaus skaitmenį reikia koduoti atskirai (t. y. viso šešioliktainio skaičiaus negalima paversti dešimtainiu).
2. Vieną šešioliktainio skaičiaus skaitmenį galima koduoti dviem dešimtainiais skaitmenimis.

1. Koduotą skaičiaus užrašą turi būti galima vienareikšmiškai dekoduoti.
2. Koduoto skaičiaus ilgis turi būti minimalus.

127. SIŲSTUVAI IR IMTUVAS.   Į vieną imtuvą signalus siunčia n siųstuvų (1 <= n <= 20 ).
Siųstuvas k skleidžia signalus kas T_k (1 <= T_k <= 100) sekundžių, o šie imtuvą pasiekia po L_k (1 <= L_k <= 50) sekundžių. Taigi kiekvieno siųstuvo darbą aprašo du skaičiai. Pavyzdžiui, T_k = 3, L_k = 2. Jei siųstuvas išsiųs signalus laiko momentais 1 ir 4, tai imtuvas gaus signalus laiko momentais 3 ir 6.

Gali atsitikti taip, kad tuo pačiu metu į imtuvą ateina keli signalai iš karto. Gautasis signalas (kelių signalų mišinys) vadinamas blogu signalu.

Tarkime, kad visi siųstuvai pasiuntė pirmąjį signalą vienu metu ir toliau veikia be perstojo.

Parašykite algoritmą, kuris nustatytų, kiek procentų visų signalų, kuriuos gauna imtuvas, yra blogi.

128. POKERIS. Šis kortų žaidimas dažnas lošimų automatuose. Panagrinėkime supaprastintą pokerio variantą. Automatas iš 24 kortų kaladės (nuo devynakės iki tūzo) parenka lošėjui penkias atsitiktines kortas. Žaidėjas nusprendžia, kurias keturias iš penkių kortų jis norėtų pasilikti, o kurią vieną pakeisti (kortą keisti privaloma). Nurodžius keičiamą kortą, automatas įdeda ją į kaladę ir iš jos išrenka bet kurią vieną kortą.

Nuo turimų penkių kortų priklauso išlošimas. Išlošiama, jei iš turimų kortų galima sudaryti kurią nors iš žemiau išvardytų kombinacijų:

1. Pora (dvi vienodo rango kortos, pavyzdžiui, dvi damos);
2. Dvi poros (pavyzdžiui, dvi dešimtakės ir du tūzai);
3. Trejetas (trys vienodo rango kortos, pavyzdžiui, trys devynakės);
4. Ketvertas (keturios vienodo rango kortos, pavyzdžiui, keturi karaliai);
5. Pilni namai – (juos sudaro aukščiau apibrėžti trejetas ir pora);
6. Visos kortos vienos rūšies (pavyzdžiui, visi kryžiai);
7. Visos kortos iš eilės (pavyzdžiui, devynakė, dešimtakė, valetas, dama ir karalius; kortų išsidėstymo tvarka nesvarbi);
8. Pokeris – visos kortos išdėstomos iš eilės ir yra vienos rūšies.

Pavyzdys. Tarkime, jūs pasilikote dvi damas ir du karalius. Atsitiktinai ištraukus penktą kortą galite gauti arba tą pačią situaciją (Dvi poras) arba Pilnus namus.

Kaip sužinoti, kokia tikimybė susidaryti Pilniems namams atsitiktinai ištraukus penktą kortą? Kadangi iš 24 kortų kaladės išimtos dvi damos ir du karaliai (t. y. keturios kortos), tai penktą kortą galime ištraukti 24 – 4 = 20 būdų, taigi iš viso yra 20 galimų skirtingų kombinacijų. Tačiau Pilni namai susidarys tik tada, jei ištraukta korta bus arba dama, arba karalius. Kadangi tarp kaladėje likusių 20 kortų yra dvi damos ir du karaliai, tai yra 2 + 2 = 4 galimos skirtingos kombinacijos, kada gausime Pilnus namus. Taigi tikimybė, kad susidarys Pilni namai bus 4 / 20 = 0,2.
O štai tikimybė, kad pasilikę dvi damas ir du karalius ir atsitiktinai ištraukus penktą kortą, turėsime tas pačias Dvi poras, lygi 0,8. Tai nesunku apskaičiuoti. Mat visų galimų situacijų tikimybių suma visada lygi 1. O šiuo atveju galimos tik dvi situacijos.

– raidė nurodo kortos rūšį: Š – širdys, B – būgnai, K – kryžiai, V – vynai.
– skaičius nurodo kortos rangą: 0 – devynakė, 1 – dešimtakė, 2 – valetą, 3 – damą, 4 – karalių, 5 – tūzą.

129. SIŲSTUVAI IR IMTUVAS. (Vykdymo laikas – 1 min) Į vieną imtuvą signalus siunčia n siųstuvų ( 1 <= n <= 20 ).
Siųstuvas k skleidžia signalus kas T_k sekundžių, o šie imtuvą pasiekia po L_k sekundžių. Kiekvienas siųstuvas turi pasiųsti pranešimą susidedantį iš P_k signalų. Taigi kiekvieno siųstuvo darbą apibūdina trys skaičiai. Pavyzdžiui, T_k = 3, L_k = 2, P_k = 2. Jei siųstuvas įjungiamas laiko momentu 0, tai jis išsiųs du signalus laiko momentais 0 ir 3, o imtuvas gaus signalus laiko momentais 2 ir 5.

Gali atsitikti taip, kad tuo pačiu metu į imtuvą ateina keli signalai iš karto. Gautasis signalas (kelių signalų mišinys) vadinamas blogu signalu.

Siųstuvai gali būti įjungti arba išjungti. Kai siųstuvas pradeda veikti (t. y. įjungiamas), jis tuoj pat išsiunčia savo pranešimą ir tada išjungiamas.

Momentas, kada paleidžiamas(i) dirbti pirmasis(ieji) siųstuvas(i), vadinamas nuliniu laiko momentu (nuo tada imamas skaičiuoti laikas). Darbo pabaiga laikomas momentas, kai imtuvas gauna paskutinį signalą.

Parašykite algoritmą nustatantį, kuriuo laiko momentu reikia įjungti kiekvieną siųstuvą, kad imtuvas negautų blogų signalų, o visi pranešimai būtų perduoti per trumpiausią laiką.

Pastaba. Laikas, per kurį siųstuvas perduoda pranešimą imtuvui, neviršija dviejų šimtų sekundžių. Pradedama skaičiuoti nuo siųstuvo įjungimo momento ir baigiama, kai imtuvas gauna paskutinį pranešimo signalą.

130. TRYS VIENODI SKAITMENYS.  (Vykdymo laikas – 50 s.) Yra tokių įdomių skaičių, kurie gali būti išreikšti dviejose skirtingose skaičiavimo sistemose trimis vienodais skaitmenimis, pavyzdžiui,
273 = 333₉ = 111₁₆.

Parašykite algoritmą visiems intervalo [m, n] skaičiams, pasižymintiems šia savybe, rasti (1 <= m <= n <= 10000).

Kitose dviejose eilutėse – šio skaičiaus užrašas dviem skaičiavimo sistemomis.

Skaičius kuria nors skaičiavimo sistema (nedešimtaine) užrašomas griežtai laikantis šių taisyklių: pradžioje – sistemos pagrindas, po to palikus vieną tarpą – skaičiaus užrašas šia sistema (tarp skaitmenų paliekama po vieną tarpą). Jei skaičiavimo sistema didesnė už dešimtainę, dalis skaitmenų užrašomi dviem dešimtainiais skaitmenimis.

Ketvirtoje bylos eilutėje rašomas tolesnis sąlygas tenkinantis skaičius ir t. t.

Jei duotame intervale nėra nei vieno skaičiaus, pasižyminčio nurodyta savybe, į rezultatų bylą rašomas nulis.

131. LOBIO IEŠKOJIMAS.  Tarkime, turime 4x4 laukelių labirintą. Keliautojo tikslas – kuo greičiau rasti paslėptą lobį ir išeiti iš labirinto. Į labirintą galima patekti tik pro vieną kurioje nors išorinėje sienoje esantį plyšį – tai drauge įėjimas ir išėjimas. Būdamas labirinte (t.y. kuriame nors laukelyje) keliautojas gali eiti bet kuria iš keturių krypčių: į viršų, į apačią, į kairę, į dešinę, žinoma, jei tik netrukdo sienos. Įstrižai eiti negalima.

Labirinto pavyzdys pateiktas žemiau esančiame paveiksle.

Kiekvienas labirinto laukelis yra tam tikros rūšies. Iš viso esama šešių rūšių laukelių:

Sausuma S. Tokių laukelių labirinte yra penki.

Trys duobės D₁, D₂, D₃. Jei keliautojas ateina į laukelį D₁, tai jis permetamas į laukelį D₂ ir iš ten atlieka tolesnį ėjimą. Analogiškai patekęs į laukelį D₂,  keliautojas permetamas į D₃, o atsidūręs laukelyje D₃, patenka į laukelį D₁.

Pelkė P. Ji viena. Pelke prasideda upė.

Žiotys Ž. Jos vienos – jomis baigiasi upė.

Upė. Ją sudaro penki laukeliai U₁, U₂, U₃, U₄, U₅. Upėje atsidūrusį keliautoją neša srovė. Iš laukelio U₁ jis patenka į U₄, iš U₂ – į U₅. Jei keliautojas patenka į kitus tris upės laukelius, jis nunešamas į žiotis Ž. Toliau keliautojas turės tęsti kelionę iš laukelio, į kurį jį atnešė srovė. Visi upės laukeliai susisiekiantys, t. y. U₁ turi bendrą kraštinę su U₂, U₂ su U₃, ir t. t. Pelkė P susisiekia su U₁, o žiotys Ž – su U₅.

Lobis L. Laikoma, jog lobis surastas, kai keliautojas atsistoja laukelyje L.

Keliautojas turi du užtaisus sienoms sprogdinti. Sienos sprogdinimas lygus vienam ėjimui. Išsprogdinęs skylę sienoje, keliautojas gali pro ją pralįsti. Sprogdinant sieną, sugriaunamas tik vienas sienos laukelis, o ne visa siena. Susprogdintos sienos neatsistato. Draudžiama sprogdinti išorines labirinto sienas, t. y pasidaryti išėjimą. Keliautojas gali ir nepanaudoti sprogmenų arba panaudoti tik vieną.

Sprogdinti galima iš bet kurių laukelių. Jei sprogdinama iš laukelių, į kuriuos keliautojas buvo permestas ar jį į ten atnešė srovė, po sprogdinimo keliautojas pasilieka tame pačiame langelyje. Pirmu ėjimu po sprogdinimo keliautojas gali lįsti pro skylę arba eiti į kitą gretimą laukelį (t. y. jis nebus iš karto permestas į kitą duobę bei jo nenuneš srovė). Beje, tai yra vienintelis atvejis, kai keliautojas pasilieka tame pačiame langelyje.

Įėjimas į labirintą bei išėjimas iš labirinto laikomas ėjimu. Permetimas iš vienos duobės į kitą arba nunešimas pagavus srovei nėra ėjimas.

Parašykite programą, kuri pagal duotą labirintą nustatytų, kiek mažiausiai ėjimų reikia, kad keliautojas rastų lobį ir išeitų iš labirinto.

Paskutinėse dviejose bylos eilutėse yra po tris skaičius. Pirmoje iš jų aprašyta dviejų laukelių ilgio siena, antroje – trijų. Pirmasis skaičius eilutėje parodo, prie kurios labirinto išorinės sienos liečiasi vidinė siena:. skaičius 1 nurodo lietimąsi su viršutine siena, 2 – su dešiniąja, 3 – su apatine, 4 – su kairiąja. Kiti du skaičiai nusako tarp kurių eilučių ar stulpelių yra siena (žr. žemiau pateiktą pavyzdį).

Pradiniai duomenys tokie, kad sprendinys visuomet egzistuoja.

132. NETVARKINGAS BIBLIOTEKININKAS. Bibliotekoje yra leidinių, kurie susideda iš kelių tomų. Tačiau šie tomai lentynose sumaišyti su kitų leidinių tomais, pavyzdžiui:

Skaičiai virš lentynos žymi vietą lentynoje, skaičiai pirmojoje eilutėje rodo leidinio numerį, antrojoje – leidinio tomo numerį.

Knygų tvarkyti bibliotekininkas nenori. Tačiau nori, kad būtų lengviau jas rasti. Tam jis susirado kiekvieno leidinio pirmą tomą, pasižiūrėjo, kiek tomų sudaro leidinį ir įsidėmėjo pirmojo tomo vietą lentynoje, t. y. susidarė lentelę. Aukščiau pateiktam pavyzdžiui lentelė atrodytų šitaip:
 

Pirma lentelė

Leidinys	Pirmo tomo vieta	Tomų skaičius
1	1	4
2	3	4
3	10	2
4	11	1

 
Po to bibliotekininkas sudarė dar vieną lentelę, turinčią tiek elementų, kiek yra vietų lentynoje. Į kiekvieną lentelės elementą įrašė tam tikrą skaičių. Jei vieta lentynoje tuščia, į lentelės elementą įrašė nulį. Jei toje vietoje padėtas kurio nors leidinio tomas, į lentelę įrašė vietą, kurioje padėtas sekantis  to paties leidinio tomas. Jei ten padėtas paskutinis kurio nors leidinio tomas, į lentelę įrašomas skaičius: -1.

Mūsų pateiktam pavyzdžiui antroji lentelė atrodo šitaip:
 

1	2	3	4	5	6	7	8	9	10	11	12	13	14
4	5	6	2	-1	7	9	-1	-1	8	-1	0	0	0

Tokiu būdu bibliotekininkas galėjo lengviau rasti skaitytojo pageidaujamą tomą. Pavyzdžiui, skaitytojas pageidauja gauti antrojo leidinio trečiąjį tomą. Iš pirmos lentelės bibliotekininkas mato, kad pirmasis tomas lentynoje yra trečias. Tada iš antros lentelės trečio stulpelio aišku, kad antrasis tomas bus šeštoje lentynos pozicijoje. O šeštasis stulpelis rodo, kad trečiasis tomas yra septintoje lentynos pozicijoje.

Tačiau kartą prisireikė perrašyti antrąją lentelę. Bibliotekininkas netyčia galėjo padaryti vieną klaidą – įrašyti ne tokį skaičių antroje eilutėje. Bibliotekininkas tikrai žino, kad perrašydamas nulius jokios klaidos nepadarė: kur senoje lentelėje buvo įrašyti nuliai, ten ir perrašytoje lentelėje tikrai yra nuliai. Taip pat aišku, kad pakeistasis skaičius yra realus, t.y. jei lentynoje yra 15 vietų knygoms, bibliotekininkas per klaidą negalėjo įrašyti 16 ar didesnio skaičiaus.

Parašykite algoritmą, kuris nustatytų, ar bibliotekininkas padarė klaidą, ir jei taip – ištaisytų ją, jeigu tai įmanoma.

Tolesnėse n eilučių pateikta pirmoji lentelė. Į kiekvieną eilutę įrašyta po du skaičius: leidinio pirmojo tomo vieta ir leidinio tomų skaičius.

Kitoje eilutėje įrašytas vietų skaičius lentynoje k (1 <= k <= 2000). Toliau eina k eilučių, kuriose pateikta antroji lentelė. Kiekvienoje eilutėje įrašyta po vieną skaičių.

Jei klaidą pataisyti galima, tai spausdinami du skaičiai (vienoje eilutėje, atskirti tarpu). Pirmasis skaičius – tai perrašytos lentelės stulpelis, kur buvo klaida, antrasis – atstatyta reikšmė.

133. NEŽINOMAS KODAVIMAS. Duota programa KOD.EXE. Ji dvejetainėje byloje A esančius duomenis užkoduoja ir surašo į bylą B.

Kaip koduoja programa KOD.EXE, galite sužinoti eksperimentuodami – pateikdami jai savus pradinius duomenis ir analizuodami iš jos gautus rezultatus.

Į pradinių duomenų bylą A žiūrima kaip į ištisinę bitų eilę. Bitai skirstomi į vienodo ilgio grupes po 7, 6, 5, 4, 3 arba 2 bitus. Jei paskutinė grupė nepilna, tai jos pabaiga užpildoma dvejetainiais nuliais.

Kiekviena grupė koduojama atskiru baitu.

KOD.EXE duom.dat duom.kod

Testuojama naudojantis bylomis, kurių dydis (užkoduotų) ne daugiau kaip 10000 baitų.

134. ŠAUDYMAS. Visiems gerai žinomas šaudymo taikinys: apskritimais apribotas plotas.

Taikinio centras sutampa su koordinačių pradžia. Duotas pirmojo (mažiausio) apskritimo spindulys r. Į jį patekę šūviai vertinami 10 balų. Šūvis, patekęs ant apskritimo ribos, vertinamas taip, tarsi būtų pataikyta į apskritimo ribojamą plotą. Kiekvieno tolesnio apskritimo spindulys du kartus didesnis už prieš einančio, o šūviai vertinami vienu balu mažiau. Jei pataikyta už paskutiniojo (dešimtojo) apskritimo ribos, šūvis vertinamas 0 balų.

Parašykite algoritmą balų, surinktų už šūvius, sumai rasti.

Visi pradiniai duomenys yra sveikieji skaičiai.

135. LABIRINTAS.  Duotas stačiakampis labirintas, sudarytas iš laukelių. Jūs stovite labirinto įėjime ir žiūrite labirinto kryptimi. Įėjimą iš abiejų pusių riboja sienos.

Parašykite algoritmą, kuris padėtų Jums išeiti iš labirinto. Iš labirinto visuomet galima išeiti.

Kreipdamiesi į modulio procedūrą dydis, sužinosite labirinto aukštį n (3 <= n <= 64000) ir plotį m (3 <= m <= 100). Abu skaičiai, kuriuos grąžina procedūra, yra longint tipo.

Kreipdamiesi į funkcijas siaure, pietus, rytai, vakarai sužinosite, ar galite iš laukelio, kuriame stovite, judėti atitinkama kryptimi. Visos šios funkcijos grąžina vieną loginio tipo reikšmę.

Nė viena iš aukščiau išvardytų funkcijų neturi pradinių duomenų.

Kreipdamiesi į procedūras priekin, atgal, kairėn, dešinėn paeisite labirintu per vieną laukelį nurodyta kryptimi. Šios procedūros negrąžina jokio rezultato.

Jūsų programa neturi spausdinti jokių rezultatų. Pasiekus išėjimą iš labirinto, modulis sustabdys jūsų programą. Modulis taip pat sustabdys jūsų programą, jei bandysite atlikti klaidingą ėjimą, t. y. eiti į laukelį, kuriame yra labirinto sienos arba jei jūsų programa viršys tam tikrą ribinį ėjimų skaičių (taip gali atsitikti, jei, pavyzdžiui, imsite vaikščioti ratu).

Nebūtina rasti trumpiausią kelią iš labirinto.

136. NAMELIAI.  (Vykdymo laikas – 1 min) Duota n pagaliukų, kurių ilgiai išreikšti sveikaisiais skaičiais. Iš jų reikėtų sudėti namelius: jo siena – kvadratas, stogas – bet koks trikampis, kurio viena kraštinė sutampa su sienos briauna.
 

Pagaliukų sudurti negalima. Kiekvieną pagaliuką galima panaudoti tik vieną kartą.

Parašykite programą, kuri suskaičiuotų, kiek daugiausia namelių galima sudaryti iš duotų pagaliukų.

137. SIŲSTUVAI IR IMTUVAS. Į vieną imtuvą signalus siunčia n siųstuvų ( 1 <= n <= 20 ).
Siųstuvas k skleidžia signalus kas T_k sekundžių, o šie imtuvą pasiekia po L_k sekundžių. Kiekvienas siųstuvas turi pasiųsti pranešimą, susidedantį iš P_k signalų. Taigi kiekvieno siųstuvo darbą apibūdina trys skaičiai. Pavyzdžiui, T_k = 3, L_k = 2, P_k = 2. Jei siųstuvas įjungiamas laiko momentu 0, jis išsiųs du signalus laiko momentais 0 ir 3, o imtuvas gaus signalus laiko momentais 2 ir 5.

Gali atsitikti taip, kad tuo pačiu metu į imtuvą ateina keli signalai iš karto. Gautasis signalas (kelių signalų mišinys) vadinamas blogu signalu.

Siųstuvai gali būti įjungti arba išjungti. Kai siųstuvas pradeda veikti (t. y. įjungiamas), jis tuoj pat išsiunčia savo pranešimą ir tada išjungiamas. Siųstuvai turi pradėti darbą paeiliui: pirmasis, antrasis ir t. t.

Pavyzdžiui, trečiasis siųstuvas negali būti įjungtas anksčiau nei antrasis (bet gali dirbti kartu su anksčiau įjungtais siųstuvais). Tuo pačiu momentu pradėti siųsti pranešimus keli siųstuvai negali.

Momentas, kada paleidžiamas dirbti pirmasis siųstuvas, vadinamas nuliniu laiko momentu (nuo tada pradedamas skaičiuoti laikas). Darbo pabaiga laikomas momentas, kai imtuvas gauna paskutinį signalą.

Parašykite algoritmą, kuris nustatytų, kuriuo laiko momentu reikia įjungti kiekvieną siųstuvą laikantis nustatytos tvarkos, kad imtuvas negautų blogų signalų, o visi pranešimai būtų perduoti per trumpiausią laiką.

Pastaba. Laikas, per kurį siųstuvas perduoda pranešimą imtuvui, neviršija dviejų šimtų sekundžių. Pradedama skaičiuoti nuo siųstuvo įjungimo momento ir baigiama, kai imtuvas gauna paskutinį pranešimo signalą.

138. SUKABINTI ŽIEDAI. Tarpusavyje sukabinta n žiedų. Pavyzdys pateiktas 138.1 paveiksle.

Parašykite algoritmą, kuris rastų, kiek daugiausiai žiedų galima pašalinti, kad tarp žiedų a ir b liktų vientisa, be išsišakojimų grandinė.

139. ERDVĖLAIVIS. Erdvėlaivis turi nugabenti svarbų krovinį iš vienos bazės į kitą, tačiau skrydžiui ne visada užtenka kuro, kurį jis gali pasiimti kelionės pradžioje. Todėl jis skrenda pro tarpines bazes, jose papildydamas kuro atsargas. Įvairiose bazėse kuro atsargų papildymas kainuoja nevienodai, todėl turėdamas ribotą kreditą skirtą kurui erdvėlaivio vadas ne visada pasirenka trumpiausią kelią.

Galioja šios sąlygos:

 kuro papildymas bazėje kainuoja fiksuotą piniginių vienetų skaičių (nesvarbu kiek pilama kuro), todėl kuro bakas užpildomas pilnai;

 erdvėlaivis skrieja pastoviu greičiu;

 laikoma, kad bazėse erdvėlaivis užtrunka artimą nuliui laiko tarpą, todėl kelionės trukmė proporcinga nuskristam keliui.

• erdvėlaivio kuro bako talpa, nurodyta kuro tūrio vienetais (1 <= V <= 100),
• kuro sąnaudos vienam ilgio vienetui (1 <= S <= 100),
• turimas kreditas, išreikštas piniginiais vienetais (1 <= K <= 100),
• bazių, kuriose erdvėlaivis gali papildyti kuro atsargas, skaičius (2 <= N <= 100).

k – kuro bako užpildymo kaina bazėje, nurodyta piniginiais vienetais (0 <= k <= 100),

(x, y, z) – bazės padėtis erdvėje, visos koordinatės nurodytos ilgio vienetais (0 <= x, y, z <= 100).

Į paskutiniąją eilutę įrašykite N-osios bazės numerį.

140. POKERIS. Šis kortų žaidimas dažnai sutinkamas lošimų automatuose. Mes nagrinėsime supaprastintą pokerio variantą. Automatas iš 24 (nuo devynakės iki tūzo) kortų kaladės atsitiktinai išrenka lošėjui penkias kortas. Lošėjas nusprendžia, kurias kortas jis norėtų pasilikti, o kurias – pakeisti. Lošėjo keičiamas kortas automatas vėl įdeda į kaladę ir vėl iš jos atsitiktinai išrenka tiek kortų, kiek jų buvo įdėta.
Nuo susidariusios kortų kombinacijos priklauso išlošimas. Išlošiančios padėtys yra šios:

1. Pora – dvi vienodo rango kortos (pavyzdžiui, dvi damos).
2. Dvi poros (pavyzdžiui, dvi dešimtakės ir du tūzai).
3. Trejetas – trys vienodo rango kortos.
4. Iš eilės – visos kortos galima išdėstomos paeiliui pagal rangą (pavyzdžiui, devynakė, dešimtakė, berniukas, dama ir karalius).
5. Vienos spalvos – visos kortos vienos rūšies (pavyzdžiui, visi kryžiai).
6. Pilni namai – trejetas ir pora.
7. Ketvertas – keturios vienodo rango kortos.
8. Pokeris – visos kortos išdėstomos paeiliui ir yra vienos rūšies.

Vienas padėtis yra lengviau sudaryti, kitas – sunkiau. Todėl sudarius vienas padėtis išlošiama mažiau pinigų, kitas – daugiau. Yra sudaryta išlošimų lentelė, kurioje nurodyta, kiek pinigų išlošiama susidarius kiekvienai iš aštuonių padėčių.

Pavyzdys. Tarkime, jūs pasilikote dvi damas ir du karalius ir norite sužinoti, kokia tikimybė susidaryti Pilniems namams atsitiktinai ištraukus penktą kortą. Kadangi iš 24 kortų kaladės išimtos dvi damos ir du karaliai, tai penktą kortą galime ištraukti 24 – 2 – 2 = 20 būdų, taigi iš viso yra 20 galimų skirtingų kombinacijų. Tačiau Pilni namai susidarys, jei ištraukta korta bus arba dama, arba karalius. Kadangi kaladėje yra dvi damos ir du karaliai, tai bus 2 + 2 = 4 galimos skirtingos kombinacijos, kuriose gali sudaryti Pilnus namus. Taigi tikimybė, kad susidarys Pilni namai bus 4 / 20 = 0,2.

Pavyzdys. Tarkime, Jūs pasilikote dvi damas ir du karalius ir susidarius Dviems poroms išlošiate 5 Lt, o susidarius Pilniems namams išlošiate 30 Lt, kitos išlošiančios padėtys šiuo atveju susidaryti negali. Jūs jau paskaičiavote, kad, Pilnų namų susidarymo tikimybė šiuo atveju lygi 0,2. Kadangi likusiose 16 iš 20 galimų kombinacijų yra Dvi poros, tai jų susidarymo tikimybė bus lygi 16 / 20 = 0,8. Taigi tuo atveju, kai pasiliksite anksčiau minėtas keturias kortas, jūsų išlošimo vidurkis bus lygus 0,8 x 5 Lt + 0,2 x 30 Lt = 10 Lt (vidutiniškai galite išlošti 10 Lt).

Kitose aštuoniose eilutėse yra po vieną sveiką skaičių, kuris yra išlošimo suma gaunama susidarius atitinkamai padėčiai kortose.

141. DIDELĖ VALSTYBĖ. Terainkognitos valstybę valdo diktatorius. Kaip dažniausiai būna tokiais atvejais, bet kokia tiksli informacija apie valstybę yra slepiama. Diktatorius teigia, kad jo valstybė yra labai didelė ir pateikia rimtų argumentų: Terainkognitą galima sutalpinti į n x n (1 <= n <= 2000) dydžio kvadratinį žemės plotą ir valstybės kontūrai lies visus jo kraštus! Tačiau tikslaus ploto diktatorius pasakyti nenori.

Žinoma, kad valstybės kontūras yra iškiliojo daugiakampio formos.

Parašykite algoritmą, kuris apskaičiuotų valstybės plotą.

Jei taškas priklauso valstybės sienai, laikoma, kad jie priklauso valstybei.

Norėdami sužinoti kvadratinio žemės ploto koordinates, kreipkitės į procedūrą dydis. Ji grąžins tris sveikuosius skaičius: apatinio kairiojo kvadrato kampo koordinates bei kvadrato dydį n.

Pavyzdinį modulį rasite diskelyje. Testavimui bus naudojama kita modulio versija.

142. NEŽINOMAS KODAVIMAS. Duota programa KOD.EXE. Ji dvejetainėje byloje A esančius duomenis užkoduoja ir surašo į bylą B.

Kaip koduoja programa KOD.EXE, galite sužinoti eksperimentuodami – pateikdami jai savus pradinius duomenis ir analizuodami iš jos gautus rezultatus.

Į pradinių duomenų bylą A žiūrima kaip į ištisinę bitų eilę. Bitai skirstomi į vienodo ilgio grupes po 7, 6, 5, 4, 3 arba 2 bitus. Jei paskutinė grupė nepilna, tai jos pabaiga užpildoma dvejetainiais nuliais.

Kiekviena grupė koduojama atskiru baitu.

KOD.EXE duom.dat duom.kod

Testuojama naudojantis bylomis, kurių dydis (užkoduotų) ne daugiau kaip 10000 baitų.

143. LOŠIMAS DISKU. (vykdymo laikas – 5 s. 12000 testų) Lošia dviese. Abu lošėjai sukioja į 6 segmentus suskirstytą žemiau nupieštą diską . Segmentai sužymėti skaičiais nuo 1 iki 6.

Lošėjai paeiliui sukioja diską per vieną segmentą į kairę arba į dešinę. Lošėjas, pasukęs diską, perskaito jo viršutiniame segmente atsiradusį skaičių n ir jį prideda prie sumos s.

Lošimo pradžioje s = 0. Lošimas baigiamas, kai s pasiekia sutartą skaičių m (pvz., 1000). Jeigu s = m, tai laimi tas, kuris pasiekė šį skaičių. Jeigu s > m, tai pralaimi tas, kas buvo priverstas viršyti m (t.y. laimėjo tas, kuris priešininkui sudarė tokią situaciją, kad jis nebegalėjo parinkti tokio ėjimo, kad suma neviršytų sutarto skaičiaus).

function diskas (n, s, m: integer): integer;

Funkcijos reikšmė yra skaičius, kuris turi atsirasti viršutiniame disko segmente atlikus ėjimą.

Pastaba. Reikia tik rasti ėjimą, bet jo neatlikti. Ėjimą atliks lošimą valdanti programa, kurios sudaryti nereikia.