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.
[53] Zippo2008-05-08 22:01:06

én még az vagyok, és pont ezt teszem:)

Előzmény: [52] Róbert Gida, 2008-05-08 21:13:24
[52] Róbert Gida2008-05-08 21:13:24

Hihetetlen, hogy milyen kevesen csinálják az S jelű példákat, mindössze nyolcan. Ha én most lennék gimnazista biztosan indulnék ebben a versenyben.

[51] Engedy Balázs2008-05-08 21:04:29

Sziasztok!

Az S.35. feladatban a példaként megadott bemenetre a helyes kimenet:

-1 1

Köszönjük az észrevételt, és elnézést kérünk a kellemetlenségekért.

[50] Zippo2008-05-08 17:39:05

a feladat nem egyenesről, hanem szakaszról beszél, de akkor is rossz, így van

[49] i2008-05-08 17:20:51

Ha az egyenesen nem szabad másik pontnak lennie, akkor viszont a példamegoldás is rossz.

[48] Zippo2008-05-08 16:59:00

na de akkor döntsék már el mit kell csinálni

Előzmény: [47] Róbert Gida, 2008-05-08 16:54:54
[47] Róbert Gida2008-05-08 16:54:54

Jogos. Lehet, hogy a feladatkitűző másra gondolt, mert viszont az igaz, hogy a szakasz által meghatározott egyenesen van egy másik nem kiválasztott pont, mert (-4,0);(-1,1);(2,2) egy egyenesre esnek, az y=(x+4)/3 egyenesen.

Előzmény: [46] Zippo, 2008-05-08 16:07:03
[46] Zippo2008-05-08 16:07:03

Lenne egy kérdésem az S35-ös feladat példájával kapcsolatban. A -1;1 pontból minden másik ponthoz húzható olyan szakasz, amin más pont nincs rajta. Akkor mért nem ez a megoldás?

[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

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