Cím:	Egy-egy feladat a 2000/2001-es Nemes Tihamér Országos Középiskolai Számítástechnikai Verseny döntőjének feladataiból
Szerző(k):	Zsakó László
Füzet:	2001/november, 485 - 487. oldal	PDF  |  MathML
Témakör(ök):	Nemes Tihamér

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.   I. kategória. Egyesek nagyon szerencsétlen napnak tartják, ha a pénteki nap valamelyik hónap 13. napjára esik. Készíts programot (PENTEK:PAS vagy PENTEK.BAS vagy PENTEK.C), amely egy adott évben megmondja, hogy mely hónapok 13. napja esik péntekre! A program első lépésként olvassa be, hogy melyik évről van szó, illetve, hogy az év első napja milyen napra esik (HÉTFŐ vagy KEDD vagy $\text{...}$ vagy VASÁRNAP). Ezután írja ki azon hónapok nevét, amelyek 13. napja pénteken van! Figyelj a szökőévekre! Példa: Bemenet: 2001 HÉTFŐ Kimenet: ÁPRILIS JÚLIUS   II. kategória. Magyarország folyóiról feljegyeztük, hogy milyen másik folyóba folynak bele (pl. a Rába a Dunába, a Sajó a Tiszába, a Hernád a Sajóba, $\text{...}$). Minden folyó legfeljebb 1 másikba folyhat bele, de lehet hogy egybe sem (pl. Duna, de a Zala sem folyóba folyik bele). Csónaktúrákat szeretnénk szervezni, de a könnyebbség kedvéért csak úgy, hogy minden folyón a folyás irányában haladjunk. Készíts programot (TURA.PAS vagy TURA.C), amely megadja, hogy * A. két különböző folyón indult túra hol találkozhat; * B. az első túrát bevárhat-e egy második úgy, hogy nem indul el addig, amíg az első oda nem ér, és ha igen, akkor az elsőnek hány folyón kell addig haladnia (ha ugyanazon a folyón indulnak, akkor 1, ha az egyik folyó éppen belefolyik a másikba, akkor 2, $\text{...}$). A TURA.BE állomány első sorában az az $N$ egész szám van, ahány folyóról tudjuk, hogy melyikbe folyik bele ($1\le N\le 1000$). A következő $2*N$ sor mindegyike egy-egy folyó nevét tartalmazza, a második, negyedik, $\text{...}$ sor azt hogy melyik folyó, a harmadik, ötödik, $\text{...}$ pedig azt, hogy melyikbe folyik bele. Az utolsó két sorban egy-egy folyó neve van, az első és a második túra kezdete. (A folyónevek legfeljebb 20 betűsek.) A TURA.KI állomány első sorába annak a folyónak a nevét kell írni, ahol a két túra először találkozhat, a sor legyen üres, ha a két túra Magyarországon nem találkozhat (pl. ha az első a Dunán, a második pedig a Tiszán indult). A második sorba azt az egész számot kell írni, ahány folyón az első túrának át kell haladnia, hogy a második túra kezdetéhez érjen. Ha a második nem tudja bevárni az elsőt, akkor ez a szám 0 legyen!   III. kategória. A porcelángyár égetőkemencéjéhez futószalagon érkeznek az égetésre váró tárgyak. Minden tárgynak ismert a súlya és a kiégetéséhez minimálisan szükséges idő. Az égetésre váró tárgyakat az érkezésük sorrendjében kell kiégetni. Egyszerre több tárgyat is rakhatunk a kemencébe, az összsúlyuk azonban nem haladhatja meg a kemence kapacitását. Az égetési idő egy menetben mindig a kemencébe rakott tárgyak minimális égetési idejének a maximuma kell legyen. Készíts olyan programot (KEMENCE.PAS, KEMENCE.C), amely kiszámítja, hogy legkevesebb mennyi idő kell az összes tárgy kiégetéséhez, továbbá megadja azt is, hogy ezen idő eléréséhez mely tárgyakat kell egy-egy menetben a kemencében együtt égetni. A KEMENCE.BE állomány első sora két egész számot tartalmaz; a tárgyak $N$ ($1\le N\le 10000$) számát és a kemence $K$ ($1\le K\le 1000$) kapacitását. A következő $N$ sor mindegyike két egész számot tartalmaz; egy tárgy $S$ ($1\le S\le 1000$) súlyát és $E$ ($1\le E\le 100$) minimális égetési idejét. A KEMENCE.KI állomány első sorába az összes tárgy kiégetéséhez minimálisan szükséges időt kell írni. A következő sorok mindegyikébe két egész számot, $I$-t és $J$-t kell írni egy szóközzel elválasztva, $I$ az első, $J$ pedig az utolsó tárgy sorszáma, amelyek egyszerre kerülnek a kemencébe. $\star$ A Nemes Tihamér OKSzTV-n az 2000/2001-es tanévben az első fordulóban 5033 tanuló vett részt 367 iskolából, közülük 683-an határon túli magyarok. A második, regionális fordulót az ország 30 városában rendeztük, amelyen 759 tanuló vett részt. A harmadik fordulót, az országos döntőt Budapesten rendeztük két helyszínen, amelyen 193 tanuló vett részt. A II‐III. kategória 10‐11. osztályosai közül a legjobb 14 számára olimpiai válogatóversenyt rendeztünk, amelynek alapján kiválasztottuk az idei Közép-Európai Informatikai Diákolimpián, Zalaegerszegen résztvevő magyar csapat tagjait. 1. csapat: Csóka Endre (Debrecen, Fazekas Mihály Gimnázium); Hargitai Gábor (Ócsa, Bolyai János Gimnázium); Pszota Zsolt (Vác, Boronkay György Szki); Pallos Péter (Fazekas Mihály Fővárosi Gyakorló Gimnázium). 2. csapat: Borosán Péter (Zalaegerszeg, Zrínyi Miklós Gimnázium); Szakál Zoltán (Keszthely, Vajda János Gimnázium); Novák Zoltán (Zalaegerszeg, Zrínyi Miklós Gimnázium); Ekler Márton (Zalaegerszeg, Zrínyi Miklós Gimnázium).   Ízelítő a válogatóverseny feladataiból:. Az elmúlt 200 évben Európa 2 országában feljegyezték, hogy a választások után milyen párt (baloldali vagy jobboldali) adta a miniszterelnököt. Olyan időszakokat keresünk, amikor az összes országban ugyanolyan jellegű párt volt hatalmon. A győztes adja a miniszterelnököt a választás napjától a következő választást megelőző napig. Készíts programot (PARTOK.PAS vagy PARTOK.C), amely megadja azokat az időintervallumokat a legelső választás és az aktuális idő között, amikor mindegyik országban azonos jellegű párt volt hatalmon! A PARTOK.BE állomány első sorában az aktuális dátum szerepel (év, hónap, nap, egy-egy szóközzel elválasztva. A második sorban az első országbeli választások száma van ($1\le N\le 200$), a következő $N$ sor pedig egy-egy választás eredményét tartalmazza. Utána következik a második országbeli választások száma ($1\le M\le 200$), majd $M$ sorban újra egy-egy választás eredménye. A választási eredmény első karaktere a $B$ vagy a $J$ betű, attól függően, hogy baloldali, vagy pedig jobboldali párt adta a miniszterelnököt, ezt követi három egész szám, egymástól és az első betűtől egy-egy szóközzel elválasztva: a választás éve, hónapja és napja. A PARTOK.KI állomány első sorába azon időintervallumok $K$ számát kell írni, amikor mindegyik országban azonos jellegű párt adta a miniszterelnököt, a következő $K$ sorba pedig növekvő időrendben az egyes intervallumokat. Minden intervallum 6 egész számot tartalmaz egymástól egy-egy szóközzel elválasztva: az időszak elejét (év, hónap, nap) és végét (év, hónap, nap). Ha két egymáshoz illeszkedő intervallumban ugyanaz a párt adta mindkét országban a miniszterelnököt, akkor az egy (!) intervallumnak számít! $\star$ A Nemes Tihamér OKSzTV III. kategóriájának 1‐22. helyezettje számára olimpiai válogatóversenyt rendeztünk, amelynek alapján az idei Nemzetközi Informatikai Diákolimpián, Tamperében (Finnország) az alábbi tanulók indultak: Novák Ádám (Eger, Neumann János KgSzKI és Gimnázium); Ritter Ádám (Fazekas Mihály Fővárosi Gyakorló Gimnázium); Hargitai Gábor (Ócsa, Bolyai János Gimnázium); Földényi Tamás (Fazekas Mihály Fővárosi Gyakorló Gimnázium).   Ízelítő a válogatóverseny feladataiból:. A ProtoNet számítógépes hálózat úgy alakult ki, hogy eredetileg különálló hálózatokat összekapcsoltak. Mindegyik hálózat saját, egyedi protokollt használt. Az egyes részhálózatok az összekapcsolás után is a régi módon, azaz saját protokollt használva működnek. A hálózati hardvert azonban felszerelték olyan szoftverrel, amely képes bármelyik két protokoll közötti váltásra. A teljes hálózat most úgy működik, hogy ha egy $X$ csomópontból közvetlenül egy $Y$ csomópontba kell csomagot küldeni, és $X$, valamint $Y$ nem azonos részhálózathoz tartozik, akkor előbb protokollváltást kell végrehajtani. A hálózati működést optimalizálni szeretnék. Ez azt jelenti, hogy olyan szoftvert kell készíteni, amely meghatározza, hogy ha egy adott $A$ csomópontból egy másik $B$ csomópontba kell küldeni a csomagot, akkor milyen útvonalat kell választani ahhoz, hogy a protokollváltások száma minimális legyen. Készíts programot (PROTO.PAS vagy PROTO.C), amely * $•$Kiszámítja, hogy az $A$ csomópontból a $B$ csomópontba küldendő csomag esetén legkevesebb hány protokollváltás szükséges! * $•$Megad egy olyan $A$-ból $B$-be vezető útvonalat, amelyen a protokollváltás a lehető legkevesebb! Eredményeink a 2001. évi Nemzetközi Informatikai Diákolimpián   2001. július 14-e és 21-e között rendezték meg a 2001. évi Nemzetközi Informatikai Diákolimpiát (IOI) Finnországban, Tamperében. A versenyen 72 ország 272 versenyzője vett részt. Versenyzőink közül  Ritter Ádám (Fazekas M. Főv. Gyak. Gimn.),  Novák Ádám (Eger, Neumann János Szki.)  Földényi Tamás (Fazekas M. Főv. Gyak. Gimn.) ezüstérmet szerzett,  Hargitai Gábor (Ócsa, Bolyai János Gimn.) 5 ponttal maradt le a bronzéremről. Ezek alapján csapatunk a nemhivatalos versenyben a 15. helyen végzett. A verseny az elmúlt éveknek megfelelően szakmailag erős, reális volt. Zsakó László