A KöMaL 2005. februári informatika feladatai

I-jelű feladatok A beküldési határidő 2005. március 15-én LEJÁRT.

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

Adott egy \(\displaystyle n\) természetes szám. Van-e olyan \(\displaystyle n\) darab valós szám, amelynek összege ugyanannyi, mint a szorzata? Lehet-e írni olyan programot, amely megadja az összes ilyen szám \(\displaystyle n\)-est? És ha van megoldás, megadhatjuk-e adatként az \(\displaystyle 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)

statisztika

I. 98. Van egy \(\displaystyle m\times n\)-es négyzetrácsunk (\(\displaystyle m\) és \(\displaystyle 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 \(\displaystyle m\times n\)-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)

statisztika

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)

statisztika

S-jelű feladatok A beküldési határidő 2005. március 15-én LEJÁRT.

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).

Feltételezhetjük, hogy n értéke legfeljebb 65000, és egy ember legfeljebb 200 másikkal ellenséges.

Figyeljünk a versenykiírásban előírt formátumra! A használt algoritmust le kell írni (vagy külön, vagy a programban kommentekben). Programot csak Pascal, C, C++ és Java nyelven lehet beadni.

Tesztadatok:

picik (5KB),
kicsik (14 KB),
normálisak (839KB),
nagyok (2,9MB),
óriásiak (25MB).

A programnak a

cat pici.3 | program > eredm_pici.3

illetve DOS ablakban:

type pici.3 | program > eredm_pici.3

utasítás hatására kell futnia. Az eredm_pici.3 file tartalma:

1
3
4
5

illetve:

cat pici.4 | program > eredm_pici.4

esetén az eredm_pici.4 file tartalma:

2
1
6

Futási idő, memóriahasználat

Az idők 2 Gigahertzes processzorra vonatkoznak. Az elvárt oszlopokban azt látjuk, hogy mennyi időben/memóriával lehet kényelmesen (semmi ravaszság a programban) megoldani a feladatot, a maximum oszlopokban pedig azt, hogy teszteléskor mennyi memóriát adunk, illetve mennyi ideig várunk az eredményre. Az egyes sorokban a kategóriához tartozó teszteken elért maximum van!

(10 pont)

megoldás, statisztika