Fórum: Informatika kömal

A feladat szövege nem zárta ki a logo nyelv használatát. Ezek szerint a válasz igen.

Azért érezhetjük, hogy egy Neumann elvű programozási nyelven a megoldást elkészíteni komolyabb falat.

Siegler Gábor

A mostani S 41. feladatnál szabad az Imagine Logo-t használni? A válaszokat előre is köszönöm. Weisz Ágoston

Itt is fent van a kiírás: http://www.komal.hu/verseny/2008-09/kiiras.h.shtml

Acm-icpc versenyeken meg c/c++/javat lehet használni. Ez amúgy eléggé versenyfüggő, hogy hol mit lehet használni.

Sziasztok,

Most olvasom a KöMaL-ban hogy nem lehet C#-ot használni a programozási feladatok megoldásához, legalábbis így értelmezem, jól értelmezem? Csak azért kérdezem mert ugye már érettségin és OKTV-n is lehet használni, és sajnálnám ha itt nem mert a mostani feladatot már meg is terveztem C#-ban.

2 napja indult középiskolásoknak kiírt maratoni programozói verseny: http://hs.spoj.pl/ Középiskolásként indulókat akkor ismerik el, ha az iskola egyik tanára hitelesíti ezt a lapon.

Idősebbek versenyen kívül indulhatnak.

Nem sokan neveztek be S-re, mindössze nyolcan.

Az előbbi, azaz egy billentyű egyszeri megnyomására hajtson végre egyetlen szimulációs lépést, majd jelenítse meg a változást grafikusan.

Van egy kérdésem a az I187-es feladathoz: lépésenkénti megjelenítés azt jelenti, hogy egy billentyű megnyomására lép tovább a program, vagy azt hogy vár két lépés közt valamennyi időt?

Most találtam a Hírek rovatban: Bolyai Pályázat

Matematikai problémák megoldását várják, müködő programmal az élet nagy problémáira, Lovász László Bolyai és Wolf díjas matematikus téma javaslatai többek között:

Hogyan jutok el leggyorsabban vagy legolcsóbban az iskolába?

Hogyan lehet jó SUDOKU rejtvényt csinálni?

Hova helyezzem el a kertben a locsolófejeket?

Nem volna-e érdemes a büfében az egyik eladónak a pénzt kezelni, a másiknak az árut kiadni?

"A pályázat beküldésének határideje: 2008. szeptember 15."

Sudoku speciel példa volt az S jelűek között.

Most fejeztem be, és beadom, nyugi:)

Igen, tudok róla, de azért kösz a figyelmeztetést.

Egyelőre nemhivatalosan tudok csak válaszolni, de véleményem szerint emiatt nem lesz érvénytelenítve a feladat.

Emellett szeretném felhívni a figyelmeteket, hogy ebben a hónapban két S-jelű feladatra is lehet megoldást küldeni, az ehavi S.35. mellett újból kitűztük a korábban túlságosan nehéznek bizonyult S.31. egyszerűbb változatát.

Szerintem add be, ha már egyszer megoldod/megoldottad.

Ettől még pontozva lesznek a programok, nem nyílvánítják érvénytelenné a feladatot, ugye?

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

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.

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.

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

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

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

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.

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?

É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).

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).

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.