Nemes Tihamér OKSzTV'99

1. feladat: Kockák (15 pont) /tesztadatok/

Építőkockákból úgy lehet stabil tornyot építeni, hogy kisebb kockára nem lehet nagyobbat, illetve könnyebb kockára nem lehet nehezebbet tenni.

Feladat:

Készíts programot, amely N kocka alapján megadja a belőlük építhető legmagasabb tornyot!

Bemenet:

A KOCKA.BE állomány első sorában a kockák (1<=N<=1000) száma van, a további N sorban pedig az egyes kockák oldalhossza és súlya (mindkettő 20000-nél kisebb pozitív egész szám), egyetlen szóközzel elválasztva.

Kimenet:

A KOCKA.KI állomány és a képernyő első sorába a legmagasabb torony M kockaszámát kell írni, a következő M sorba pedig az építés szerint alulról felfelé sorrendben a felhasznált kockák oldalhosszát és súlyát.

Példa:

2. feladat: Barátságok (16 pont) /tesztadatok/

Egy pszichológiai vizsgálatban jegyezték fel, hogy egy N tanulóból álló csoportban ki kit tart a legszimpatikusabbnak.

Bemenet:

A BARAT.BE állomány első sorában a tanulók száma (2<=N<=1000), a további N sorban a tanulók neve és a nekik legszimpatikusabb tanuló neve, egyetlen szóközzel elválasztva. A nevek szóközt nem tartalmazhatnak, hosszuk legfeljebb 20.

Feladat és kimenet:

Készíts programot, amely a képernyőre és a BARAT.KI állományba írja soronként az alábbiakat.
A. Az első sorba a senkinek sem szimpatikus tanulók nevét, egy-egy szóközzel elválasztva.
B. A második sorba azokat a párokat, amelyek tagjai egymásnak a legszimpatikusabbak, de senki másnak nem szimpatikus egyik sem. A párok tagjai közé kötőjelet (-), a párok közé szóközt kell írni.
C. A harmadik sorba a legkedveltebb tanuló nevét (akit a legtöbben adtak meg legszimpatikusabbként), ha több van, akkor mindegyiket, egy-egy szóközzel elválasztva.
D. A negyedik sorba azt a legnagyobb számot, ahány csoportba lehet oszani a tanulókat úgy, hogy minden tanuló ugyanazon csoportba kerüljön, mint amelyikben a neki legszimpatikusabb van.

Példa:

3. feladat: Terv (14 pont) /tesztadatok/

Egy nagyszabású építkezés azzal kezdődött, hogy kijelölték az építési területen az építhető épületek lehetséges helyeit. Minden lehetséges épület alaprajza téglalap alakú, megadható egy rögzített koordinátarendszerben az épület bal alsó sarkának (x,y) koordinátáival és az x tengellyel, illetve az y tengellyel párhuzamos oldalainak dx, illetve dy hosszával. Az építendő épületeket egymást nem takaró módon kell elhelyezni, azaz az origóból nézve egyik sem takarhatja bármely másik kiválasztott épület egyetlen pontját sem.

Feladat:

Írj programot, amely kiszámítja az egymást nem takaró módon elhelyezhető épületek legnagyobb számát.

Bemenet:

A TERV.BE állomány első sora a lehetséges épület elhelyezések (1<N<5000) számát tartalmazza. A további N sor mindegyike négy pozitív egész számot tartalmaz: x y dx dy (0<x, y, dx, dy<20000) egy-egy szóközzel elválasztva, egy lehetséges épület elhelyezés adatait. Az első két szám az épület bal alsó sarkának x, illetve y koordinátája, a harmadik szám az x tengellyel, a negyedik pedig az y tengellyel párhuzamos oldal hossza.

Kimenet:

A TERV.KI állomány és a képernyő első sora az egymást nem takaró módon elhelyezhető épületek legnagyobb K számát tartalmazza. A további K sorban kell megadni az elhelyezett épületek adatait, ugyanúgy, mint a bemeneti állományban.

Példa:

4. feladat: Kamion (15 pont) /tesztadatok/

Egy vállalat az ország különböző városaiban lévő üzemeiben alkatrészeket termel. A heti termelést a hét végén kamionokkal szállítja a központi raktárába. A kamionforgalom korlátozása miatt minden városból pontosan egy másik városba (egy irányban) mehetnek a kamionok közvetlenül. Ezért a vállalat úgy tervezi a szállításokat, hogy minden olyan városból, amelybe más városból nem lehet eljutni, egy-egy kamiont indít, a többi vároból viszont egyet sem. A korlátozások miatt  így minden kamion útja a központi raktárig egyértelműen meghatározott.
Minden kamion, amely útja során áthalad egy városon, az ott termelt alkatrészekből bármennyit felvehet, feltéve, hogy nincs tele. Ismerve a városokban termelt alkatrészek számát, ki kell számítani azt a legkisebb kamionkapacitást, amellyel a szállítás megoldható, ha minden kamion azonos kapacitású. Az eredményt a KAMION.KI állományba kell írni.

Bemenet:

A KAMION.BE állomány első sorában a városok N (1<N<=200) száma van. A központi raktár az 1. városban van, és onnan nem kell szállítani. Az állomány kövekező N-1 sorának mindegyike két egész számot tartalmaz egy szóközzel elválasztva. Az állomány I-edik sorában  az első szám azt a várost adja meg, ahova az I-edik városból mehet kamion. A második szám pedig az I-edik városban termelt alkatrészek száma. (Az 1. városból kivezető út nincs megadva.)

Példa:

5. feladat: Akadálypálya (15 pont) /tesztadatok/

Egy jármű négyzetrácsos elrendezésű pályaelemekből álló, M sorból, N oszlopból álló pályán mozoghat. Minden pályaelem vagy üres, vagy a közepén áthaladó sínt tartalmaz, amelyen a jármű haladhat. Egy pályaelem négy szomszédja a négyzetrácsos elrendezésben a tőle balra, jobbra, lefelé vagy fölfelé lévő pályaelem. A jármű egy lépésben a következő három lehetséges mozgást végezheti:

1. 90 fokkal elfordítja azt a pályaelemet, amelyen éppen áll.
2. Átmegy egy szomszédos pályaelemre, feltéve, hogy azon sín olyan irányban áll, hogy az csatlakozik az aktuális pályaelemen lévő sínhez.
3. 90 fokkal elfordít egy szomszédos pályaelemet.
Írj programot, amely kiszámítja azt a legkevesebb lépésszámot, amely megtételével a jármű a pálya bal felső (1,1) pontjából eljuthat a jobb alsó (M,N) pontjába.

Bemenet:

A PALYA.BE állomány első sorában a pálya méretét megadó M N számpár van egy szóközzel elválasztva (1<=M, N<=100). A következő M sor mindegyike N számot tartalmaz egy-egy szóközzel elválasztva:

0: az adott pályaelem nem tartalmaz sínt (üres)
1: a pályaelemen a sín vízszintes irányban áll
2: a pályaelemen a sín függőleges irányban áll

Kimenet:

A képernyőre és a PALYA.KI állomány első és egyetlen sorába azt a legkisebb lépésszámot kell írni, amely megtételével a jármű a pálya bal felső pontjából eljuthat a jobb alsó pontjába. Ha a jármű nem tud eljutni, akkor a -1 értéket kell kiírni.

Példa:

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