A számítástechnika-versenyben kitűzött feladatok 2005. február

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

Az I pontversenyben kitűzött gyakorlatok

I. 97. Kísérletezzünk, gondolkozzunk!

Adott egy n természetes szám. Van-e olyan n darab valós szám, amelynek összege ugyanannyi, mint a szorzata? Lehet-e írni olyan programot, amely megadja az összes ilyen szám n-est? És ha van megoldás, megadhatjuk-e adatként az n darab szám közül néhánynak az értékét?

Beküldendő a válaszokat tartalmazó és magyarázó szöveg-fájl (i97.txt) és a válaszokat megadó program (i97.pas).

(10 pont)

I. 98. Van egy mxn-es négyzetrácsunk (m és n pozitív egész számok), melynek egyes négyzeteire egységnégyzet alapú hasábot állítunk. A hasábok magasságát egy mxn-es mátrix tartalmazza.

Írjunk programot, amely a képernyőre kirajzolja a konstrukció egy jellemző távlati képét, az elölnézeti és oldalnézeti képpel együtt. Demo üzemmódban a program adhatja meg az egyes oszlopok magasságát, User üzemmódban pedig kérje be a szükséges adatokat, és az azoknak megfelelő ábrát jelenítse meg.

Beküldendő a program (i98.pas).

(10 pont)

Megjegyzés. Ennek a feladatnak folytatása szerepel a következő havi feladatok között.

I. 99. Meseországban tallérral működnek az ital-automaták.

Egy számolótábla harmadik sorának első néhány mezőjében csökkenő sorrendben felsorolták a létező pénzérméket.

Az az első előírás, hogy ha az első sor első mezőjébe beírjuk, hogy egy ital hány tallér (amely természetes szám), akkor a negyedik sorban - rendre az egyes érmék értéke alá kiírva - jelenjen meg, hogy melyik érméből hány darabra van szükségünk.

A második előírás okát ne firtassuk: Minden tétel befizetését a lehető legnagyobb pénzérméből a lehető legtöbb darabbal kötelező kezdeni, majd ugyanezt az elvet kell ismételten alkalmazni a még fennmaradó értékekre.

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

(10 pont)

Felhívjuk a versenyzők figyelmét, hogy a feladatok értelmezése, a szükséges eljárások megtervezése és megvalósítása (beleértve az input és output megtervezését is!) a megoldás szerves részét képezik, hacsak a feladat szövege nem tartalmaz valamiféle megkötést. Természetesen minden reális értelmezést elfogadunk, de a kapott pontszám függhet az értelmezéstől, például attól, hogy ki milyen korlátozások felvállalása mellett tudta (elfogadható futásidővel) megoldani a felvetett problémát.

Nem lenne versenyszerű, ha e-mailt küldő versenyzőinknek extra információkat adnánk - ezért kérjük, ilyen kérdéseket a jövőben ne is küldjenek, azokra nem is válaszolunk!

Megjegyzés. Rossz feladat nincs, legfeljebb olyan, amelynek az a megoldása, hogy a kívánt adathalmaz, ábra stb. nem létezik. Ilyen kérdések a gyakorlatban rendszeresen előfordulnak, gyors és határozott felismerésük (esetleg a hozzá tartozó bizonyítással együtt!) igen értékes, gyakran a probléma átfogalmazásához, a nézőpont megváltoztatásához vezet.

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

Az S pontversenyben kitűzött feladat

S. 6. Egy stadionba egy mérkőzésre n ember érkezik. Tudjuk, hogy ki kivel ellenséges (feltesszük, hogy az ellenségesség kölcsönös). A feladat az, hogy ültessük le az embereket a stadion jobb és bal lelátójára úgy, hogy egy lelátón belül ne legyenek egymással ellenséges emberek, ha pedig ez nem lehetséges, akkor találjunk erre bizonyítékot.

Hogyan nézzen ki egy ilyen bizonyíték? Soroljunk fel páratlan sok embert úgy, hogy mindenki ellenséges a sorban előtte állóval és utána következővel, és az utolsó is ellenséges az elsővel. (Ezeket az embereket tényleg nem tudjuk megfelelően kettéosztani a két lelátóra.)

A programunk az adatokat a standard bemenetről olvassa. Az emberek sorszámozva vannak 1-től n-ig. A bemenet első sora az emberek n száma, az ezután következő sorokban két-két sorszám, - két egymással ellenséges ember sorszáma - található.

Ha sikerül szétültetni az embereket, akkor a standard kimenetre írt eredmény legyen azon emberek sorszáma, akik a bal oldalon üljenek (az 1. embernek a bal oldalon kell ülnie). Ha nem sikerül a szétültetés, akkor a standard kimenetre írjuk ki a fent említett bizonyítékot (a páratlan sok ember sorszámát).

Minta- és tesztállományok itttalálhatók. Feltételezhetjük, hogy n értéke legfeljebb 65 000, és egy ember legfeljebb 200 másikkal ellenséges. Figyeljünk a versenykiírásban előírt formátumra (leírás kell; a Delphiben és más egzotikus nyelveken beküldött programok nem versenyszerűnek minősülnek).

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

A beküldési határidő: 2005. március 15.