KöMaL - Középiskolai Matematikai és Fizikai Lapok
English Információ A lap Pontverseny Cikkekről Távoktatás Hírek Fórum Internetes Tesztverseny
Játékszabályok
Technikai információk
TeX tanfolyam
Regisztráció
Témák

 

Rendelje meg a KöMaL-t!

Támogatóink:

tehetseg.hu

Ericsson

Google

Emberi Erőforrások Minisztériuma

Emberi Erőforrás Támogatáskezelő

Oktatáskutató és Fejlesztő Intézet

ELTE

Reklám:

MBUTTONS

VersenyVizsga portál

Kísérletek.hu

Matematika oktatási portál

Fórum - Informatika kömal

  Regisztráció    Játékszabályok    Technikai információ    Témák    Közlemények  

Ön még nem jelentkezett be.
Név:
Jelszó:

  [1. oldal]    [2. oldal]    [3. oldal]    [4. oldal]    [5. oldal]    [6. oldal]    [7. oldal]    [8. oldal]    [9. oldal]    [10. oldal]    [11. oldal]    [12. oldal]  

Ha a témához hozzá kíván szólni, először regisztrálnia kell magát.
[298] Róbert Gida2015-06-25 22:29:43

Mégis jó, az eddigi utolsó vödört nézzük, az lefedi a (j+1)-től az i-edikig terjedő repedéseket, és erre megy a dinamikus programozási megoldás.

Előzmény: [297] Róbert Gida, 2015-06-25 22:17:38
[297] Róbert Gida2015-06-25 22:17:38

Ez nem jó. Lehet, hogy több vödör festék kell egy adott w hosszhoz. (példa inputra a megoldás pont nem ilyen).

Előzmény: [296] Róbert Gida, 2015-06-25 22:10:48
[296] Róbert Gida2015-06-25 22:10:48

Lejárt S99. megoldása, &tex;\displaystyle O(N^2)&xet; időben: http://ideone.com/tHt9Zc, ehhez még komment sem kell olyan rövid.

Egyébként azt hiszem idén (is) megnyertem volna az S jelű versenyt.

[295] Róbert Gida2015-06-21 09:55:05

"Polinomiális megoldás is létezik, ami mindenre lefut: folyam algoritmussal"

Valóban, már látom (nem programoztam le).

Előzmény: [294] Weisz Ágoston, 2015-06-20 19:02:12
[294] Weisz Ágoston2015-06-20 19:02:12

Polinomiális megoldás is létezik, ami mindenre lefut: folyam algoritmussal. De ez persze nem volt elvárás, már az is messze túlteljesített volna, amit küldtél. Nincs semmi érdekes a képen :(

Előzmény: [293] Róbert Gida, 2015-06-17 19:37:27
[293] Róbert Gida2015-06-17 19:37:27

I378. érdekes feladat volt, meg is lepett, mert az I jelű informatikánál nem szokott programozás lenni. &tex;\displaystyle O(max(m,n)*4^{min(m,n)})&xet; időben megoldható, így a két kis feladat még optimálisan is megoldható, a nagynál pedig úgy keresek jó megoldásokat, hogy mindig csak egy résztéglalapon oldom meg a feladatot (többi pixel fix), ez lehet akár egy 50*12-es (vagy egy 12*50-es) téglalap is a bonyolultság miatt. Úgy érzem, hogy ez is optimális, bár cost=3400-nál is ezt éreztem. Elvileg valamit kéne látnunk a fényképeken? Persze több optimális megoldás, azaz különböző fénykép, is lehet. Az első in.1-re a megoldás az üres fénykép. Legjobb megoldásaim, a "fényképek":

in.1-re:

00000

00000

00000

00000

00000

00000

36 forint költség.

in.2-re:

100000000011

110000110011

110000111111

110000111111

000000111111

000000111110

000000111110

110000111110

111000111110

111100011100

163 forint költség.

in.3-ra:

00011111111000000000000000000000000111111000111110

00111111111000000000000000000000001111111000000110

00111111111000000000000000000000001111111000000000

11111111111000000000000000000000001111111000000000

11111111111000000000000000000000001111111000000000

11111111111000000000000000001100000011111000000000

11111111111000000000000000111100000000000000000000

11111111111000000000000001111100110000000000000000

11100011111000000000000001111100111000000000000000

11000000111000000000000001111100111000000000000000

10000000000000000000000000011000000000000000000000

00000000000000000000000000000000000000000000000000

00000000000000000000000000000000000000000000000000

00000000000000000000000000011000000000000000000000

00000000000000000000000000011100000000000000000000

00000000000000000000111000011111000000000000000000

00000000011000011111111100011111111000000000000000

00000000111111111111111100011111111101111100000011

00000000111111111111111100011111111101111111111111

11111111111111111111111100011111111000111111111111

11111111111111111111111111111111111000001111111111

11111111111111100111111111111111111000001111111100

11111111111111100111111111111000000000000111111000

01111111111111000000001111100000000000000111100000

00111111111111000000000111000000000000000111000000

00111111111111000000000111000000000000000000000000

00111111111111000000000011000000000000000000000000

00111111111110000000000011000000000000001100000000

11110000001100000000000011111000000000111111100000

11110000000000000000000011111110000000111111111100

11110000000000000000000011111110000000111111111100

11110000000000000000000011111110001111111111111100

11111111000000000000000011111111111111111111111111

11111111000000000001111111111111111111111111111111

11111111100000000001111111111111111111111111111111

11111111100000000000001111111111111111111111111110

11110000000011000000000000000000011111111111111110

11110000000111000000000000000000011111111111110000

11110000000111000000000000000000111111111111100000

00000000000111000000000000000001111111111111100000

00000000011111000000000000000011111111111111100000

00000001110011000000000000000111111111111111100001

00000111110000000000000000000111111111111111111001

00000111110000000000000000001111111111111111111111

00000111110000000111111000001111111111111111111111

01111111111000000111111110001111111111111111111111

11111111111000000111111111111111111111111111111111

00111111111000000011111111111111111110001111111111

00111111100000000011111111111111111100001111111111

01111110000000001111111111111111111100001111111111

3399 forint költség.

[292] Szomszédod2015-05-31 21:26:34

Úgy tűnik a honlapra nem kerültek fel a I. 378. feladathoz tartozó bemenetek.

[291] Róbert Gida2015-05-12 18:51:19

Lejárt S98. megoldása optimális, lineáris időben: http://ideone.com/BTBvud (nem teszteltem agyon).

Először meghatározom azt, hogy az egyes alkatrészek mely csoportokben szerepelnek. Majd, ha tudom, hogy egy adott alkatrészt (x-ediket) cserélni kell, akkor azon csoportok méretét eggyel "csökkentem" amelyekben ez szerepel. Ha a csoport mérete 1-re változik, akkor kapunk egy elemet, amelyet mindenképpen cserélni kell, na de melyiket? Ez klasszikus feladat: ha t a cserélt elemek összege, és s a csoport elemeinek összege, akkor y=(s-t)-edik elemet kell cserélni (azaz egy csoportnál azt is tartsuk számon, hogy hogyan változik az elemek összege). out[] tömbnél: out[i]=1, ha az i-edik elemet mindenképpen cserélni kell és 0, ha nem (vagy még nem tudjuk biztosan, hogy cserélni kell-e).

Az algoritmus helyes, hiszen csak azon elemeket cserélem amelyeket mindenképpen cserélni kell. Sőt, az alkatrészek minimális számához tartozó alkatrészek halmaza egyértelmű.

[290] Róbert Gida2015-03-13 19:43:29

Lejárt S96. feladat megoldása: ez egy az egyben a Huffman kódolást kéri, borzasztóan rövid c++ megoldásom: http://ideone.com/fjWhxn.

[289] Róbert Gida2014-11-14 14:25:19

Lejárt S91. feladatnál valami roppant gyenge tesztek lehettek. Igazából sokkal gyorsabb megoldást én sem tudok, mint a közölt, az &tex;\displaystyle O(n*S^2)&xet;-es megoldásnál nagyjából 360 milliós méretű tömböt kéne kiszámolni, ami 1 másodperc alatt nehézkesen fut le (&tex;\displaystyle S=6000,n=60&xet; esetén, használva az &tex;\displaystyle A\le B\le C&xet; trükköt).

De kb. még egy kilencszeres gyorsítás érhető el: az optimum ugyanis legfeljebb &tex;\displaystyle \frac S3+max(a_i)&xet;: haszáljunk mohó algoritmust, minden lépésben az kapja az ajándékot, aki eddig a legkisebb összértékben kapott (az optimum egyébként legalább &tex;\displaystyle \frac S3&xet;, de ez nem kell). Memóriában pedig elég &tex;\displaystyle O(S^2)&xet;.

[288] Róbert Gida2014-05-14 18:25:17

Régebben néhány versenyükön indultam, most nem vagyok aktív tag.

Előzmény: [287] Bélus, 2014-05-14 17:02:54
[287] Bélus2014-05-14 17:02:54

Topcoderezel?

Előzmény: [286] Róbert Gida, 2014-05-14 12:33:05
[286] Róbert Gida2014-05-14 12:33:05

Lejárt S89. megoldása: http://ideone.com/vJP729

[285] Róbert Gida2014-03-13 19:54:55

Nem tudom miért kell állandóan ilyen korán kirakni a megoldásokat.

Lejárt S87. megoldása: http://ideone.com/v5kOi1. Ránézésre rövidebb, mint a közölt.

[284] Róbert Gida2014-03-08 19:55:13

Nem sikerült megértened a feladatot.

Előzmény: [283] ferrari13, 2014-03-08 19:13:48
[283] ferrari132014-03-08 19:13:48

Mégegyszer próbálkozom, mert az előbb valamiért nem írta ki rendesen:

Egy segítséget szeretnék kérni az "i341" feladathoz.

Az M-01 megálló gondolom az első megálló, mivel oda 0 mp alatt ér oda, és ez csak akkor lehetséges, ha onnan indul.

Lesz mondjuk 4 felszálló, de ebből rögtön 0,4 le is száll (10 százalék), tehát aki felszáll, az száll le, mivel nincs még fent senki előtte.

A másik lehetőség, hogy már kezdetben van egy bizonyos számú ember a villamoson, de azt viszont nem írta a feladat.

[282] ferrari132014-03-08 18:31:30

Egy segítséget szeretnék kérni az "i341" feladathoz.

Az M-01 megálló gondolom az első megálló, mivel oda 0 mp alatt ér oda, és ez csak akkor lehetséges, ha onnan indul.

Az 1. járat esetén lesz 4 felszálló, de 10

A másik lehetőség, hogy már kezdetben van egy bizonyos számú ember a villamoson, de azt viszont nem írta a feladat.

[281] Weisz Ágoston2014-01-23 18:52:02

Igen, ez a lényeg. Ha érdekel a többi feladat, azokra is szívesen várok megoldásokat ;)

Előzmény: [280] Róbert Gida, 2014-01-16 10:38:46
[280] Róbert Gida2014-01-16 10:38:46

Valóban! Meg is találtam:

http://ideone.com/RJw0CN

Előzmény: [279] Weisz Ágoston, 2014-01-15 12:43:00
[279] Weisz Ágoston2014-01-15 12:43:00

Az ötlet jó. Van lineáris megoldás is ;)

Előzmény: [278] Róbert Gida, 2014-01-14 20:21:22
[278] Róbert Gida2014-01-14 20:21:22

Lejárt s85. gyors megoldása, némi magyarázattal:

http://ideone.com/ktBxy7

[277] Weisz Ágoston2013-12-30 12:55:50

Igen, különböző, tehát 3 értékes részsorozata van: a jelölésben az intervallum kezdete és vége fog szerepelni: (1, 1), (2, 2), (1, 2) a 3 különböző értékes részsorozat.

Előzmény: [276] Kurokawa, 2013-12-30 11:13:19
[276] Kurokawa2013-12-30 11:13:19

S. 85. Különbözőnek számít-e, az a két értékes részsorozat, amelyek elemei rendre megegyeznek, de az elhelyezkedésük különböző az eredeti sorozatban? Például az (1, 1) sorozatnak 3 vagy csak 2 értékes részsorozata van, ha C=1?

[275] Weisz Ágoston2013-10-30 08:36:30

Nem kell nagy szám aritmetikát programozni hozzá. Minden belefér a standard int-be (32 bites).

Előzmény: [274] ferrari13, 2013-10-28 17:50:12
[274] ferrari132013-10-28 17:50:12

Az "S" feladatnál a törés ára (o1,o2...,s1,s2...) értéke mennyi lehet maximálisan?

  [1. oldal]    [2. oldal]    [3. oldal]    [4. oldal]    [5. oldal]    [6. oldal]    [7. oldal]    [8. oldal]    [9. oldal]    [10. oldal]    [11. oldal]    [12. oldal]  

  Regisztráció    Játékszabályok    Technikai információ    Témák    Közlemények  

Támogatóink:   Ericsson   Google   Szerencsejáték Zrt.   Emberi Erőforrások Minisztériuma   Emberi Erőforrás Támogatáskezelő   Oktatáskutató és Fejlesztő Intézet   ELTE   Nemzeti Tehetség Program   Nemzeti
Kulturális Alap