Pirmojo etapo uždavinių sąlygos

58. KOKIA SKAIČIAVIMO SISTEMA. Pradiniai duomenys – du sveikieji skaičiai a ir s (s > 0, a >= s). Teigiama, kad skaičius s yra lygus skaičiaus a skaitmenų sumai. Tačiau akivaizdu, kad taip nėra. Kyla įtarimas, kad skaičiai a ir s užrašyti kita, ne dešimtaine, skaičiavimo sistema.
Parašykite algoritmą, kuris nustatytų, ar egzistuoja tokia skaičiavimo sistema, kad būtų tenkinama sąlyga s = skaitmenų suma (a), ir jeigu egzistuoja, tai rastų šios skaičiavimo sistemos pagrindą x.

59. PARKETO KLOJIMAS. Stačiakampio kambario grindys klojamos parketo lentelėmis eglutės raštu:

Geriausias lentelių išdėstymas yra toks, kai duoto dydžio lentelėmis (jos nepjaustomos) padengiamas kuo didesnis kambario plotas (aukščiau pateiktame paveiksle lentelių išdėstymas nėra geriausias).

Parašykite algoritmą geriausiam lentelių išdėstymui rasti, t. y. reikia suskaičiuoti, kiek daugiausiai lentelių galima pakloti duoto ploto kambaryje.

60. TEIGINYS APIE STATŲJĮ TRIKAMPĮ. Stačiojo trikampio statinių a ir b ilgių kvadratų suma yra lygi įžambinės c ilgio kvadratui: a² + b² = c². 

• a) yra teisingas,
• b) gali būti teisingas,
• c) yra klaidingas.

Jeigu galima rasti kelis skaičių trejetus, tai reikia rasti trikampio, kurio plotas mažiausias, kraštines. Pavyzdžiui, kai pradiniai duomenys 0, 15, 0, tai kraštinių ilgiai gali būti 9, 15, 12 arba 15, 20, 25, bet rezultatu reikia laikyti sprendinį 9, 15, 12.

 61. ATSTATYK SKAIČIUS. Algoritmo parametrai – keturi neneigiami skaičiai. Trečiasis skaičius turi būti lygus pirmųjų dviejų sumai, o ketvirtasis – pirmųjų dviejų mažiausiam bendrajam kartotiniui. Tačiau ne visi skaičiai žinomi. Vietoj nežinomų skaičių užrašyti nuliai.

Parašykite algoritmą rasti nežinomiems skaičiams, jeigu juos galima rasti. Jeigu galimi keli sprendiniai, tai reikia pateikti mažiausią. (Jei randami keli skaičiai ir galimos kelios jų mažiausios kombinacijos, tai reikia imti tą, kurios pirmesnis skaičius mažesnis).

Jeigu sprendinio negalima rasti, tai reikia palikti nulį nepakeistą.
 

Pavyzdžiai

Pradiniai duomenys	Rezultatai
60  90  150  180  60  90    0    0   0  90    0    0   0   0    0    0    0   0    0  180  61  90    0  180	60   90  150  180  60   90  150  180   1   90   91   90   1    1    2    1   1  180  181  180  61   90    0  180

Reikia atstatyti prarastąjį skaitmenį, jeigu jis tikrai buvo prarastas ir įmanoma tai padaryti (t. y. jei renkant nebuvo padaryta daugiau klaidų). Atkreipiame dėmesį, jog uždavinys gali turėti daugiau negu vieną sprendinį.

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

2003    23  2126
2003   123  2126

2003   123   212
2003   123  2126

2003   123  2126
2003   123  2126

   3   123  2126
2003   123  2126
   3  2123  2126

 345  7876   111
SPRENDINIŲ NĖRA 

63. PAPRASTOSIOS TRUPMENOS. Reikia rasti visas teigiamas paprastąsias trupmenas, kurių reikšmė mažesnė už 1. Trupmenos vardiklis turi neviršyti duotojo natūraliojo skaičiaus n.

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

Jeigu galimi keli sprendiniai – tinka bet kuris. Jeigu uždavinys neturi nė vieno sprendinio – visus keturis skaičius reikia pakeisti nuliais.

function dbdf (x, y: integer): integer;
begin
  if x = 0
     then dbdf := y
     else dbdf := dbdf(y mod x, x)
end;

Mažiausiam bendrajam kartotiniui rasti galima pasinaudoti šitokia funkcija:

function mbkf (x, y: integer): integer;
begin
  mbkf := x div dbdf(x, y) * y
end;

65. LYGTIS. n-ojo laipsnio lygtis yra šitokio pavidalo:

a_nxⁿ + a_n-1x^n-1 + ... + a₁x + a⁰ = 0;

koeficientai a_n, a_n-1, ..., a₁, a₀ yra sveikieji skaičiai.

Parašykite programą visiems n-ojo laipsnio (1 <= n <= 50) lygties sveikiesiems sprendiniams rasti.

a) n-ojo laipsnio lygtis gali turėti daugiausia n sprendinių;

b) galioja lygybė:

a_nxⁿ + a_n-1x^n-1 + ... + a₁x + a₀ = a_n(x - x₁)(x - x₂)...(x - x_n-1)(x - x_n);
čia x₁, x₂, ... x_n – lygties šaknys.

Kiekvienai lygčiai skiriama viena pradinių duomenų eilutė. Iš viso pradinių duomenų byloje yra 8 eilutės. Vadinasi, vienu atlikimu programa turi išspręsti 8 lygtis.

66. DOMINO KAULIUKAI. Duota krūvelė domino kauliukų. Kiekvienas domino kauliukas perskirtas į dvi puses. Kiekvienoje pusėje užrašytas skaičius iš intervalo 0..6. Du kauliukus galima sujungti, jei skaičiai, užrašyti ant sujungiamų kauliukų pusių, sutampa.

Reikia nustatyti, ar krūvelėje esančius kauliukus galima išdėlioti į vieną liniją.

Laikykite, kad krūvelė nėra tuščia ir kauliukų skaičius neviršija 20000.

Iš viso pradinių duomenų byloje yra ne daugiau kaip 28 užpildytos eilutės, nes tiek yra skirtingų kauliukų.

 

67. DAUGIANARIAI. Daugianariu vadinamas tokio pavidalo reiškinys:

a_nxⁿ + a_n-1x^n-1 + ... + a₁x + a₀.

Koeficientai a_n, a_n-1, ..., a₁, a₀ yra realieji skaičiai. Laipsniai n, n-1, …, 1, 0 – sveikieji neneigiami skaičiai. Nariai, kurių a_i = 0, praleidžiami. Didžiausias n, kurio a_n <> 0, vadinamas daugianario laipsniu.

Su daugianariais atliekamos aritmetinės operacijos. Pavyzdžiui,

(-5x³ + 3,5x² - 1) + (6x³ + 2x + 1) = (x³ + 3,5x² + 2x)
(-5x³ + 3x² - 1) - (-5x³ + 3x² - 2) = (1)
(2,5x³ + 1) x (2x² - 6x) = (5x⁵ - 15x⁴ + 2x² - 6x)
(5x⁵ - 15x⁴ + 2x² - 6x) / (2x² - 6x) = (2,5x³ + 1)
(5x⁵ - 15x⁴ + 2x² - 6x) / (2,5x³ + 1) = (2x² - 6x)

Pateiktuose pavyzdžiuose daugianariai dalijosi be liekanos (t. y. buvo gaunama liekana, lygi nuliui). Tačiau liekana gali būti nelygi nuliui. Liekanos gavimo operaciją žymėsime simboliu \. Liekanos gavimo operacijos rezultatą apibrėšime šitaip:

P_dalmuo ir P_liekana turi būti tokie, kad būtų tenkinamos sąlygos:

čia Pⁱ – daugianaris, d(P_i) – daugianario P_i laipsnis.

Pavyzdžiui:

(5x⁵ - 15x⁴ + 3x² - x + 3) / (2,5x³ +1) = (2x² - 6x);
(5x⁵ - 15x⁴ + 3x² - x + 3) \ (2,5x³ + 1) = (x² + 5x + 3).

Parašykite programą, kuri atliktų operacijas +, -, *, / ir \ su daugianariais.

-5x³ + 3,5x² - 1

vaizduojamas šitaip:

3  -5.0  3.5  0.0  -1.0

68. HAMMINGO SEKA. Reikia generuoti didėjančią natūraliųjų skaičių seką, kurios kiekvienas narys išreiškiamas sandauga

čia i, j, k – sveikieji neneigiami skaičiai.

Parašykite programą, kuri generuotų tokią seką. Generavimą reikia baigti, kai gaunamas paskutinis sekos narys, dar neviršijantis 2³² – 1 (t. y. maxlongint) arba paspaudžiamas tarpo klavišas.

Programos dydis neturi viršyti 4Kbaitų.

69. TRUMPIAUSIAS KELIAS. (Šis uždavinys (bei uždavinys Rėmeliai) buvo pasiūlytas Šeštojoje tarptautinėje olimpiadoje, vykusioje 1994 m. Stokholme, Švedijoje, tačiau toje olimpiadoje nebuvo panaudotas.)  Duotas stačiakampis laukas, kurio kampų koordinatės yra (0, 0) ir (100, 100). Jo viduje išdėstyta n (n <= 30) kvadratėlių. Reikia rasti trumpiausią kelią iš taško (0, 0) į (100, 100) tokį, kuris nekirstų kvadratėlių.

Be to, žinoma, kad

a) kiekvieno kvadratėlio kraštinės ilgis yra 5 vienetai;
b) kvadratėlių kraštinės yra lygiagrečios koordinačių ašims;
c) kvadratėlių kampų koordinatės – sveikieji skaičiai;
d) kvadratėliai vienas nuo kito atskirti bent vienu vienetu.

70. RĖMELIAI. Paveikslėlyje vaizduojami vienas ant kito sudėti rėmeliai. Kiekvienas viršutinis rėmelis dengia apatinius. Rėmelio plotis – 1 simbolis, kiekviena rėmelio briauna ne trumpesnė kaip 3 simboliai. Visų rėmelių matosi bent po vieną kiekvienos briaunos simbolį. Kampinis simbolis priklauso abiem to kampo briaunoms.
 
 

Parašykite programą, kuri surastų, kokia tvarka n (n <= 26) rėmelių yra sudėti vienas ant kito.

Pirmoje bylos eilutėje yra piešinuko aukštis a, antroje – piešinuko plotis p. Likusiose a duomenų bylos eilutėse yra piešinukas. Kiekvienos šių eilučių ilgis – p. Rėmeliai žymimi skirtingomis lotyniškosios abėcėlės didžiosiomis raidėmis (nuo A iki Z). Fonas žymimas tašku (.).

Pradiniai duomenys tenkina reikalavimus:
a <= 30; p <= 30;