Keturioliktoji moksleivių informatikos olimpiada

Trečiojo etapo antrosios dalies uždavinių testai

Jaunesniųjų grupė

1. (270). APIE ERDIOŠO HIPOTEZĘ.
Testo nr.
Pradinis
duomuo
Vienas iš skleidinių
Skleidinių
skaičius
Paaiškinimai
1
 6 4/6=4/(2*3)=1/2+1/7+1/(2*3*7)
5
 Minimalus testas. 7 skleidiniai, mažos vardiklių reikšmės.
2
 199 4/199=4/199=
1/(2*5*5)+1/(2*5*997)+1/(5*5*199*997)
40
 Maksimalus vardiklis
3
 192 4/192=4/(2*2*2*2*2*2*3)=
1/(7*7)+1/(3*787)+1/(2*2*2*2*7*7*787)
676
 Maksimalus skleidinių kiekis
4 180 4/180=4/(2*2*3*3*5)=
1/53+1/(3*3*53)+1/(3*5*53)
618
 Skleidinių gan daug
5 181 4/181=4/181=
1/(2*23)+1/(2*2*2*347)+1/(2*2*2*23*181*347)
17
 Skleidinių mažai
6 40 4/40=4/(2*2*2*5)=
1/17+1/(2*17)+1/(5*17)
84
 Atsitiktiniai testai pateikti didėjimo tvarka
7 81 4/81=4/(3*3*3*3)=
1/(2*11)+1/(2*3*7*11)+1/(3*3*3*3*7)
42
8
 114 4/114=4/(2*3*19)=
1/(2*19)+1/(3*41)+1/(2*19*41)
134
9
 154 4/154=4/(2*7*11)=
1/(2*3*7)+1/(2*7*47)+1/(3*11*47)
251

5. (274). DĖŽĖS.
Testo nr.
Pradiniai duomenys
Rezultatas
X
Y
Paaiškinimai
1
 3 3 1 1 1
0
0
 Panašus į pavyzdinį testą
2
 8 12 5 59 65
3
3
 Mažas testas be jokių gudrybių
3
 400 50 100 5000 5050
7
43
 Vidutinio  dydžio testas
4
 600 300 600 6889 6900
10
1
 Vidutinio  dydžio testas
5
 600 1 3 1201 2403
2
1200
 Į vidutines dėžes telpa tik po 1 mažiausiąją dėžę; N2=1
6
 1 800 200 3396 3600
200
4
 Į didžiąsias dėžes telpa po 1 vidutinę; N1=1
7
 1 1 200 200 600
200
200
 Tuščių dėžių skaičius lygus didelių dėžių skaičiui; Į dideles ir į vidutines dedama tik po vieną dėžę. K=M; N1=N2=1;
8 901 902 903 9912 9922
1
9
 Didelis testas
9 1000 1000 1000 9991 10000
1
8
 Didžiausias testas
10 1 25 60 60 120
60
0
 Tuščių dėžių skaičius lygus didelių dėžių skaičiui;  Į dideles dėžes dedama po vieną dėžę; K=M; N1=1; N2>1;
11 6 5 30 30 30
0
0
 Tuščių dėžių skaičius lygus didelių dėžių skaičiui;  Į dideles dėžes dedama daugiau nei po vieną dėžę; K=M; N1>1; N2>1;
12 4 7 13 364 429 13
52
 Visos didelės ir visos vidutinės dėžės užpildytos
13
 17 19 40 296 312
16
0
 Neišveža nė vienos mažos dėžės.

Vyresniųjų grupė

1. (275). SIMBOLIŲ KEITIMAS.
Testo
nr.
Keitimų
skaičius 
N
Paaiškinimai
1
 2 Du nesusiję keitimai.
2
 13 Daug keitimų, bet tik du (pirmas ir paskutinis) tėra priklausomi. Priklausomus reikia sukeisti vietomis
3
 2 NEGALIMA. Yra tik du keitimai, bet sudaro ciklą.
4
 5 5 keitimai, sudarantys medį
5
 9 9 keitimai, sudarantys du medžius
6
 20 Vienas keitimų medis, sudarytas iš 20 keitimų
7
 20 20 keitimų, sudarančių 5 eiles
8
 21 NEGALIMA. Grafas iš 20 keitimų su vienu ciklu
9
 25 Daug keitimų, reikia juos sudėti teisinga tvarka 
10
 23 Didelis testas (23 keitimai), turintis vienintelį atsakymą.
11
 20 NEGALIMA. Grafas iš dviejų dalių, turinčių po ciklą

2. (276). KVADRATAI.
Testo
nr.
Taškų 
skaičius 
N
Galimas rezultatas
Paaiškinimai
1
 4 81
1 1 10 10		 Vienas paprasčiausių testų; Duotieji taškai sudaro kvadratą, kurio kraštinės  ilgis 9.
2
 8 100
6 6 16 16		 Du skirtingų plotų kvadratai
3
 16 117
4 24 19 27 		 Vidutinio sudėtingumo testai. Dauguma taškų yra stačiakampės gardelės mazguose
4
 32 225
9988 10016 10009 10013
5
 64 900
199976 200032 200018 200026
6
 131 64
999996 3999996 1000004 4000004		 Taškų „populiacija“ – apskritimo formos sritis
7
 256 325
1000044 999994 1000063 1000011		 Taškų „populiacija“ – sudėtingos formos sritis.
8
 512 84100
10001500 9999855 10001790 10000145
9
 1000 25000000000000
47500000 47500000 52500000 52500000		 Taškų koordinatės ir kiekis – maksimalūs pagal duotąją sąlygą. 
10
 1000 2499999900000001
1 50000000 50000000 99999999
11
 0 Sprendinio nėra

3. (277).  SEIMAS.
Testo nr.
Pradinis duomuo
N
Didžiausias galimas 
posėdžių skaičius
 Frakcijų skaičius
Paaiškinimai
1
 4 4 1 Šią grupę testų turi įveikti net tie sprendimai, kuriuose paprasčiausiai perrenkami visi įmanomi variantai;
2
 10 30 3
3
 20 720  5
4
 30 8064 6
5
 60 7983360 9 Šią grupę testų turi įveikti sprendimai, kuriuose naudojamos dinaminio programavimo idėjos.
6
 100 21794572800 12
7
 150 177843714048000 15
8
 200 270322445352960000 18
9
 1000 12762485561898303488 43 Šiems testams įveikti jau reikia efektyvesnės įdėjos.
10
 10000 ... 139
11
 100000 ... 445
12
 1000000 ... 1412