Fórum: Informatika kömal

Á köszönöm szépen, így már valóban helyes a kimenet, erre nem is gondoltam volna, nem is néztem az ábrát mivel láttam, hogy sokkal több téglalap van rajta mint a példában :)

Szerintem azt nézd meg, hogy a megadott koordináták "cellákat" vagy "pontokat" jelölnek.

Ha pontokat, akkor az "1 14 2 16" egy &tex;\displaystyle 1\times 2&xet;-es téglalap, míg ha cellákat, akkor &tex;\displaystyle 2\times 3&xet;-as. A mintához adott ábra alapján nekem úgy tűnik, hogy pontok koordinátái vannak megadva. (90 fokkal forgasd el az ábrát.)

Sziasztok! Szerintem az I/S 4. feladat példa be- és kimenete hibás az oldalon. Mellékelnék két képet (http://imgur.com/a/x184e). Az elsőn a példa bemenet található, majdnem biztos vagyok benne, hogy megegyezik az oldalon találhatóval :) A másodikon pedig a téglalapok láthatóak, a bemenet alapján, különböző betűk különböző téglalapokat, az 'x' pedig üres helyet jelent (a színezés pedig csak esztétikai célokat szolgál). Szóval a feladat alapján az 'N', 'K', 'H', 'L' jelű téglalapok nem láthatóak, viszont a példa kimenet csak 3 darabot említ.

Üdv, mraron.

A pozíció helyett a helyes megfogalmazás: hány 1 egység hossuú részen járt legalább k-szor. Így remélem összeillik a példával.

"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ű.

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?

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.

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.

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.

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.

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

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.

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

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

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 :(

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.

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

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

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.

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

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

Topcoderezel?

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

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.

Nem sikerült megértened a feladatot.

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.