Oktatási Hivatal A 2015/2016 tanévi Országos Középiskolai Tanulmányi Verseny második forduló javítási-értékelési útmutató INFORMATIKA II. (programozás) kategória 1. feladat: Épület (25 pont) Egy N szintes épület szintjeit fehér (F), piros (P) és zöld (Z) színnel festhetjük ki. Fehér emeletet csak piros emelet követhet, zöld emeletet pedig nem követhet piros! Készíts programot (epulet.pas,…), amely megadja, hogy az épület hányféleképpen színezhető ki! Mivel az eredmény nagyon nagy is lehet, ezért azt MOD 20160109 kell kiírni! A standard bemenet első sorában az emeletek száma van (1≤N≤1000). A standard kimenet egyetlen sorába a színezések lehetséges legnagyobb számát kell kiírni MOD 20160109! Példa: bemenet kimenet 3 12 Magyarázat: FPF, FPP, FPZ, PFP, PPF, PPP, PPZ, PZF, PZZ, ZFP, ZZF, ZZZ Korlátok: Időlimit: 0.5 mp Memórialimit: 32MiB A tesztek 50%-ában N≤20. Értékelés: 1. N=1 3 2. N=2 6 3. N=5 48
2 pont 2 pont 2 pont
4. N=10 1536 5. N=20 1572864 6. N=50 31531196 7. N=100 48843151 8. N=200 51264603 9. N=500 31057915 10. N=1000 48147051
2 pont 2 pont 3 pont 3 pont 3 pont 3 pont 3 pont
OKTV 2015/2016
1. oldal
2. forduló
Informatika II. kategória 2. feladat: Ádám-Éva (35 pont) Ádám és Éva különböző városokban lakik és találkozni szeretnének egymással. Vannak olyan városok, ahova Ádám nem léphet be, illetve olyanok, amelyek Éva számára tiltottak. Bármely két város közötti közvetlen út megtétele ugyanannyi időbe kerül. Készíts programot (adameva.pas, …), amely megadja, hogy mely város lesz az, amelyben a leghamarabb találkozhatnak! A standard bemenet első sorában a városok száma (1≤N≤1000), a közöttük levő közvetlen utak száma (1≤M≤100 000), valamint Ádám és Éva városának sorszáma (1≤A,E≤N) van. A következő M sor soronként egy-egy közvetlen út két végpontjának sorszámát (1≤Ui≠Vi≤N) tartalmazza. Az utolsó előtti sorban Ádám tiltott városai száma (0≤TA
kimenet 3
2 1
5
4
3
Korlátok: Időlimit: 0.5 mp Memórialimit: 32MiB A tesztek 60%-ában N≤100. Értékelés: 1. Szomszédos Ádám és Éva 2. Egy közbülső város van
3 pont 3 pont
3. Az egy közbülső város tiltott mindkettőnek 4. Az egy közbülső város csak az egyiknek tiltott 5. Nincs megoldás 6. Mindkettőnek egy másiknak tiltott városon kell átmenni 7. Véletlen közepes teszt 8. Véletlen közepes teszt 9. Véletlen nagy teszt 10. Véletlen nagy teszt
3 pont 3 pont 3 pont 3 pont 3 pont 4 pont 5 pont 5 pont
OKTV 2015/2016
2. oldal
2. forduló
Informatika II. kategória 3. feladat: Háromszög (25 pont) Adott N pont a síkon. Készíts programot (haromszog.pas,…), amely megadja a ponthalmaz három olyan pontját, amelyek olyan háromszöget alkotnak, hogy a ponthalmaz egyetlen más pontja sem esik a háromszögbe, vagy oldalára! A standard bemenet első sorában a pontok száma van (3N10 000), a következő N sorban pedig az egyes pontok koordinátái (-10 000xi,yi10 000). A bemenetre teljesül, hogy a pontok nem esnek egy egyenesre. A standard kimenet első sorába annak a három pontnak a sorszámát kell írni, amelyek olyan háromszöget alkotnak, hogy a ponthalmaz egyetlen más pontja sem esik ebbe a háromszögbe, vagy oldalára! A három pontot órajárással ellentétes körüljárás szerint kell megadni! Több megoldás esetén bármelyik megadható. 3
Példa:
1
bemenet
kimenet
6 5 7 7 4 6 2
6 5 2
4
2
6
6 5 7 5 2 3
5
Korlátok: Időlimit: 0.5 mp Memórialimit: 32MiB A tesztek 60%-ában N≤100. Értékelés: 1. N=2 2. N=4 3. Egyenesen kívül egy pont 4. A pontok két vízszintes egyenesen 5. A pontok két függőleges egyenesen 6. Véletlen kicsi bemenet
2 pont 2 pont 2 pont 2 pont 2 pont 3 pont
7. Véletlen közepes teszt (N=1000) 8. Véletlen közepes teszt (N=1000) 9. Véletlen nagy teszt (N=10 000) 10. Véletlen nagy teszt (N=10 000)
3 pont 3 pont 3 pont 3 pont
OKTV 2015/2016
3. oldal
2. forduló
Informatika II. kategória 4. feladat: Építkezés (30 pont) Egy nagyszabású építkezés terve N különböző munka elvégzését tartalmazza. Minden munkát pontosan egy nap alatt lehet elvégezni. A terv tartalmaz több megelőzési előírást, amely szerint egy U munkát előbb kell elvégezni, mint egy másik adott V munkát. A munkákat úgy kell ütemezni, hogy minden megelőzési előírás teljesüljön! Készíts programot (epitkezes.pas,…), amely kiszámítja, hogy legkevesebb hány nap telik el két adott A és B munka elvégzése között, ha minden megelőzési előírást betartanak! A standard bemenet első sora a munkák számát (1N10 000) és a megelőzési előírások számát (1M100 000) tartalmazza. A második sor a kitüntetett A és B munka sorszámát tartalmazza (1A≠BN). A további M sor mindegyike egy megelőzési előírást tartalmaz (1Ui≠ ViN), ami azt jelenti, hogy az Ui, munkát előbb kell elvégezni, mint a Vi munkát. Feltehető, hogy a munkák elvégezhetők olyan sorrendben, amely szerint minden megelőzési előírás teljesül. Az is feltehető, hogy az A munkát biztosan előbb kell elvégezni, mint a B munkát. A standard kimenet első sorába egy egész számot kell írni, a legkevesebb napok számát, amely az A és a B munka elvégzése között eltelik, ha minden megelőzési előírást betartanak! Példa: bemenet
kimenet
8 3 1 1 2 3 3 4 4 5 7 6 5
3
11 6 2 3 3 4 7 7 5 6 6 8 8
7 1
3 2
4
5
6 8
Korlátok: Időlimit: 0.5 mp Memórialimit: 32MiB A tesztek 50%-ában N≤100. Értékelés: 1. Egy lánc 2. A fa 3. Inverz fa 4. Több fa 5. Általános körmentes gráf 6. Általános est, N=1000, M=2000 7. Véletlen kis bemenet 8. Véletlen közepes bemenet
2 pont 2 pont 2 pont 2 pont 3 pont 3 pont 4 pont 4 pont
9. Véletlen nagy bemenet 10. Véletlen nagy bemenet
4 pont 4 pont
OKTV 2015/2016
4. oldal
2. forduló
Informatika II. kategória 5. feladat: Ütemezés (35 pont) Egy nagyszabású rendezvényen sok eseményt szeretnének megrendezni. Több esemény szervezője jelentkezett, megadva azt, hogy az adott esemény hány napig tartana (folyamatosan), továbbá, hogy milyen határidőig tudnák vállalni az esemény megtartását. Írj programot (utemez.pas,…), amely kiszámítja, hogy legjobb esetben hány eseményt lehet megtartani, és meg is ad egy ütemezést! A standard bemenet első sorában a rendezvény napjainak száma (2N10 000) és a jelentkezett események száma (1M100 000) van. A további M sor mindegyike egy esemény V időtartamát és H határidejét tartalmazza (1VHN). Az események határidő szerint növekvően, azon belül időtartam szerint növekvő sorrendben vannak. A standard kimenet első sorába a legtöbb megtartható esemény K számát kell írni! A további K sor mindegyike egy esemény ütemezését tartalmazza! Az eső szám az esemény sorszáma, a második szám pedig annak a napnak a sorszáma legyen, amelyik napon kezdődik az esemény megtartása! Ha egy esemény beosztás szerinti kezdő napja E és V napig tart, a határideje pedig H, akkor az E+V-1H egyenlőtlenségnek teljesülni kell! A beosztás tetszőleges sorrendben kiírható, több megoldás esetén bármelyik megadható. Példa: bemenet
kimenet
10 7 2 3 4 5 2 7 2 8 3 8 1 10 4 10
4 1 3 4 6
1 3 5 7
1
1
3
3
4
4
6
Korlátok: Időlimit: 0.5 mp Memórialimit: 32MiB A tesztek 60%-ában N≤100. Értékelés: 1.Csak egy beosztható 2. Mind beosztható
1+0 pont 1+1 pont
3 A kicsik beoszthatók 4.Határidő szerint növekvően kiválasztható 5. Véletlen kis bemenet 6. Véletlen kis bemenet 7. Véletlen közepes bemenet 8. Véletlen közepes bemenet 9. Véletlen nagy bemenet 10. Véletlen nagy bemenet
1+2 pont 1+2 pont 1+2 pont 2+2 pont 2+2 pont 2+3 pont 2+3 pont 2+3 pont
Elérhető összpontszám: 150 pont + 50 pont az 1. fordulóból
OKTV 2015/2016
5. oldal
2. forduló
