Az I. 197. feladat (2008. november)

I. 197. Egy áruházban N különféle terméket szeretnénk megvenni, több részletben, minden alkalommal néhány terméket megvásárolva. Írjunk programot, mely a termékek árainak ismeretében meghatározza, hogy azokat milyen felosztásban vegyük meg ahhoz, hogy az egyes vásárlások során az 5-ösökre való kerekítésből adódó hibák összességében számunkra a lehető legnagyobb megtakarítást eredményezzék.

A program a termékek számát és árait a standard bemenetről olvassa. Minden sorban egy-egy bevásárlólista leírása szerepel: a megvásárolni kívánt termékek N száma, majd a₁,...,a_N, szóközzel elválasztott pozitív egész számok, a termékek árai. Egy listán a termékek árösszege legfeljebb , a bemenet végét egy ,,0'' tartalmú sor jelzi.

A program bevásárlólistánként egy sort, ebben pedig egyetlen számot írjon a standard kimenetre: az adott listán szereplő összes termék optimális felosztásban történő megvásárlása esetén a kerekítési hibákból adódó összes hasznunkat vagy veszteségünket.

Beküldendő a program forráskódja (i197.pas, i197.cpp, ...), valamint a program rövid dokumentációja (i197.txt, i197.pdf, ...), amely tartalmazza a megoldás rövid leírását, és megadja, hogy a forrásállomány melyik fejlesztőkörnyezetben fordítható.

(10 pont)

A beküldési határidő 2008. december 15-én LEJÁRT.

A megoldás menete

Vizsgáljuk meg általánosságban egy optimális csoportosítás szerkezetét, azaz keressünk olyan általános tulajdonságait, amelyek alapján később bármely konkrét problémára konstruálhatunk egy egyszerűen elkészíthető, mégis optimális megoldást.

Először is vegyük észre, hogy a feladat során minden termék esetén elegendő árának 5-tel való osztási maradékát vizsgálni, a kerekítés szempontjából a hányados nem játszik szerepet. A továbbiakban végig az öttel adott maradékokkal fogunk dolgozni, mégpedig előjeles formában, ugyanis ezek épp az adott termék (vagy termékcsoport) megvásárlása esetén a kerekítésből adódó hasznunkkal egyeznek meg.

Tekintsünk tehát az optimális megoldásban egy egyszerre megvásárolt termékhalmazt. Kulcsfontosságú a következő észrevétel: ha ebben van néhány termék, amelyeket együtt megvéve a kerekítésből hasznunk származna, akkor ezeket külön is megvehetjük. Egészen pontosan: ha van olyan valódi részhalmaz, melyben szereplő termékek árainak összege az előzőek definiált módon nemnegatív maradékot ad, akkor ezt a termékhalmazt külön megvásárolva is optimális marad a megoldás.

Szemlétetésképp álljon itt egy táblázat, mely megmutatja, hogy két, adott maradékot adó halmazt egyben (fenn) vagy külön (lenn) megvéve mennyi a nyereségünk. Látható, hogy ha valamelyik részhalmaz maradéka is pozitív, akkor csak jól jöhetünk ki a szétbontással.

Ez az észrevétel jelentősen leegyszerűsíti egy (speciális szerkezetű) optimálios megoldás elkészítését.

Az előzőekből rögtön következik, hogy azon termékeket, amelyek már önmagukban is pozitív (vagy zérus) haszonnal járnak, nyomban megvehetjük egymagukban, külön. Így a továbbiakban már csak a negatív (-1) és (-2) maradékú termékekkel kell foglalkoznunk.

Tekintsük azt az esetet, amikor (-1)-es maradékúból több van, mint (-2)-esből! Szemléljük sorra, milyen csoportok szerepelhetnek egy optimális megoldásban! Az előbbiek alapján a csoportok, amelyek egyáltalán szóba jöhetnek:

A {-1,-1} ugyanaz, mint két {-1}, ezért azzal nem foglalkozunk. Azt állítjuk, hogy van olyan optimális megoldás, melyben sem {-2}, sem {-2,-2} csoport nem szerepel.

a.) Tegyük fel ugyanis, hogy az optimális megoldásban van egy {-2} csoport. Mivel (-1)-es maradékból több van, ezért kell, hogy legyen egy {-1} vagy egy {-1,-1,-1} csoport. Előbbit a (-2)-vel kombinálva 3 Ft veszteségből 2 Ft nyereséget csináltunk, tehát a megoldás nem lenne optimális, ellentmondás. Tehát egy {-1,-1,-1} van, amelynek 2 tagját a (-2)-re cserélve a nyereség nem változik, tehát a megoldás továbbra is optimális.

b.) Tegyük most fel, hogy az optimális megoldásban van egy {-2,-2} csoport. Mivel (-1)-es maradékból több van, ezért kell, hogy legyen legalább két {-1} vagy egy {-1,-1,-1} csoport. Előbbieket a két (-2)-vel ({-1,-2},{-1,-2}) kombinálva 1 Ft veszteségből 4 Ft nyereséget csináltunk, tehát a megoldás nem lenne optimális, ellentmondás. Ha egy {-1,-1,-1} van, akkor az előző módon párosítva a nyereség nem változik, tehát az átcsoportosítást végrehajtva a megoldás továbbra is optimális.

Tehát arra jutottunk, hogy van olyan optimális megoldás, melyben csak {-1,-2}, {-1} (nyilván legfeljebb 2 darab) és {-1,-1,-1} csoportok szerepelnek. Így az optimális csoportosítás már triviálisan elvégezhető: mivel (-2)-es önmagában nem állhat, ezért az összeset összepárosítjuk egy (-1)-essel, majd a maradék (-1)-esekből a lehető legtöbb hármas csoportot képezzük, az egy vagy kettő maradékot pedig egyenként vesszük meg.

Ha (-2) maradékú termékből van több, akkor hasonló érveléssel arra jutunk, hogy van olyan optimális megoldás, mely {-1,-2}, {-2} (legfeljebb 1) és {-2,-2} csoportokból áll. Tehát optimális csoportosítást kapunk a következő módon. Mivel (-1)-es önmagában nem állhat, ezért az összeset összepárosítjuk egy (-2)-essel, majd a maradék (-2)-esekből a lehető legtöbb kettes csoportot képezzük, az esetleges maradékot pedig egyedül vesszük meg.

Általános megoldás: Látható, hogy mindkét esetben a megoldáshoz először a lehető legtöbb {-1,-2} párt kell képezni, majd a maradékot kettesével (-2), vagy hármasával (-1) párosítani, amíg lehet, végül, ha még így is marad valami, azzal nem tudunk mit kezdeni.

A megoldást az alábbi képlettel megadhatjuk, ahol a '/' az egészosztás, a '%' pedig a maradékképzés jele:

M=min(m_-1,m_-2)

H=1^.m₁+2^.m₂+2^.M+1^.((m_-2-M)/2)+(-2)^.((m_-2-M)%2)+2^.((m_-1-M)/3)+(-1)^.((m_-1-M)%3)

A beérkezett megoldásokról

A feladatra sok szép megoldás érkezett, de sajnos nem kevés olyan is akadt, amely az esetek nagyrészében szuboptimális megoldást adott. A leggyakoribb tévedés az volt, hogy a beadott algoritmusok először {-1,-1,-1} és {-2,-2} csoportokat hoztak létre, és csak ezután próbálkoztak a {-1,-2} csoportokkal. Ezekre a megoldásokra - mivel az optimális csoportosítás kitalálása a feladat döntő részét képezte, a kód mindössze néhány sor volt - legfeljebb félpontszámot, azaz 5 pontot lehetett kapni.

A bemenet beolvasása sajnos sok versenyzőnek okozott kisebb-nagyobb problémát: bár mindenki be tudta olvasni jól a bemenetet, de néhányan ezt a két sorban elintézhető feladatot több tucat soros megoldássá bonyolították. Sokan karakterenként olvastak a bemenetről, és maguk próbálták a szóközök mentén azt szétbontani és számmá alakítani. Néhányan egyszerre beolvastak egy egész sort, és az így kapott sztringen dolgoztak. Ez utóbbi Pascal nyelv esetén komoly problémákhoz vezetett, lévén, hogy a Pascal-os string típus legfeljebb 255 hosszú szöveget képes tárolni.

Pedig, mint említettük, a bemenet beolvasása roppant egyszerűen megtehető: Pascal-ban egy integer típusú i változót feltételezve a read(i) utasítás a standard bemenetről beolvassa a következő számot. Mindössze ezt kellett volna használni az egyes sorokban szereplő számok számának meghatározására, majd egy for-ciklusban beolvasni ugyanígy a megfelelő számú további számot. C/C++-ban ennek a scanf("%d",&i), ill. a cin>>i utasítások felelnek meg.

Néhányan ellenőrizték a bemenet helyességét. Erről már sokszor volt szó (lásd: itt), és most is leszögezzük: a bemenetet ellenőrizni nem kell és nem is ajánlott.

Nagyon sokan nem tartották be a feladatban megadott be- és kimeneti specifikációt. Sok program különféle szövegekben értesítte a felhasználót arról, hogy milyen értékeket írjon be, majd törölte a képernyőt, a futás végén billentyűleütésre várt. A tesztelést igyekszünk automatizálni, de ennek lehetővé tételéhez ezeket a felesleges utasításokat minden esetben kézzel kell eltávolítanunk a programból, jelentősen megnövelve a javításhoz szükséges időt. Kérünk titeket, hogy ezeket az elkészült programból beküldés előtt legalább kommentezzétek ki!

A standard be- és kimenet és a billentyűzet és képernyő közti különbségről

Sajnos sokan nem tudjátok pontosan, mi is valójában a standard bemenet, és miben is különbözhet vajon a billentyűzettől. Ezért álljon itt egy kis ismertető.

A standard be- és kimenet nem más, mint 2 kommunikációs csővezeték elnevezése, melyek a legtöbb operációs rendszeren a program indulásakor automatikusan létrejönnek. Egy csővezetéknek értelemszerűen két vége van: egy író és egy olvasó vége. Ezek között a csővezeték egyirányú bájtfolyam-továbbítást végez: amit az egyik végén befolyik (beleírunk), a másik végén ugyanolyan formában kifolyik (kiolvasható).

A standard csővezetékek létezésének értelme, hogy így a program alapszinten minden további nélkül tud kommunikálni a külvilággal (felhasználóval), nem kell ehhez a programozónak esetlegesen sok-sok sor OS-specifikus kódot külön írni. Például: Pascal-ban a külön fáljparaméter nélküli readln, ill. writeln hívás (uses CRT nélkül!) a standard bementről olvas, ill. a standard kimenetre ír. Hasonlóan működik C-ben a printf() és scanf().

Ha a parancssorbol indítjuk az alkalmazást (mint szokásos), akkor sincs ez másként, a readln és writeln ugyanúgy a standard csatornákkal dolgozik, csak a standard bemenet csatorna írható vége rácsatlakozik a "billentyűzet", a stdout olvasható végére pedig a "képernyő".

Ezen csatornák további remek tulajdonsága, hogy természetesen nem csak a billentyűzetet/monitort lehet rájuk csatlakoztatni, hanem például egy másik programot is, vagy akár fájlba is irányíthatóak. Mint vélhetőleg rögtön kitalátátok, pontosan ez fog történni javítás során, ezért fontos, hogy a standard csatornákat haszáljátuk... és ne pedig a billentyűzetet, amely esetén automatizálnunk, meg kell hagyni, jóval nehezebb lenne.

Pascalban sokan már ösztönszerűen azzal kezditek a programot, hogy "uses crt". Ennek a sornak egy nagyon hátrányos mellékhatása az, hogy a read/write/readln/writeln ennek következményeként már nem a standard csővezetékekkel dolgozik, hanem "közvetlenül" a képernyőre ír és a billentyűzetről olvas. Így természetesen a tesztelést nem tudjuk elvégezni, ezért ezt is szinte minden egyes Pascal programból ki kell törölnünk.

Összefoglalva: Nektek mindössze annyi dolgotok van, hogy a programot Pascal-ban a CRT unit (s így a clrscr, readkey, keypressed, stb...), ill. C-ben a conio.h állomány használta nélkül készítitek el.

A javításkori helyes működésről azzal tudtok előre megbizonyosodni, hogy létrehoztok mondjuk egy innn_be.txt fájlt, lefordítjátok a programot pl. innn(.exe)-vé, majd a következő paranccsal úgy indítjátok el, hogy a program sztandard be- és kimenetére most ne a billentyűzet és képernyő csatlakozzon, hanem a megadott fájlok:

innn < innn_be.txt > innn_ki.txt

Ha ezzel a jó eredmény a kimeneti fájlba kerül, akkor a programotok a javítás során is elsőre jól fog működni, így a javítást számunkra számottevő mértékben egyszerűsítitek.

Reméljük, így már érthető, hogy miből fakadnak az elvárások, a jövőbeli együttműködéseteket pedig előre is köszönjük!

Engedy Balázs

Mintamegoldás

Hivatalos megoldás C++ nyelven: kerek.cpp

Földes Imre (Szolnok, Verseghy Ferenc Gimnázium) megoldása Pascal nyelven: I197.PAS

Statisztika:

14 dolgozat érkezett.
10 pontot kapott:	Fehér Péter, Földes Imre, Kővágó Zoltán.
9 pontot kapott:	Englert Péter.
8 pontot kapott:	2 versenyző.
6 pontot kapott:	1 versenyző.
5 pontot kapott:	3 versenyző.
4 pontot kapott:	2 versenyző.
3 pontot kapott:	1 versenyző.
1 pontot kapott:	1 versenyző.

A KöMaL 2008. novemberi informatika feladatai