KöMaL - Középiskolai Matematikai és Fizikai Lapok
Sign In
Sign Up
 Magyar
Information
Contest
Journal
Articles

 

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 15 January 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 tesztfileok.zip tömörített állományban lévő forrásokkal teszteltük (a mintamegoldás kimenetele is itt található).


Statistics:

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.

Our web pages are supported by:   Ericsson   Cognex   Emberi Erőforrás Támogatáskezelő   Emberi Erőforrások Minisztériuma   Nemzeti Tehetség Program    
MTA Energiatudományi Kutatóközpont   MTA Wigner Fizikai Kutatóközpont     Nemzeti
Kulturális Alap   ELTE   Morgan Stanley