Középiskolai Matematikai és Fizikai Lapok
Informatika rovattal
Kiadja a MATFUND Alapítvány
Már regisztráltál?
Új vendég vagy?

Fórum: Informatika kömal

  [1]    [2]    [3]    [4]    [5]    [6]    [7]    [8]    [9]    [10]    [11]    [12]    [13]    [14]  

Szeretnél hozzászólni? Jelentkezz be.
[45] Róbert Gida2008-04-18 00:50:52

Érdekes, N=4-re ez már lassú, most próbáltam ki, egy perc alatt sem futott le egyetlen gridre, több, mint 1 millió cserét végrehajtva. Már az elején volt jobb választás is. Így teljesen elment a málnásba. Holott szvsz N=4-re még egy ember is meg tudja oldani.

Tényleg azt kell szimulálni, ahogy az ember lassan, de módszeresen megold egy ilyet. Azt is nézem, hogy minden sorra, oszlopra, kis négyzetre és minden betűre azt is megnézem, hogy hány helyre írhatom be oda a betűt. Ha ez adja a minimumot, akkor egy ilyet választok (és persze ezen lépek vissza a backtrackkel).

Előzmény: [44] Róbert Gida, 2008-03-29 21:44:56
[44] Róbert Gida2008-03-29 21:44:56

Valószínűleg megértenék az algoritmust: a javítás annyiban áll, hogy mindig azt az eddigi üres mezőt próbálom ki (írok be egy számot arra a mezőre), ahol a legkevesebb lehetőségem van, ezt úgy értem, hogy az adott sor, oszlop, illetve kis négyzet a lehető legtöbb számot blokkolja a mezőn, illetve, ha minden számot blokkolna, akkor visszalépek.

A leggyorsabb Sudoku megoldók egyéként ahogy emlékszem kb. 1000 feladványt oldanak meg 1 másodperc alatt 1 GHz-es gépen, régebben voltak is ilyen versenyek, hogy minél gyorsabbat írjanak.

Azért sem érdektelen a probléma, mivel ez 1 millió dolláros probléma: az nxnxnxn-es Sudoku (hagyományos: n=3) ugyanis NP teljes probléma, így egy polinomiális algoritmus rá 1 millió dollárt érne (Milleniumi probléma).

Előzmény: [43] Schmieder László, 2008-03-29 09:51:03
[43] Schmieder László2008-03-29 09:51:03

Az S.29. feladat egyik mintamegoldása valóban olyan programozási szerkezeteket és stílust tartalmazott, amit manapság nem szerencsés terjeszteni - ezt a megoldást levettük a honlapról.

A feladat visszalépéses kereséssel történő megoldását azért fogadtuk el 10 pontosnak, mert ez egy középiskolásoknak szóló tanulmányi verseny. A megoldást írók feltehetően azért nem foglalkoztak a hatékonyság kérdésével, mert az általuk írt programok egy "átlagos" sudoku feladatot másodpercek alatt megoldottak.

Annak végiggondolása, hogy melyik algoritmus kb. mennyi idő alatt végez egy bizonyos sudoku táblával - úgy gondoljuk - már egyetemi szint.

A hozzászólással tehát olyan szempontból egyetértek, hogy nem a visszalépéses keresés a "végső" megoldás, tehát a KöMaL S verseny megoldóinak is lesz majd mit tanulni egyetemen. De a hozzászólás azon részével (stílusával) nem értek egyet, hogy emiatt a versenyzők nem érdemelnék meg a maximális pontszámot.

Ha Róbert Gida tud olyan megoldást mutatni, amelyik egy "tetszőleges" sudoku táblával gyorsan végez, és az algoritmust egy informatika szakkörön elmeséli középiskolásoknak, akik azt meg is értik, akkor lehet szó arról, hogy többet várjunk el az S versenyzőktől.

Előzmény: [41] Róbert Gida, 2008-03-11 01:28:56
[42] Róbert Gida2008-03-18 21:37:02

I.180. backtrack, klasszikus alkalmazás ebben a 8 bástyás feladatban.

S.33. bfs, azaz szélességi kereséssel megtalálható a legrövidebb út ebben a feladatban, kb. 4*S*M állapot van (minden pont foka legfeljebb 4). A szélességi kereséssel optimális O(S*M) időben és tárban megoldható a feladat.

[41] Róbert Gida2008-03-11 01:28:56

A következő Sudoku feladatnak ti mennyi idő alatt találnátok meg legalább egy megoldását, és egy számítógépes program, és egy olyan program ami történetesen maximális 10 pontot kapott rá? Pontok hiányzó számot jelentenek. Ennek minden szabályos Sudoku megfejtés a megoldása (permutációval) és sor-oszlopcserékkel is még több, mint 5 milliárd megoldása van, mégsem találta meg az adott 10 pontos program egyetlen megoldását sem a gépem 1 óra alatt, de valószínűleg 1 év sem lenne neki elég. Az ok borzasztó egyszerű: gagyi a backtracking, ha valaki úgy csinálja, mint a beküldő, és sorrendben megy végig a mezőkőn. Én erre a programra 1 árva pontot nem adtam volna, már az elején is gyanús volt, hogyan lehet ilyen rövid a kód, az acm.uva-n kb 3-szor hosszabb kódot írtam a Sudoku-ra, persze nem ilyen gagyit. A Sudoku:

.........

.........

.........

.........

.........

.........

789......

456......

.23......

Az adott program az utolsó sorig elmegy, amikor felfedezi, hogy oda 1-es került, így a mátrix (1,1) helyébe beírt 1-es rossz lesz. Csak ugye ez backtracking, így a Nap is kihűl mire a program az (1,1) pozicióba visszalépteti. Sőt az utolsó előtti sorig terjedő összes olyan elhelyezkedést megvizsgálja, ami helyes és (1,1)-ben 1 van, ami rohadt sok eset. Hiszen ezek az elrendezések mind jók, csak az utolsó sor első egyese rontja el.

Előzmény: [40] Róbert Gida, 2008-03-10 23:56:54
[40] Róbert Gida2008-03-10 23:56:54

http://www.komal.hu/kep/abra/9e/1f/59/3c09e9df1cae1d41516331fe0/s29.c

Ez lenne egy feltett mintamegoldás egy versenyzőtől a Sudoku problémára. Ilyenek vannak benne:

"if(tabla[i][j] == 0) goto kezd;"

Rossz programozási gyakorlatra vall a goto utasítás

"else tabla[i][j] = temp - 48;"

Nem mindenhol egyértelmű az ascii karaktertábla, még a 128 alatti értékekre sem, így helyesebb azt írni:

else tabla[i][j] = temp - '0';

Az exit()-hez az stdlib.h include-olása nélkül warningot ad a fordító (nálam).

Továbbá, ha ezt egy online judge-nak próbálta volna elküldeni, akkor biztos rossz válasszal küldte volna vissza, mert ma már mindegyik megköveteli, hogy az int main-ből return 0-val térjen vissza.

Más hiba nem volt benne.

[39] Tibixe2008-02-05 20:22:11

Nem a pontozás részére gondoltam, hanem arra, hogy ha egy C-vel éppen ismerkedő látogató megnézi, még azt hiheti, hogy ezt lehet így is csinálni.

[38] Engedy Balázs2008-02-03 18:41:58

Kedves Tibixe!

A programozásnak (szoftverfejlesztésnek) van jó néhány olyan aspektusa, melyek a pontversenyben (és a legtöbb ilyen témájú versenyben) egyáltalán nem, vagy csak kis szerephez jutnak. Úgy, ahogy dokumentáció címén általában megelégszünk egy pársoros leírással, nem célunk túlságosan belemélyedni az implementációs részletekbe sem.

A be- és kivitellel kapcsolatban mindössze annyit várunk el, hogy a program képes legyen a feladatban specifikált bemenetet beolvasni, a kimenetet pedig a kért formátumban kiírni.

Egyes feladatok esetén a bemeneti specifikáció nem teljes, itt ennek konkretizálása is a versenyzők feladata, a verseny része. A józanész határain belül minden megoldást el szoktunk fogadni.

A józanész határa pedig a feladat szövegéből derül ki, természetesen feladatról feladatra más. Így elképzelhető, hogy ha valaki a bemenetet egy fix hosszú tömbbe olvassa be, azt egyik feladatnál pontlevonással jutalmazzuk, míg egy másik feladatnál programját mintamegoldásként közöljük.

Például az I. 163. feladatnál a fájlban lévő összes kódszó egyszerre történő beolvasása 2 pont veszteséget jelentett, ellenben az I. 170.-nél úgy gondoljuk, hogy a felhasználótól bekért egyetlen szóról azért nyugodtan feltehetjük, hogy 100 karakternél rövidebb lesz.

Az dinamikus szélességű beolvasás valóban jobb, de bonyolultabb is, így ésszerű esetben a fix tömb használatát is elfogadjuk, még annak ellenére is, hogy egy éles programnál komoly biztonsági kockázatot jelenthet. Az ilyen jellegű ismeretek számonkérése ennek a pontversenynek nem célja - ahogy a legtöbb ilyen témájú versenynek sem.

Üdv, E.B.

Előzmény: [37] Tibixe, 2008-01-30 14:44:09
[37] Tibixe2008-01-30 14:44:09

http://www.komal.hu/kep/abra/a0/b3/5a/7b2fb72d775efbb0583da1532/i170.cpp

Ebben a mintamegoldásban (!) csak nekem szúrja a szememet, hogy rögzített méretű bufferbe olvas be mindenféle hosszúságellenőrzés nélkül?

Én meg itt szórakoztam a reallockal...

[35] Tibixe2007-12-01 18:35:27

Van valami részletes információ az informatika pontverseny szabályairól?

A versenykiírást meg a tudnivalókat megnéztem, de ezeket nem tudtam meg belőle, főleg a C (és C++) nyelvet illetően:

1) Milyen fordítókkal, milyen operációs rendszer alatt futtatják?

2) Milyen header fájlokat használhatok? Csak szabványban szereplőket? Melyik szabvány? Vagy ami a fordítóval jön? Például a Linux rendszereken alapból include pathban van a crypt.h, a glibc tartalmazza, szóval akkor azt felhasználhatnám?

[34] rlblaster2007-02-04 12:49:57

Uff, ezt elnéztem. Elnézést, hogy nem olvastam vissza. Lehet törölni az utolsó három (az összes) hozzászólásomat. :)

Előzmény: [33] rlblaster, 2007-02-04 12:48:21
[33] rlblaster2007-02-04 12:48:21

Lehet sokat pofázok, de a S23 példakimenetének utolsó sorában nincs véletlenül hiba?

Ez van ott: --- szabad 675 358-377 161-177 378-382 1046-1078

Szerintem pedig: --- szabad 675 358-377 161-177 378-382 1146-1778

Magyarázat 1:

Ha összeadom a területeket a példakimenet szerint, nem 675 fog kijönni a szabad területnek.

Magyarázat 2:

Az egész példakimenet:

hoember 175 1099-1145 411-538

idojaras.txt 160 1-160

mese.doc 208 383-410 178-357

mikulas.jpg 560 539-1098

--- szabad 675 358-377 161-177 378-382 1046-1078

Most vegyük pl. a 1050-es szektort. Az most a mikulas.jpg-hez tartozik vagy a szabad területhez? (hasonlóan vannak átfedések a hoember és a szabad terület között)

Köszönöm.

Előzmény: [32] rlblaster, 2007-01-31 06:44:27
[32] rlblaster2007-01-31 06:44:27

Valaki meg tudná mondani, mert én nem tudtam kiolvasni a feladatból, hogy hány karakter lehet a fájlnév maximális mérete? (netán 8+1+3?)

Köszönöm.

Előzmény: [31] ocsi01, 2007-01-28 22:42:18
[31] ocsi012007-01-28 22:42:18

Az S.23. feladat szerintem el van írva, ugyanis a példára a kimenet utolsó sorának utolsó két száma nem 1046-1078 ahogy az újságban van, hanem 1146-1778 ( gondoljatok bele, az utolsó üres hely mérete 633, már itt hibázik a dolog)

[30] Fálesz Mihály2007-01-23 20:16:11

Szerintem aki Linux párti (mint én is), az maradjon a GCC-nél és tanuljon meg Xwin grafikát programozni. (Btw a rajzolás nem nagy ügy, de mire ki tudsz nyitni egy ablakot... :-) )

Az egyáltalán nem baj, ha egy feladat megoldásához új dolgoknak kell utánajárnod. Amit most megtanulsz, az később is nagyon hasznos lesz.

[29] Schmieder László2007-01-20 19:34:56

A grafika valóban kérdés - bár valójában csak Linux/GCC fejlesztés mellett. Mert hogy Win alatt a Borland vagy a Microsoft C++ fejlesztőkben könnyen elérhető a grafika (majdnem olyan egyszerű, mint a régi jó graphics.h).

Ha valaki kitart a GCC mellett Lin vagy Win alatt, akkor nincs ötletem. Az természetesen túlzás, hogy valaki csak emiatt OpenGL-t tanuljon (gondolom én, aki nem is ismerem).

Szóval azt gondolnám, hogy a feladat kedvéért egy Borland 30 napos próbaverziót, vagy egy Microsoft otthoni változatot érdemes letölteni, és azzal megismerkedni (a honlapjukon megtalálhatók).

Előzmény: [28] Szász Bence, 2007-01-13 01:43:10
[28] Szász Bence2007-01-13 01:43:10

Bocsánat kihagytam. A fő kérdés az lenne, hogyan lehet grafikázni egy KöMaL feladat megoldásakor (tehát milyen könyvtárat kell/lehet használni).

Előzmény: [27] Szász Bence, 2007-01-13 01:36:02
[27] Szász Bence2007-01-13 01:36:02

Sziasztok! Kicsit bután érzem magam, de azért felteszem a kérdést :) Az a lénye, hogy grafikázni nem igen grafikáztam még C++ nyelven, csak valamikor nagyon régen a graphics.h segítségével. Ma viszont azzal szembesültem, hogy ez már nincs benne a GCC-ben és mindengol "őskövület"-nek titulálják. Komolyan OpenGL-el kéne rajzolgatnom? Mivel lehetne pixeleket/vonalakat rajzolgatni egyszerűen? A válaszokat előre is köszönöm.

[26] Róbert Gida2006-12-02 00:41:39

Először megnyitod a file-t, megszámolod hány oldal stb. van benne, ekkor a végén már mindent tudni fogsz, hogy mennyi memória kell, foglalsz memóriát malloc-kal és megint megnyitod a file-t, feltöltöd adatokkal a mtárixot/vektort.

Jó, persze lehet végtelen ciklus is az inputok között, bár ilyenkor nem áll le a progi, így nem értem, hogy miért lenne a tesztek között ilyen. De persze utolsó tesztnek ilyet berakhatnak, hogy megnézzk, hogy olyan 1 perc alatt tényleg nem áll le.

Előzmény: [25] ocsi01, 2006-12-01 23:31:05
[25] ocsi012006-12-01 23:31:05

Hát... a malloc az rendben, bár a kétszeres filescannelést nem értem, hogy érted, de nem is az adatok feldolgozásával van gondom... csak mert furcsa dolog úgy programt írni, hogy nem tudom hány oldallal számoljak... mert ez esetleg nagyban befolyásolhatja a megoldásmenetet!!!

Végtelenciklusra sok eset van, de miért kéne bármit is feltételeznem az inputról ami nincs leírva?

[24] Róbert Gida2006-11-30 23:15:06

Persze ez c++ban van.

Előzmény: [23] Róbert Gida, 2006-11-30 23:12:02
[23] Róbert Gida2006-11-30 23:12:02

Több mód is van rá, remélem nem árulok el titkokat: próbálkozhatsz malloc/realloc párossal, dinamikus helyfoglalás, csak malloc-kal is megoldható, de ehhez kétszer dolgozod fel a txt állományt, illetve, ha gyorsabban szeretnéd, csak egyszer feldolgozva, de ahhoz realloc is kell.

Szerintem sokszög belső pontjából nem indítják, persze még így is ciklizálhat szerintem, de nyilván nem szerepel ilyen az inputok között.

Előzmény: [22] ocsi01, 2006-11-30 22:57:43
[22] ocsi012006-11-30 22:57:43

A mostani S.21. el van bajom. Engem nagyon zavar az, hogy nem tudom maximum hány csúcsot kell tudnom kezelni!!! Mert ez nincs megadva a feladatban úgy mint máskor! A másik roblémám, hogy a feladat azt kéri, addig fusson a program amíg a képzeletbeli golyó el nem éri a terepasztal szélét. De kérdem én, hogy mi van ha soha nem éri el? ( zárt síkodomon belülről indul, nem tud kijönni!!)

[21] kdano2006-10-12 18:10:26

Nem igazán értem, hogy mi számít "itt"-nek. Mert az olimpiai válogatón egyáltalán nem erről szól. Ha nem a megfelelő fájlba írod, automatikusan 0 pontot ad a javítóprogram. Ha nem megfelelő a fájlnév (ahogy azt 2005-ben megjártam :P), akkor le se tudja futtatni, úgy is nulla pont.

Ezeken kívül a feladatok értékelése ugyanúgy megy, mint a CEOI-n (ha jól tudom az IOI-t most babrálták át..), azaz lefuttatják a tíz tesztadatra, s minden egyes teszt 3-4-5 pontot ér. Ezeket típushibák, időkorlát (általában 1 mp) betartásának ellenőrzésére élezik ki, így a tesztek egyszerre ellenőrzik az algoritmus helyességét, a gyorsaságát és hogy precízen van-e lekódolva. Ilyenből van 7 forduló, összesen 13 feladat. Ezzel elég jól kiszelektálódnak azok, akik túl jól teljesítenek, s így a fordulóról fordulóra való továbbjutás végén az olimpiá(k)ra is kijutnak.

Előzmény: [17] Kós Géza, 2006-10-04 09:16:33
[17] Kós Géza2006-10-04 09:16:33

A precizitás itt arról szól, hogy követed-e a specifikációt.

Pl. ha a feladat szerint a bemenő adatokat az stdin-ről kell olvasni, akkor nem raksz ki a képernyő közepére egy ablakocskát, hogy abba írják be. (Mint az már annyiszor megtörtént a KöMaL versenyeiben is.)

Előzmény: [16] Ozsy, 2006-10-03 18:07:05

  [1]    [2]    [3]    [4]    [5]    [6]    [7]    [8]    [9]    [10]    [11]    [12]    [13]    [14]