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.
[304] Róbert Gida2015-12-07 16:08:17

"A kezdőpozíciót nem kell beleszámolni? Vagy azt nem kell beleszámolni, ahova megérkezik a robot a végén? Vagy valamit rosszul értelmezek?"

Táblázatod alapján én is 7-et látok. És nyilván mindent bele kell számolni. Amúgy szigorúan értelmezve a robot alapból tesz 2 utasítást amikor elindul: "Egy robot a következő utasítások szerint mozog: először a 0 pozícióból indul, majd a 15 R utasításra 15 lépést jobbra lép, és a 20 L utasításra 20 lépést balra. " ezt nem is tudom máshogy értelmezni, nyilván a "majd" után kellett volna egy "például" is.

I/S pontversenyre visszatérve: az októberi feladat tankönyvi példa volt. Meglehetősen egyszerű.

Előzmény: [303] Kurokawa, 2015-12-06 19:54:00
[303] Kurokawa2015-12-06 19:54:00

Valóban érdekes a I/S pontverseny esete. Az elsőt megcsináltam, de még most sincs eredménye. A másodikat már nem is volt kedvem megcsinálni. Persze csak ezután szembesültem azzal, hogy az is részét képezi a S pontversenynek. Így megint 10 pont mínuszban vagyok. Kezdek rájönni, hogy ez a pontverseny nem nekem való... :)

De igazából nem panaszkodni jöttem elsősorban, hanem az S. 102. feladathoz lenne kérdésem. A példabemenet szerint nekem 7 ilyen pozíció létezik. A kezdőpozíciót nem kell beleszámolni? Vagy azt nem kell beleszámolni, ahova megérkezik a robot a végén? Vagy valamit rosszul értelmezek?

[302] Róbert Gida2015-11-10 18:39:56

Az új I/S pontversenyről mit lehet tudni? Havonta látok egy feladatot, de a versenykiírásban I/S-ről nem beszéltek.

[301] Schmieder László2015-11-08 21:24:04

Az I.382. feladat példájában a két utolsó sor helytelenül jelent meg. A honlapon a példákat javítottuk.

[300] Schmieder László2015-09-16 19:04:37

Az I.379. feladat példája a lapban hibásan jelent meg, és egy pár napig a honlapon is hibásan szerepelt . A példát javítottuk, a honlapon helyesen megjelenő példa helyes. Elnézést kérünk.

[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

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