DWITE Online Computer Programming Contest
Floppy Disk 3½-inch High Density
Over the course of approximately 35 years, floppy disks have evolved from 8 inches in size down to 3½ inches. Their storage capacity ranged from 80 kilobytes (KB) to 240 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 3½-inch 1.44 MB capacity disk.
Your job in this problem is to put files onto the 3½-inch 1.44 MB capacity disk so that there is minimum amount of unused space left on the floppy disk.
The input will contain five sets of data. Each set begins with an integer N, the number of files available to go onto the floppy disk, 1 ≤ N ≤ 25. The next N lines, for each set, will contain an integer S, the size in kilobytes (KB) of each of the files, 1 ≤ S ≤ 1440.
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
40 35 28
Sample Input Analysis
In the first set, the files with sizes 1000 and 400 use up the most storage space on the diskette.
In the second set, the files with sizes 650, 500, 233 and 22 use up the most storage space on the diskette.
In the third set, the files with sizes 599, 578 and 235 use up the most storage space on the diskette.
Point Value: 10 (partial)
Time Limit: 1.00s
Memory Limit: 16M
Added: Nov 13, 2008
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3