2 et testai

Tryliktoji moksleivių informatikos olimpiada

Antrojo etapo uždavinių testai

8--9 klasės

1 (234). LYGIAGRETUS RIKIAVIMAS. (teorinis uždavinys). Žemiau pateiktas paveikslas parodo kaip gaunamas rezultatas.

Atsakymas: y₁=1, y₂=3, y₃=5, y₄=2, y₅=4, y₆=6.

2(235). ROMĖNIŠKI SKAITMENYS.

Testo nr. Pradinis duomuo Rezultatas Paaiškinimai

1 I 1 Mažiausias romėniškas skaičius

2 MMMCMXCIX 3999 Didžiausias romėniškas skaičius

3 MDCLXVI 1666 Nėra nei pasikartojančių skaitmenų, nei mažesnių skaitmenų prieš didesnius

4 DCXXXVII 637 Yra pasikartojančių skaitmenų, tačiau nėra mažesnių skaitmenų prieš didesnius

5 MCDIX 1409 Yra mažesnių skaitmenų prieš didesnius, tačiau nėra pasikartojančių skaitmenų

6 MMMCCXLV 3245 Yra ir mažesnių skaitmenų prieš didesnius, ir pasikartojančių skaitmenų

7 MMDLXIX 2569 Atsitiktinis testas

8 MMCMLXXIX 2979 Atsitiktinis testas

3 (236). TRIŽENKLIAI SKAIČIAI.

Testo nr. Pradiniai duomenys Rezultatas Paaiškinimai

1 1 5 6 9 4 2 5 1 4 8 9 1 2 3 -1 12 Nė vienas triženklis skaičius nepasikartoja kelis kartus

2 8 8 8 8 8 8 8 8 8 8 8 8 8 8 -1 1 Visi sekos nariai yra vienodi skaitmenys

3 5 5 4 4 5 4 5 5 4 5 5 4 4 5 4 5 4 4 4 5 5 4 4 5 4 4 -1 7 Seka sudaryta iš dviejų skirtingų skaitmenų (bus nemažai pasikartojančių triženklių skaičių)

4 4 0 2 5 8 0 0 5 4 8 0 0 0 4 5 8 7 4 1 5 4 0 1 4 0 1 -1 15 Sekoje yra nulių (t.y. sujungę tris gretimus sekos narius gausime ne triženklį skaičių)

5 4 1 5 7 8 9 5 1 2 5 4 1 5 8 9 7 8 4 5 4 1 5 4 8 5 7 -1 21 Atsitiktinis testas

Antrojo etapo uždavinių testai

10-12 klasės

1 (237). LYGIAGRETUS RIKIAVIMAS (teorinis uždavinys). Pateikiame vieną rikiavimo tinklą:

Šis rikiavimo tinklas atitinka rikiavimą sukeitimu. Įvykdžius 1, 2 ir 4 komparatorius didžiausias sekos narys „nuskęs“ žemyn ir y₄ reikšmė taps lygi didžiausiam sekos nariui. Įvykdžius 3 ir 5 komparatorius y₃ reikšmė taps lygi antrajam didžiausiam sekos nariui. 6-asis komparatorius teisinga tvarka surikiuos pirmuosius du sekos narius.

Šio tinklo žingsnių skaičius lygus 5. Deja, tai nėra minimalus žingsnių skaičius.

Žemiau pateikiame keturių žingsnių tinklą, rikiuojantį seką iš keturių narių:

Iš pirmo žvilgsnio nėra akivaizdu, ar šis tinklas teisingai rikiuoja seką. Tuo galima įsitikinti tik atidžiau panagrinėjus tinklą.

Vertintojams gali tekti nemažai padirbėti norint įvertinti moksleivių sukurtus tinklus. Todėl pateikiame keletą pastabų bei pasiūlymų:

tinklo įvedimams parinkite mažėjančią seką (pvz., 4, 3, 2, 1); Dauguma klaidingų sprendimų neįveiks šio testo;
prie bet kurio iš aukščiau pateiktų dviejų tinklų prijungus papildomų komparatorių, tinklas pilnai surikiuos seką;
analizuojant tinklą galima lengvai patikrinti, ar teisingose vietose atsiduria mažiausias ir didžiausias sekos elementai;
yra tik 16 skirtingų pradinės sekos variantų; tad galima patikrinti juos visus;

Atsakymas:optimalus keturių skaičių rikiavimo tinklas turi keturis žingsnius; galimas sprendimas pateiktas aukščiau esančiame paveiksle

2 (238). DANGORAIŽIS.

Tes-
to
nr. Pradi-
nis
duo-
muo Rezultatai Paaiškinimai

1 12      1     5     2     1     1     1     1     1     1     1 Paprastas atvejis

2 635 123   234   234   230   224   224   159   123   123   123 Du gretimi n

3 636 123   234   234   231   224   224   161   123   123   123

4 4500 1291 2400 2400 2400 1901 1301 1300 1300 1300 1300 n baigiasi nuliais

5 6002 1696 2801 2801 2800 2800 2800 1803 1800 1800 1800 n viduryje yra keli nuliai

6 7821 2262 3373 3364 3362 3362 3362 3362 3184 2284 2262 Atsitiktinis testas

7 10548 3653 4764 4215 4215 4214 4154 4105 4105 4105 4104 n viduryje yra vienas nulis

8 15648 5624 12384 6735 6735 6734 6374 5674 5625 5625 5624 Atsitiktinis testas

9 22222 8642 19753 11115 8642 8642 8642 8642 8642 8642 8642 Visi n skaitmenys vienodi

10 32089 12598 23619 22709 14709 12619 12619 12619 12619 12619 12609 n arti viršutinės ribos

3 (239). JANGO LENTELĖ.
Visiems testams pradiniai duomenys bus tokie:
9 sk
3 5 9 21 25 32 48 89 93 0
4 7 11 26 30 41 52 0
8 10 14 28 46 0
16 19 22 29 47 0
24 27 33 50 0
38 40 0
42 49 0
54 0
56 0

Skiriasi tik įterpiamas skaičius sk ir rezultatai.

Testo nr. sk Paaiškinimai

1 1 Įterpiamas skaičius atsiduria pirmosios eilutės pirmame stulpelyje; padidėja lentelės eilučių skaičius

2 95 Lentelė baigiama pildyti, kai pailgėja pirmoji eilutė

3 64 Lentelė baigiama pildyti, kai pailgėja antroji eilutė

4 31 Lentelė baigiama pildyti, kai pailgėja šeštoji eilutė

5 34 Lentelė baigiama pildyti, kai pailgėja trečioji eilutė

6 13 Padidėja lentelės eilučių skaičius

Rezultatai

1 testas 2 testas

1 5 9 21 25 32 48 89 93
3 7 11 26 30 41 52
4 10 14 28 46
8 19 22 29 47
16 27 33 50
24 40
38 49
42
54
56 3 5 9 21 25 32 48 89 93 95
4 7 11 26 30 41 52
8 10 14 28 46
16 19 22 29 47
24 27 33 50
38 40
42 49
54
56

3 testas 4 testas

3 5 9 21 25 32 48 64 93
4 7 11 26 30 41 52 89
8 10 14 28 46
16 19 22 29 47
24 27 33 50
38 40
42 49
54
56 3 5 9 21 25 31 48 89 93
4 7 11 26 30 32 52
8 10 14 28 41
16 19 22 29 46
24 27 33 47
38 40 50
42 49
54
56

5 testas 6 testas

3 5 9 21 25 32 34 89 93
4 7 11 26 30 41 48
8 10 14 28 46 52
16 19 22 29 47
24 27 33 50
38 40
42 49
54
56 3 5 9 13 25 32 48 89 93
4 7 11 21 30 41 52
8 10 14 26 46
16 19 22 28 47
24 27 29 50
33 40
38 49
42
54
56

Testo nr.	Pradinis duomuo	Rezultatas	Paaiškinimai
1	`I`	`1`	Mažiausias romėniškas skaičius
2	`MMMCMXCIX`	`3999`	Didžiausias romėniškas skaičius
3	`MDCLXVI`	`1666`	Nėra nei pasikartojančių skaitmenų, nei mažesnių skaitmenų prieš didesnius
4	`DCXXXVII`	`637`	Yra pasikartojančių skaitmenų, tačiau nėra mažesnių skaitmenų prieš didesnius
5	`MCDIX`	`1409`	Yra mažesnių skaitmenų prieš didesnius, tačiau nėra pasikartojančių skaitmenų
6	`MMMCCXLV`	`3245`	Yra ir mažesnių skaitmenų prieš didesnius, ir pasikartojančių skaitmenų
7	`MMDLXIX`	`2569`	Atsitiktinis testas
8	`MMCMLXXIX`	`2979`	Atsitiktinis testas

Testo nr.	Pradiniai duomenys	Rezultatas	Paaiškinimai
1	`1 5 6 9 4 2 5 1 4 8 9 1 2 3 -1`	`12`	Nė vienas triženklis skaičius nepasikartoja kelis kartus
2	`8 8 8 8 8 8 8 8 8 8 8 8 8 8 -1`	`1`	Visi sekos nariai yra vienodi skaitmenys
3	`5 5 4 4 5 4 5 5 4 5 5 4 4 5 4 5 4 4 4 5 5 4 4 5 4 4 -1`	`7`	Seka sudaryta iš dviejų skirtingų skaitmenų (bus nemažai pasikartojančių triženklių skaičių)
4	`4 0 2 5 8 0 0 5 4 8 0 0 0 4 5 8 7 4 1 5 4 0 1 4 0 1 -1`	`15`	Sekoje yra nulių (t.y. sujungę tris gretimus sekos narius gausime ne triženklį skaičių)
5	`4 1 5 7 8 9 5 1 2 5 4 1 5 8 9 7 8 4 5 4 1 5 4 8 5 7 -1`	`21`	Atsitiktinis testas

Tes- to nr.	Pradi- nis duo- muo	Rezultatai	Paaiškinimai
1	`12`	`1 5 2 1 1 1 1 1 1 1`	Paprastas atvejis
2	`635`	`123 234 234 230 224 224 159 123 123 123`	Du gretimi n
3	`636`	`123 234 234 231 224 224 161 123 123 123`	Du gretimi n
4	`4500`	`1291 2400 2400 2400 1901 1301 1300 1300 1300 1300`	n baigiasi nuliais
5	`6002`	`1696 2801 2801 2800 2800 2800 1803 1800 1800 1800`	n viduryje yra keli nuliai
6	`7821`	`2262 3373 3364 3362 3362 3362 3362 3184 2284 2262`	Atsitiktinis testas
7	`10548`	`3653 4764 4215 4215 4214 4154 4105 4105 4105 4104`	n viduryje yra vienas nulis
8	`15648`	`5624 12384 6735 6735 6734 6374 5674 5625 5625 5624`	Atsitiktinis testas
9	`22222`	`8642 19753 11115 8642 8642 8642 8642 8642 8642 8642`	Visi n skaitmenys vienodi
10	`32089`	`12598 23619 22709 14709 12619 12619 12619 12619 12619 12609`	n arti viršutinės ribos

Testo nr.	sk	Paaiškinimai
1	`1`	Įterpiamas skaičius atsiduria pirmosios eilutės pirmame stulpelyje; padidėja lentelės eilučių skaičius
2	`95`	Lentelė baigiama pildyti, kai pailgėja pirmoji eilutė
3	`64`	Lentelė baigiama pildyti, kai pailgėja antroji eilutė
4	`31`	Lentelė baigiama pildyti, kai pailgėja šeštoji eilutė
5	`34`	Lentelė baigiama pildyti, kai pailgėja trečioji eilutė
6	`13`	Padidėja lentelės eilučių skaičius

1 testas	2 testas
`1 5 9 21 25 32 48 89 93` `3 7 11 26 30 41 52` `4 10 14 28 46` `8 19 22 29 47` `16 27 33 50` `24 40` `38 49` `42` `54` `56`	`3 5 9 21 25 32 48 89 93 95` `4 7 11 26 30 41 52` `8 10 14 28 46` `16 19 22 29 47` `24 27 33 50` `38 40` `42 49` `54` `56`

3 testas	4 testas
`3 5 9 21 25 32 48 64 93` `4 7 11 26 30 41 52 89` `8 10 14 28 46` `16 19 22 29 47` `24 27 33 50` `38 40` `42 49` `54` `56`	`3 5 9 21 25 31 48 89 93` `4 7 11 26 30 32 52` `8 10 14 28 41` `16 19 22 29 46` `24 27 33 47` `38 40 50` `42 49` `54` `56`

5 testas	6 testas
`3 5 9 21 25 32 34 89 93` `4 7 11 26 30 41 48` `8 10 14 28 46 52` `16 19 22 29 47` `24 27 33 50` `38 40` `42 49` `54` `56`	`3 5 9 13 25 32 48 89 93` `4 7 11 21 30 41 52` `8 10 14 26 46` `16 19 22 28 47` `24 27 29 50` `33 40` `38 49` `42` `54` `56`