Egy építkezés befejezéséhez N különböző munkát kell elvégezni. Minden munka pontosan egy nap alatt teljesíthető, egy napon több munka is végezhető. A terv alapján azonban tudjuk, hogy bizonyos munkát előbb kell elvégezni, mint másokat. Pontosabban, a terv (A, B) párok halmazát tartalmazza, ami azt jelenti, hogy az A munkát előbb kell elvégezni, mint a B munkát.Feladat:
Írj programot (EPIT.PAS, EPIT.C vagy EPIT.CPP), amelyBemenet:
- kiszámítja, hogy legkevesebb hány nap kell az összes munka elvégzéséhez;
- és megadja a munkáknak egy olyan beosztását, amely teljesíti a követelményeket.
Az EPIT.BE állomány első sora az N és T egész számokat tartalmazza: N az elvégzendő munkák száma (1<=N<=200), a munkákat az 1, ..., N számokkal azonosítjuk, T pedig a tervben megadott előzési párok száma (1<=T<=10000). A további T sor mindegyikében két egész szám van: A és B (1<=A<=N, 1<=B<=N), ami azt jelenti, hogy az A munkát előbb kell elvégezni, mint B-t.Kimenet:Az EPIT.KI állomány első sorába egy egész számot kell írni, M-et, ami a lehető legkevesebb napok száma, ami alatt az összes munkát el lehet végezni. Ezt követően pontosan M sornak kell lennie. Az állomány I+1-edik sora azon munkák sorszámát tartalmazza egy-egy szóközzel elválasztva, amelyeket az I-edik napon kell elvégezni. Ha több megoldás is van, közülük egy tetszőlegeset kell kiírni. Ha nem lehet a tervben megadott feltételeket teljesíteni, akkor az első sorba 0-t kell írni.Példa:
EPIT.BE EPIT.KI 10 11
1 3
3 4
1 5
5 3
3 7
5 6
1 8
8 6
6 9
9 10
7 105
1 2
5 8
3 6
4 7 9
10
Bergengócia egyetemeire N informatikus szakra jelentkezhetnek a felvételizők, a szakokat sorszámukkal azonosítjuk. Közös felvételi vizsgát tesznek, azaz mindenkinek egyetlen pontszáma van. Minden diák meghatározhatja a felvételi lapján, hogy melyik egyetemre akar kerülni, a szokásos prioritási sorrendben. Ezen kívül tudjuk, hogy hogy melyik szakra hányan vehetők fel.A felvételi ponthatárokat úgy kell megállapítani, hogy teljesüljenek az alábbi feltételek:
Feladat:
- Minden jelentkező arra a szakra kerül be, amelyik az első a prioritási sorrendjében, amelyen a ponthatár nem nagyobb, mint az ő pontszáma.
- Minden szakra az így felvett jelentkezők száma nem haladja meg a szakra megadott keretszámot, kivéve egy esetet, amikor eggyel magasabb pontszámmal a szakra a keretszámnál kevesebb kerülne be, ekkor a felvehetők száma a keretszám 110 százaléka (lefele kerekítve) lehet.
- Bármely két, azonos pontszámú jelentkező esetén, ha jelentkeztek ugyanarra a szakra, akkor vagy mindkettőt felvették, vagy egyiket sem vették fel.
- A ponthatár megállapítása olyan legyen, hogy összességében a lehető legtöbb jelentkezőt vegyenek fel.
Írj programot (FELVET.PAS, FELVET.C vagy FELVET.CPP), ami meghatározza, hogy melyik szakon mennyi lesz a felvételi ponthatár (a felvett tanulók pontszámai közül a legkisebb, ha senki nem került be a szakra, akkor 0), és hogy melyik tanuló melyik szakra került be.Bemenet:A FELVET.BE állomány első sorában a szakok N (1<=N<=100) és a felvételizők M (1<=9000) száma van, egy-egy szóközzel elválasztva. A második sorban N darab szám van, szintén egy-egy szóközzel elválasztva: minden szakra a maximálisan felvehető diákok száma, a keretszám (0<=K(I)<=1000). A következő M sorban a diákok adatai vannak: a pontszámuk (0<=P(I)<=120), majd azon szakok sorszáma a jelentkezés sorrendjében, ahova be szeretne kerülni.Kimenet:A FELVET.KI állomány első sorába N darab számot kell írni: az i. szám az i. szakon a felvételi ponthatár, illetve 0, ha egyetlen diákot sem vettek fel. A második sorba M darab számot kell írni: az i. szám annak a szaknak a sorszáma, ahová az i. diák bekerült, illetve 0, ha a diákot nem vették fel sehova.Példa:
FELVET.BE FELVET.KI 4 5
1 2 2 3
98 3 2 1 4
81 1 3 2
82 4
92 3 1
0 1 2 3 481 0 92 82
3 1 4 3 0
Egy szabályos hatszög alakú térképet szabályos hatszögekre bontottunk úgy, hogy minden oldalán N darab kisebb hatszög lett. A szemben levő csúcsokat összekötő átlókra az ábra szimmetrikus, így a hatszögeket 3 index segítségével azonosíthatjuk (mindegyik az egyik tengely mentén állandó). Az i index a vízszintes tengely mentén állandó, felfelé csökken, lefelé nő. A j index a jobbra lefelé haladó tengely mentén állandó, ettől balra csökken, jobbra pedig nő. A k index pedig a balra lefele haladó tengely mentén állandó, ettől balra növekszik, jobbra pedig csökken.
Így az (i, j, k) indexű elem szomszédainak indexei az ábra szerint alakulnak. Legyen a középső kis hatszög indexe a (0, 0, 0)! Minden egyes pontnak ismerjük a tengerszint feletti magasságát.Feladat:
Készíts programot (HATSZOG.PAS, HATSZOG.C, HATSZOG.CPP), amely a (p, q, r) indexű pontból meghatározza a legrövödebb olyan ún. vízszintes út hosszát az (x, y, z) pontba, amelynek során a tengerszint feletti magasság nem változik!Bemenet:A HATSZOG.BE állomány első sorában a nagy hatszög mérete (1<=N<=80) van. A következő 2*N-1 sorban annyi tengerszint feletti magasság van (0<=magasság<=1000), amennyi a térkép egy-egy sorához szükséges. Az utolsó sorban a kezdő (p, q, r) és a végpozíció (x, y, z) indexei találhatók, egy-egy szóközzel elválasztva.Kimenet:A HATSZOG.KI állomány egyetlen sorába a legrövidebb (p, q, r)-ből (x, y, z)-be vezető vízszintes út hosszát kell írni. Ha ilyen út nincs, akkor a kiírt szám legyen -1!Példa:
HATSZOG.BE HATSZOG.KI 3
5 6 7
1 1 1 8
1 2 3 2 1
1 1 1 1
1 1 1
-1 -1 2 1 0 -14
Adott a síkon M pont. El kell helyezni a koordináta-rendszer tengelyeivel párhuzamos egyeneseket úgy, hogy minden megadott pont rajta legyen legalább egy egyenesen. Azonban, az egyeneseket csak párosával lehet elhelyezni, ami azt jelenti, hogy ha az (X, X) ponton átmenő X tengellyel párhuzamos egyenest elhelyeztünk, akkor el kell helyezni a párját, tehát az (X, X) ponton átmenő, Y tengellyel párhuzamos egyenest is.Feladat:
Írj programot (LEFED.PAS, LEFED.C vagy LEFED.CPP), amelyBemenet:
- kiszámítja, hogy legkevesebb hány tengelyekkel párhuzamos egyenespár kell az összes pont lefedésére,
- és megad minimális számú lefedő egyenes-párokat.
A LEFED.BE állomány első sora az N és M két egész számokat tartalmazza: N (1<=N<=200) a négyzetrács sorainak és oszlopainak száma. A következő M sor mindegyike két egész számot tartalmaz: X, Y (1<=X<=N, 1<=Y<=N), amelyek egy lefedhető pont koordinátái.Kimenet:A LEFED.KI állomány első sorába egy egész számot kell írni, E-t, ami a lehető legkevesebb, tengelyekkel párhuzamos egyenespár száma, amellyel az összes pont lefedhető. A második sor pontosan E egész számot tartalmazzon, azokat az X értékeket, amelyekre az (X, X) ponton átmenő, X tengellyel és Y tengellyel párhuzamos lefedő egyenespárt fektettünk. Ha több megoldás is van, közülük egy tetszőlegeset kell kiírni.Példa:
LEFED.BE LEFED.KI 5 7
1 3
2 3
3 3
3 1
3 2
3 4
5 22
3 5