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.
[195] Gema Barnabás2012-01-02 21:05:40

Nem, ezt úgy értem, hogy bizonyos javascript fájlokhoz, amik a grafikonhoz rajzolásához szükségesek, csak az interneten keresztül lehet hozzáférni.

[194] jonas2012-01-02 13:11:12

Csak online működő azt jelenti, hogy a beküldési határidőkor beküldsz egy webcímet, és utólag odarakod a megoldást?

Előzmény: [193] Gema Barnabás, 2012-01-02 11:56:38
[193] Gema Barnabás2012-01-02 11:56:38

Az i282-es feladatban csak online működő megoldások is elfogadhatók?

[192] Antal János Benjamin2011-12-13 16:28:51

akkor ugye az elfogadható, ha az tgz kiterjesztést átírtam gz-re?

Előzmény: [189] Schmieder László, 2011-12-13 09:37:31
[191] Róbert Gida2011-12-13 15:57:52

Igen, valóban van O(N+Q)-as algoritmus is: http://en.wikipedia.org/wiki/Lowest_common_ancestor

Előzmény: [190] Adrián Patrik, 2011-12-13 12:26:24
[190] Adrián Patrik2011-12-13 12:26:24

S66-ot nem ismertem, én találtam ki hozzá az algoritmust. (Nem azt állítom, hogy a világon elsőként, csak hogy nem ismertem előtte.)

És csak egy sejtés: Nem lehet a feladatot O(N)+O(Q) idő alatt megoldani? Szerintem igen, de ez csak sejtés, mert O(Q)+O(Nlog N)-es megoldást adtam, az időkorláthoz az is elég volt.

Előzmény: [188] Róbert Gida, 2011-12-13 01:16:58
[189] Schmieder László2011-12-13 09:37:31

Bocsánat, valóban értelmesebb lett volna .tgz kiterjesztéssel kérni a tömörített állományokat.

Előzmény: [187] Antal János Benjamin, 2011-12-12 17:50:25
[188] Róbert Gida2011-12-13 01:16:58

I274. A triviális megoldást tették fel, ami 8 pontot ért. Miért nem láthattunk egy 10 pontos megoldást (9 darab is volt belőle)?

Visszatérve az S jelűekhez: (lejárt) S66. megoldható O((N+Q)*log(N)) időben. Ez is halálismert feladat volt.

Előzmény: [177] Adrián Patrik, 2011-11-11 20:44:51
[187] Antal János Benjamin2011-12-12 17:50:25

Igen, én is ezen agyalok, hogy akkor i279.tgz, vagy i279.gz, vagy i279.tar.gz néven küldjem be. Nem szeretnék egy ilyenen elhasalni, és bukni jópár pontot.

[186] Fálesz Mihály2011-12-12 17:42:35

Abban igazad van, hogy a gzip nem csomagol, csak tömörít, (esetleg egymás után ír).

Ha info szerkesztő lennék, és több fájlt várnék összecsomagolva és gzippelve, akkor inkább "i279.tar.gz" vagy "i279.tgz" néven kérném a fájlt.

Előzmény: [185] Antal János Benjamin, 2011-12-12 17:34:02
[185] Antal János Benjamin2011-12-12 17:34:02

Az i279-es feladatban, az i279.gz fájlban ha egy tar fájlt tárolok, az gond? Csak mert a gzip csak egy fájlt képes tömöríteni.

[184] Siegler Gábor2011-12-04 08:10:44

A képet meg szeretnénk nézni, ezért egy billentyű lenyomása után záródjon be.

Előzmény: [182] Antal János Benjamin, 2011-12-02 22:00:56
[183] Antal János Benjamin2011-12-02 22:46:49

Valamit grafikus felülethez ugyan ez a kérdésem. Azonnal záródjon be, vagy egy billentyűlenyomásra, vagy x idő múlva?

[182] Antal János Benjamin2011-12-02 22:00:56

Sziasztok!

Az i277-es feladatban, a program ahogy kirajzolta a képet, azonnal záródjon is be, vagy egy billentyűlenyomáskor záródjon be?

Köszi

[181] Engedy Balázs2011-11-25 14:18:26

Igen.

Előzmény: [180] Adrián Patrik, 2011-11-16 22:48:57
[180] Adrián Patrik2011-11-16 22:48:57

S66-ban feltehetjük-e, hogy a házakat 0-tól N-1-ig számozzuk?

[179] Adrián Patrik2011-11-13 17:01:43

Az, hogy egy feladat ismert, még nem jelenti, hogy könnyű is. Sőt, sokszor épp az ellenkezője; a sudoku szerintem pont ilyen.

Előzmény: [178] Róbert Gida, 2011-11-12 22:09:45
[178] Róbert Gida2011-11-12 22:09:45

OK, bár annak nem látom sok értelmét, hogy ismert feladatokat tűznek ki, mondjuk ez I jelű feladat volt, de S-ben is volt teljesen ismert probléma, mondjuk a sudoku.

A probléma spec. esete annak, amikor egész számok vannak a téglalapba írva, és keressük azt a téglalapot, amiben a számok összege a legnagyobb. Magasabb dimenzióban is láttam már kitűzve ezt a feladatot, nincs nagy újdonság benne, csak többet kell írni.

De d=2 dimenzióban is érdekes a feladat, nem ismert a bonyolultsága, nyilván n2 művelet kell, de O(n3)-nél van gyorsabb algoritmus is. Talán O(\frac {n^3}{\log n})-es, nem emlékszem.

Egy másik már érdekesebb általánosítás, amikor nem egy téglalapba, hanem egy tóruszra írjuk az egész számokat, és keressük a téglalapot amiben a számok összege a legnagyobb.

Előzmény: [177] Adrián Patrik, 2011-11-11 20:44:51
[177] Adrián Patrik2011-11-11 20:44:51

Nem is írta senki, hogy azt kell implementálni. (Remélem legalábbis, hogy nem, mert a ,,halálismert'' változatot csináltam.)

Előzmény: [176] Róbert Gida, 2011-11-11 15:48:33
[176] Róbert Gida2011-11-11 15:48:33

I274. Amit második megoldásnak írtok az egy O(n2*m2)-es algoritmus. De van O(n*m*min(n,m))-es megoldás is. Igazából halálismert.

A tiétek nem is hinném, hogy n=m=500 esetén lefutna egy perc alatt a gépeteken.

[175] Róbert Gida2011-10-31 16:55:18

Igen, így már helyes a kód.

Egyébként tree[i] méretére helyes volt az n>>i. Egy bizonyítás erre: 2-hatványok összeadása miatt látható, hogy pos=u*2i-1 valamilyen u égeszre, így pos2=w*2i-1 is teljesül, de akkor pos2>>i=w-1 és n>pos2=w*2i-1 miatt (n>>i)\gew, kettőt összerakva (pos2>>i)<(n>>i). Talán emiatt is célszerű pos=-1-ről indulni, hogy tree[i] mérete n>>i legyen.

Előzmény: [174] Engedy Balázs, 2011-10-31 04:22:00
[174] Engedy Balázs2011-10-31 04:22:00

Ezt azért nem nevezném interval tree-nek. Amit írsz, az valójában teljesen analóg a versenyző által készített megoldással, annyi különbséggel, hogy te csak a bináris fa leveleiben "tárolsz" elemeket, illetve egy tömböt indexelsz ügyesen ahelyett, hogy külön objektumok lennének a csúcsok.

Mindenesetre ha már lekódoltad, kirakom ezt is megoldásnak, köszönjük! (Annyit módosítottam rajta, hogy a szükséges méretű tömböket foglalja le dinamikusan, ne pedig eggyel rövidebbet, mert így gyakran elszállt. Remélem, most már jó.)

Előzmény: [173] Róbert Gida, 2011-10-30 23:35:47
[173] Róbert Gida2011-10-30 23:35:47

Olvasva a hivatalos megoldást az S64. feladatra nekem úgy tűnt, hogy a kiírók nem ismerik az interval tree-t. Nem mellesleg sokkal egyszerűbb kódot kapunk vele, mint a feltett max. 10 pontos kód.

Megoldásom itt van: http://ideone.com/ay5q3

Előzmény: [172] Engedy Balázs, 2011-10-30 21:06:32
[172] Engedy Balázs2011-10-30 21:06:32

Az S.64. javítása épp most készült el, már ki is került.

Egyébként ugyanaz a javítási határidő/időköz, mint a többi pontversenyben: igyekszünk a következő feladat határideje előttre kijavítani, de ez nem mindig sikerül.

Előzmény: [171] H2CO3, 2011-10-29 18:05:57
[171] H2CO32011-10-29 18:05:57

Szaisztok! Csak annyit szeretnék kérdezni, hogy az informatika feladatokat milyen időközönként/határidővel javítják? Hamarosan az októberi forduló beküldési határideje is lejár, de még a szeptemberi feladatok sincsenek javítva... remélem, nem költözött el az e-munkafüzet...?

Köszi a válaszokat!

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