Fórum: Számtech. OKTV

http://programozobajnoksag.com/

Megértettem, fairnek tűnik, végiggondolom. Köszönöm a segítséget.

Pedig Ágoston már elmondta a jó megoldást, csupán két irányt felcserélt: az első csoportba kerülnek tehát azok, amelyekre a_ib_i, a másodikba pedig az a_i>b_i feltételnek megfelelők. Az első csoportot a_i szerint növekvően, a második csoportot b_i-k szerint csökkenően rendezzük, majd a gépeknek sorban beadjuk az első, majd a második csoportba került elemeket, amilyen hamar csak tudjuk. (Vegyük észre a forgási szimmetriát!)

Hogy ne csak kötözködjek, egy kis hint a bizonyításhoz: induljunk ki egy optimális ütemezésből (tehát ahol nem csak a sorrendet, hanem a végrehajtások pontos idejét is tudjuk minden munkadarabra mindkét gépnél), és mutassuk meg, hogy amikor cserékkel az ütemezés elejére rendezzük a_i-k szerint növekvő sorrendbe az első csoport elemeit, illetve a végére b_i-k szerint csökkenő sorrendbe a második csoportba tartozó munkadarabokat, akkor az áthelyezések során az optimalitási tulajdonság nem sérül, illetve az ütemezés továbbra is legális marad. (És végül eljutunk a fenti algoritmus által előállított ütemezéshez.)

Ha az egyetemen tananyag, te biztosan tudod a választ, szóval hálás lennék, ha elmondanád...

És A gép mi szerint dolgozik?

Ez a 10-20 1-6 1-6 1-6 elemnégyest a 10-20 elemmel kezdené, holott valamelyik 1-6 elemmel kellene.

Elnézést, pont fordítva: a szerint növekvőbe, b szerint csökkenőbe...

Ütemezéselméletnek hívják ezeket a feladatokat, egyetemen tanítják is. Több, mint valószínű ezt a feladatot is. Szerintem polinom alg. van rá.

Egy ötlet: legyen a[i] az A műveletek elvégzési ideje, b[i] a B műveleteké. Válasszuk két csoportba az elemeket: ha a[i]-b[i] nemnegatív, akkor az elsőbe, ha negatív akkor a másodikba. Az első csoportot rendezzük 'a' szerint csökkenőbe, a másikat 'b' szerint növekvőbe. Ekkor a sorrend úgy lesz, hogy először az első csoport rendezetten, majd a második. Ez a sorrend megfelelő lesz (legalábbis szerintem). Tehát az első így kepott elemet beadjuk A gépnek, ha kész akkor a 2. rakjuk A-ba és a készet B-be.

Arra tudsz példát, amikor nem optimális ha B az A által már megmunkált darabok közül a neki ( B-nek ) legtöbb időt igénylőnek kezd neki?

Um, nem látszik a példaábra amit csináltam,szóval leírom ide is:

1. tárgy: A művelet 8, B művelet 1 időegység 2. tárgy: A művelet 1, B művelet 6 időegység 3. tárgy: A művelet 6, B művelet 3 időegység

Megoldás, A és B gépben is a tárgyak sorrendje:

2. tárgy-> 3. tárgy-> 1. tárgy

Hello mindenki!

Bármely ciki legyen is, elakadtam az egyik 2. fordulós problémával. Úgy sejtem, nincs polinomiális megoldása, de bizonyítani nem tudom, és mindeddig nem találtam tökéletes megoldást, sem én, sem azok, akikkel már beszéltem a problémáról.

A 4. feladatról lenne szó. Adott N tárgy, melyeken A és B gépnek el kell végeznie egy-egy műveletet. Minden tárgyon először A majd utána B műveletet kell elvégezni, egy gép egyszerre csak egy tárgyon dolgozhat. Minden tárgyra adott, hogy mennyi idő alatt tudjuk elvégezni rajta A és B műveletet. A feladat egy olyan program megírása, ami megadja a tárgyak sorrendjét A illetve B gépben (szinte biztos, hogy a két sorrend bizonyíthatóan azonos minden esetben) úgy, hogy minél hamarabb végezzünk az összes tárggyal. Tehát ha adott 3 tárgy,

t: 1. | 2. | 3. A: 8 | 1 | 6 B: 1 | 6 | 3

akkor azokra megadja, hogy az optimális sorrend a 2.->3.->1.

Felmerül ötletként, hogy B szerint csökkenő sorrendben rendezünk, hogy A szerint növekvőbe, hogy B szerint csökkenőbe majd A szerint növekvőbe, hogy A szerint növekvőbe majd B szerint csökkenőbe, A/B szerint növekvőbe, A-B szerint növekvőbe, valamint az is, hogy ha adott egy optimális sorrend n tárgyra, akkor n+1 tárgynál az eredeti n tárgy egymáshoz viszonyított sorrendje nem fog változni, azonban ezekhez mindhez találtunk olyan kombinációkat, amikor hibás adatot produkálnak. Nagyon érdekelne, hogy létezik-e polinomiális algoritmus, vagy ha nem, akkor annak a bizonyítása, hogy a probléma nem oldható meg polinomiális időben.

Válaszaitokat előre is köszönöm.

Sziasztok!

Más is tud valamit arról hogy holnap nem 10kor hanem 9kor kezdődik a prog. 2. forduló?

Ez most elég fontos lenne tudnom, mert már így is átrakták Paksról Pécsre(és Szekszárdi vagyok), szóval kilométerből nem lesz hiány...

Kössz,

NemBen

Már értelek, így teljesen jó.

Ezért írtam, hogy 2*M*N állapot van összesen, egy kapcsoló minden nyitott ajtót bezár, illetve kinyitja a csukottakat ha rálépünk, így csak az a lényeges, hogy páros vagy páratlan sokszor léptünk kapcsolóra. (i,j,paritás)-sal le lehet írni a helyzetet, (i,j) a labirintusbeli helyed, míg paritás a kapcsolókra történt lépesszámnak a paritása.

És igen... nagyon komplex.

RG-nek üzenem, hogy a labirintus aközben is megváltozhat, miközben kóborlunk benne. Lehet, hogy csak én nem értem jól mit akarsz mondani, de mintha a tiedből ez kimaradt volna...

Milyen komplexitású megoldásra gondoltál?

Itt egy kis nehezítés a labirintushoz, lehet rajta gondolkodni (én tudom a megoldást, csak a hecc kedvéért adom föl...):

Adott egy M*N-es labirintus. Minden mezőjén vagy ajtó van, vagy kapcsoló, vagy semmi. Minden kapcsolóhoz megadjuk, hogy mely ajtó(ka)t kapcsolja, valamint minden ajtóhoz a kiindulási helyzetét. A zárt ajtó falként, a nyitott semmiként viselkedik.

Adjuk meg, hogy hogyan lehet a legrövidebb úton eljutni az (1;1) pontból az (M;N) pontba!

ja, ennyire nem vagyok benne a programozásban :P

Én is ezt írtam: bfs=breadth first search, magyarul szélességi keresésnek hívják.

Hát ha nem Dijkstra, akkor Dijkstra light, ismertebb nevén szélességi bejárás :P

http://home.fazekas.hu/~kdano/misc/DNS.PAS

Ez a megoldásom 5 pontot ért a 15-ből, mivel benne felejtettem egy hülye debuggoló sort.. 5 pont az öt helyes első sor, tehát valószínűleg ettől függetlenül a program jó. Nem igazán volt kedvem ismét felfogni, hogy mit csinál a program, úgyhogy ez a debuggoló sor még mindig benne van. Egyébként fogyaszd egészséggel.

Kösz, ennyi segítség már elegendő lesz.

A labirintus marha egyszerű: összesen ugye M*N mező van, de azt is kell tudnod, hogy páros sokszor léptél kapcsolóra vagy sem, azaz 2*M*N állapot van (ha páros sokszor akkor minden ajtó úgy van, ahogy eredetileg volt, különben pont fordítva). Legrövidebb utat keresünk egy start állapot között és egy vége állapot között (vigyázz, mert ez kétféle, aszerint, hogy a végén páros vagy páratlan sokszor léptünk a kapcsolóra), hát mi a túró, ha nem Dijkstra algoritmusa! Bár ezt bfs-el is meg lehet oldani O(M*N) időben és tárban.

A DNS-t nem tudom hogy kell, bár az utóbbi hónapokban kb. 5 ilyen feladatot csináltam meg, ha ez is ebbe a kategóriába tartozik, akkor O(L1*L2) időben megoldható, ahol L1,L2 a két string hossza. A feladat őse Levenshtein távolság problémája, wikipedia-n fent van, ez persze nem az OKTV feladat, de szerintem valami hasonló lesz itt is a megoldás.