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.
[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?

[273] Róbert Gida2013-10-11 21:08:42

Lejárt S82 megoldása némi megjegyzéssel: http://ideone.com/cfZHQ9. Tényleg gyors megoldás, nagyjából az input-output annyi időbe telik (scanf/printf-fel), mint maga az algoritmus. c++ algoritmusait, vagy lassabb rendezéseket sem használok, hogy mindenhol gyorsítsak. Bár remélem ezt gyors gépre rakjátok, nálam n=1000000-nál csak az input-output elvesz nagyjából 0.75 másodpercet (ha "NEM" a válasz, akkor persze ez kevesebb). (Persze scanf/printf-nél is van gyorsabb eljárás.)

[272] Fodor Zsolt2013-10-08 21:43:42

Azokat is, akik a válaszra válaszoltak, sőt, akik ezekre válaszoltak, stb.

Előzmény: [271] ferrari13, 2013-10-08 20:48:19
[271] ferrari132013-10-08 20:48:19

Az i325-ös feladatnak a 7-es részében "kik szerepelnek az innen induló levélfolyamban feladóként" feladatra csak azokat kell nézni, akik arra a levélre válaszoltak, vagy azokat is, akik a válaszra válaszoltak?

Példa: Be: 4-es levél a négyes levélre (10. levélként) érkezett egy válasz a 2-es levélküldőtől, majd 11. levélként érkezett egy válasz a 10-es levélre az 1-es levélküldőtől. Ilyenkor csak a 2-est vagy az 1-est is ki kell írni?

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