Pirmojo etapo uždavinių sąlygos

144. LOGINIS KUBAS. Iš taško X reikia patekti į tašką Z. Keliai eina per kubo briaunas ir viršūnes. Per briauną galima eiti visada. Per viršūnę galima eiti tik tada, kai jos vardu pažymėto loginio kintamojo reikšmė yra true.

Užduotis. Parašykite loginį reiškinį, kurio reikšmė būtų true tada ir tik tada, kai iš taško X galima patekti į tašką Z.

145. FIGŪROS IŠ VIRVUTĖS. Ilgoje virvutėje kas 10 cm užmegzta po mazgelį (virvutės pradžioje užrištas mazgelis, o gale jo nėra). Lenkdami per mazgelius iš virvutės galime sudaryti tokias geometrines figūras: trikampius, kvadratus, stačiakampius.
Pavyzdžiui, kai virvelėje užmegzta 10 mazgelių, galime sudaryti tokias figūras:

Žinodami užrištų virvutėje mazgelių skaičių pabandykite sudaryti kuo daugiau skirtingų anksčiau minėtų geometrinių figūrų (sutampančių figūrų neturi būti). Vienodos formos figūros laikomos skirtingomis, jei jų kraštinių ilgiai yra skirtingi.

Užduotis. Parašykite algoritmą šiam uždaviniui išspręsti, kai pradinis duomuo – mazgelių skaičius, o rezultatai – sudarytų trikampių, kvadratų ir stačiakampių skaičiai atskirai. Skaičiuodami stačiakampių skaičių, kvadratų nelaikykite stačiakampiais.

146. ROBOTAS IR KUBELIAI. Kubeliai sudėti į tris greta esančias krūveles. Robotas vienu žingsniu (judesiu) gali paimti kubelį nuo bet kurios krūvelės ir pastatyti jį ant gretimos krūvelės viršaus. Kubelius reikia sukrauti taip, kad visose krūvelėse jų būtų po lygiai arba susidarytų tik vienas laiptelis. Pavyzdžiui,

Vienas laiptelis reiškia, kad norint nuo pirmos krūvelės patekti ant trečios teks lipti vieną kartą (tik žemyn arba tik aukštyn).

Užduotis. Sudarykite algoritmą, kuri rastų trumpiausią roboto žingsnių seką, kai žinomas kiekvienos krūvelės kubelių skaičius.
Roboto žingsnį sudaro du skaičiai – krūvelės, nuo kurios paimamas kubelis, ir krūvelės, ant kurios uždedamas kubelis, numeriai. Jei galimi keli variantai – spausdinti bet kurį. Jei nereikia perkelti nei vieno kubelio, spausdinkite pranešimą GERAI.

Užduotis. Parašykite algoritmą, kuris nustatytų ar iš pradinės viršūnės galima patekti į galinę.

148. MOKYTOJO DIENA.  Spalio mėnesio pirmąjį sekmadienį švenčiama Mokytojo diena.

Užduotis. Parašykite algoritmą, nustatantį kurią mėnesio dieną duotaisiais metais bus švenčiama Mokytojo diena. Žinoma, kad duotieji metai priklauso šiam šimtmečiui.

149. LAIPTAI IŠ KUBELIŲ. Iš kubelių galima sudėlioti įvairaus aukščio ir formos laiptus (iš kairės pusės laiptai statūs, kiekviena pakopa – kubelio pločio).

Užduotis. Parašykite algoritmą, kuris išspausdintų kokius laiptus galima sudėlioti iš n kubelių (n <= 14) bei rastų skirtingų formų laiptų skaičių.

Šio pavyzdžio rezultatas galėtų būti toks:
6
5 1
4 2
3 2 1
Laiptų skaičius: 4

Elektroninis indikatorius  sudarytas iš šešių horizontalių ir aštuonių vertikalių elektroninių brūkšnelių.

Nuspaudus skaitmenį užsidega atitinkami brūkšneliai. Paveikslėlyje parodomas indikatoriaus skaitmenų vaizdavimas.
 

Kartą sugedo elektroninis indikatorius. Atėjus svečiui ir surinkus buto numerį, turėjo  numeris neužgeso, o pagaliukai, kurie turėjo užsidegti, kad matytųsi naujas numeris, pakeitė savo būsenas: tie kurie degė užgeso, kurie nedegė – ėmė šviesti.

Užduotis. Žinoma, kad sugedus indikatoriui name pabuvojo n svečių, taip pat žinoma, kuriame bute kiekvienas iš jų lankėsi. Visi svečiai ėjo po vieną. Prieš pirmojo svečio vizitą indikatorius rodė 00. Parašykite algoritmą, kuris rastų ir išspausdintų elektroninio indikatoriaus būseną po visų svečių apsilankymo. Kaip ekrane pavaizduoti indikatoriaus būseną, sugalvokite patys.

151. DIDMENINIS PIRKIMAS. Žinoma, kad perkant daugiau prekių jų vienetas kainuoja pigiau. Pundelyje yra 12 porų kojinių, dėžėje – 12 pundelių. Pavyzdžiui, kojinių dėžė kainuoja 247 litus, pundelis – 21 lt, pora – 2 lt. Įdomu tai, kad jei mums reikėtų 11 porų kojinių, tai geriau pirkti pundelį ir vienerias kojines kam nors atiduoti.

Užduotis. Pirkėjas nori įsigyti n porų kojinių. Sudarykite algoritmą, vadovaudamiesi kuriuo pigiausiai nupirktume kojines. Jei už tą pačią kainą galima nupirkti didesnį ir mažesnį kiekį kojinių, tai perkamas didesnis kiekis. Raskite perkamų dėžių, pundelių ir porų skaičių.

152. SLAPTA KALBA. Julija ir Rita dažnai mokykloje dalijasi paslaptimis. Norėdamos, kad niekas jų nesuprastų, sugalvojo slaptą kalbą. Kiekvienas žodis padalijamas į dvi dalis ir tos dalys sukeičiamos vietomis. Žodžiai, sudaryti tik iš vienos raidės, paliekami tokie patys. Pavyzdžiui, sakinys:

Aš pirkau naujus džinsus.

Ša kaupir jusnau susdžin.

Ša aupirk ujusna sdžinsu.

Sakinio ilgis neviršija 255 simbolių, jis sudarytas tik iš raidžių bei tarpų ir užbaigiamas tašku. Tarp žodžių palikta po vieną tarpą.

Užduotis. Parašykite algoritmą paveiksliukui spausdinti, kai duotas kvadrato kraštinės ilgis n (n <= 20).

154. TRYS SODININKAI. Trys draugai apsigyvenę kaime nusprendė mokytis sodininkauti. Kaime buvo didžiulis sodas, jame augo po vieną vaismedį kiekviename kvadratiniame ploto vienete.

Kiekvienas iš trijų draugų pasirinko stačiakampį sklypą ir nusprendė prižiūrėti jame esančius medžius. Susirinkus draugėn paaiškėjo, kad jų pasirinkti sklypai persidengia, t. y. kai kuriuos vaismedžius prižiūrės ne vienas, o keletas sodininkų.

Užduotis. Parašykite algoritmą, kuris suskaičiuotų, kiek vaismedžių panorėjo prižiūrėti visi trys draugai.

155. TEKSTO TVARKYMAS. Duotas tekstas, sudarytas iš žodžių, kai kurių skyrybos ženklų (taško, kablelio, dvitaškio bei kabliataškio), skliaustų „(“, „)“ bei tarpų.

Užduotis. Šį tekstą reikia išspausdinti stulpeliu, kurio vienoje eilutėje telpa n simbolių. Prieš atidarantįjį (kairįjį) skliaustą, taip pat po visų skyrybos ženklų turi būti paliekamas tarpas. Jei po uždarančiojo (dešiniojo) skliausto yra skyrybos ženklas, tarp skliausto ir ženklo tarpas nepaliekamas, kitais atvejais po šio skliausto paliekamas tarpas.

Keliant į naują eilutę, skyrybos ženklai bei uždarantysis skliaustas negali būti atskirti nuo prieš juos esančio žodžio, o atidarantysis skliaustas – nuo po jo einančio žodžio. Tekstas turi būti išlygiuotas pagal abu kraštus: pirmasis ir n-asis eilutės simboliai negali būti tarpai. Išimtis – paskutinė eilutė, kuri gali turėti mažiau nei n simbolių. Tarpai tarp žodžių turi būti kiek galima vienodesnio ilgio.

Rezultatas
Abrikosų¤¤vaismedžiai¤užauga
didesni¤¤¤¤¤už¤¤¤¤giminingas
slyvas.¤¤¤Pakankamai¤¤¤gerai
ištveria¤¤šalčius,¤¤pražysta
gegužės¤¤¤¤pradžioje¤¤¤¤¤(ar
viduryje).

Pastaba. Kad pavyzdys būtų suprantamesnis, tarpai jame vaizduojami simboliu „¤“.

156. AR DAUG KALBATE TELEFONU? Klientams pageidaujant „Telekomas“ gali nusiųsti kompiuterinę bylą su mėnesio pokalbių duomenimis. Byloje yra tokie duomenys apie kiekvieną pokalbį:

pokalbio diena ir pradžios laikas;
numeris, su kuriuo sujungta;
pokalbio trukmė minutėmis;
pokalbio kaina.

Sudarykite programą, kuri surinktų tokią telefono abonentui rūpimą informaciją:

• išvardytų 5 (ar mažiau, jei nesusidaro penki) telefono numerius, su kuriais prakalbėtos didžiausios pinigų sumos; jei yra daugiau negu 5 tokie numeriai, pateiktų bet kuriuos penkis;
• rastų 3 (ar mažiau, jei abonentas telefonu naudojosi tik vieną ar dvi paras) paras, kurių metu buvo kalbėta telefonu daugiausia (t. y. pokalbių trukmių suma paroje yra didžiausia); jei yra daugiau negu 3 tokios paros, pateiktų bet kurias tris (para prasideda 0 valandų 0 minučių);
• nustatytų, kokią išlaidų dalį procentais sudaro vietiniai pokalbiai;
• nustatytų, kokią išlaidų dalį procentais sudaro vienos minutės trukmės pokalbiai;

Kiekvienos eilutės ilgis - 43 simboliai, o struktūra tokia:

DD_:_VV.NN_:_***************_:_PPP_:_LLL.CC

Pradiniai duomenys korektiški - visi pokalbiai vyko tik tą patį mėnesį.

Antroje eilutėje spausdinkite tris (ar mažiau) paras (mėnesio dienų numerius), kurių metu daugiausiai kalbėta. Tarp dienų palikite po vieną tarpą.

Trečioje eilutėje spausdinkite išlaidų dalį, kurią sudaro vietiniai pokalbiai bei išlaidų dalį, kurią sudaro vienos minutės trukmės pokalbiai. Šie du skaičiai spausdinami pateikiant du skaitmenis po kablelio. Tarp skaičių paliekama po vieną tarpą.

Pradiniai duomenys

7
01 : 12.00 : *********259601 : 120 : 008.40
10 : 19.20 : ******890025690 : 019 : 174.06
15 : 23.58 : *****8720529405 : 011 : 028.70
16 : 00.14 : *************02 : 010 : 000.00
17 : 01.28 : *********421558 : 015 : 001.07
18 : 15.36 : *********329405 : 310 : 021.05
25 : 08.35 : *******82153360 : 001 : 002.20
 

Rezultatai

890025690 8720529405 329405 259601 82153360
1 16 18
12.96 0.93

Paaiškinimai

Mokėti reikia atitinkamai po 174,06; 8,70; 21,05; 8,40 ir 2,20 Lt. 18 dieną kalbėta 310 min., 1 dieną - 120 min., 10 ir  16 dienomis  – po 19 min. Atsakyme galima pateikti bet kurias tris paras iš šiųketurių

157. ŽAIDIMAS SU ŠAŠKE. Žaidimą su šaške žaidžia vienas žmogus. Lentoje vienas šalia kito nupiešta n kvadratėlių. Jie sunumeruoti nuo 1 iki n. Į kiekvieną kvadratėlį įrašytas sveikasis skaičius nuo -n iki n. Pirmame kvadratėlyje įrašytas nulis. Jame žaidimo pradžioje pastatoma šaškė.

Žaidimas pradedamas metant lošimo kauliuką, turintį nuo 1 iki 6 akių. Žaidėjas pastumia šaškę per tiek kvadratėlių į priekį, kiek iškrito kauliuko akių. Jei šaškė sustoja ant kvadratėlio su teigiamu skaičiumi – ji per tiek kvadratėlių pastumiama į priekį, jei ant neigiamo – per tiek kvadratėlių perstumiama atgal. Taip vaikštoma tol, kol patenkama ant kvadratėlio su nuliu. Tada vėl metamas kauliukas ir judama į priekį.

Jei iš paskutiniojo kvadratėlio šaškei dar reikia judėti į priekį, ji patenka į pirmąjį kvadratėlį. Jei judėdama atgal šaškė patenka į pirmąjį langelį, tai iš ten niekur toliau nebeina – sustoja ir vėl metamas kauliukas.

Sutarta, kad perstumiant šaškę iš vieno kvadratėlio į kitą, ji aplanko ne tik tuos du, bet ir visus jos kelyje pasitaikančius kvadratėlius. Šaškės perstūmimas nuo vieno kvadratėlio ant kito gretimo laikomas žingsniu. Vadinasi, vienu ėjimu šaškė gali padaryti kelis žingsnius.

Žaidimas baigiamas, kai aplankomi visi kvadratėliai.

Panagrinėkime pavyzdį. Piešinyje parodyta, kaip judės šaškė, jei mėtant kauliuką iškrito 1, 2, 1. Kiekvienas žingsnis pavaizduotas rodykle. Iki žaidimo pabaigos šaškė padarė 15 žingsnių.

Parašykite algoritmą, randantį tokią kauliuko akių seką, kuriai iškritus žaidimas baigtųsi per mažiausią žingsnių skaičių.

158. SKAIČIAI. Sudarykite programą, kuri natūraliojo skaičiaus įprastą užrašą (vardininko linksniu) pakeistų jo skaitine reikšme. Pavyzdžiui, užrašas

tūkstantis devyni šimtai devyniasdešimt devyni

1999

Žodis „vienas“ prieš tūkstančius ir šimtus gali būti praleistas, pavyzdžiui, skaičiaus 125 užrašas gali būti

vienas šimtas dvidešimt penki

šimtas dvidešimt penki

Kiekvienoje jų – vieno skaičiaus užrašas žodžiais. Žodžiai skaičiaus užraše skiriami bent vienu tarpu. Vartojamos tik mažosios raidės. Eilutės ilgis neviršija 255 simbolių. Keičiamų skaičių intervalas – nuo 1 iki 999999.

Jei kurio nors skaičiaus užrašas netaisyklingas, tai rezultatas laikomas lygus nuliui.

159. ŽAIDIMAS „MINŲ LAUKAS“. Turbūt daugeliui teko žaisti žaidimą „Minų laukas“ (Minesweeper). Trumpai apibūdinsime žaidimą: stačiakampėje lentoje, padalintoje į nm langelių, išdėstyta k minų (pavyzdyje n = m = 6, k = 8).
 

Užduotis. Duotas kvadratinis nn žaidimo laukas, kurio dalis langelių yra atverta. Juose minų nėra. Parašykite programą, kuri visus užvertus langelius suskirstytų į tris grupes: 1) langelius, kuriuose tikrai yra mina, 2) kuriuose minos tikrai nėra ir 3) kuriuose minos buvimas neaiškus: gali būti, bet gali ir nebūti.

Pastaba. Jei atvertame langelyje įrašytas nulis, tai atverti ir visi jo kaimyniniai langeliai.

Likusiose n eilučių pateikiama informacija apie žaidimo lauką. Kiekvienoje eilutėje yra po n simbolių. Raidė U žymi užvertą laukelį, o skaitmenys 0, 1, … 8 rodo, kiek minų yra kaimyniniuose langeliuose.

Pradiniai duomenys korektiški: sprendinys visada egzistuoja.

Pradinių duomenų ir rezultatų bylose tarpų tarp simbolių nėra.

160. ŠOKOLADO VALGYMAS.  Turime didžiulį stačiakampį šokolado gabalą, sudarytą iš n x m plytelių – kvadratėlių. Viršuje kampinė kairioji plytelė nevalgoma – joje įmaišyta kažkas neskanaus. Tai plytelė-apgavikė.

Šokoladą valgo paeiliui dviese pagal tokią taisyklę: galima laužti bet kokio dydžio stačiakampį gabalą, kurio laužimo linija būtų tiesė. Tam, kam tenka „apgavikė“ – pralaimi. Valgančiųjų tikslas: laimėti arba, jei neįmanoma, bent prisivalgyti kuo daugiau šokolado.

Pavyzdžiui, šokoladas yra 3x4 plytelių dydžio:

Atsilaužus pirmajam valgytojui, lieka 3x2 plytelių dydžio šokoladas:

Atsilaužus antrajam lieka 3x1 plytelių:

Atsilaužus pirmajam lieka viena (nevalgoma) plytelė:

Aišku, kad antrasis pralaimi, nes jam teko nevalgoma plytelė. Be to, pirmasis suvalgė 8 plyteles, antrasis – 3.

Sudarykite algoritmą pirmajam valgytojui, kad jis laimėtų arba, jei neįmanoma laimėti – suvalgytų kuo daugiau šokolado. Laikykite, kad antrasis valgytojas šokoladą laužo optimaliai.

161. BURATINAS, LAPĖ ALISA IR KATINAS BAZILIJUS KVAILIŲ LAUKE. Plėšikai lapė Alisa ir katinas Bazilijus. stengiasi pagauti Buratiną, kuris norėdamas surasti Auksinį raktelį turi pereiti Kvailių lauką.

Kvailių laukas yra kvadrato formos, padalintas į nxn langelių. Lauko eilutės numeruojamos iš apačios į viršų, stulpeliai – iš kairės į dešinę. Langelis apibūdinamas dviem skaičiais:  pirma nurodoma eilutė, po to – stulpelis.

Plėšikai lapė Alisa ir katinas Bazilijus įsitaisę už lauko ribų kairėje arba dešinėje pusėje (arba ir vienoje, ir kitoje). Bijodami išsiduoti jie kiūto vienoje vietoje ir niekur nejuda. Plėšikai mato tik po vieną horizontalę (tą, šalia kurios jie pasislėpę). Buratinui pavyko sužinoti, kur jie slepiasi.

Buratinas gali judėti langeliais vertikaliai ir horizontaliai visomis keturiomis kryptimis. Vienas žingsnis – tai perėjimas iš vieno langelio į jam gretimą. Buratinas, norėdamas, kad jo nepastebėtų plėšikai, gali slėptis už šiukšlių konteinerių.

Kvailių lauke yra du šiukšlių konteineriai, kuriuos galima stumdyti (žinoma, jei prieš konteinerį nieko nėra). Jei toje horizontalėje, kurioje slepiasi plėšikas, tarp jo ir Buratino yra šiukšlių konteineris, tai plėšikas Buratino nemato.
 

Pavyzdys

L – lapė Alisa  K – katinas Bazilijus  B – Buratinas  # – šiukšlių konteineriai  $ – Auksinis raktelis

Parašykite algoritmą, kuris rastų tokią Buratino žingsnių seką, kad jis nepastebėtas pasiektų Auksinį raktelį.

Pradiniai duomenys tokie, kad uždavinys turi sprendinį.

162. SKAIČIAI. Olimpiados dalyviams buvo duotas toks uždavinys.
 

Sudarykite programą, kuri natūraliojo skaičiaus įprastą užrašą (kiekinį skaitvardį vardininko linksniu) pakeistų jo skaitine reikšme. Pavyzdžiui, užrašas  tūkstantis devyni šimtai devyniasdešimt devyni  būtų pakeistas į  1999.  Skaičiai vadinami taisyklinga lietuvių kalba, kiekiniais skaitvardžiais. Žodis „vienas“ prieš tūkstančius ir šimtus gali būti praleistas, pavyzdžiui, skaičiaus 125 užrašas gali būti  vienas šimtas dvidešimt penki  arba  šimtas dvidešimt penki.

Pradiniai duomenys įrašyti byloje SKAI.DAT. Pirmoje eilutėje nurodytas keičiamų skaičių kiekis n (1 <= n <= 400). Toliau eina n eilučių. Kiekvienoje jų – vieno skaičiaus užrašas žodžiais. Žodžiai skaičiaus užraše skiriami bent vienu tarpu. Vartojamos tik mažosios raidės. Eilutės ilgis neviršija 255 simbolių. Keičiamų skaičių intervalas nuo 1 iki 999999.

Rezultatai spausdinami į bylą SKAI.REZ po vieną skaičių eilutėje. Skaičiai turi būti išdėstyti tokia pat tvarka, kokia jie buvo pateikti pradinių duomenų byloje. Jei kurio nors skaičiaus užrašas netaisyklingas, tai rezultatas laikomas lygus nuliui.

Šį uždavinį sprendžia programa SKAIC.EXE (ją kartu su pradinių duomenų bei rezultatų bylos pavyzdžiais rasite archyve  10ol_162.zip; pavartota kodavimo lentelė 770). Kai kuriais atvejais ši programa pateikia klaidingus rezultatus. Suraskite klaidas.

Rastąsias klaidas aprašykite byloje, kurios prievardis turi būti .TXT.

Taip pat sudarykite kontrolinių duomenų rinkinį (testą), kuris aprėptų visas Jūsų rastas klaidas. Jį įrašykite į bylą SKAIC.DAT. tokiu pat formatu, kaip nurodyta uždavinio sąlygoje.

163. GELEŽINKELIO GROTELĖS. Yra žinomas toks šifravimo algoritmas, vadinamas „Geležinkelio grotelių“ metodu. Pavyzdžiui, turime sakinį „AŠ PASKAMBINSIU“ ir skaičių k = 6. Skaičių k vadinsime aukščiu. Sakinį užrašykime tokiu būdu:

Tarpo simbolis čia pažymėtas kaip pabraukimo simbolis.

 Dabar užrašykime pirmą eilutę, šalia antrą ir t.t. Gauname tokį užšifruotą tekstą: „AIŠBN MSPAIAKUS“.

Duotas užšifruotas tekstas bei to paties teksto neužšifruotas fragmentas. Parašykite algoritmą, kuris rastų tokį mažiausią aukštį k, kuris galėjo būti naudojamas užkodavimui. 

Antroje eilutėje įrašytas neužšifruoto teksto fragmentas. Jo ilgis neviršija 255 simbolių.

Likusiose eilutėse įrašytas užšifruotas tekstas. Jei n mažesnis nei 100, tai tekstas pateikiamas vienoje eilutėje, priešingu atveju tekstas pateikiamas eilutėmis po 100 simbolių. Jei n nesidalija iš 100 be liekanos, paskutinėje eilutėje pateikti likę simboliai, kurie netilpo į ankstesnes eilutes.

Tekstas gali būti sudarytas iš didžiųjų bei mažųjų raidžių, įvairių kitų nevaldančių simbolių bei tabuliacijos simbolio. Didžiosios ir mažosios raidės tekste laikomos skirtingomis. Kiekvienas simbolis tekste pasikartoja ne daugiau 6000 kartų.

Duomenų pavyzdžius rasite bylose GROTEL1.DAT ir GROTEL2.DAT. Neužšifruoti tekstai, atitinkantys šiuos duomenis, įrašyti bylose GROTEL1.TXT ir GROTEL2.TXT. Bylas rasite archyve 10ol_163.zip

164. DVIPARTINĖ  SISTEMA Stačiakampio formos valstybė padalinta į n x m kvadratėlių formos rajonų. Valstybės gyventojai yra pasidalinę į dvi tarpusavyje nesutariančias partijas: baltųjų ir juodųjų. Partijų nariai pasiskirstę po visus rajonus. Nesutarimams augant gyventojai nutarė pasidalinti rajonus ir įkurti dvi valstybes: baltųjų ir juodųjų.

Rajono priklausomybę vienai iš dviejų naujų valstybių sprendžia patys gyventojai referendumu. Ir juodųjų, ir baltųjų partijų vadovybės įsikūrussios viename po referendumo jų partijai atitekusiame rajone. Tie rajonai paskelbti abiejų būsimų valstybių sostinėmis.

Kadangi partijų nariai pasiskirstę chaotiškai, gali atsitikti taip, kad kurios nors vienos (ar abiejų) valstybių rajonai suskils į izoliuotas salas ir vienos valstybės gyventojai negalės tarpusavyje susisiekti nepažeisdami kitos valstybės teritorijos. Laikoma, kad rajonai susisiekia, jei jie turi bendrų kraštinių (kampais nepakanka liestis).

Izoliuotų rajonų situaciją galima išspręsti valstybėms keičiantis rajonais. Tarkime, kad po referendumo naujų valstybių žemėlapis atrodo taip (164.1 pav.). Baltųjų valstybė suskilusi į dvi dalis. Abi valstybės taps vientisomis, jei jos susikeis pora rajonų (164.2  pav.).

164.1 pav.	164.2 pav.

Parašykite programą, kuri sukurtų tokį abiejų valstybių žemėlapį, kad jų plotas nepakistų, sostinės liktų toje pačioje vietoje, o kiekvienos valstybės teritorija būtų vientisa.

Jei valstybėms vis dėlto teks keistis rajonais, byloje įrašykite n eilučių po m simbolių kiekvienoje. Tašku žymėkite baltiesiems atitekusius rajonus, žvaigždute – juodiesiems.

165. KAM LYGI SUMA. Kompiuteris veiksmus su realiaisiais skaičiais atlieka apytiksliai, todėl kartais galima gauti įdomių situacijų.

Duota programa:

program realus;
{$N+}
  var a: double;
begin
  a := ;
  if a + 1 = a
    then writeln('LYGU')
    else writeln('NELYGU')
end.

Tipas double atitinka tipą real, tik juo galima vaizduoti skaičius iš platesnio intervalo ir tikslesnius, t.y. turinčius daugiau skaitmenų.

Programoje kintamajam a nepriskirta jokia reikšmė. Jums reikia rasti tokį mažiausią teigiamą skaičių a, kad būtų spausdinamas pranešimas LYGU.

Pavyzdžiui, turime reiškinį: a+b+(c+d)*(e+f)–(c+d)*e. Jo reikšmei suskaičiuoti prireiks keturių laiko vienetų.

Per pirmą laiko vienetą galime atlikti šiuos veiksmus:
1_a := a+b;                                           1_c := e+f  (antruose skliaustuose);
1_b := c+d;  (pirmuose skliaustuose)      1_d := c+d (trečiuose skliaustuose).

Per antrą laiko vienetą atliekame:
2_a := 1_b*1_c;      2_b := 1_d*e.

Per trečią laiko vienetą atliksime operaciją:
3_a := 1_a+2_a.

Per ketvirtą laiko vienetą suskaičiuosime reiškinio reikšmę:
4_a := 3_a–2_b.

Parašykite algoritmą, kuris suskaičiuotų, per kiek mažiausiai laiko vienetų galima apskaičiuoti reiškinio reikšmę.

Pastaba. Negalima atskliausti ar kitaip matematiškai prastinti reiškinio. Pavyzdžiui, (a+b+c)+d nėra tapatu a+b+c+d, o (a – b) + c – (a – b) netapatu c.

167.  ŽODŽIŲ RATAS. (vykdymo laikas 1 min.). Duotas žodynas, sudarytas iš m žodžių, ir tuščias ratas, turintis n langelių. Langeliai sunumeruoti nuo 1 iki n laikrodžio rodyklės apėjimo tvarka.

Žodžiai (iš duoto žodyno) talpinami į ratą pagal tokias taisykles:

•  Žodis turi būti rašomas po vieną raidę į vieną rato langelį pagal laikrodžio rodyklę;
•  Žodžiai gali persikloti;
•  Bet kurios dvi gretimos rato raidės turi priklausyti bent vienam tam pačiam žodžiui;
•  Rate negali likti tuščių langelių.

SAMBA
TAISYKLA
LOBIS
TIMPA
BATAI
SENIS
PALTAI
AIDAI
TIKSLO
IMTI

Parašykite algoritmą, kuris surašytų į ratą žodžius pagal aukščiau išvardintas taisykles taip, kad rate esančių žodžių ilgių suma būtų didžiausia.

Likusiose m eilučių įrašytas žodynas po vieną žodį į eilutę. Visi žodžiai sudaryti tik iš didžiųjų raidžių ir žodžio ilgis neviršija 20 simbolių.

Jei vieno žodžio galūnė sutampa su kito žodžio pradžia, tai vadinsime sąryšiu. Pradiniai duomenys tokie, kad sąryšių skaičius žodyne neviršija 110.

Į likusias 2sk eilučių įrašykite rate esančius žodžius, kiekvienam žodžiui skirdami po dvi eilutes. Pirmoje eilutėje įrašykite rato langelio numerį kuriame yra pirmoji žodžio raidė, antroje – patį žodį.

Jei sprendinio nėra, į rezultatų bylą įrašykite žodį NEGALIMA.

168. ATMINTIES PASKIRSTYMAS. Kai kompiuterio atmintyje reikia išdėstyti duomenis, naudojamas toks algoritmas:
Jei duomenų dydis yra b baitų, tai ieškomas toks mažiausias neneigiamas skaičius k, kad b <= 2^k. Tada duomenims skiriamas laisvas 2^k baitų dydžio blokas.

Blokai formuojami laikantis tokių taisyklių:

•  visa atmintis (jos dydis 2^N) gali būti daloma į dvi lygias dalis – blokus. Kiekvieno jų dydis bus lygus 2^N-1;
•  bet kuris laisvas blokas gali būti vėl dalomas į dvi lygias dalis ir t. t.;
•  jei du gretimi vienodo dydžio blokai yra laisvi, jie gali būti sulieti į vieną laisvą bloką.

Ketvirtąjį bloką padalijus į dvi dalis, numeracija pasikeis taip:

Duota duomenų įrašymo ir trynimo operacijų seka. Parašykite algoritmą, kuris atliktų kiek galima daugiau operacijų. Įrašymo operacijos negalima atlikti, jei trūksta vietos atmintyje.

Pateikiame modulio procedūrų ir funkcijų antraštes:

function dydis: integer; – ši funkcija grąžina skaičių N. Žinoma, kad atminties talpa lygi 2^N baitų;

function skaicius: integer; – ši funkcija grąžina dar neatliktų operacijų skaičių;

procedure oper (var op: char; var nr, b: longint); – nusako tolesnę operaciją, kurią reikia atlikti. Jei tai įrašymo operacija, tuomet op = 'R', nr parodo įrašymo operacijos numerį, b – įrašomų duomenų kiekį baitais. Jei duomenis reikia trinti, tuomet op = 'T', nr pasako kurios įrašymo operacijos metu įrašytus duomenis reikia ištrinti, kintamojo b reikšmė lieka neapibrėžta.

procedure pusiau (i: longint); – padalija i-ąjį nuo pradžios bloką į du vienodo dydžio blokus;

procedure jungti (i: longint); – sujungia i-ąjį nuo pradžios bloką su (i+1)-uoju bloku;

procedure rasyti (nr, b: longint); – įrašo b baitų į bloką, kurio numeris nr.

procedure trinti (nr: longint); – ištrina duomenis iš bloko, kurio numeris nr,

procedure baigti; – darbas užbaigiamas, kai nepavyksta atlikti kurios nors įrašymo operacijos arba kai jau atliktos visos operacijos.

Prieš skaitant naują operaciją būtina atlikti ankstesnę operaciją.

169. ŠIMTALANGĖS ŠAŠKĖS. (vykdymo laikas – 40 sek.). Šaškėmis žaidžiama šimtalangėje lentoje padalintoje į 10x10 langelių. Kai kuriuose juoduose langeliuose išdėstytos baltos ir juodos šaškės. Damų tarp jų nėra. Vaikšto tik baltosios šaškės. Juodosios šaškės arba stovi vietoje arba nuimamos nuo lentos, jeigu jas nukirto.

Baltosios šaškės vaikšto ir kerta kaip įprasta. Vienintelė išimtis – kirsti neprivaloma. Baltoji šaškė gali nekirsti, o pradėjusi kirsti juodąsias šaškes baltoji šaškė gali bet kada sustoti.

Parašykite algoritmą, kuris suskaičiuotų, kiek mažiausiai ėjimų reikia, norint, kad žaidžiantysis šaškėmis įgytų baltąją damą, t. y. viena baltųjų šaškių virstų dama.

Antroje ir ketvirtoje eilutėje tarp numerių palikta po vieną tarpą.

Sprendime ėjimų skaičius neviršys 15 ėjimų.

Jei nei viena baltoji šaškė negali tapti dama, tuomet rezultatas turi būti lygus nuliui.

Pavyzdys

Pradiniai duomenys
1 18 14 1 2 3 6 7 8 11 31 32 39 40 42 45 46
Rezultatai
3  18 23  23 27  27 36 47

169.2 pav.

Vienu ėjimu baltoji šaškė gali paeiti arba įstrižai į kairę arba įstrižai į dešinę, jei tas langelis yra tuščias (169.3 pav.).

169.3 pav.

Jei tame langelyje stovi juodoji šaškė, o už jos tuščias langelis, tą šaškę galima nukirsti. Vienu ėjimu galima nukirsti kelias šaškes. Kirsti galima ir pirmyn ir atgal.

169.4 pav.

Baltųjų šaškė virsta dama, kai ji pasiekia pirmą eilutę (46–50 langelius).

170. PAKEISK ŽODĮ. Duoti du žodžiai. Iš pirmojo žodžio pagal nurodytas taisykles reikia gauti antrą žodį.

Keičiama taikant šias operacijas:
 

Perkelti	žymeklis pastumiamas per vieną simbolį į dešinę;
Pašalinti	pašalinamas simbolis, kurį rodo žymeklis; žymeklis rodo tolesnį simbolį;
Pakeisti (x)	simbolis, kurį rodo žymeklis, pakeičiamas simboliu x; žymeklis lieka toje pačioje vietoje;
Įterpti (x)	prieš žymeklio rodomą simbolį įterpiamas simbolis x; žymeklis lieka toje pačioje vietoje;
Numesti	pašalinamas visas žodžio galas, pradedant simboliu, kurį rodo žymeklis (įskaitant ir žymeklio rodomą simbolį); tai gali būti tik paskutinė operacija; žymeklis rodo žodžio pabaigos simbolį.

  Pradžioje žymeklis visuomet stovi žodžio pradžioje, ties pirmuoju simboliu. Iš vieno žodžio gauti kitą galima daugeliu būdų. Pavyzdžiui, iš žodžio „matai“ gauti žodį „pamatė“ galime šitaip:
 

Operacija	Žodis
	matai
Įterpti (p)	pmatai
Įterpti (a)	pamatai
Perkelti	pamatai
Perkelti	pamatai
Perkelti	pamatai
Pašalinti	pamati
Pakeisti (ė)	pamatė
Perkelti	pamatė_

Čia žodį pakeitėme pavartoję 8 operacijas. O gal galima tai padaryti dar greičiau?

Parašykite programą, kuri rastų greičiausią būdą, t. y. mažiausią skaičių operacijų, duotam žodžiui pakeisti kitu duotu žodžiu taikant nurodytas operacijas.

Laikoma, kad po paskutiniojo žodžio simbolio eina žodžio pabaigos simbolis. Baigus, žymeklis turi rodyti žodžio pabaigos simbolį, o žymekliui atsistojus ties šiuo simboliu darbas baigiamas.

Abu žodžiai sudaryti tik iš mažųjų raidžių ir kiekvieno ilgis neviršija ….. simbolių.

171. GELEŽINKELIO GROTELĖS. Yra žinomas toks šifravimo algoritmas, vadinamas „Geležinkelio grotelių“ metodu. Pavyzdžiui, turime sakinį „AŠ PASKAMBINSIU“ ir skaičių k = 6. Skaičių k vadinsime aukščiu. Sakinį užrašykime tokiu būdu:

Tarpo simbolis čia pakeistas pabraukimu.

Dabar užrašykime pirmą eilutę, po jos – antrą ir t.t.

AI
ŠBN
_MS
PAI
AKU
S

Gauname tokį užšifruotą tekstą: „AIŠBN MSPAIAKUS“.

Žemiau matote, kaip galėtų atrodyti mūsų pavyzdžio eilutės surikiuotos nežinoma tvarka. Neužšifruotas fragmentas galėtų būti „SKAMB“.

ŠBN
PAI
AI
_MS
S
AKU 

Nei vienos duomenų eilutės, kurioje įrašytas tekstas, ilgis neviršija 255 simbolių. Tekstas gali būti sudarytas iš didžiųjų bei mažųjų raidžių, įvairių kitų nevaldančių simbolių bei tabuliacijos simbolio. Didžiosios ir mažosios raidės tekste laikomos skirtingomis. Kiekvienas simbolis tekste pasikartoja ne daugiau 1000 kartų.

Duomenų pavyzdžius rasite bylose GROTEL1.DAT ir GROTEL2.DAT. Neužšifruoti tekstai, atitinkantys šiuos duomenis, įrašyti bylose GROTEL1.TXT ir GROTEL2.TXT. Bylas rasite archyve 10ol_171.zip.

Vakare vietiniai moksleiviai turėjo pasidalinti svečius po namus, kur jie gyventų visą viešnagės laiką. Vienam moksleiviui leidžiama apnakvydinti tik vieną svečią. Mokytojas surinko vietos moksleivių pageidavimus. Kiekvienas moksleivis pateikė sąrašą svečių, su kuriais jis susipažino ir vieną iš kurių jis sutiktų priimti.

Parašykite algoritmą, kuris padėtų mokytojui paskirstyti svečius taip, kad patenkintų moksleivių (vietinių ir svečių) skaičius būtų didžiausias. Savaime suprantma, kad visi japonai turi būti apgyvendinti.

Pastaba. Moksleivio pageidavimas laikomas abipusiu sąryšiu: t. y. jei Jonas nori apgyvendinti Chau Youd, tai reiškia, kad Chau Youd sutinka gyventi pas Joną. Ir analogiškai, jei Petras nenori priimti Chau Youd ir jo neįtraukė į savo sąrašą, tai reiškia, kad Chau Youd taip pat nenori gyventi pas Petrą.

Likusiose n eilučių įrašyti vietinių moksleivių pageidavimai. Vieno moksleivio pageidavimams skiriama viena eilutė. Taigi antroje eilutėje įrašyti pirmojo moksleivio pageidavimai, trečioje – antrojo ir t.t.

Pirmasis skaičius eilutėje reiškia sąrašo ilgį ilg, likusieji ilg skaičių – japonų, kuriuos norėtų apgyvendinti moksleivis, numerius.