Mathematical and Physical Journal
for High Schools
Issued by the MATFUND Foundation
Already signed up?
New to KöMaL?

Problem I. 197. (November 2008)

I. 197. We are buying N different items in a shop, not necessarily at once, but during several purchases. From March 1, 2008 in Hungary, the final Forint (HUF) sum of a purchase has to be rounded off to the nearest integer multiple of 5 HUF. Knowing the prices of items, write a program to decide which items should be bought during which purchase such that our loss due to these rounding-offs is minimized.

The number of products and their prices are read from the standard input. Each line of the input contains a list of items to be purchased: the number N of items (1\le N\le 10\;000), then their prices a1,...,aN (positive integers, separated by a space). The total sum in each line is at most 1\;000\;000\;000. The end of input is denoted by a line containing a single ``0''.

The output is written to the standard output. Each line of the output corresponds to a line in the input, and contains a single integer: our gain or loss in HUF due to the rounding-offs if optimal purchases are made.

In the table, ``Példabemenet'' is the input and ``Példakimenet'' is the output.

The source code of your program (i197.pas, i197.cpp, ...) together with a short documentation (i197.txt, i197.pdf, ...) should be submitted, also containing a brief description of your solution and the name of the developer environment to use for compiling the source code.

(10 pont)

Deadline expired on December 15, 2008.


Sorry, the solution is available only in Hungarian. Google translation

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.

Ár Maradék (haszon)
5n+0 0
5n+1 1
5n+2 2
5n+3 -2
5n+4 -1

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:

{-2}
{-2,-2}
{-1}
{-1,-1,-1}
{-1,-2}

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.m1+2.m2+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


Statistics:

14 students sent a solution.
10 points:Fehér Péter, Földes Imre, Kővágó Zoltán.
9 points:Englert Péter.
8 points:2 students.
6 points:1 student.
5 points:3 students.
4 points:2 students.
3 points:1 student.
1 point:1 student.

Problems in Information Technology of KöMaL, November 2008