DWITE Online Computer Programming Contest, February 2006, Problem 2
Over the course of approximately 35 years, floppy disks have evolved
from inches in size down to
inches. Their storage capacity ranged
from
kilobytes (KB) to
megabytes (MB). Most recently they are
becoming extinct, with floppy disk drives being an optional accessory
with the purchase of a new computer.
One of the more commonly used floppy disks during its time, was the
-inch
MB capacity disk.
Your job in this problem is to put files onto the -inch
MB
capacity disk so that there is the minimum amount of unused space left on
the floppy disk.
The input will contain five sets of data. Each set begins with an
integer , the number of files available to go onto the floppy disk,
. The next
lines, for each set, will contain an
integer
, the size in kilobytes (KB) of each of the files,
.
The output will contain five lines of data. Each line will contain the minimum amount of unused space left on the floppy disk.
Sample Input (3 sets of data only)
5
1000
500
100
150
400
6
500
233
650
75
22
875
4
235
578
900
599
Sample Output
40
35
28
Sample Input Analysis
In the first set, the files with sizes and
use up the most
storage space on the diskette.
In the second set, the files with sizes ,
,
and
use up the
most storage space on the diskette.
In the third set, the files with sizes ,
and
use up the most
storage space on the diskette.
Comments