Trečioji moksleivių informatikos olimpiada

                                       Pirmojo etapo uždavinių sąlygos

 

16. KURIAI METŲ SAVAITEI PRIKLAUSO DIENA Duoti trys skaičiai, reiškiantys metus, mėnesį ir dieną. Parašykite algoritmą, kuris nustatytų, kelintai metų savaitei priklauso duotoji diena.

17. LYGYBĖ. Lygybė (a + b + c + d)4 = abcd yra teisinga. Čia pažymėjimas abcd suprantamas kaip keturženklis skaičius, kurio pirmasis skaitmuo lygus a, antrasis – b, trečiasis – c, ketvirtasis – d.Parašykite algoritmą skaičiui abcd rasti. Vienodos raidės žymi tuos pačius skaitmenis.

18. PAPRASTAS KELIAS. Turime 100 x 100 langelių lentą. Kelias tarp dviejų lentos langelių A ir B yra gretimų langelių seka, kurios pirmasis narys yra langelis A, o paskutinis narys – langelis B. Gretimi langeliai yra tie, kurie liečiasi kraštinėmis arba kampais (kiekvienas langelis, nesantis lentos krašte, turi aštuonis gretimus langelius). Tokio kelio ilgis – tai sekos narių skaičius.

Pradiniai duomenys yra dvi natūraliųjų skaičių poros, žyminčios langelių A ir B koordinates.
Parašykite algoritmą rasti trumpiausio kelio tarp langelių A ir B ilgiui.

19. LENTA SU SKYLĖMIS.  Duota lenta, padalyta į m x n vienodų kvadratėlių. Dalis kvadratėlių išpjauta. Kokį didžiausią kvadratą be skylių galima rasti lentoje?

Pavyzdžiui, jei 6 x 9 dydžio lentoje išpjauti trys kvadratėliai taip, kaip parodyta paveiksle (19.1 pav), tai algoritmo rezultatas turi būti lygus 4 (galima rasti 4 x 4 dydžio kvadratą, aprėmintą dviguba linija).


19.1 pav.

Parašykite algoritmą šiam uždaviniui išspręsti.

Papildomi uždaviniai, skelbti spaudoje

20. FAKTORIALAS IR TRJETO LAIPSNIS. Parašykite algoritmą, kuris rastų, iš kurio didžiausio trejeto laipsnio yra dalus duotojo skaičiaus faktorialas.

21. STAČIAKAMPIS. Stačiakampio viršūnių koordinatės – natūralieji skaičiai. Koordinatės išdėstytos laikrodžio rodyklės apėjimo tvarka. Kiek taškų, kurių koordinatės taip pat natūralieji skaičiai, yra stačiakampio viduje ?

Parašykite algoritmą šiam uždaviniui išspręsti.

22. LOŠIMAS DEGTUKAIS. Lošia dviese. Yra dvi degtukų krūvelės. Lošėjai paeiliui ima degtukus iš krūvelių. Galima imti vieną arba du degtukus iš vienos (bet kurios) krūvelės. Laimi paėmęs paskutinius degtukus.

Parašykite algoritmą, kuris nurodytų, kaip elgtis duotoje situacijoje, t. y. kiek ir iš kurios krūvelės imti degtukų, kad laimėtume, jeigu tik galima laimėti.

Pradiniai duomenys – kiekvienoje krūvelėje esančių degtukų skaičius.

 
 

Aukštesniosioms mokykloms

23. DVI PROGRESIJOS. Duotos dvi aritmetinės progresijos
17; 21; 25;…       ir       16; 21; 26; …
Kai kurie skaičiai sutinkami abiejose progresijose (pavyzdžiui, 21).

Sudarykite algoritmą pirmųjų n skaičių, esančių abiejose progresijose, sumai rasti. Sprendimą pagrįskite.

24. LANGELIŲ TUŠAVIMAS. Parašykite algoritmą, kuris nustatytų, ar galima begaliniame languotame popieriaus lape užtušuoti n langelių taip, kad kiekvieno užtušuoto langelio gretimų užtušuotų langelių skaičius būtų lyginis (bet ne nulis) ir, jei galima, pateiktų bent vieną užtušuotų langelių išdėstymo variantą.

Gretimais langeliais yra laikomi tie, kurie turi bendrą kraštinę.

25. DAUGIAKAMPIS. Duotos n taškų koordinatės plokštumoje. Reikia sunumeruoti šiuos taškus tokia tvarka, kad nubraižytume (jei galima) daugiakampį (laisvų taškų ar atkarpų neturi likti).

Parašykite algoritmą šiam uždaviniui spręsti. Sprendimą paaiškinkite. 

Antrojo etapo uždavinių sąlygos

26. ATSISKAITYMAS DOLERIAIS. Lietuvoje dažnai atsiskaitoma doleriais. Cirkuliuoja tiktai banknotai (jų vertė ne mažesnė kaip vienas doleris), nes monetų (centų) bankas neparduoda. Dolerio vertė palyginti didelė, todėl kyla problemų, kai reikia nedidelį dolerių skaičių padalyti į kelias proporcingas dalis. 

Pradiniai duomenys – dolerių skaičius, kurį reikia padalyti duotam asmenų skaičiui n (n < 100) už pagamintą produktą, bei kiekvieno asmens indėlis į produkto gamybą, išreikštas procentais. 

Rezultatai – dolerių sumos, kurias reikia duoti kiekvienam asmeniui.
Reikia išdalyti visus dolerius taip, kad paklaidų suma būtų mažiausia. Paklaida, padaryta skaičiuojant kurio nors asmens užmokestį, lygi tiksliai apskaičiuoto užmokesčio ir užmokesčio, išreikšto sveikuoju dolerių skaičiumi, skirtumo absoliučiam didumui (moduliui).

Trumpai paaiškinkite uždavinio sprendimo idėją ir parašykite algoritmą.

27. TIESĖS. Duoti keturių tiesių, užrašytų lygtimis y = a · x + b, koeficientai a1, b1, a2, b2, a3, b3, a4, b4.

Parašykite algoritmą, kuris nustatytų, ar šios tiesės susikirsdamos sudaro keturkampį, ir, jeigu sudaro, rastų to keturkampio viršūnių koordinates. Pradiniai duomenys bus parinkti tokie, kad tiesių susikirtimo taškai būtų sveikieji skaičiai.

Trumpai paaiškinkite uždavinio sprendimo idėją.

 
 
 

Trečiojo etapo uždavinių sąlygos

28. SKAIČIŲ LENTELĖS ATSTATYMAS. Ekonomikoje, statistikoje ir kitur dažnai vartojamos skaičių lentelės su eilučių ir stulpelių sumomis. Į paskutinį (dešinįjį) stulpelį rašomos visų ankstesnių (kairesnių) tos eilutės skaičių sumos, o į paskutinę (apatinę) eilutę – visų aukštesnių to stulpelio skaičių sumos, pavyzdžiui,

Jeigu dalį skaičių ištrintume, tai, pasinaudodami likusiais, tam tikrais atvejais galėtume atstatyti prarastus skaičius, tuo pačiu ir pradinę (tikrąją) lentelę.
Pradiniai duomenys surašyti į tekstinę bylą. Pirmoje bylos eilutėje – sveikųjų skaičių lentelės eilučių skaičius m (2 <= m <= 10) ir stulpelių skaičius n (2 <= n <= 10). Kiekvienoje tolesnėje bylos eilutėje – duomenys apie vieną žinomą (neištrintą) lentelės sveikąjį skaičių: jo eilutės numeris, jo stulpelio numeris ir pats skaičius. 

Reikia:
1) pateikti duotą lentelę, nesamų skaičių vietą pažymėjus brūkšneliais;
2) nustatyti, ar įmanoma vienareikšmiškai atstatyti nesančius skaičius; jeigu neįmanoma – spausdinti pranešimą, paaiškinantį dėl ko neįmanoma (buvo neteisingos sumos pradinėje lentelėje arba per daug prarastų skaičių); jeigu įmanoma – pateikti atstatytą lentelę, kurioje visi atstatytieji skaičiai pažymėti žvaigždute, prirašyta skaičiaus gale.
Rezultatai spausdinami displėjaus ekrane.

29. DAUGIAKAMPIS. Duotos n taškų koordinatės plokštumoje. Reikia sunumeruoti šiuos taškus tokia tvarka, kad nubraižytume (jei galima) daugiakampį (laisvų taškų ar atkarpų neturi likti).

Parašykite algoritmą šiam uždaviniui spręsti. Sprendimą paaiškinkite.

Pradiniai duomenys surašyti į tekstinę bylą. Vienoje bylos eilutėje  pateikiama informacija apie vieną tašką, t. y. du sveikieji skaičiai – to taško koordinatės (x ir y).
Displėjaus ekrane reikia pateikti rezultatą – taškų koordinates – ta tvarka, kaip bus braižomas daugiakampis, jei galima nubraižyti, arba spausdinti pranešimą, paaiškinantį, kad negalima nubraižyti daugiakampio.

Pastaba. Šis uždavinys buvo duotas pirmame etape aukštesniųjų mokyklų moksleiviams. Kadangi jo nė vienas moksleivis neįveikė, buvo nutarta pakartoti jį baigiamojo rato dalyviams.