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

Problem I. 172. (December 2007)

I. 172. There is a ``winter sale'' at a shop, so one gets a voucher of value 100 HUF if one purchases goods for more than 3000 HUF. The voucher can be redeemed at a next purchase. We plan to buy some items in that shop and want to exploit those vouchers optimally: we may visit the shop more than once and regroup the items as necessary in order to minimize the total amount we pay, that is, to get the maximal number of vouchers.

Prepare your program to group items (at most 100) to be bought, such that we get the maximal number of vouchers (that is, the total amount we pay is minimal). Each line of the input text file contains the identifier of each item (a 6-digit number) and its price (between 10 HUF and 50 000 HUF) separated by a space. The first command line argument of your program is the name of the input file, while the second argument is the name of the output file. The output file should only contain the amounts to pay at different purchases, each occasion in a separate line, finally, the total amount in the last line.

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

(10 pont)

Deadline expired on January 15, 2008.

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

A feladat megoldása a mellékelt, alapos kommentezéssel ellátott Pascal programban I172MO.PAS olvasható, lényege:

- a 3000 Ft-nál értékesebb termékeket egyszerűen egyesével megvesszük,

- a maradék termékekből megpróbáljuk a legkisebb elemszámú, legkisebb értékű 3000 Ft-ot elérő termékcsoportkat összeállítani.

A beküldött megoldásokat az alábbi tömörített állományban lévő forrásokkal teszteltük (a mintamegoldás kimenetele is itt található).


6 students sent a solution.
9 points:Földes Imre, Horváth 135 Loránd.
8 points:1 student.
7 points:1 student.
6 points:1 student.
3 points:1 student.

Problems in Information Technology of KöMaL, December 2007