Fórum: Informatika kömal

Lejárt S112. megoldása: http://ideone.com/l8KSzq, az nem egészen trivi, hogy ez egy sima prioritásos sorral megoldható. Egyébként legutóbb az S110-nél sütöttem el a prioritásos sort.

A statisztika jobb lesz a feladatok kijavulása után - most véletlenül bekapcsoltuk, még a javítás+pontozás előtt.

Lejárt S111. feladat megoldása: http://ideone.com/A8poMH.

Úgy látom elérkeztünk a minimumhoz: "Az S. 111. feladat statisztikája 0 dolgozat érkezett."

Egyébként valószínűleg lényegében 2*N darab gcd számítása is elég lehet egy jobb algoritmussal (a legrosszabb esetben), az enyém bizonyítással együtt 3*N-t tud, de még ez is kényelmesen lefut.

Feladatokból rengeteg van fent az interneten: online judge. Van, ahol (néhány) kategóriára szét is osztják a feladatokat: urionlinejudge vagy például: mohó algoritmusos példák a codeforces-on.

Valami irodalmat tudsz (vagy bárki más) ajánlani hasonló típusú feladatokkal, megoldásokkal, ötletekkel, módszerekről?

Lejárt S.110. megoldása.

\(\displaystyle K=0\) esetnek szerintem van értelme, ezért is nem ezt írtam. És a kérdések is értelmesek, például: \(\displaystyle 2.\) feladat: \(\displaystyle 0\) torony stb.

Jó szívvel megköszöntem volna, ha a feladatnál arra hívod fel a figyelmet, hogy K=0 esetnek nincs értelme. Helyette elég barátságtalan stílusban írtál. A mintamegoldás szerzője elég okosan ebben az esetben nem írt ki semmit.

Megköszönni nem tudom, hogy feltételezed, hogy a beküldött megoldások javításánál nem tesztelem a programokat.

További jó munkát kívánok!

I.406.-ra közölt tökéletes 10 pontos (minta)megoldás a diáktól hibás. \(\displaystyle k=0\) kockára semmit nem fog kiírni az \(\displaystyle if(k>0)\{\) miatt. De ezt az if-et törölve sem lesz jó a program például a 7. feladat megoldása miatt. Roppant gyenge lehetett a teszt, ha volt egyáltalán.

A Kömal S-sel kapcsolatos kérdésre szeretnék válaszolni: Mivel nincs ott a feladatban, hogy mit kell csinálni, ha nem lehet feszítőfát építeni, ezért feltételezhetjük, hogy mindig lehet. A bemenetben minden súly max 3-szor szerepel, így elegendő feltételezni, hogy összefüggő a gráf.

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