Dvylikoji moksleivių informatikos olimpiada

Pirmojo etapo uždavinių sąlygos

8–9 klasių grupė

 

1 (202). KELIŲ TIESIMAS. (teorinis uždavinys). Paveikslėlyje matote miesto planą. Mieste yra trys nauji mikrorajonai bei pilis. Planuojama užveisti žirgyną ir atidaryti zoologijos sodą. Miesto taryba nori nutiesti po vieną kelią iš kiekvieno mikrorajono į visas tris lankytinas vietą, t.y. iš viso reikės nutiesti 9 kelius. Taip pat ji pageidauja, kad keliai kirstųsi kuo mažesnį skaičių kartų. Kelių ilgis bei tiesumas nesvarbus.

Užduotis. Pasiūlykite miesto tarybai kuo geresnį kelių tiesimo projektą.

2 (203). POMIDORAI. Žinomas įdomus faktas: tarp neprinokusių pomidorų padėjus keletas raudonų pomidorų, aplink juos esantys žali pomidorai ims nokti greičiau.

Vienoje eilėje sudėta n pomidorų. Laikykime, kad jie sunumeruoti nuo 1 iki n (2<=n<=70). Vienas šių pomidorų yra raudonas. Jo numeris yra m (1<=m<=n). Per pirmąją dieną prinoksta abu šio pomidoro kaimynai. Per kiekvieną tolesnę dieną prinoksta abu kiekvieno raudono pomidoro kaimynai (suprantama, jei jie dar neprinokę). Nepamirškite, kad kraštinis pomidoras turi tik vieną kaimyną.

Užduotis. Parašykite programą, kuri suskaičiuotų, kiek dar liks neprinokusių pomidorų po d (1<=d<=30) dienų.
Pavyzdys. Aukščiau esantį paveikslą atitiktų šie pradiniai duomenys 9 4 2. Gautas rezultatas turėtų būti lygus 4.


1 pav. Taip atrodė pomidorų eilė pradžioje;


2 pav. Pomidorų eilė praėjus vienai dienai;


3 pav. Pomidorų eilė praėjus dviem dienoms;

3 (204). AR GERAME NAME GYVENSITE?. Nekilnojamo turo agentūra siūlo jums pirkti butą. Agentūroje sužinojote, kad name yra n (1<=n<=100) butų ir m (1<=m<=5) laiptinių. Visose laiptinėse butų skaičius yra vienodas. Kiekvienos laiptinės kiekvieno aukšto aikštelėje yra po k butų. Jums siūlo pirkti butą, kurio numeris nr (1<=nr<=n).

Butai name numeruojami taip kaip įprasta: pirma sunumeruojami pirmos laiptinės butai, po to antros ir t.t. Laiptinėse butai numeruojami iš apačios į viršų.

Užduotis. Parašykite programą, kuri nustatytų
a) kelių tai aukštų namas;
b) kiek butų yra vienoje laiptinėje;
c) kuriame aukšte yra jums siūlomas butas;

Pavyzdžiui, jei pradiniai duomenys yra 24 3 2 6, tai rezultatai turėtų būti: 4 8 3

Paaiškinimas. Pradinių duomenų eilutė reiškia, kad name yra 24 butai, 3 laiptinės, kiekvieno aukšto laiptinės aikštelėje yra po 2 butus, o jums siūlomo buto numeris yra 6.

Iš šių duomenų galite pasakyti, kad namas yra 4 aukštų, kiekvienoje laiptinėje yra po 8 butus, o jums siūlomas butas yra 3 aukšte.

Pirmojo etapo uždavinių sąlygos

10–12 klasių grupė







4 (205). ORIENTAVIMOSI VARŽYBOS.  (teorinis uždavinys). Paveikslėlyje pateiktas vietovės žemėlapis, kurį sudaro punktai (pažymėti apskritimais) ir keliai tarp jų.. Varžybų dalyviai turi pradėti bėgti iš starto (pradinio punkto), perbėgti kiekvienu keliu po vieną kartą ir pasiekti finišą. Tą patį punktą (netgi starto bei finišo) galima aplankyti kelis kartus. Starto bei finišo punktai nesutampa.

Deja, maketuojant žemėlapį, pasimetė prie punktų buvę užrašai. Maketuotojas prisiminė tik tiek, kad finišas buvo į vakarus nuo starto. Atidžiai pastudijavus žemėlapį paaiškėjo, kad vis dėl to vienareikšmiškai galima nustatyti, kur turėjo būti startas ir kur finišas.

Užduotis. Nurodykite starto bei finišo punktus. Trumpai paaiškinkite savo atsakymą.
Pastaba. Patogumo dėlei visus punktus sunumeravome atsitiktinai parinktais skaičiais iš intervalo [1..9].

5 (206). POMIDORAI.  Žinomas įdomus faktas: tarp neprinokusių pomidorų padėjus keletas raudonų pomidorų, aplink juos esantys žali pomidorai ims nokti greičiau.

Vienoje eilėje sudėta n pomidorų. Laikykime, kad jie sunumeruoti nuo 1 iki n (4<=n<=200). Trys iš šių pomidorų yra raudoni. Jų numeriai yra m1, m2, m3 (1<=mi<=n). Per vieną dieną prinoksta abu kiekvieno raudono pomidoro kaimynai. Suprantama, kraštinis pomidoras turi tik vieną kaimyną.

Užduotis. Parašykite algoritmą, kuris suskaičiuotų, kiek dar liks neprinokusių pomidorų po d (1<=d<=30) dienų.
Pastaba. Pradiniuose duomenyse raudonų pomidorų numeriai pateikiami didėjimo tvarka.



1 pav. Taip atrodė pomidorų eilė pradžioje;


2 pav. Pomidorų eilė praėjus vienai dienai;


3 pav. Pomidorų eilė praėjus dviem dienoms;

Pavyzdys. Šiuos piešinius atitiktų tokie pradiniai duomenys: 19 2 13 15 2, o gautas rezultatas būtų lygus 8.

6 (207). DAUGYBA A LA RUSSE. A la russe – tai daugybos algoritmas dviems teigiamiems sveikiesiems skaičiams (pažymėkime juos N ir M) sudauginti. Aprašysime jį. Pradžioje tarpinei sandaugai priskiriamas nulis.

Jei pirmasis daugiklis nelyginis, tuomet antrasis daugiklis pridedamas prie tarpinės sandaugos, jei lyginis – tarpinė sandauga nekeičiama. Po to pirmasis daugiklis padalinamas iš dviejų (imama sveikoji dalis), o antrasis – padvigubinamas pridedant jį patį prie jo paties.

Veiksmai kartojami. Kai pirmasis daugiklis tampa lygus vienam, veiksmai atliekami paskutinįjį kartą, o gautoji tarpinė sandauga tampa lygi skaičių N ir M sandaugai.


Pavyzdžiui, sudauginkime skaičius 325 ir 6874.
 
Pirmasis daugiklis
Antrasis daugiklis
Tarpinė sandauga
325
162
 81
 40
 20
 10
  5
2
1
6874
13748
27496
54992
109984
219968
439936
879872
1759744
6874
6874
34370=6874+27496
34370
34370
34370
474306=34370+439936
474306
2234050=474306+1759744

Gauname: 325x6874=2234050;

Toks daugybos algoritmas primena kompiuterio aparatinėje įrangoje (angl. hardware) realizuotą dvejetainę daugybą.


Užduotis. Parašykite programą, kuri šiuo būdu sudaugintų du skaičius. Žinoma, kad sandauga neviršys maxlongint.
Reikia spausdinti visas skirtingas tarpines bei galutinę sandaugos reikšmes. Aukščiau pateikto pavyzdžio pradiniai duomenys būtų 325 6874, o rezultatą sudarytų keturi skaičiai: 6874 34370 474306 2234050.

Antrojo etapo uždavinių sąlygos

8–9 klasių grupė


7 (208). KAS PAĖMĖ PINIGINĘ. (teorinis uždavinys). Vienoje įstaigoje dingo piniginė. Buvo apklausti visi penki tame kabinete buvę asmenys ir gauti tokie parodymai:

 
EMILIJA:   1. Aš neėmiau;
2.  Aš niekada savo gyvenimo nieko nevogiau;
3.  Tai padarė Tadas;
JUDITA: 1. Aš neėmiau;
2.  Mano tėvas labai turtingas ir aš turiu savo piniginę;
3.  Rita žino kas tai padarė;
DARIUS: 1. Aš nieko nežinau apie vagystę;
2.  Su Rita aš susipažinau prieš metus;
3.  Tai padarė Tadas;
TADAS: 1. Aš nekaltas;
2.  Tai padarė Rita;
3.  Emilija meluoja sakydama, kad aš tai padariau;
RITA: 1. Aš neėmiau;
2.  Kalta Judita;
3.  Darius gali už mane garantuoti, nes mes su juo draugaujame nuo mažumės;

    Vėlesnė apklausa leido nustatyti, kad kiekvienas iš penkių asmenų davė po du teisingus ir vieną klaidingą parodymą.


Užduotis. Iš pateiktų apklausos duomenų nustatykite, kuris asmuo paėmė piniginę. Paaiškinkite savo sprendimą.

8 (209). ĮDOMI SEKA. Seka formuojama tokiu būdu. Pirmasis sekos narys yra bet kuris nelyginis natūralusis skaičius didesnis už vienetą. Kiekvienas tolesnis sekos narys lygus:
 
 
p div 2, jei p yra lyginis;
3p+1, jei p yra nelyginis;

čia p yra prieš tai buvęs sekos narys. Seka užbaigiama, kai gaunamas vienetas.

Pavyzdžiui, pirmasis sekos narys lygus 7. Tuomet gaunama tokia seka:
7 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1

Spėjama, kad tokia seka visuomet yra baigtinė. Tačiau dar nė vienam moksleininkui nepavyko to įrodyti.

Užduotis. Duotas pirmasis sekos narys p (3<=p<30000). Parašykite programą, kuri suskaičiuotų koks bus sekos ilgis. Jei seka turi daugiau nei 300 narių, reikia išspausdinti pranešimą, kad sekos pabaiga nepasiekta.
Pavyzdys. Jei pradinis duomuo lygus 7, rezultatas turėtų būti lygus 17.
Pastaba. Tarpiniai rezultatai gali viršyti maxint.

9 (210). KAS VADAS. n (1<=n<=50) vaikų stovi ratu. Vienas žaidžiančiųjų pasako skaičių k (2<=k<n). Norėdami išsirinkti žaidimo vadą, vaikai skaičiuoja šitaip: pirmi (k–1) vaikai lieka stovėti, k–asis išeina iš rato, tolesni (k–1) vaikų lieka rate, o k–asis vėl iškrenta ir t.t. Vaikui išėjus ratas susiglaudžia. Skaičiuojama tik pagal laikrodžio rodyklę ir tol, kol lieka vienas vaikas – vadas.

Užduotis. Parašykite programą, kuri nustatytų kas taps vadu, t.y. rastų to vaiko numerį n vaikų rate. Laikoma, kad vaikai sunumeruoti pagal laikrodžio rodyklę.

Pavyzdžiui, jei pradiniai duomenys yra 6 2, tai rezultatas turėtų būti: 5.

Paveiksle parodyta kokia tvarka iškris vaikai. Pirmiausia iškritęs vaikas pažymėtas raide a, antras iškritęs – raide b ir t.t.
 

Antrojo etapo uždavinių sąlygos

10–12 klasių grupė

10 (208). KAS PAĖMĖ PINIGINĘ. (teorinis uždavinys). Vienoje įstaigoje dingo piniginė. Buvo apklausti visi penki tame kabinete buvę asmenys ir gauti tokie parodymai:

 
EMILIJA:   1. Aš neėmiau;
2.  Aš niekada savo gyvenimo nieko nevogiau;
3.  Tai padarė Tadas;
JUDITA: 1. Aš neėmiau;
2.  Mano tėvas labai turtingas ir aš turiu savo piniginę;
3.  Rita žino kas tai padarė;
DARIUS: 1. Aš nieko nežinau apie vagystę;
2.  Su Rita aš susipažinau prieš metus;
3.  Tai padarė Tadas;
TADAS: 1. Aš nekaltas;
2.  Tai padarė Rita;
3.  Emilija meluoja sakydama, kad aš tai padariau;
RITA: 1. Aš neėmiau;
2.  Kalta Judita;
3.  Darius gali už mane garantuoti, nes mes su juo draugaujame nuo mažumės;

    Vėlesnė apklausa leido nustatyti, kad kiekvienas iš penkių asmenų davė po du teisingus ir vieną klaidingą parodymą.


Užduotis. Iš pateiktų apklausos duomenų nustatykite, kuris asmuo paėmė piniginę. Paaiškinkite savo sprendimą.

11 (211). ŠAŠKĖS. Turime n (3<=n<=10) langelių eilę. Langeliai sunumeruoti nuo 1 iki n iš kairės į dešinę. Ant kiekvieno langelio stovi šaškių krūvelė (nuo 0 iki 10 šaškių). Vienu ėjimu galima sukeisti dviejuose langeliuose esančias šaškių krūveles.

Užduotis. Parašykite programą, kuri perkilnotų šaškių krūveles taip, kad krūvelių aukščiai būtų sutvarkyti nedidėjančiai. Reikia išspausdinti ėjimų skaičių bei pačius ėjimus eilės tvarka. Ėjimą nusako sukeičiamų krūvelių langelių numeriai.


Pavyzdžiui, duotos 3 krūvelės. Jose yra 2, 5 ir 4 šaškės. Šaškes sukeisti galima dviem ėjimais. Galimas rezultatas yra:
2
1 2
2 3

Šį pavyzdį iliustruoja žemiau pateikti piešiniai.
 

a) Duotoji krūvelė;

b) Atliktas pirmasis perstatymas;

c) Atliktas antrasis perstatymas;

12 (212). ORNAMENTAS. Ornamentas sudarytas iš nxn tamsių ir šviesių kvadratėlių. Naujas ornamentas gaunamas turimą ornamentą paslenkant įvairiomis kryptimis. Galima paslinkti į kairę, į dešinę, į viršų bei į apačią.

Paslenkant ornamentą į kurią nors pusę, visos eilutės (stulpeliai) paslenkami per vieną poziciją, o nebetelpanti kraštinė eilutė (stulpelis) perkeliama į priešingą pusę. Paslinkimas iliustruojamas žemiau pateiktuose paveikslėliuose.
 

a) Pradinis ornamentas;

b) Pradinis ornamentas paslinktas į viršų;

c) Pradinis ornamentas paslinktas į apačią;

d) Pradinis ornamentas paslinktas į kairę

e) Pradinis ornamentas paslinktas į dešinę;


Pradiniai duomenys. Pirmoje bylos ORN.DAT eilutėje įrašytas ornamento dydis n (3<=n<=10). Antroje eilutėje įrašyta komandų seka. Komandų seka sudaryta iš raidžių K (į kairę), D (į dešinę), V (į viršų), A (į apačią). Tarp raidžių tarpų nėra . Komandų seką sudaro ne daugiau kaip 25 komandos. Likusiose n eilučių pateiktas pats ornamentas. Tamsūs langeliai žymimi didžiosiomis „O“ raidėmis, šviesūs – taškais (.).
Užduotis. Parašykite programą, kuri nupieštų naują ornamentą, gautą iš duotojo ornamento atlikus duotąsias komandas.
Pavyzdys: (atitinka paveikslą a):
 
Pradiniai duomenys
Rezultatai
Rezultatą atitinkantis piešinys
5
KKKAAAD
OOOOO
.O...
..O..
O..O.
OO..O		 O....
.O.O.
..OOO
OOOOO
....O

 

Trečiojo etapo uždavinių sąlygos

I dalis

8–9 klasių grupė


13 (213). VALIUTOS. Daugelio Vakarų Europos valstybių valiutų kursai yra susieti su euru pastoviu santykiu. Tuomet santykis tarp atskirų šių valstybių valiutų taip pat pasidaro pastovus.
Duota N valstybių (valstybės sunumeruotos nuo 1 iki N) valiutų santykių lentelė, kurios i, j langelyje (t. y. i-ame stulpelyje ir j-oje eilutėje) įrašytas skaičius rodo, kiek i-osios valstybės valiutos vienetas kainuoja j-osios valstybės valiutos vienetų. Lentelė neišbaigta, t. y., ne visų valstybių valiutų santykiai žinomi. Vietoj nežinomų santykių įrašyti nuliai.

Užduotis. Remiantis lentelėje esančiais duomenimis reikia apskaičiuoti kiek galint daugiau nežinomų santykių, kitaip sakant, reikia kuo daugiau nulių pakeisti valiutų santykiais. Taigi rezultatas yra pradinė valiutų santykių lentelė, tik papildyta apskaičiuotais santykiais (kurių santykių apskaičiuoti neįmanoma, lieka nuliai).


Pradiniai duomenys pateikti byloje VALIUTOS.DAT. Pirmoje šios bylos eilutėje įrašytas valstybių skaičius N (2 <= N <= 120). Tolesnėse N eilučių pateikiama valiutų santykių lentelė. Kiekvienoje eilutėje yra įrašyta po N skaičių (realiojo tipo), atskirtų tarpais. Nulis reiškia nežinomą santykį.

Rezultatai – gautoji valiutų santykių lentelė – turi būti įrašyta į tekstinę bylą VALIUTOS.REZ tuo pačiu formatu, kaip ir pradiniai duomenys: pirmoje eilutėje turi būti įrašytas valstybių skaičius N, tada turi eiti N eilučių, atitinkančių valiutų santykių lentelės eilutes. Kiekvienoje eilutėje turi būti įrašyta po N skaičių, atskirtų tarpais.

PASTABA: Valiutų santykius aprašykite realiųjų skaičių tipu ir skaičiavimus su jais atlikite bei rezultatus pateikite neapvalindami.


Pavyzdys

Pradiniai duomenys
5
0    2    4    0    0
0    1    0    0    0
0.25 0    1    0    0
0    0    1    1    0
0    0    0    0    1

Rezultatai
5
1    2    4    4    0
0.5  1    2    2    0
0.25 0.5  1    1    0
0.25 0.5  1    1    0
0    0    0    0    1

14 (214). BŪRĖJA. Viena būrėja gali išburti ir pasakyti, koks šansas, kad vienas asmuo (pažymėkime jį A1) susitiks su kitu asmeniu (A2). Šis šansas išreiškiamas skaičiumi nuo 1 iki 100 (procentais).

Buriama šitaip: į būrėją kreipęsis asmuo A1 pasako jai savo vardą ir pavardę bei asmens A2 vardą ir pavardę, pavyzdžiui, Jonas Jonaitis ir Janina Petrienė. Visus duomenis (A1 vardą ir pavardę bei A2 vardą ir pavardę) būrėja surašo be tarpų į vieną eilę (didžiosios ir mažosios raidės laikomos vienodomis), pavyzdžiui:

JONASJONAITISJANINAPETRIENĖ

Šitokią eilę sutarsime vadinti pirmąja raidžių grupe.

Antrąją raidžių grupę sudarys kelios raidžių eilės. Šią grupę būrėja formuoja taip: paeiliui ima pirmosios grupės raides ir

Tuomet būrėja po gauta antrąją raidžių grupe parašo, kiek kiekviename stulpelyje pasikartoja raidžių. Gaunama ilga skaitmenų eilutė – pavadinkime ją skaičiumi sk1.

Aukščiau pateiktam pirmosios raidžių grupės pavyzdžiui antroji grupė bei skaičius sk1 bus šitokie:
JONASITPERĖ
JONASIT E
J NA I
  NA I
  N
32542421211   Tai yra skaičius sk1

Toliau būrėja sudaro skaičių sk2 tokiu būdu: sudeda pirmąjį sk1 skaitmenį su paskutiniuoju ir gautą sumą prilygina skaičiui sk2. Antrąjį sk1 skaitmenį sudeda su priešpaskutiniu ir gautą sumą prirašo prie skaičiaus sk2 galo, trečiąjį skaitmenį sudeda su priešpriešpaskutiniu ir gautą sumą prirašo prie sk2 galo. Šiuos veiksmus kartoja, kol nelieka skaičiaus sk1 skaitmenų arba lieka vienas vidurinysis skaitmuo, – šiuo atveju jį prijungia tiesiog prie sk2 galo.

Iš skaičiaus sk2 tokiu pat būdu gaunamas skaičius sk3 ir t. t., kol gautas skaičius tampa mažesnis arba lygus šimtui.

Pavyzdžiui:
32542421211
437544   { 4=3+1, 3=2+1, 7=5+2, 5=4+1, 4=2+2, 4=4 }
8712     { 8=4+4, 7=3+4 , 12=7+5 }
108      { 10=8+2, 8=7+1 }
90       { 9=1+8, 0=0 }

Skaičius 90 ir bus rezultatas. Čia jis reiškia, kad šansas, jog A1 susitiks su A2, yra 90 procentų.

 Užduotis. Parašykite programą, kuri suskaičiuotų, koks yra šansas susitikti dviems asmenims, kurių vardai ir pavardės žinomos.

Pradiniai duomenys įrašyti byloje BUR.DAT. Pirmoje eilutėje įrašytas asmens A1 vardas ir pavardė, kitoje eilutėje – asmens A2 vardas ir pavardė. Vardas ir pavardė skiriami vienu tarpu. Vieno asmens vardo ir pavardės ilgis drauge neviršija 25 simbolių.

Rezultatą – vieną rastąjį skaičių – spausdinkite ekrane.

Trečiojo etapo uždavinių sąlygos

I dalis

10–12 klasių grupė

15 (215). ŽAIDIMAS SU LABIRINTU. (Vykdymo laikas – iki 20 sek.; procesorius Pentium 133 MHz) Žaidimą sudaro stiklu uždengta kvadratinė plokštelė su joje išraižytu labirintu, kuriame yra rutuliukas. Kadangi plokštelė uždengta stiklu, rutuliukas iš jos negali iškristi. Plokštelė pritvirtinta statmenai prie sienos taip, kad ją galima sukti 90 laipsnių kampu į kairę (prieš laikrodžio rodyklę) arba į dešinę (pagal laikrodžio rodyklę). Sukant plokštelę rutuliukas nejuda (jis fiksuojamas). Atlikus posūkį rutuliukas atleidžiamas, jis krenta žemyn, kol sutinka kliūtį (labirinto sieną) ir jo padėtis vėl fiksuojama.

Užduotis. Duotas nxn dydžio labirintas, rutuliuko vieta koordinatėmis (x, y) bei posūkio komandų seka, žymima raidėmis K arba D. Labirinto langeliai numeruojami pradedant apatiniu kairiuoju kampu nuo 1 (x žymi eilutes, y – stulpelius). Parašykite programą, kuri nustatytų, kurioje vietoje atsidurs rutuliukas atlikus komandų seką.


Pradiniai duomenys pateikiami byloje LABIR.DAT.

Pirmoje eilutėje įrašytas labirinto dydis n (1 <= n <= 1000) bei rutuliuko padėtis du skaičiai x ir y (1 <= x, y <= n). Antroje eilutėje įrašytos komandos – raidžių K ir D seka be tarpų (yra bent viena komanda, bendras komandų skaičius neviršija 5000).

Likusiose n eilučių pateiktas pats labirintas: 0 žymi praėjimus, o 1 – sienas.

Rezultatai – du skaičiai (rutuliuko koordinatės) įrašomi į bylą LABIR.REZ.

 
Pavyzdys
Pradiniai duomenys
Rezultatai
Paaiškinimai
10 3 7
DDDKD
1111110000
0011110110
1100001001
1001100000
1101110110
0000001000
1000110000
0000110000
1001001100
1001101111		 8 3 1111110000
0011110110
11****1001
10011*****
110111011*
000000100*
100011000*
000011****
1001001100
1001101111

16 (216). PRISKYRIMO SAKINIAI. (Vykdymo laikas – iki 10 sek.; procesorius Pentium 133 MHz). Nagrinėsime priskyrimo sakinius, kurie yra tam tikros, griežtai nusakytos formos (vadinsime ją X forma):

<kintamasis>:=<kintamasis><ženklas><skaičius>;

Čia esantys žymenys reiškia:

<kintamasis> – bet koks sveikojo tipo (integer) kintamasis, kurio vardas yra viena mažoji lotyniškosios abėcėlės raidė;
<ženklas> – arba sudėties (+), arba daugybos (*) operacija;
<skaičius> – bet koks neneigiamas sveikojo tipo skaičius.

X formos priskyrimo sakinių pavyzdžiai:
x:=y+3;
z:=z*5;
a:=b+0;

Užduotis. Duotas natūralusis skaičius S ir X formos priskyrimo sakinių seka (ją sudaro ne mažiau kaip du sakiniai). Parašykite programą, kuri pašalintų (jei to reikia ir įmanoma) tam tikrus sekos sakinius (išskyrus paskutinįjį – jo šalinti negalima), kad įvykdžius likusių sakinių seką paskutiniame sakinyje esančio kintamojo reikšmė būtų lygi S. Jeigu tai galima padaryti keliais būdais, pakanka pasirinkti bet kurį vieną. Visų kintamųjų pradinės reikšmės lygios 1.

Sakinių eilės tvarkos keisti negalima, pavyzdžiui, jeigu pašalinome antrą sakinį, o pirmą ir trečią palikome, tai naujoje sekoje pradžioje turi eiti pirmas, paskui trečias.

Jeigu atlikę pradinę seką (nieko nepašalinę) paskutinio sakinio kintamojo reikšmę gauname lygią S, tai ta seka gali būti programos vykdymo rezultatu.


Pradiniai duomenys įrašyti byloje SAKINIAI.DAT. Pirmoje šios bylos eilutėje įrašytas skaičius S. Antroje eilutėje nurodytas priskyrimo sakinių skaičius N. Trečioje ir tolesnėse eilutėse įrašyti X formos priskyrimo sakiniai (po vieną sakinį kiekvienoje eilutėje). Sakiniai rašomi nuo pirmos eilutės pozicijos. Tarp sakinio elementų nėra jokių tarpų. Kiekvieno sakinio pabaigoje iš karto (be jokio tarpo) yra kabliataškis (;).

Rezultatai rašomi į bylą SAKINIAI.REZ. Pirmoje eilutėje rašykite žodį NE, jeigu sekos neįmanoma pertvarkyti taip, kad atlikus ją paskutinio sakinio kintamojo reikšmė būtų lygi S, arba žodį TAIP, jei tai įmanoma padaryti. Pastaruoju atveju į tolesnes eilutes įrašykite likusios sekos dalies sakinių numerius po vieną į atskirą eilutę (pagal tai, kaip sakiniai buvo pateikti pradinėje sekoje: laikoma, kad jie numeruojami iš eilės 1, 2, 3 ir t. t.).
Pavyzdys
SAKINIAI.DAT SAKINIAI.REZ
Komentarai
12
4
n:=n*2;
m:=n+1;
n:=n*3;
k:=n+6;		 TAIP
1
3
4		 Atlikę seką paskutiniu sakiniu turime gauti skaičių 12. Jeigu pašalinsime antrą sakinį (kuris šiuo atveju netgi netrukdo), tai matysime, kad toks rezultatas tikrai gaunamas. (atlikus pirmąjį sakinį n reikšmė tampa lygi 2, trečiąjį – 6 ir ketvirtąjį – k reikšmė tampa lygi 12). 
12
4
n:=n*2;
m:=n+1;
n:=n*0;
k:=n+6; 		 NE Čia vėl turėtume gauti kintamojo k reikšmę lygią 12. Pastebėkime, kad tada n reikšmė turėtų būti 6. Kintamojo n reikšmę keičia trečiasis ir pirmasis sakiniai. Atlikus trečiąjį sakinį jo reikšmė tampa lygi 0, o pirmąjį – 2. Kitokių galimybių kintamojo n reikšmei keisti nėra, todėl byloje SAKINIAI.REZ šiuo atveju rašome NE. 
9
4
n:=n*2;
n:=n+1;
n:=n+2;
k:=n+4; 		 TAIP
1
2
3
4		 Šiuo atveju turime paimti visus pradinės sekos sakinius (visais kitais atvejais kintamojo k reikšmė būtų mažesnė už 9).

Ribojimai
1. Sakinių skaičius pradinėje byloje SAKINIAI.DAT neviršija 22 sakinių
2. Testuose sakiniai bus pateikti tokie, kad niekuomet (pavyzdšiui, pašalinus bet kurią sekos dalį ir atliekant likusios dalies sakinius) neįvyks perpildymas.


Trečiojo etapo uždavinių sąlygos

II dalis

8–9 klasių grupė

17 (217). LENTELĖ (Vykdymo laikas – iki 10 sek.; procesorius Pentium 133 MHz). Tarkime, kad turime lentelę, sudarytą iš 4 eilučių ir N stulpelių (N <= 20). Kiekviename lentelės langelyje reikėtų įrašyti po skaitmenį: nulį arba vienetą, kai žinomos kiekvieno stulpelio ir kiekvienos eilutės sumos.

Užduotis. Reikia parašyti programą, kuri užpildytų lentelės langelius (jeigu tai įmanoma padaryti). Jei galimi keli sprendiniai, reikia pateikti bet kurį vieną.


Pradiniai duomenys įrašyti byloje LENT.DAT. Pirmoje eilutėje nurodytas lentelė stulpelių skaičius N (N <= 20). Antroje eilutėje pateikiamos kiekvieno stulpelio skaičių sumos (N skaičių). Trečioje eilutėje įrašytos kiekvienos eilutės sumos (keturi neneigiami natūralieji skaičiai).

Rezultatus įrašykite į bylą LENT.REZ. Pirmoje eilutėje įrašomas žodis TAIP, jeigu pavyko rasti sprendinį, arba NE, jeigu sprendinio nėra.Tuo atveju, kai sprendinys surastas, antroje eilutėje įrašomi lentelės pirmosios eilutės duomenys, trečioje – antrosios ir t. t.

Pavyzdys

Pradinė lentelė (N=4)
 
? ? ? ? 1
? ? ? ? 3
? ? ? ? 3
? ? ? ? 4
4 3 3 1  

Rezultatų lentelė
 
1 0 0 0 1
1 1 1 0 3
1 1 1 0 3
1 1 1 1 4
4 3 3 1  

Pradinių ir galutinių duomenų pavyzdžiai
LENT.DAT LENT.DAT Paaiškinimas
4
4 3 3 1
1 3 3 4		 TAIP
1 0 0 0
1 1 1 0
1 1 1 0
1 1 1 1		 Sąlygoje duotas pavyzdys

18 (218). LABIRINTAS Labirintą sudaro kambariai ir perėjimai tarp jų. Perėjimais galima judėti tik nurodyta kryptimi. Labirinte ciklų nėra.

Kiekviename kambaryje yra arba prizas, arba bauda, – tai išreiškiama taškais. Keliautojui patekus į kambarį, jei kambaryje yra prizas, taškai pridedami prie keliautojo sąskaitos, o jei kambaryje yra bauda, tai keliautojo sąskaita sumažinama baudos taškais.

Keliautojas gali pasirinkti, kuriame kambaryje jis nori pradėti judėti labirintu, ir kuriame kambaryje jis sustos; tačiau keliautojas privalo aplankyti bent vieną labirinto kambarį.

Užduotis. Parašykite programą, kuri duotam labirintui surastų didžiausią taškų skaičių, kurį gali surinkti keliautojas (jei visuose kambariuose yra tik baudos, tai didžiausiais taškų skaičius bus neigiamas). Pradiniu momentu sąskaitoje yra nulis taškų.


Pradiniai duomenys įrašyti byloje LABIR.DAT. Pirmoje eilutėje įrašytas labirinto kambarių skaičius N (2 <= N <= 80). Toliau eina N eilučių, atitinkančių kambarius (kambariai numeruojami nuo 1 iki N). Kiekvienoje eilutėje pirmas skaičius T reiškia, kiek taškų yra šiame kambaryje: jei T > 0, tai prizas, jei T< 0, tai bauda. Toliau eilutėje įrašytas skaičius P, kuris lygus perėjimų, išeinančių iš atitinkamo kambario, skaičiui, po jo pateikta P kambarių, į kuriuos veda tie perėjimai, numeriai. Skaičiai eilutėse skiriami tarpais.

Rezultatus įrašykite į bylą LABIR.REZ. Pirmoje eilutėje įrašykite skaičių, reiškiantį, kokį didžiausią taškų skaičių galima surinkti duotajame labirinte.
Pradinių ir galutinių duomenų pavyzdžiai
LABIR.DAT LABIR.REZ Paaiškinimas
7
  1 1 5
 -1 1 5 
 10 2 1 2
 50 1 7
-10 1 4
-2  1 3
-3  0		 51 Keliautojo maršrutas: 3, 1, 5, 4.
4
-1  0 
-7  1  4 
-2  2  1  2
-3  0		 -1 Keliautojo maršrutas: 1 .

19 (219).CENTAI Tarkime, kad 200x metais visų pajamos tiek išaugs, kad teks atsisakyti 1 ir 2 centų monetų. Tegul prekių kainos būtų skaičiuojamos cento tikslumu, bet visa mokėjimo suma turi būti apvalinama 5 centų tikslumu: 1 ir 2 centai keičiami į 0 centų; 3, 4, 6 ir 7 centai keičiami į 5 centus; 8 ir 9 centai keičiami į 10 centų.

Į nedidelę parduotuvę, prekiaujančią įvairiomis smulkmenomis, atėjęs taupus pirkėjas nori nusipirkti prekių, kuo daugiau išlošdamas iš centų apvalinimo. Tam jis prekes perka dalimis, į vieną pirkinį (krepšelį) dėdamas tokias prekes, kad iš apvalinimo gautų didžiausią naudą.

Užduotis. Reikia parašyti programą, kuri pirmiausia apskaičiuotų maksimalų pelną (išlošį), o tada tam pelnui rastų minimalų pirkimų (ėjimų pro kasą) skaičių. Gali būti situacija, kai pelno negaunama, o prarandama kažkokia pinigų suma. Tokiu atveju pelnas bus neigiamas.


Pradiniai duomenys įrašyti byloje CENTAI.DAT. Pirmoje eilutėje pateiktas pirkėjo perkamų prekių skaičius N. Tolesnėse N eilučių pateiktos prekių kainos, išreikštos centais.

Rezultatus įrašykite į bylą CENTAI.REZ. Pirmoje bylos eilutėje reikia pateikti du skaičius: pirkėjo pelną, išreikštą centais, ir pirkimų (ėjimų pro kasą) skaičių.

Pradinių  duomenų   ir  rezultatų  pavyzdžiai:
CENTAI.DAT CENTAI.REZ
1 pavyzdys
 3
2
2
3		  2 1
2 pavyzdys 1
1023		 -2 1

20 (220). ŽVAIGŽDUTĖS Tarkime, kad turime labai ilgą eilę simbolių, išdėstytų tokia tvarka: viena žvaigždutė, vienas tarpas, dvi žvaigždutės, du tarpai, trys žvaigždutės, trys tarpai ir t. t.

Užduotis. Reikia parašyti programą, kuri nustatytų, koks simbolis yra k–ojoje pozicijoje.


Pradiniai duomenys įvedami iš klaviatūros. Pateikiamas vienas sveikasis skaičius – ieškomo simbolio pozicija k(1<=k<=30000).

Rezultatus –– rastąjį simbolį – spausdinkite ekrane žodžiu: TARPAS arba ŽVAIGŽDUTĖ.

Pastaba: Kadangi pradiniai duomenys įvedami iš klaviatūros, o rezultatai rašomi ekrane, tai pageidautina tvarkingai ir vaizdžiai apiforminti dialogą su kompiuteriu.

21 (221). PAŽINTYS. Į renginį turėjo atvykti N asmenų. Asmenys įvardyti skaičiais nuo 1 iki N.

Yra žinoma, kurie asmenys su kuriais buvo pažįstami iki renginio pradžios. Du asmenys renginio metu būtinai susipažins, jei jie turi arba renginio metu įsigijo bendrą pažįstamą.

Renginio organizatoriai, gerai žinodami kas ką, pažįsta buvo tikri, kad renginio metu visi asmenys susipažins. Tačiau vienas asmuo į renginį neatvyko ir todėl visiems susipažinti nepavyko.

Užduotis. Parašykite programą, kuri nustatytų, koks asmuo neatvyko į renginį.


Pradiniai duomenys pateikti byloje PAZINTYS.DAT. Pirmoje eilutėje įrašytas dalyvių skaičius N (2 < N <= 200). Antroje eilutėje pateikti numeriai tų asmenų, kuriuos pažįsta pirmasis asmuo: pirmas šios eilutės skaičius rodo, kiek asmenų iš viso pažįsta pirmasis asmuo, toliau pateikiami patys numeriai. Trečioje eilutėje analogiškai pateikti numeriai tų asmenų, kuriuos pažįsta antrasis asmuo ir t. t.

Rezultatą – neatvykusio asmens numerį – įrašykite į bylą PAZINTYS.REZ.
Pastaba. Jeigu sprendinių (neatvykusių asmenų) gali būti keletas, tai užtenka pateikti bet kurį vieną

Pavyzdys:
 
PAZINTYS.DAT PAZINTYS.REZ
7
2 2 7
2 1 4
2 4 5
4 2 3 6 7
2 3 6
2 4 5
2 1 4		 4

Trečiojo etapo uždavinių sąlygos

II dalis

10–12 klasių grupė


22 (222). ŽAIDIMŲ AUTOMATAS. Vieno žaidimų automato skyde yra dešimt langelių, kiekviename kurių matomas vienas skaitmuo (nuo 0 iki 9). Po langeliais yra mygtukai, kurie sunumeruoti nuo 1 iki 10.

Kiekvienas mygtukas valdo tam tikrus langelius. Jų sąryšiai pateikti lentelėje.
 
Mygtuko nr. Mygtuko valdomi langelių numeriai
1
 4, 5, 8, 9, 10
2
 9, 10
3
 8, 10
4
 3, 5, 9, 10
5
 6, 8, 9
6
 2, 3, 4, 5, 8, 10
7
 1, 2, 4, 6, 8, 9, 10
8
 10
9
 7, 8, 10
10
 5, 7, 9, 10

Paspaudus bet kurį iš mygtukų, jo valdomuose langeliuose esantys skaitmenys padidėja vienetu (tuo atveju, kai langelyje buvo matomas skaitmuo 9, jis tampa 0).

Užduotis. Parašykite programą, kuri duotai langelių skaitmenų sekai surastų trumpiausią mygtukų paspaudimų seką (jei tik tokia egzistuoja), kurią atlikus visų langelių skaitmenys taptų vienodi.


Pradiniai duomenys – 10 skaitmenų – įrašyti bylos AUTOMAT.DAT pirmoje eilutėje. Tarp skaitmenų palikta po vieną tarpą.

Rezultatus įrašykite į bylą AUTOMAT.REZ. Pirmoje eilutėje įrašykite žodį NEGALIMA, jeigu neįmanoma rasti aprašytos paspaudimų sekos, arba GALIMA, jeigu tokią seką galima rasti. Pastaruoju atveju antroje eilutėje turi būti įrašytas mygtukų paspaudimų skaičius N, o likusiose dešimt eilučių – skaičiai (po vieną kiekvienoje eilutėje), rodantys, kiek kartų buvo paspaustas atitinkamas mygtukas. (Jeigu mygtukas nebuvo paspaustas, rašomas nulis.)

Pastabos:
1. Jeigu sprendinių (trumpiausių sekų) yra keletas, tai pakanka pateikti bet kurią vieną.
2. Jeigu iš pat pradžių visi skaitmenys vienodi, tai atsakymas turi būti GALIMA, o mygtukų paspaudimų skaičius lygus nuliui.


Pradinių ir galutinių duomenų pavyzdžiai
AUTOMAT.DAT
 AUTOMAT.REZ Paaiškinimas
4 4 4 4 4 4 4 4 4 3 GALIMA
1
0
0
0
0
0
0
0
1
0
0		 Užtenka paspausti tik 8-tą mygtuką
0 0 0 0 0 0 0 9 9 7 GALIMA
3
0
1
1
0
0
0
0
1
0
0		 Paspaudę 2, 3 ir 8-tą mygtukus langeliuose gausime visus nulius

23 (223).  LENTA. Stačiakampė lenta, kurios ilgis N, plotis M, buvo padalinta lygiagrečiomis lentos kraštams tiesėmis į N*M vienetinio dydžio kvadratėlių. Dalis kvadratėlių buvo išpjauti. (Gali būti, kad dėl to lenta tapo nebevientisa, o susidedanti iš kelių dalių.) Norima likusią lentą supjaustyti į vientisus dviejų vienetinių kvadratėlių dydžio stačiakampius.

Užduotis. Parašykite programą, kuri suskaičiuotų, kokį didžiausią tokių stačiakampių skaičių galima išpjauti iš šios skylėtos lentos.


Pradiniai duomenys pateikti byloje LENTA.DAT. Pirmoje bylos eilutėje įrašyti du skaičiai: lentos ilgis N ir plotis M (2<=N,M<=50). Antroje eilutėje nurodytas išpjautų kvadratėlių skaičius (gali būti ir neišpjautas nė vienas kvadratėlis, tuomet nurodomas 0). Toliau pateikiama tiek eilučių, kiek yra išpjautų kvadratėlių – kiekvienoje iš šių eilučių įrašytos vieno išpjauto kvadratėlio koordinatės (du skaičiai): pirmoji koordinatė (nuo 1 iki N) nurodo eilutę, antroji (nuo 1 iki M) – stulpelį.

Rezultatą – didžiausią skaičių stačiakampių, kuriuos galima išpjauti iš duotos lentos – įrašykite į bylą LENTA.REZ.

Pradinių ir galutinių duomenų pavyzdžiai
 
LENTA.DAT
 LENTA.REZ
Paaiškinimas
3 4 
4 
2 4 
2 3 
2 2
1 3		 3 Vienas iš galimų pjaustymo variantų 
(išpjauti langeliai pažymėti pilka spalva)
4  4 
5 
1  1 
3  3 
2  2 
4  4
1  4		 4 Vienas iš galimų pjaustymo variantų
(išpjauti langeliai pažymėti pilka spalva)

24 (221). PAŽINTYS. Į renginį turėjo atvykti N asmenų. Asmenys įvardyti skaičiais nuo 1 iki N.

Yra žinoma, kurie asmenys su kuriais buvo pažįstami iki renginio pradžios. Du asmenys renginio metu būtinai susipažins, jei jie turi arba renginio metu įsigijo bendrą pažįstamą.

Renginio organizatoriai, gerai žinodami kas ką, pažįsta buvo tikri, kad renginio metu visi asmenys susipažins. Tačiau vienas asmuo į renginį neatvyko ir todėl visiems susipažinti nepavyko.

Užduotis. Parašykite programą, kuri nustatytų, koks asmuo neatvyko į renginį.


Pradiniai duomenys pateikti byloje PAZINTYS.DAT. Pirmoje eilutėje įrašytas dalyvių skaičius N (2 < N <= 200). Antroje eilutėje pateikti numeriai tų asmenų, kuriuos pažįsta pirmasis asmuo: pirmas šios eilutės skaičius rodo, kiek asmenų iš viso pažįsta pirmasis asmuo, toliau pateikiami patys numeriai. Trečioje eilutėje analogiškai pateikti numeriai tų asmenų, kuriuos pažįsta antrasis asmuo ir t. t.

Rezultatą – neatvykusio asmens numerį – įrašykite į bylą PAZINTYS.REZ.
Pastaba. Jeigu sprendinių (neatvykusių asmenų) gali būti keletas, tai užtenka pateikti bet kurį vieną

Pavyzdys:
 
PAZINTYS.DAT PAZINTYS.REZ
7
2 2 7
2 1 4
2 4 5
4 2 3 6 7
2 3 6
2 4 5
2 1 4		 4

25 (224). DAUGIANARIO SKAIDYMAS DAUGINAMAISIAIS. Iš matematikos kurso jūs mokate skaidyti reiškinius dauginamaisiais, pavyzdžiui, reiškinį ab+ac+3b+3c galima užrašyti dviejų dauginamųjų sandauga:

ab+ac+3b+3c = a(b+c)+3(b+c) = (a+3)(b+c)

Bendru atveju skaidymas dauginamaisiais yra gana sudėtingas uždavinys, tačiau atskirais atvejais (kaip pateikta žemiau sąlygoje) jis gali būti gana lengvai išsprendžiamas.


Dviejų ar daugiau kintamųjų supaprastintus (t. y. kurių panašūs nariai sutraukti) antrojo laipsnio daugianarius, kurių visi nariai (vienanariai) turi teigiamus sveikuosius koeficientus, o koeficientai prie kvadratų yra vienetai, vadinsime A klasės daugianariais.

Dviejų ar daugiau kintamųjų supaprastintus pirmojo laipsnio daugianarius, kurių visi nariai (vienanariai) turi teigiamus sveikuosius koeficientus, vadinsime B klasės daugianariais.

A klasės daugianarių pavyzdžiai:

2ab+4ac+af+3ef+ce
a2+b2+bc
xy

B klasės daugianarių pavyzdžiai:

3a+f+2g
a+78b
x


Reiškinių, kurie nepriklauso daugianarių A klasei, pavyzdžiai:
 
ab+b Vienanaris b nėra antrojo laipsnio
ab-bc Koeficientas prieš bc nėra teigiamas
ab+abc Vienanaris abc nėra antrojo laipsnio
ab+1,5xy Koeficientas prieš xy nėra sveikasis skaičius
2a2+b2 Koeficientas prie a2 nėra lygus vienetui

Reiškinių, kurie nepriklauso daugianarių B klasei, pavyzdžiai:
 
b+b Daugianaris nėra supaprastintas
a-c Koeficientas prieš c nėra teigiamas
ab+c Vienanaris ab nėra pirmojo laipsnio

Užduotis. Parašykite programą, kuri duotąjį A klasės daugianarį išskaidytų dviejų dauginamųjų, kurių kiekvienas yra B klasės daugianaris, sandauga.


Pradiniai duomenys. įrašyti byloje DAUGIN.DAT. Pirmoje eilutėje pateiktas skaičius N (N<625), kuris reiškia vienanarių, sudarančių A klasės daugianarį, skaičių. Kitose N eilučių užrašyti vienanariai – po vieną kiekvienoje eilutėje.Visi kintamieji žymimi  mažomis lotyniškomis raidėmis, daugybos ženklas praleidžiamas (kaip įprasta matematikoje). Laipsnis (šiame uždavinyje jis gali būti lygus tik dviem) rašomas be jokių tarpų šalia kintamojo, pavyzdžiui, a2 užrašomas a2. Skaitinis koeficientas (jis negali būti didesnis negu 10000) rašomas prieš kintamuosius ir praleidžiamas, jeigu lygus vienetui (kaip įprasta matematikoje).

Rezultatus įrašykite į bylą DAUGIN.REZ. Pirmoje eilutėje rašykite skaičių 0, jeigu nepavyko suskaidyti daugianario dauginamaisiais arba skaičių K – jeigu pavyko. Čia K reiškia keliais būdais galima suskaidyti daugianarį. Pastaruoju atveju antroje ir trečioje bylos eilutėse pateikite bet kurio skaidymo būdo pirmąjį ir antrąjį dauginamąjį.

Pradinių ir galutinių duomenų pavyzdžiai
 
DAUGIN.DAT
 DAUGIN.REZ
Paaiškinimas
2
ab
ac		 1
a
b+c		 ab+ac=a(b+c)
2
ab
a2		 1
a
a+b		 ab+a2=a(a+b)
6
xy
zx
tx
25uy
25uz
25ut		 1
x+25u
y+z+t		 xy+zx+tx+25uy+25uz+25ut = 
(x+25u)(y+z+t)
2
a2
b2		 0 a2+b2=????????

26 (225). SKAIČIAI (Vykdymo laikas – iki 20 sek.; procesorius Pentium 133  MHz).
Duota N (1 <= N <= 10) sveikųjų skaičių bei dar vienas sveikasis skaičius S. Reikia nustatyti, kuriuos duotus skaičius sudėjus galima gauti nurodytą skaičių S (jei tai įmanoma).

Užduotis. Reikia parašyti programą, kuri iš duotų sveikųjų skaičių rastų tokį rinkinį, kad jų suma būtų lygi sveikajam skaičiui S. Jeigu yra keli galimi sprendiniai, reikia pateikti bet kurį vieną. Jeigu nurodytos sumos negalima gauti, tuomet reikia apie tai pranešti.


Pradiniai duomenys įvedami klaviatūra. Pirmiausia įvedamas sveikasis skaičius S (duota suma) ir tik tada atskira eilute N (1<=N<=10) sveikųjų skaičių. Skaičiai rašomi vienoje eilutėje, skiriant juos bent vienu tarpo simboliu.

Rezultatus spausdinkite ekrane, apiformindami lygybe, pavyzdžiui:

1389 = 1202 + 79 + 100 + 8

Jeigu nurodytos sumos negalima gauti, tuomet po lygybės rašykite žodį NEGALIMA.

Pastaba: Kadangi pradiniai duomenys įvedami klaviatūra, o rezultatai rašomi ekrane, tai pageidautina tvarkingai ir vaizdžiai apiforminti dialogą su programos vartotoju. Programos gale parašykite kreipinį Readln.