Pirmojo etapo uždavinių sąlygos

85. ŽENKLO KAITA. Duota netuščia sveikųjų nenulinių skaičių seka. Sekos pabaigoje yra nulis. Parašykite algoritmą, kuris nustatytų, kiek kartų šioje sekoje skaičiai keičia ženklą.

86. KETURŽENKLIŲ SKAIČIŲ SUMA. Duoti keturi skaitmenys: a, b, c, d. Reikia rasti sumą visų skirtingų keturženklių skaičių, kuriuos galima gauti perstatinėjant šiuos skaitmenis. Parašykite algoritmą šiam uždaviniui išspręsti.

87. DEGTUKAI. Duota n degtukų. Parašykite algoritmą, kuris nustatytų, ar iš duotų degtukų galima sudėlioti bent vieną iš šių figūrų: lygiakraštį trikampį, kvadratą ar stačiakampį. Dėliojamai figūrai turi būti panaudoti visi degtukai; be to, degtukų laužyti negalima.

88. ĮDOMI SEKA. Duotas natūralusis skaičius k. Reikia rasti k-ąjį sekos, kurią sudaro iš eilės surašyti natūraliųjų skaičių kvadratai, skaitmenį. Parašykite algoritmą šiam uždaviniui išspręsti.

89. BŪDVARDŽIŲ LAIPSNIAVIMAS. Parašykite algoritmą būdvardžiams laipsniuoti.

90. KUOLIUKAI. Palei kelią lygiais atstumais įkalti kuoliukai. Kadangi kuoliukai nevienodo aukščio, tai gaunama graži banguota tvorelė:

Tvorelės atkarpą h_i , h_i+1, ..., h_i+k (čia h_i, i = 1...n yra kuoliukų aukščiai) vadinsime išgaubta banga, jei tenkinamos sąlygos: h_i < h_i+1 <= h_i+2 <= .   . <= h_i+j >= h_i+j+1 >= … >= h_i+k-1 > h_i+k. Analogiškai apibrėžiama įgaubta banga.

Bangos ilgiu vadinsime kuoliukų skaičių bangoje.

s = a + b;
d = a x b.

92. SAVOTIŠKI SKAIČIAI. Parašykite programą, randančią visus n-ženklius skaičius (2 <= n <= 5), kurie yra dalūs iš savo skaitmenų ir kurių iš kito galo perskaitytas skaičius taip pat dalus iš šių skaitmenų. Palindrominius skaičius (vienodai skaitomus iš abiejų galų) atmeskite.

Atkreipiame dėmesį, kad programoje reikėtų vartoti sveikųjų skaičių tipą longint, leidžiantį didesnes sveikųjų skaičių reikšmes.

Parašykite algoritmą, kuris nustatytų, ar galima plokšteles uždėti vieną ant kitos taip, kad nesimatytų nė vienos skylutės. Jei negalima, reikia rasti, kiek mažiausiai skylučių matysis. Plokšteles galima visaip sukioti ir vartyti (bet uždėjus plokšteles vieną ant kitos, jų kraštai turi sutapti).

95. STOGAS. Ant horizontalios plokštumos (pvz., stalo) nubrėžtas kvadratas. Iš visų keturių kvadrato kampų vertikaliai į viršų kyla keturi virbai, kurių aukščiai a, b, c, d – sveikieji skaičiai (žymima pagal laikrodžio rodyklę).

Parašykite algoritmą, kuris nustatytų, ar ant virbų viršūnių galima uždėti plokščią stogą taip, kad jis gulėtų ant visų keturių virbų viršūnių – t. y. ar visų keturių virbų viršūnių taškai yra vienoje plokštumoje.

Jeigu stogo uždėti negalima, reikėtų pabandyti perstatyti virbus – gal tada pavyktų uždėti.

Jei yra galimi keli išdėstymo variantai, spausdinamas bet kuris vienas.

96. SIENINIS KALENDORIUS. Ant sienos kabo šio amžiaus metų mt kalendorius. Atverstas mėnuo mn. Toje vietoje, kur turi būti diena d, gilyn iškirpta s (s <= 12 - mn) skylučių.

Kiekvieno mėnesio pirmoji savaitė atspausdinta tuo pačiu atstumu nuo kalendoriaus lapo viršaus ir kairiojo krašto. Dienos surašytos stulpeliais nuo pirmadienio iki sekmadienio. Paveikslėlyje (96.1 pav.) pateiktas kalendoriaus lapelio pavyzdys.

Kokį skaičių (dienos numerį) matysime pro iškirptą skylutę ?

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

Kairiausias skaičiaus skaitmuo laikomas pirmuoju sekos nariu.

Antrąjį sekos narį randame skaičiuodami pradinio skaičiaus skaitmenis į dešinę per tiek pozicijų, kokia yra pirmojo sekos nario reikšmė. Skaičiuojama ratu – pasiekus skaičiaus galą vėl pradedama nuo pradžios.

Pagal antrojo sekos nario reikšmę analogiškai randamas trečiasis narys ir t. t.

Seka baigiama pasiekus kairiausiąjį skaičiaus skaitmenį (t. y. pirmąjį sekos narį). Visi skaičiaus skaitmenys turi įeiti į seką ir tik po vieną kartą.

Sakykime, turime skaičių 83441. Norėdami patikrinti, ar jis yra ciklinis skaičius, turime atlikti šiuos veiksmus:

1) pradedame nuo kairiausio skaitmens, t. y. nuo 8:
8 3 4 4 1

2) einame į dešinę per aštuonis skaitmenis:
8 3 4 4 1

3) einame į dešinę per keturis skaitmenis:
8 3 4 4 1

4) einame į dešinę per keturis skaitmenis:
8 3 4 4 1

5) einame į dešinę per tris skaitmenis:
8 3 4 4 1

6) paslenkame per vieną skaitmenį ir pagaliau pasiekiame pirmą skaičiaus skaitmenį, nuo kurio ir buvome pradėję:
8 3 4 4 1

Parašykite algoritmą, kuris patikrintų, ar duotas skaičius yra ciklinis, ir jei ne, tai reikia rasti mažiausią ciklinį skaičių, didesnį už duotąjį.

98. REIŠKINYS. Pradinis duomuo – Paskalio aritmetinis reiškinys, kurį gali sudaryti tik skaičiai, kintamųjų vardai (sudaryti tik iš raidžių ir skaitmenų) ir aritmetinės operacijos +, –, *, /, div, mod.
Duotas reiškinys yra teisingas.

Parašykite programą, kuri suskaičiuotų, kiek šiame reiškinyje yra skaičių, kiek kintamųjų ir kiek aritmetinių operacijų atskirai.

Šaškės stumdomos tik juodaisiais langeliais. Paveiksle (99.1 pav.) parodytas lentos juodųjų langelių numeravimas.

Situacija nusakoma dviem skaičiais b ir j: b – baltosios šaškės langelio numeris, ir j – juodosios šaškės langelio numeris. Baltoji šaškė eina aukštyn (link langelių su mažesniais numeriais), juodoji – žemyn.

Parašykite programą, kuri rastų geriausią baltosios šaškės ėjimą duotoje situacijoje, t. y. tokį, kad baltoji laimėtų, jeigu ji gali laimėti arba pasiektų lygiąsias, jeigu ji gali jas pasiekti (bet negali laimėti). Jei baltoji šaškė negali nei laimėti, nei pasiekti lygiųjų, tai pasirenkamas bet kuris ėjimas (vis tiek pralošime). Visais atvejais reikia laikyti, kad juodoji šaškė lošia optimaliai.

Tiems, kas nelošia šaškėmis.

1. Šaškės gali stovėti tik ant juodųjų langelių.
2. Šaškė gali eiti tik pirmyn įstrižai į gretimą langelį, pvz, baltoji šaškė iš 38 langelio gali eiti į 32 arba 33 langelį, iš 15 langelio – tik į 10, o juodoji šaškė iš 38 langelio – į 42 arba 43 langelį.
3. Šaškė kerta kitos spalvos šaškę, jei jos abi stovi tos pačios įstrižinės gretimuose langeliuose ir toje pačioje įstrižainėje už kertamos šaškės yra tuščias langelis. Pavyzdžiui, jeigu 20 ir 24 langeliuose yra skirtingų spalvų šaškės, tai jos viena kitą kerta, o nukirs ta, kurios eilė eiti; jei šaškės yra langeliuose 20 ir 25, tai kirsti gali tik 25 langelio šaškė (jeigu jos eilė eiti).
4. Kirsti galima abiem kryptimis – pirmyn ir atgal.

100. KVADRATINĖ ŠAKNIS.Žinoma, kad sveikasis skaičius gali turėti iki 80 skaitmenų imtinai.
Reikia nustatyti, ar šio skaičiaus tiksli kvadratinė šaknis yra sveikasis skaičius. Jei taip, tai reikia rasti šią šaknį.

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

Parašykite algoritmą, kuris šiame lape rastų tokį didžiausią stačiakampį, kad visos jame esančios raidės būtų skirtingos.

Jei tokių stačiakampių yra keletas, pakanka rasti bet kurį vieną.

102. KAM PATIKĖTI PASLAPTĮ. Du geri draugai pasipasakoja visas paslaptis. Vienas asmuo gali turėti kelis gerus draugus, kurie tarpusavyje gali ir nebūti geri draugai. Pavyzdžiui, A gali draugauti su B ir su C, nors B ir C nėra geri draugai. Tokiu atveju B paslaptys pasieks C ir atvirkščiai – C paslaptys pasieks B per A. Tokios grandinės gali būti ilgos ir, kaip sakoma, paslaptys greit pasklinda po visą pasaulį.

Reikia parašyti programą, kuri nustatytų, kokį didžiausią paslapčių skaičių galima patikėti duotai asmenų grupei, kad kiekvienas asmuo žinotų tik po vieną paslaptį.

Pirmoje eilutėje nurodytas draugų porų skaičius. Kiekviena tolesnė eilutė skiriama vienai draugų porai. Joje du skaičiai – asmenų kodai.

Asmenų sąrašas atskirai nepateikiamas. Laikoma, kad kiekvienas jų paminėtas porų sąraše.

103. PAŠTO ŽENKLAI. Turime n (n <= 30) skirtingų pašto ženklų verčių. Tarp jų visuomet yra minimali vertė, t.y. lygi 1. Kiekvienos vertės pašto ženklų skaičius neribotas.

Parašykite programą, randančią tokią didžiausią vertę, kad visi skaičiai nuo 1 iki rastojo būtų gaunami panaudojus ne daugiau kaip m (m <= 30) pašto ženklų.

Pavyzdžiui, jei n = 4, ženklų vertės 1, 4, 12, 21, o m = 5, tai bet kurią vertę nuo 1 iki 71 galima gauti panaudojus ne daugiau kaip 5 ženklus.

104. LOŠIMAS DEGTUKAIS. Du lošėjai paeiliui ima iš krūvelės degtukus. Vienu ėjimu galima imti ne daugiau kaip pusę krūvelėje esančių degtukų. Pralaimi tas, kuriam tenka paimti paskutinį degtuką.

Parašykite programą, kuri rastų pirmojo lošėjo laimintį ėjimą, jei toks egzistuoja (mat gali būti situacija, kad kokį ėjimą bepadarytų pirmasis, jis vis tiek pralaimės). Laikykite, kad priešininkas žais optimaliai, t. y. visuomet rinksis geriausią ėjimą.

105. TRAUKINYS. Turime keturių rūšių vagonus: pašto, krovininius, keleivinius ir vagonus restoranus. Iš šių vagonų reikia suformuoti traukinio sąstatą. Vagonus galima sukabinti laikantis tokių taisyklių :

1) pašto vagonas gali būti kabinamas tik po garvežio (sąstato pradžioje) arba po kito pašto vagono. Sąstate gali būti ne daugiau kaip 2 pašto vagonai (jų gali ir visai nebūti);
2) vagonas restoranas turi būti tarp dviejų keleivinių vagonų. Restoranų skaičius neribojamas, tačiau jų gali ir visai nebūti;
3) sąstate būtinai turi būti bent vienas keleivinis vagonas. Šios rūšies vagonų skaičius neribojamas;
4) krovininiai vagonai kabinami tik sąstato gale, vienas po kito. Jų gali būti ne daugiau kaip trys (gali ir visai nebūti).

Pastaba. Garvežys neįskaitomas į sąstatą.

106. LOGINIS REIŠKINYS. Pradinis duomuo – Paskalio loginis reiškinys, kurį gali sudaryti tik skaičiai (sveikieji ir realieji), kintamųjų vardai (sudaryti tik iš raidžių ir skaitmenų), skliaustai: „(“ ir „)“, lyginimo (=, <>, <, >, <=, >=) bei loginės (not, and, or) operacijos.

Duotas taisyklingai užrašytas reiškinys.

Parašykite programą, kuri suskaičiuotų, kiek šiame reiškinyje yra skirtingų skaičių, kiek skirtingų kintamųjų ir kiek skirtingų lyginimo bei loginių operacijų atskirai.

Pastaba. Du skaičiai laikomi skirtingais, jei jie yra skirtingų tipų arba to paties tipo, tačiau nelygūs.

Žaidimo tikslas – rasti tokią kirtimų seką, kad lentoje liktų tik viena šaškė. Parašykite algoritmą šiam tikslui pasiekti.

108. NESĖKMINGAS SKRYDIS ORO BALIONU. Du Terainkognita valstybės gyventojai pasiryžo apskristi aplink savo šalį oro balionu. Jiems beskrendant naktį sugedo prietaisai ir teko nusileisti.

Nusileidus ant žemės ir pajutus tvirtą pagrindą po savo kojomis, keliautojams reikia nustatyti, ar pakliuvo į savo valstybės teritoriją, ar ne.

Terainkognitos teritorija – paprastojo daugiakampio formos.

Parašykite programą, kuri nustatytų, ar oro balionas nusileido Terainkognitos teritorijoje (ar bent ant sienos), ar ne.

Pastaba. Daugiakampis vadinamas paprastuoju, jei jo kontūras neturi persikirtimų.

109. PAŠTO ŽENKLAI. Turime n (n <= 30) skirtingų pašto ženklų verčių. Tarp jų visuomet yra minimali vertė, t.y. lygi 1. Kiekvienos vertės pašto ženklų skaičius neribotas.

Parašykite programą, randančią tokią didžiausią vertę, kad visi skaičiai nuo 1 iki rastojo būtų gaunami panaudojus ne daugiau kaip m (m <= 30) pašto ženklų.

Pavyzdžiui, jei n = 4, ženklų vertės 1, 4, 12, 21, o m = 5, tai bet kurią vertę nuo 1 iki 71 galima gauti panaudojus ne daugiau kaip 5 ženklus.

110. ATSPĖK SKAIČIŲ. Žaidžiama dviese. Pirmasis žaidėjas sugalvoja keturženklį skaičių, kurio visi skaitmenys skirtingi. Antrasis spėja – pateikia kokį nors keturženklį skaičių. Tuomet pirmasis pasako, kiek skaitmenų atspėjo antrasis ir kiek iš jų yra savo vietose.

Pavyzdžiui, sugalvotas skaičius 7280.
Antrasis žaidėjas pateikia skaičių 8630.
Pirmasis žaidėjas atsako: atspėti du skaitmenys, iš jų vienas teisingoje vietoje.

Parašykite algoritmą, kuris atspėtų skaičių, t. y. kad būtų žaidžiama už antrąjį žaidėją. Spėjimų skaičius turi būti minimalus.

Pirmojo žaidėjo ėjimus atliks kompiuteris. Abu bendrauja modulio ŽAIDIMAS procedūros ėjimas pagalba. Ši procedūra turi vieną pradinį duomenį – sveikąjį keturženklį skaičių ir du rezultatus: atspėtų skaitmenų skaičių ir atspėtų savo vietose esančių skaitmenų skaičių.

Pastaba. Moksleiviams buvo pateikta viena modulio ŽAIDIMAS versija, testavimui buvo naudojama kita.

unit žaidimas;
interface
  procedure ėjimas (sk: integer; var atsp, vietoj: integer);
    {gavusi skaičių, procedūra palygina jį su „sugalvotu“ }
    { skaičiumi ir pasako kiek skaitmenų atspėta ir kiek iš jų }
    { yra savo vietose }
implementation
  var ska: string;        { sugalvotas skaičius }
      aibė: set of char;  { sugalvoto skaičiaus skaitmenų aibė }
      skt: longint;       { spėjimų skaičius }
  procedure ėjimas (sk: integer; var atsp, vietoj: integer);
    var s: string; { spėjamas skaičius, paverstas eilute }
        i: integer;
  begin
    skt := skt + 1;
    if skt = 100    { jei viršijamas spėjimų limitas }
       then begin
              writeln ('Viršytas spėjimų limitas - 100');
              halt
            end;
    if (sk < 1000) or (sk > 9999)
       then begin
              write ('Bandyta spėti ne keturženklį skaičių: ');
              writeln (sk);
              halt
            end;
    str (sk, s);  { bus paprasčiau lyginti dvi eilutes }
    if s = ska    { jei skaičius atspėtas }
       then begin
              writeln ('Atspėta per ', skt, ' kartų.');
              halt
            end
    else begin  { rasime kiek skaitmenų savo vietoje ir kiek atspėta }
           vietoj := 0;
           for i := 1 to 4 do
               if s[i] = ska[i]
                  then vietoj := vietoj + 1;
           atsp := 0;
           for i := 1 to 4 do
               if s[i] in aibė
                  then atsp := atsp + 1
        end;
  end; { ėjimai }

  var reikšmė, kl_kodas, elem_sk: integer;
      c: char;
begin
  writeln ('Tai yra demonstracinis modulis.');
  writeln ('Sugalvokite keturženklį skaičių patys: ');
  readln (ska);
  reikšmė := 0; { įvestas skaičius verčiamas simbolių eilute }
  val (ska, reikšmė, kl_kodas);
  if (kl_kodas <> 0)  or   { jei skaičius įvestas klaidingai }
     (reikšmė < 1000) or (reikšmė > 9999)
     then
       begin
         writeln ('Sugalvojote ne keturženklį skaičių.');
         halt
       end;
  aibė := [ska[1]] + [ska[2]] + [ska[3]] + [ska[4]];
  elem_sk := 0;
  for c := '0' to '9' do
      if c in aibė
         then elem_sk := elem_sk + 1;
  if elem_sk <> 4
     then
      begin
        writeln ('Skaičiaus skaitmenys turi būti skirtingi.');
        halt
      end;
end.

111. TIESIAMI KELIAI. Projektuojami modernūs daugiajuosčiai keliai. Tarkime, kad yra m (1 <= m <= 100) miestų. Iš pradinio (pirmojo) miesto į galinį (m-ąjį) miestą tiesiamas kelių tinklas, einantis per likusius m – 2 miestus. Keliai nebūtinai turi eiti per kiekvieną miestą. Į pradinį miestą neateina, o iš galinio miesto neišeina joks kelias. Tinklą turėtų sudaryti ne daugiau kaip k kelių. Kiekvienas kelias yra vienos krypties ir jam numatytas maksimalus eismo juostų skaičius.

Projekte numatytą mašinų juostų skaičių reikėtų optimaliai patikslinti taip, kad mašinos galėtų judėti nesustodamos (t. y. nesusidarytų kamščiai) ir kad visų kelių, išeinančių iš pradinio miesto, bendras juostų skaičius būtų didžiausias. Kamščiai nesusidarys, jei į kiekvieną tarpinį miestą įeinančių juostų skaičius bus lygus išeinančių juostų skaičiui.

Likusiose k eilučių nurodoma po tris duomenis: miesto, iš kurio išeina kelias, numeris, miesto, į kurį ateina kelias, numeris, maksimalus galimas šio kelio eismo juostų skaičius.

112. KAIP PANEŠTI MILIJONĄ. Brolių Grimų pasakoje „Šešiese skersai žemės“ šeši draugai nugali suktą karalių.

Norėdamas atsikratyti nemalonių svečių, karalius pasišaukia vieną iš jų ir sako:

– Klausyk, aš tau duosiu tiek aukso, kiek gali panešti ant savo pečių, tik iškeliaukit iš mano karalystės.

Kraudamasis į maišą brangenybes, vaikinas norėtų, kad maiše esančių daiktų svoris būtų kuo mažesnis, o jų vertė – kuo didesnė.

Parašykite programą, kuri patartų, kurias brangenybes verta imti, kurių – ne.

Likusiose n eilučių įrašyta kiekvienos brangenybės svoris ir vertė. Brangenybės numeruojamos nuo 1 iki n, t. y. antroje bylos eilutėje įrašyti duomenys apie pirmąją brangenybę, trečioje – apie antrąją ir t. t.

113. ŠACHMATAI. Tradicinėje šachmatų lentoje (8 x 8 langeliai) iš viso stovi n figūrų – baltų ir juodų. Figūros žymimos raidėmis:

K – karalius,
V – valdovė,
B – bokštas,
R – rikis,
Ž – žirgas,
P – pėstininkas.

Lentos langeliai sunumeruoti skaičiais, kaip parodyta paveiksle. Kiekvienos figūros padėtis lentoje nusakoma užrašu, kurio pirmasis simbolis žymi spalvą (raidė b arba j), antrasis – figūros pavadinimą, trečiasis ir ketvirtasis – skaičiai, nurodantys figūros padėties lentoje koordinates, pavyzdžiui, bV14, jK85.

Reikia parašyti algoritmą, kuris nustatytų, ar baltieji šachuoja juodųjų karalių (t.y. ar grasina jį nukirsti). Jei taip, algoritmas turi pateikti kurį nors vieną atsakomąjį juodųjų ėjimą arba pranešti žaidimo baigmę – žodį MATAS. Ėjimas nusakomas keturių simbolių užrašu pagal aukščiau minėtas taisykles (nurodomas tik langelis, į kurį einama). Jei karalius nešachuojamas, pakanka pranešti: NEŠACHUOJAMA.

Pastaba. Nereikalaujama, kad juodieji žaistų protingai (optimaliai), t. y. jie turi tik nurodyti tokį ėjimą, kad šiuo metu atsikratytų šacho, į tolesnes pasekmes neatsižvelgiant.