Tryliktoji moksleivių informatikos olimpiada

Pirmojo etapo uždavinių testai

8--9 klasės

 
 

1 (228). HAMMINGO KODAI. (teorinis uždavinys). Jei pranešimas neiškraipytas, teisingos lygybės:

b5=b2+b3+b4;   (1)
b6=b1+b3+b4;   (2)
b7=b1+b2+b4;  (3)

Tikriname pirmąjį pranešimą (1100011); b2+b3+b4=1+0+0=1<>0=b5; Pirmoji lygybė neteisinga, toliau galima nebetikrinti: pranešimas iškraipytas.

Tikriname antrąjį pranešimą (1010110); b2+b3+b4=0+1+0=1=1=b5; pirmoji lygybė teisinga; b1+b3+b4=1+1+0=0<>1=b6; antroji lygybė neteisinga: pranešimas iškraipytas.

Tikriname trečiąjį pranešimą (1111111); b2+b3+b4=1+1+1=1=1=b5; pirmoji lygybė teisinga; b1+b3+b4=1+1+1=1=1=b3; antroji lygybė teisinga; b1+b2+b4=1+1+1=1=1=b7; trečioji lygybė irgi teisinga. Išvada: pranešimas neiškraipytas.

Tikriname ketvirtąjį pranešimą (0101010); b2+b3+b4=1+0+1=0=0=b5; pirmoji lygybė teisinga; b1+b3+b4=0+0+1=1=1=b6; antroji lygybė teisinga; b1+b2+b4=0+1+1=0=0=b7; trečioji lygybė irgi teisinga. Išvada: pranešimas neiškraipytas.

Atsakymas: pirmieji du pranešimai gauti iškraipyti, trečias ir ketvirtas pranešimai atėjo neiškraipyti.

2(229). JAPONŲ KALENDORIUS.
Testo nr.
Pradinis duomuo
Rezultatas
Paaiškinimai
1
 1984  ŽALIA Paprasčiausias atvejis – 1984-ieji metai
2
 2001  BALTA Einamieji metai
3
 1804  ŽALIA Pirmieji ciklo metai
4
 2103  JUODA Paskutinieji ciklo metai
5
 1945  ŽALIA Žalios spalvos metai
6
 2137  RAUDONA Raudonos spalvos metai
7
 1859  GELTONA Geltonos spalvos metai
8
 1970  BALTA Baltos spalvos metai
9
 1942  JUODA Juodos spalvos metai (baigiasi skaitmeniu 9)
10
 1943  JUODA Juodos spalvos metai (baigiasi nuliu)
11
 2200 BALTA Ribinis atvejis

3 (230). PALŪKANOS
Testo nr.
Pradinis duomuo
Rezultatas
Paaiškinimai
1
 2047 0 Palūkanų nėra
2
 32767 0 Didžiausia suma, kai palūkanų nėra
3
 1 0 Mažiausia paskolinta suma
4
 8190 1 Tikrinama, ar gerai pereinama nuo pinigų sumos, kai palūkanų nėra, iki to atvejo, kai palūkanos atsiranda
5
 8191 0
6
 8192 8191
7
 19206 13561 Atsitiktiniai testai
8
 589 434
9
 1483  564
10
 14498 1885


 

Pirmojo etapo uždavinių testai

10-12 klasės

 1 (231). HAMMINGO KODAI.
A) Jei pranešimas neiškraipytas, sumas galime perrašyti šitaip:

S1=b4+b5+b6+b7=(b1+b1)+(b2+b2)+(b3+b3)+(b4+b4+b4+b4)
S2=b2+b3+b6+b7=(b1+b1)+(b2+b2)+(b3+b3)+(b4+b4)
S3=b1+b3+b5+b7=(b1+b1)+(b2+b2)+(b3+b3)+(b4+b4)

Žinoma, kad sudėjus du vienodus bitus, visada gausime nulį (0+0=0 ir 1+1=0). Taigi, jei pranešimas atėjo neiškraipytas, visos trys sumos turi būti lygios nuliui. Užpildome pirmąją lentelės eilutę.

Sakykime buvo iškreiptas pirmasis pranešimo bitas. Skaičiuojant S3 sumuojama ir iškreiptojo bito reikšmė (b1), ir neiškreipta to paties bito reikšmė (ji įeina į b7). Taigi S3 reikšmė tampa lygi vienetui, S1 ir S2 reikšmės lieka lygios nuliui. Užpildome antrąją lentelės eilutę.

Analogiškai analizuodami, kas atsitinka kai iškreipiamas antras, trečias ir t.t. pranešimo bitai užpildome likusią lentelės dalį. Beje, skaičiai S1S2S3 sudaro dvejetainį skaičių, kuris reiškia klaidos poziciją.
 

S1 S2 S3 Kuriame bite padaryta klaida
0
0
0
 Pranešimas neiškreiptas
0
0
1
 Iškreiptas pirmasis bitas
0
1
0
 Iškreiptas antrasis bitas
0
1
1
 Iškreiptas trečiasis bitas
1
0
0
 Iškreiptas ketvirtasis bitas
1
0
1
 Iškreiptas penktasis bitas
1
1
0
 Iškreiptas šeštasis bitas
1
1
1
 Iškreiptas septintasis bitas

B) Apskaičiuojame sumas: S1=b4+b5+b6+b7=0; S2=b2+b3+b6+b7=1; S3=b1+b3+b5+b7=0; Iš lentelės matome, kad iškreiptas antrasis bitas.

Atsakymas: neiškreiptas pranešimas atrodo šitaip: 1000011

2 (232). PALŪKANOS.

Bet kokia skola, neviršijanti trisdešimties tūkstančių bus išmokėta per 15 arba mažiau dienų. Pradiniais duomenimis parinkti beveik visi galimi d variantai.
Testo nr.
Pradinis 
duomuo
Rezultatai
1
 1 1 1
2
 3  7 4
3
 5  31 16
4
 6  63 32
5
 7  127 64
6
 9  511 256
7
 12 4095 2048
8
 13  8191 4096
9
 14  16383 8192
10
 15  30000 16384

 3 (233). TEOREMA 6174.
 
Testo nr.
Pradinis
duomuo
Rezultatas
Paaiškinimai
1
 3965
8
  Tie patys skaitmenys, tik sudėlioti skirtinga tvarka
2
 9653
8
3
 5369
8
4
 3569
8
5
 6565
5
 Pradiniame duomenyje yra vienodų skaitmenų
6
 2822
7
 Trys pradinio skaičiaus skaitmenys yra vienodi
7
 7513
2
 Išbandomi visi atsakymų variantai
8
 1058
3
9
 2143
4
10
 8709
5
11
 3259
6
12
 6981
7
13
 6549
8
14
 9998
6
 Seka turi ne keturženklių narių