Az iskola bejáratánál N lépcsőfok van. Egyszerre maximum K fokot tudunk lépni, ugrani fölfele. Minden nap egyszer megyünk be az iskolába.Feladat:
Készíts programot (LEPCSOK.PAS, LEPCSOK.C, LEPCSOK.CPP), amely megadja, hogy hány napig tudunk más és más módon feljutni a lépcsőkön!Bemenet:A LEPCSOK.BE állomány egyetlen sorában a lépcsőfokok N száma (1<=N<=32) és a legnagyobb lépés K lépcsőszáma (1<=K<=10) van.Kimenet:A LEPCSOK.KI állományba egyetlen számot kell írni: hányféle módon lehet felmenni a lépcsőn.Megjegyzés:(1,1,1), (1,2) és (2,1) a lehetséges lépések.Példa:
LEPCSOK.BE LEPCSOK.KI 3 2
3
Adott a számegyenesen N darab zárt intervallum a kezdő és a végpontjával, amelyek egész számok. Ki kell választani a lehető legkevesebb intervallumot úgy, hogy bármely [K, V] intervallumhoz legyen olyan kiválasztott [A, B] intervallum, amely tartalmazza [K, V] legalább egy pontját. Tehát van olyan X egész szám, hogy K<=X<=V és A<=X<=B.
Feladat:Írj programot (INTER.PAS, INTER.C, INTER.CPP), amely kiszámítja, hogy legkevesebb hány intervallumot kell kiválasztani úgy, hogy minden intervallum legalább egy pontját tartalmazza egy kiválasztott intervallum!Bemenet:Az INTER.BE szöveges állomány első sorában az intervallumok N (0<N<=10000) száma van. A következő N sor mindegyike két egész számot tartalmaz egy szóközzel elválasztva; K V (1<=K<=V<=10000). K egy intervallum kezdőpontja, V pedig a végpontja.Kimenet:
Az INTER.KI szöveges állomány első sorába a kiválasztott intervallumok M számát kell írni! Az állomány további M sora rendre egy-egy kiválasztott intervallum kezdő és végpontját tartalmazza egy szóközzel elválasztva!Példa:
INTER.BE INTER.KI 6
1 3
2 4
1 4
3 5
3 6
4 7
1
3 6
Francia kártya - 3. feladat (45 pont) /tesztadatok/
Francia kártyával sokféle játékot játszhatunk. Az egyik játékban a játékosok az osztásnál kapott 14 lapból letehetnek kártyahármasokat: vagy egymást követő lapokat (pl. pikk 8 9 10), vagy pedig azonos értékű lapokat (pl. pikk 3 kor 3 treff 3).
A kártyák színe: pikk, treff, kor, karo; értéke pedig 2, 3, 4, 5, 6, 7, 8, 9, 10, bubi, dama, kiraly, asz lehet. (Az állományokban ékezet nélküli szavakat használunk!)
Feladat:
Készíts programot (FRANCIA.PAS, FRANCIA.C, FRANCIA.CPP), amely beolvassa egy játékos kártyáit, majd megadja a lehető legtöbb letehető kártyahármast!Bemenet:
A FRANCIA.BE szöveges állomány első sorában a treff, második sorában a pikk, harmadik sorában a káró, negyedik sorában pedig a kör lapok értékei szerepelnek. Az első mindegyik sorban az adott színű lapok K száma, majd ezt követi a K lap értéke, egy-egy szóközzel elválasztva.Kimenet:
A FRANCIA.KI állományba első sorába azt az S számot kell írni, ahány kártyahármast le lehet tenni. A következő S sor mindegyikében három kártya színe és értéke szerepeljen egy-egy szóközzel elválasztva.Példa:
FRANCIA.BE FRANCIA.KI 4 2 6 7 8
3 8 9 10
4 2 5 10 asz
3 9 10 dama
2
pikk 8 pikk 9 pikk 10
treff 6 treff 7 treff 8
vagy:
2
treff 6 treff 7 treff 8
pikk 10 karo 10 kor 10
Mozi - 4. feladat (30pont) /tesztadatok/
Egy moziban N egymás mellé helyezett szék mindegyikén egy-egy ember üldögél. Az N ember – az 1..N számokkal jelöljük őket – egymáshoz viszonyított helyzete N számmal írható le. Az embereket véletlenszerűen ültették le, de közülük néhányan megmondták, hogy ki mellett szeretnének ülni. Ennek eléréséhez helyet kell cserélniük. Egy lépésben két, szomszédos széken ülő ember helyet cserélhet.Feladat:
Készíts programot (MOZI.PAS, MOZI.C vagy MOZI.CPP), amely megadja a minimális lépésszámot, ami alatt egy kezdő elrendezésből a megadott igények szerinti kívánt végső elrendezés elérhető.Bemenet:A MOZI.BE szöveges állomány első sorában az emberek N száma (1<=N<=8) és az igények M száma (1<=M<=N) van egy szóközzel elválasztva. A következő M sor mindegyikében olyan két ember sorszáma van egy szóközzel elválasztva, akik egymás mellé szeretnének ülni. Az utolsó sorban pontosan N szám van, egy-egy szóközzel elválasztva, az emberek kezdeti elhelyezése.Kimenet:A MOZI.KI állományba egyetlen számot kell írni, a cserék minimális számát, amivel elérhető, hogy az igények mindegyikét kielégítsék. Ha nincs ilyen csereszám, akkor az állományba a -1 számot kell írni.Példa:
MOZI.BE MOZI.KI 8 3
1 2
1 3
7 8
1 3 5 7 2 4 6 85
Részhalmazok - 5. feladat (30pont) /tesztadatok/
Egy N létszámú osztályból K tagú csoportot szeretnénk kiválasztani. Az osztály tanulóit 0 és N-1 közötti számokkal azonosítjuk. Egy csoportot megadhatunk egy N bites számmal, ahol az i-edik helyiértéken 1 szerepel, ha az i-edik tanuló tagja a csoportnak, illetve 0, ha nem tagja.
Az A csoportot kisebbnek mondjuk a B csoportnál, ha az A-nak megfelelő N-bites szám kisebb a B-nek megfelelő N-bites számnál.
Feladat:
Írj programot (RESZ.PAS, RESZ.C, RESZ.CPP), amely megadja egy N létszámú osztály I-edik K tagú csoportját!Bemenet:A RESZ.BE állomány első sorában az osztály N létszáma (1<=N<=40) és a csoport K létszá¬ma (1<=K<=N), valamint az igényelt csoportok M száma (1<=M<=1000) van, egy-egy szóközzel elválasztva. A következő M sor mindegyike egyetlen I számot tartalmaz (1<=I), ahányadik K tagú csoportot meg kell adni az osztályból.Kimenet:A RESZ.KI szöveges állományba pontosan M sort kell írni, a bemenetben szereplő I számoknak megfelelő csoportokat. Mindegyik sorban pontosan K szám legyen növekvő sorrendben, a csoportban szereplő tanulók sorszámai egy-egy szóközzel elválasztva.Példa:
RESZ.BE RESZ.KI 5 3 4
1
2
10
5
0 1 2
0 1 3
2 3 4
0 1 4
Csoportok - 6. feladat (40pont) /tesztadatok/
Minden operációs rendszer egyik fő feladata, hogy az erőforrások hozzáférési jogosultságait kezelje. A jogosultságok kezelésének egyik módja a csoportok képzése. Minden erőforrás egy csoportot alkot, és csak azok a felhasználók használhatják az erőforrást, amelyek benne vannak az erőforrás csoportjában. Egy felhasználó több csoportban is benne lehet. Azt mondjuk, hogy az U felhasználó ekvivalens a V felhasználóval, ha bármely C csoportra U benne van a C csoportban, akkor V is benne van a C csoportban, és fordítva, ha V benne van a C csoportban, akkor U is benne van a C csoportban.Feladat:
Írj programot (CSOPORT.PAS, CSOPORT.C, CSOPORT.CPP), amely kiszámítja az ekvivalens felhasználók csoportjait!Bemenet:A CSOPORT.BE szöveges állomány első sorában az adatsorok K (0<K<=10000) száma van. A következő K sor mindegyike egy csoportba tartozó felhasználókat ad meg. A sorban az első szám C egy csoport azonosítója (1<=C<=30). A sorban a további számok azoknak a felhasználóknak az azonosítói, akik a C csoportba tartoznak. A sort a 0 szám zárja, ami nem felhasználói azonosító. A felhasználók azonosítói 1 és 10000 közötti egész számok.Kimenet:A CSOPORT.KI szöveges állomány első sora egy E egész számot tartalmazzon, amely a különböző ekvivalens felhasználók halmazainak száma. Az állomány további E sora rendre felhasználók egy-egy ekvivalens halmazát adja. Egy sorban legyenek az egymással ekvivalens felhasználók.Példa:
CSOPORT.BE CSOPORT.KI 3
30 1 5 7 3 0
20 1 4 2 6 3 0
11 2 3 7 1 5 0
4
1 3
2
4 6
5 7
Út - 7. feladat (50 pont) /tesztadatok/
Egy városban különböző terek vannak. Egyesek között már vannak utak, mások között pedig még nincsenek utak, építeni kellene közéjük. Vannak a terek között bizonyos területek, amelyeket az önkormányzat útnak jelölt ki. Amikor elkezdődött az útépítés, rájöttek, hogy nem lesz elég pénz az összes út felépítésére, a meglevők "visszaalakítása" pedig szintén borzasztóan költséges.
Feladat:
Írj programot (UT.PAS, UT.C, UT.CPP), amely meghatározza, hogy melyik utakat építse fel az önkormányzat, hogy a lehető legkevesebbe kerüljön, és úgy, hogy minden térről el lehessen jutni minden térre.Bemenet:Az UT.BE állomány első sorában a terek száma (0<N<=250), az összes lehetséges út száma (0<M<=10000), valamint a már felépített utak száma (0<=K<=M) van. A következő M sor mindegyikében három szám található: I, J, S, ahol az út az I. térről a J. térre vezet és S forintba kerül a megépítése (0<S<=10000). Az utolsó sorban K db egész szám van egy-egy szóközzel elválasztva, amelyek megadják, hogy a megadás sorrendjében hányadik út van már felépítve.Kimenet:Az UT.KI állomány első sorába a művelet összköltségét (a már megépített utak költsége nélkül), a második sorába pedig a megépítendő utak U számát kell írni. A harmadik sorba a megépítendő U darab út sorszámát kell írni, egy-egy szóközzel elválasztva.Példa:
UT.BE UT.KI 6 9 2
1 2 3
5 6 3
1 4 2
1 6 1
2 3 2
2 5 8
2 6 6
3 4 7
4 5 5
1 2
5
3
4 3 5
Poligon -8. feladat (50 pont) /tesztadatok/
Adott a síkon N pont az (x,y) koordinátáival. A pontokat a 1,…,N számokkal azonosítjuk. Egy a pontokat összekötő, zárt, nem-metsző poligon megadható a pontok azonosítóinak egy felsorolásával: a felsorolásban egymást követő pontokat kötjük össze egyenes szakaszokkal, továbbá, az utolsót az elsővel is összekötjük.Feladat:
Írj programot (POLIGON.PAS, POLIGON.C,POLIGON.CPP), amely összeköti pontpárokat egyenes szakaszokkal úgy, hogy olyan zárt poligont kapjunk, amelyben nincs metsző szakaszpár.Bemenet:
A POLIGON.BE szöveges állomány első sorában a pontok N (2<N<=5000) száma van. A további N sor mindegyike 2 darab egész számot tartalmaz, egy-egy pont x és y koordinátáit (-20000 <=x,y<= 20000). A pontok nem esnek egy egyenesre.Kimenet:A POLIGON.KI szöveges állományba egy sort kell kiírni, a pontsorszámoknak egy olyan sorozatát, amely minden pontot tartalmazó zárt, nem-metsző poligont ír le.Példa:
TULELO.BE TULELO.KI 5
2 0
1 4
0 2
3 2
2 4
3 2 5 4 1
Hálózat - 9. feladat (50 pont) /tesztadatok/
Minden számítógépes hálózat többnyire úgy épül fel, hogy csomópont-párokat kétirányú adatátvitelt biztosító közvetlen vonal kapcsol össze. A hálózat hibatűrő képessége függ a hálózat topológiájától. Egy jellemző tulajdonsága lehet a hálózatnak, hogy bármely csomópont benne van egy legalább három csomópontot tartalmazó körben.
Feladat:
Írj programot (HALOZAT.PAS, HALOZAT.C, HALOZAT.CPP), amely kiszámítja az alábbi két kérdésre adandó választ!Bemenet:
- Melyek azok a csomópontok, amelyek nincsenek benne egyetlen körben sem?
- Minimálisan hány új közvetlen vonallal kell bővíteni a hálózatot, hogy bármely csomópont benne legyen egy legalább három csomópontot tartalmazó körben? Meg is kell adni egy ilyen bővítést.
A HALOZAT.BE szöveges állomány első sorában két egész szám van: N M. A számok közül N (3<=N<=1000) a csomópontok száma, M (N-1<=M<=10000) pedig a csomópontokat összekötő közvetlen vonalak száma. A csomópontokat az 1,...,N számokkal azonosítjuk. A további M sorban egy X Y szám-pár van (egy szóközzel elválasztva), ami azt jelenti, hogy az X és az Y csomópontot közvetlen vonal köti össze (X<>Y). Minden csomópont-párt legfeljebb egy közvetlen vonal köt össze. A hálózatra teljesül, hogy bármely két csomópontja között létezik útvonal.Kimenet:A HALOZAT.KI szöveges állomány első sorába egy K egész számot kell írni, ami azon csomópontok száma, amelyek nincsenek benne egyetlen körben sem. A második sorba kell kiírni ezt a K darab csomópontot egy-egy szóközzel elválasztva, tetszőleges sorrendben. Ha K értéke 0, akkor a második sor üres sor legyen. A harmadik sorba egy L egész számot kell írni, ami a legkevesebb új közvetlen kapcsolatok száma, amelyekkel bővítve a hálózatot, minden pont benne lesz legalább egy körben. A következő L sor mindegyikébe egy-egy számpárt kell írni egy szóközzel elválasztva, minden szám-pár egy bővítendő közvetlen kapcsolat legyen.Példa:
HALOZAT.BE HALOZAT.KI 7 8
1 2
2 3
3 1
2 4
4 6
6 5
7 1
3 4
3
6 5 7
1
5 7
Játék - 10. feladat(50 pont) /tesztadatok/
Tekintsük azt az egyszemélyes játékot, amelyet egy olyan négyzetrácsos táblázaton játszanak, amelynek M sora és N oszlopa van. Bizonyos mezőkön gyöngyöket helyeznek el, és lehetnek olyan mezők, amelyekre nem lehet lépni, a többi mező üres. A játékszabály a következő:
A játék célja az, hogy a játékos a lehető legtöbb gyöngyöt gyűjtse a játékkal.
- A játékos a tábla (1, 1) koordinátájú bal felső sarkából indul. Ez a mező nem csapda és nem tartalmaz gyöngyöt.
- Bármely mezőre legfeljebb egyszer léphet.
- Csapda mezőre nem léphet.
- Egy lépésben szomszédos mezőre léphet egyet jobbra, lefelé vagy felfelé.
- Ha gyöngyöt tartalmazó mezőre lép, akkor az ott lévő valamennyi gyöngy az övé lesz.
- A játék akkor ér véget, ha a játékos nem tud lépni.
Feladat:
Írj programot (JATEK.PAS, JATEK.C, JATEK.CPP), amely kiszámítja, hogy adott kezdeti játékállásból mennyi az elérhető maximális pontszám, és megad egy olyan lépéssorozatot, amely a legtöbb pontot eredményezi!Bemenet:A JATEK.BE szöveges állomány első sorában négy egész szám van egy-egy szóközzel elválasztva: M N U V. Rendre M (1<=M<=100) a táblázat sorainak, N (1<=N<=100) az oszlopainak száma. A következő U sor mindegyikében egy X Y szám-pár van, ami egy csapdamező koordinátái, X (1<=X<=M) a sor index, Y (1<=Y<=N) pedig az oszlopindex. Ezt követi V darab sor, soronként három szám: X Y Z . X (1<=X<=M) és Y (1<=Y<=N) egy olyan mező koordinátái, ahol Z számú (0<Z<=100) gyöngy van a táblán. A tábla többi mezője üres. A táblán lévő számok összege nem nagyobb 30000-nél.Kimenet:
A JATEK.KI szöveges állomány első sorába az elérhető maximális pontszám értékét kell írni. A második sorba egy olyan lépéssorozatot kell írni, amely egy olyan szabályos játékot ad meg, amellyel a maximális pontszám elérhető. A lépéseket a J, L, F betűkkel kódoljuk; J azt jelenti, hogy az aktuális mezőről jobbra, L azt hogy lefelé, F pedig, hogy felfelé lép a játékos. A betűket válassza el pontosan egy szóköz!Példa:
JATEK.BE JATEK.KI 6 5 2 4
3 3
5 3
1 2 3
2 3 2
3 4 5
5 2 1
11
L L L L J F F F F J L J L J F F