A számítástechnika-versenyben kitűzött feladatok 2004. október

Kérjük, olvassa el a versenykiírást.

Az I pontversenyben kitűzött gyakorlatok

I. 85. Egy 5x5-ös sakktáblát kell bejárni lóval, minden egyes mezőt egyszer érintve. Készítsünk programot (i85.pas,...), amely kidolgozza és kirajzolja a ló lehetséges útvonalait. (Az útvonalat az érintett mezők középpontjait összekötő szakaszokkal jelezhetjük, a bejárás sorrendjében.)

(10 pont)

I. 86. Egy 5x5-ös sakktábla minden mezőjén egy 0 vagy egy 1 számjegyet kell elhelyezni úgy, hogy mind a 16 darab, 2x2-es mezőből álló részlet más és más legyen.

a) Hány ilyen elrendezés létezik?

b) Ezek között hány olyan elrendezés van, amelyben a bal szélső oszlop pontosan megegyezik a jobb szélső oszloppal?

c) Hány elrendezés marad, ha még azt is előírjuk, hogy a felső és az alsó sor is pontosan megegyezzen egymással?

Készítsünk programot (i86.pas,...), amely leszámolja és kiírja az a), b) és c) feltételeknek megfelelő esetek számát!

(10 pont)

I. 87. Készítsünk táblázatot, amely k-adik sorának n-edik mezőjében azt a számot tartalmazza, ahányféleképpen k darab különböző színű dobókockával dobva pontosan n pontot érhetünk el összesen.

Beküldendő a táblázat (i87.xls).

(10 pont)

Az I-jelű feladatok megoldásai a következő címre küldendők:

Az S pontversenyben kitűzött feladat

S. 2. Találtunk egy kincsesbarlangot, melyben n darab - különböző értékű és tömegű - kincs van. Ezekből szeretnénk néhányat w kilogramm teherbírású hátizsákunkba rakni úgy, hogy a bepakolt kincsek értékének összege a lehető legnagyobb legyen.

Írjunk programot, amely kiszámítja a legnagyobb bepakolható értéket. A program bemenetének első sorában n, második sorában w áll. Ezután n további sor következik, mindegyik egy kincs tömegét és értékét tartalmazza. (Az adatok ezúttal is helyesek lesznek, az ellenőrzéstől eltekinthetünk.) A program kimenete egyetlen szám, a legnagyobb bepakolható érték.

Példa: 

Beküldendő:

A program, a rövid leírás, és a futási eredmény a teszt adatokon. Csak olyan programokat küldjetek be, amelynek kimenete a 4 eredménnyel megadott teszten megegyezik a megadott eredményekkel!

Értékelés:

Pontot csak az kaphat, akinek programja a kiírás szerinti, le tudjuk fordítani, van hozzá leírás, és a kicsi teszt adatokon a helyes eredményt adja (max. 5 pont). További 3 pont kapható, ha a program a nagy teszt adatokon is a helyes eredményt produkálja (max 10 perc futási idő alatt). Ezenkívül 1-1 extra pontot kap, akinek a programja az 1. ill. 2. óriási teszten is (1 órán belül) a helyes eredményt adja.

Teszt adatok

(10 pont)

Az S-jelű feladatok megoldásai a következő címre küldendők:

A beküldési határidő: 2004. november 15.