Nemes Tihamér OKSzTV 2002

Második forduló

9-10. osztályosok

2002. január 19. 900-1400


1. feladat: Tipp (15 pont) /tesztadatok/

Egy szerencsejátékban a résztvevők sorban egymás után egy-egy 1 és M közötti számot tippelnek. Az nyer, aki elsőként tippelt arra a számra, amelyre a résztvevők közül a legtöbben tippeltek. Ha több ilyen szám is van, akkor az összes ilyen szám első tippelője nyer.

Feladat:

Írj programot (TIPP.PAS, TIPP.C vagy TIPP.CPP néven), amely fogadja és feldolgozza a tippeket, majd megadja a nyertes játékos sorszámát, a nyertes számot, és azt, hogy hányan választották ezt a számot!
Bemenet:
A TIPP.BE állomány első sorában a versenyzők száma (1<=N<=5000) és a tipp maximális értéke (1<=M<=1000000) van, egyetlen szóközzel elválasztva. A következő N sorban van az egyes versenyzők tippje.
Kimenet:
A TIPP.KI állományba annyi sort kell írni, ahány győztes van (tippjük szerint növekvő sorrendben). Minden sorban három szám legyen egy-egy szóközzel elválasztva: a győztes sorszáma, a tippje, valamint az, hogy hányan tippelték ezt a számot!
Példa:
TIPP.BE TIPP.KI
6 100
25
20
15
15
30
20
3 15 2
2 20 2

2. feladat: Ütemezés (20 pont) /tesztadatok/

Mekk Elek ezermester népszerű vállalkozó, sokan keresik fel megrendelésekkel. Minden munkája pontosan egy napig tart. Minden megrendelés határidős, és amit elvállal, határidőre el is végzi. A mester a következő évre beérkezett megrendelések közül a lehető legtöbbet akarja elvállalni, de egyszerre csak egy munkán tud dolgozni.

Feladat:

Írj programot (UTEMEZ.PAS, UTEMEZ.C vagy UTEMEZ.CPP néven) a következő évi megrendelések egy lehető legnagyobb elemszámú részhalmazának a kiválasztására és ütemezésére annak érdekében, hogy a mester a lehető legtöbb munkát határidőre el tudjon végezni. A programnak egy ilyen ütemezést kell eredményül adnia.
Bemenet:
Az UTEMEZ.BE állomány első sora a megrendelések N számát (1<=N<=10000) tartalmazza. A következő N sor mindegyikében egy-egy H pozitív egész szám, az adott megrendelés határideje áll (1<=H<=365), tehát a J-edik munkát az állomány J+1-edik sora írja le.
Kimenet:
Az UTEMEZ.KI állomány első sorában a kiválasztott munkák M száma legyen. A következő M sor mindegyikébe két számot kell írni egy-egy szóközzel elválasztva. Az első szám a kiválasztott munka száma legyen, a második pedig annak a napnak a sorszáma, amelyiken az adott munkát el kell végezni. Ha több megoldás is van, közülük egy tetszőlegeset kell kiírni az állományba!
Példa:
UTEMEZ.BE UTEMEZ.KI
6
3
2
7
4
2
1
5
5 1
1 3
2 2
4 4
3 7
Megjegyzés: 5 1 helyett a 6 1, a 3 7 helyett pedig a 3 5 vagy a 3 6 is jó.

3. feladat: Üvegválogatás (20 pont) /tesztadatok/

Egy palackozó üzembe N db ládában érkeznek be az üvegek. Alakjuk szerint K fajta üveget különböztetnek meg. Ismert, hogy az egyes ládákban hány darab üveg van az egyes fajtákból. A palackozáshoz az üvegeket a fajtájuk szerint szét kell válogatni. Minden üvegfajta számára kijelölnek egy ládát (a meglévő N közül), és a többi ládából az adott fajta üveget ebbe a ládába rakják át. A cél az, hogy a lehető legkevesebb üveget kelljen átrakni a válogatás során.

Feladat:

Írj programot (VALOGAT.PAS, VALOGAT.C vagy VALOGAT.CPP néven), amely kiszámítja, hogy legkevesebb hány üveget kell átrakni, és ez mely ládák kijelölésével érhető el!
Bemenet:
A VALOGAT.BE állomány első sorában a ládák (2<=N<=10) és a fajták (2<=K<=N) száma van. A következő N sor mindegyike egy-egy láda tartalmát írja le. Minden sor pontosan K db nemnegatív egész számot tartalmaz, ahol a J-edik szám a ládában található J-edik üvegfajta darabszáma (1<=J<=K). (A ládák elég nagyok ahhoz, hogy mindegyikbe tetszőleges számú üveg beleférjen.)
Kimenet:
A VALOGAT.KI állományba két sort kell írni. Az első sorban a válogatáshoz minimálisan szükséges átrakások száma legyen. A második sor pontosan K számot tartalmazzon egy-egy szóközzel elválasztva, ahol a J-edik szám annak a ládának a sorszáma legyen, amelyiket a J-edik üvegfajta számára kijelöltünk. Ha több megoldás is van, közülük egy tetszőlegeset kell kiírni.
Példa:
VALOGAT.BE VALOGAT.KI
5 4
1 7 2 6
3 1 2 4
3 1 5 6
6 4 7 8
6 7 1 4
58
5 1 3 4


4. feladat: Tükörszó (20 pont) /tesztadatok/

Egy szót tükörszónak nevezünk, ha balról és jobbról kiolvasva betűről betűre megegyezik. (Tehát minden egybetűs szó tükörszó.) Minden szó felbontható részekre úgy, hogy minden rész tükörszó legyen. Minimálisnak nevezzük az olyan felbontást, amely egy szót a lehető legkevesebb tükörszóra szed szét.

Feladat:

Írj programot (TUKOR.PAS, TUKOR.C vagy TUKOR.CPP néven), amely kiszámítja, hogy egy adott szó minimális felbontása hány tükörszóból áll!
Bemenet:
A TUKOR.BE állomány egyetlen sorában egy legfeljebb 100 karakterből álló S szó van.
Kimenet:
A TUKOR.KI állományba egyetlen számot kell írni: az S szó minimális felbontásához szükséges tükörszavak számát.
Példa:
TUKOR.BE TUKOR.KI
abbakabadara 5

Elérhető összpontszám: 75 pont + 25 pont az 1. fordulóból