1et testai

Keturioliktoji moksleivių informatikos olimpiada

Pirmojo etapo uždavinių testai

8--9 klasės

KUR EITI ROBOTUI. (teorinis uždavinys). Imkime užkoduotąją komandų seką: 0101110. Pirmasis simbolis 0 reiškia komandą pirmyn. Tolesnis simbolis 1 reiškia komandą atgal.
Trys vienetai gali reikšti:

atgal atgal atgal arba
atgal kairėn arba
kairėn atgal arba
dešinėn

Paskutinysis nulis reiškia komandą pirmyn.

Atsakymai yra keli, nes netinkamai parinkti kodiniai žodžiai. Pavyzdžiui, komandos atgal kodas užrašytas du kartus (t.y. du vienetukai) sutampa su komandos kairėn kodu.

Parenkant kodavimo sistemą visuomet žiūrima, kad ji tenkintų prefikso savybę, t. y. joks kodas nebūtų kito kodo pradžia. Tada kodavimas visuomet bus vienareikšmis. Be abejo, galima parinkti tokius kodus, kad prefikso savybė nebūtų tenkinama, bet būtų galima dekoduoti vienareikšmiškai. Žr. vyresniųjų grupei skirtą pirmą uždavinį. Tačiau toks kodavimas kelia daugiau problemų.

Atsakymas: užkoduotoji komandų seka atitinka keturias skirtingas neužkoduotas komandų sekas:

1) pirmyn   atgal   atgal     atgal    atgal   pirmyn
2) pirmyn   atgal   atgal     kairėn   pirmyn
3) pirmyn   atgal   kairėn    atgal    pirmyn
4) pirmyn   atgal   dešinėn   pirmyn

GALVOSŪKIS SU TRIŽENKLIU SKAIČIUMI.

Testo nr. Pradiniai duomenys Rezultatas Paaiškinimai

1 1 9
792
Pirmasis skaitmuo mažesnis už trečiąjį

2 7 3
396
Pirmasis skaitmuo didesnis už trečiąjį

3 4 0
396
Apverstas triženklis turi du skaitmenis

4 8 9
99
Gautasis skirtumas turi du skaitmenis

5 2 5
297
Kiti galimi rezultatai

6 7 9
198

7 8 3
495

8 2 8
594

9 9 2
693

10 9 0
891

KATINAS LIFTE.

Testo nr. Pradiniai duomenys Rezultatai Paaiškinimai

1 3 2
1 20 TAIP
19 Katinas be sustojimų parvažiuoja namo

2 3 2
20 1 NE
0 Liftas tik leidosi iš paskutinio aukšto į pirmą

3 1 7
3 5 2 8 5 6 20 TAIP
31 Liftas laukia pirmame aukšte

4 16 13
9 8 15 12 20 5 9 8 1 5 18 19 6 NE
31 Liftas pirma pakyla į paskutinį aukštą, tik po leidžiasi į pirmąjį

5 4 8
5 20 3 12 5 9 2 3 NE
0 Liftas nė karto nenusileidžia į pirmą aukštą

6 4 8
5 1 13 12 5 9 2 3 NE
32 Litftas nė karto nepakyla į paskutinį aukštą

7 5 10
6 1 3 5 7 9 11 14 18 20 TAIP
19 Katinas važiuoja tik aukštyn

8 7 18
1 6 3 8 5 19 14 2 15 4 18 7 11 16 12 11 20 19 TAIP
119 Katinas važinėja aukštyn-žemyn

9 4 10
2 1 15 20 14 20 9 20 6 20 TAIP
19 Liftas pasiekia pirmą aukštą ir po to kelis kartus nuvažiuoja į paskutinį

10 4 15
18 1 3 2 15 20 2 1 9 20 5 1 6 18 20 TAIP
21 Liftas kelis kartus važiuoja iš pirmojo į paskutinįjį aukštą

Pirmojo etapo uždavinių testai

10-12 klasės

VIENAREIKŠMIS KODAVIMAS.
A)
1 žingsnis. Poros: 110 ir 11 (priesaga 0); 10ir 100 (priesaga 0);
2 žingsnis Poros: 0 ir 00 (priesaga 0);

Naujų priesagų negauname, o gauta priesaga 0, nelygi nė vienam kodiniam žodžiui.
Atsakymas: pirmasis kodų rinkinys yra vienareikšmis.

B)
1 žingsnis. Poros: 1101 ir 11011(gauta priesaga 1)
2 žingsnis. Poros: 1 ir 100 (gauta priesaga 00); 1 ir 101 (gauta priesaga 01);
1 ir 1101 (gauta priesaga 101); 1 ir 11011 (gauta priesaga 1011);

Matome, kad gavome priesagą 101, kuri sutampa su trečiuoju kodiniu žodžiu. Taigi galime baigti darbą.

Nevienareikšmės sekos pavyzdys: 11011101. 11011101 = 1101+1101; taip pat:
11011101=11011+101;

Atsakymas: antrasis kodų rinkinys yra nevienareikšmis. Nevienareikšmio kodavimo pavyzdys- 11011101.

SKAIČIAUS ŠAKNIS.

Testo nr. Pradinis
duomuo Rezultatas

1
9
9

2
25
7

3
306
9

4
1508
5

5
68975
8

6
111111
6

7
7587932
5

8
21804978
3

9
659872015
7

10
2059799999
5

KATINAI LIFTE.

Testo nr. Pradiniai
duomenys Rezultatai Paaiškinimai

1 3 2
1 20 TAIP
19
1 Micius ir Kicius be sustojimų parvažiuoja namo

2 3 2
20 1 NE
0
20 Liftas tik leidosi iš paskutinio aukšto į pirmą; Micius nakvos lifte; Kicius lips laiptais

3 1 7
3 5 2 8 5 6 20 TAIP
3
11 2 Liftas laukia pirmame aukšte;

4 16 13
9 8 15 3 20 5 9 8 1 5 18 19 6 NE
3
13 Liftas pirma pakyla į paskutinį aukštą, tik po leidžiasi į pirmąjį;

5 4 8
5 20 3 12 5 9 2 3 NE
0
20 Liftas nė karto nenusileidžia į pirmą aukštą

6 4 8
5 1 13 12 5 9 2 3 NE
32
20 Litftas nė karto nepakyla į paskutinį aukštą

7 5 10
6 1 3 5 7 9 11 14 18 20 TAIP
19
1 Katinas važiuoja tik aukštyn

8 7 18
1 6 3 8 5 19 14 2 15 4 18 7 11 16 12 11 20 19 TAIP
119
20 Katinas važinėja aukštyn-žemyn; Kicius lipa laiptais, nes jis užlips greičiau, nei nuvažiuos liftu;

9 4 10
2 1 15 20 14 20 9 20 6 20 TAIP
19
1 Liftas pasiekia pirmą aukštą ir po to kelis kartus nuvažiuoja į paskutinį

10 4 15
18 1 3 2 15 20 2 1 9 20 5 1 6 18 20 TAIP
21
1 3 2 Liftas kelis kartus važiuoja iš pirmojo į paskutinįjį aukštą

11 3 10
2 1 16 6 17 5 18 3 20 3 TAIP
93
1 3 5 6 20 Kicius laiptais užlipa per lygiai tiek pat laiko, per kiek jis nuvažiuotų

12 3 10
2 1 10 6 17 5 18 3 20 3 TAIP
81
1 3 5 Kicius gali įlipti keliuose aukštuose;

13 3 8
2 8 20 4 17 3 20 3 NE
0
20 Liftui pirmą kartą pasiekus paskutinį aukštą, Kicius dar nebus į jį įlipęs

Testo nr.	Pradiniai duomenys	Rezultatas	Paaiškinimai
1	`1 9`	`792`	Pirmasis skaitmuo mažesnis už trečiąjį
2	`7 3`	`396`	Pirmasis skaitmuo didesnis už trečiąjį
3	`4 0`	`396`	Apverstas triženklis turi du skaitmenis
4	`8 9`	`99`	Gautasis skirtumas turi du skaitmenis
5	`2 5`	`297`	Kiti galimi rezultatai
6	`7 9`	`198`
7	`8 3`	`495`
8	`2 8`	`594`
9	`9 2`	`693`
10	`9 0`	`891`

Testo nr.	Pradiniai duomenys	Rezultatai	Paaiškinimai
1	`3 2` `1 20`	`TAIP` `19`	Katinas be sustojimų parvažiuoja namo
2	`3 2` `20 1`	`NE` `0`	Liftas tik leidosi iš paskutinio aukšto į pirmą
3	`1 7` `3 5 2 8 5 6 20`	`TAIP` `31`	Liftas laukia pirmame aukšte
4	`16 13` `9 8 15 12 20 5 9 8 1 5 18 19 6`	`NE` `31`	Liftas pirma pakyla į paskutinį aukštą, tik po leidžiasi į pirmąjį
5	`4 8` `5 20 3 12 5 9 2 3`	`NE` `0`	Liftas nė karto nenusileidžia į pirmą aukštą
6	`4 8` `5 1 13 12 5 9 2 3`	`NE` `32`	Litftas nė karto nepakyla į paskutinį aukštą
7	`5 10` `6 1 3 5 7 9 11 14 18 20`	`TAIP` `19`	Katinas važiuoja tik aukštyn
8	`7 18` `1 6 3 8 5 19 14 2 15 4 18 7 11 16 12 11 20 19`	`TAIP` `119`	Katinas važinėja aukštyn-žemyn
9	`4 10` `2 1 15 20 14 20 9 20 6 20`	`TAIP` `19`	Liftas pasiekia pirmą aukštą ir po to kelis kartus nuvažiuoja į paskutinį
10	`4 15` `18 1 3 2 15 20 2 1 9 20 5 1 6 18 20`	`TAIP` `21`	Liftas kelis kartus važiuoja iš pirmojo į paskutinįjį aukštą

Testo nr.	Pradinis duomuo	Rezultatas
1	`9`	`9`
2	`25`	`7`
3	`306`	`9`
4	`1508`	`5`
5	`68975`	`8`
6	`111111`	`6`
7	`7587932`	`5`
8	`21804978`	`3`
9	`659872015`	`7`
10	`2059799999`	`5`

Testo nr.	Pradiniai duomenys	Rezultatai	Paaiškinimai
1	`3 2` `1 20`	`TAIP` `19` `1`	Micius ir Kicius be sustojimų parvažiuoja namo
2	`3 2` `20 1`	`NE` `0` `20`	Liftas tik leidosi iš paskutinio aukšto į pirmą; Micius nakvos lifte; Kicius lips laiptais
3	`1 7` `3 5 2 8 5 6 20`	`TAIP` `3` `11 2`	Liftas laukia pirmame aukšte;
4	`16 13` `9 8 15 3 20 5 9 8 1 5 18 19 6`	`NE` `3` `13`	Liftas pirma pakyla į paskutinį aukštą, tik po leidžiasi į pirmąjį;
5	`4 8` `5 20 3 12 5 9 2 3`	`NE` `0` `20`	Liftas nė karto nenusileidžia į pirmą aukštą
6	`4 8` `5 1 13 12 5 9 2 3`	`NE` `32` `20`	Litftas nė karto nepakyla į paskutinį aukštą
7	`5 10` `6 1 3 5 7 9 11 14 18 20`	`TAIP` `19` `1`	Katinas važiuoja tik aukštyn
8	`7 18` `1 6 3 8 5 19 14 2 15 4 18 7 11 16 12 11 20 19`	`TAIP` `119` `20`	Katinas važinėja aukštyn-žemyn; Kicius lipa laiptais, nes jis užlips greičiau, nei nuvažiuos liftu;
9	`4 10` `2 1 15 20 14 20 9 20 6 20`	`TAIP` `19` `1`	Liftas pasiekia pirmą aukštą ir po to kelis kartus nuvažiuoja į paskutinį
10	`4 15` `18 1 3 2 15 20 2 1 9 20 5 1 6 18 20`	`TAIP` `21` `1 3 2`	Liftas kelis kartus važiuoja iš pirmojo į paskutinįjį aukštą
11	`3 10` `2 1 16 6 17 5 18 3 20 3`	`TAIP` `93` `1 3 5 6 20`	Kicius laiptais užlipa per lygiai tiek pat laiko, per kiek jis nuvažiuotų
12	`3 10` `2 1 10 6 17 5 18 3 20 3`	`TAIP` `81` `1 3 5`	Kicius gali įlipti keliuose aukštuose;
13	`3 8` `2 8 20 4 17 3 20 3`	`NE` `0` `20`	Liftui pirmą kartą pasiekus paskutinį aukštą, Kicius dar nebus į jį įlipęs