 |
Az I. 221. feladat (2009. október) |
I. 221. Péter és Pál ikrek. Féltékenyek egymásra, olyannyira, hogy bármilyen osztozkodásnál addig nem nyugszanak, míg a két érték egyező nem lesz.
Idén születésnapjukon népes családjuktól 25 ajándékot kaptak, amelyek összértéke biztosan nem éri el az 1000 eurót. Nekünk csak azt kell megválaszolnunk, hogy eloszthatók-e az ajándékok úgy, hogy Péternek és Pálnak is ugyanolyan értékben jusson.
A feladatot táblázatkezelő program segítségével oldjuk meg. Az ajándékok értékét, amelyek egész számok, a B3:Z3 tartományba jegyeztük be. A választ az A1 cellában adjuk meg. A megoldás során saját függvény vagy makró nem alkalmazható.
Beküldendő egy tömörített állományban (i221.zip) a táblázatkezelő munkafüzet (i221.xls, i221.ods, ...), illetve egy rövid dokumentáció (i221.txt, i221.pdf, ...), amelyben szerepel a megoldáskor alkalmazott táblázatkezelő neve, verziója, valamint a megoldás rövid leírása.
(10 pont)
A beküldési határidő 2009. november 10-én LEJÁRT.
A megoldók három csoportba oszthatók. Néhányan dinamikus programozási feladatként (táblázatkitöltőként) értelmezték és oldották meg a feladatot. Mások megpróbálták megadni az ajándékok testvéries felosztását. Ez nem mindig járt sikerrel. Voltak, akik kihasználták a táblázatkezelő nyújtotta lehetőségeket és a Solver bővítménnyel igen egyszerű megoldást adtak. A szerzett pontszám természetesen független a megoldás módjától.
Az alábbiakban a táblázatkitöltés módszerét ismertetjük részletesen.
Akik úgy gondolják, hogy meg kell vizsgálni az összes elosztási lehetőséget a kérdés megválaszolásához, nem veszik figyelembe, hogy az ajándékok elosztását nem, csak az eloszthatóságát kell megadnunk. Ebben az esetben viszont nem kell megkülönböztetnünk az ajándékokat és elegendő csupán annak értékével dolgoznunk.
Csak azzal a nemtriviális esettel foglalkozunk érdemben, ahol az ajándékok összértéke páros.
Ha meg tudjuk határozni, hogy milyen értékben kaphatott ajándékot egyikük, lényegében megoldottuk a feladatot. Ugyanis könnyen belátható, hogy ha az értékek között szerepel az ajándékok összértékének fele, akkor az ajándékok egyenlő értékben eloszthatók.
Vegyük észre, hogy nincs is szükség az összes lehetséges értékre. Elegendő, ha 500-ig meghatározzuk (csak egyikük ajándékaival törődünk), hiszen az összérték 1000-nél nagyobb nem lehet.
Oldjuk meg a feladatot lépésről lépésre haladva, azaz határozzuk meg, hogy az első k ajándékból hogyan részesülhetett egyikük. Ehhez az ajándékok sorrendjét rögzíteni kell, de a sorrend a végeredmény - az összes elosztása - szempontjából nem lényeges.
Ennek meghatározására egy 501 soros és 26 oszlopos segédtáblát használunk. A segédtábla i. oszlopának j. sora azt jelzi, hogy az egyik testvér i darab ajándék eloszltását követően kaphatott-e j értékben ajándékot. Ha kaphatott, jelöljük IGAZ, egyébként HAMIS értékkel.
A 0. oszlopban - lévén egyetlen ajándékot sem osztottunk ki - a 0. sor kivételével HAMIS érték szerepel. Ez fejezi ki, hogy 0 értékben kaphatott ajándékot.
Alkossunk egy másolható képletet, amely a nagyobb (mint 0) oszlopszámokra a teljes tartományon belül szabadon másolható. Az i. oszlop j. sorának kitöltésénél két esetet kell megvizsgálnunk: az adott testvér megkapta-e az ajándékot vagy sem.
(1) Ha nem kapta meg, akkor a j. cella értéke csak akkor lehet igaz, ha j értékben kaphatott az első i-1 ajándékból.
(2) Ha megkapta az i-edik ajándékot, és annak értéke E(i), akkor a j értékben csak úgy juthat ajándékhoz, ha az első i-1 ajándékból j-E(i) értékben részesülhetett.
Ha ezt a teljes segédtáblára megfogalmazzük, akkor az utolsó oszlop megfelelő cellájának értéke megadja, hogy a feladat kérdésére a választ. A kérdéses cella a j=[ajándékok összértéke]/2.
A mintaként adott megoldásban a segédtáblát az A5:Z505 tartományban felvéve a következő értékeket használjuk:
A5=IGAZ A6:A505=HAMIS
B5 érékét egy függvénnyel adjuk meg, amelyet a teljes B5:Z505 tartományba átmásolhatunk.
B5=VAGY(A5;HA(SOR()-B$3>4;INDEX(A$5:A$505;SOR()-B$3-4)))
A logikai függvény első paramétere az (1), a második pedig a (2) esethez tartozik.
Figyelem, újabb sorok beszúrásával a B5:Z505 tartomány celláinak értéke módosításra szorul.
A választ az A1-es cellában kell előállítani.
Ehhez az A3 cellában meghatározom az ajándékok összértékét. A3=SZUM(B3:Z3)
Az előállíthatósághoz szükséges, hogy az összeg páros legyen és a segédtábla utolsó oszlopában az ajándék összértékének felét adó sorban IGAZ érték szerepeljen.
A1=HA(ÉS(MARADÉK(A3;2)=0;INDEX(Z6:Z505;A3/2));"Igen";"Nem")
Statisztika:
7 dolgozat érkezett. 10 pontot kapott: Balla Attila, Gaizer Bence, Paróczi Gergő. 8 pontot kapott: 1 versenyző. 5 pontot kapott: 1 versenyző. 3 pontot kapott: 1 versenyző. 2 pontot kapott: 1 versenyző.
A KöMaL 2009. októberi informatika feladatai