DWITE Online Computer Programming Contest
February 2006

Problem 2

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

Sample Output

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.

All Submissions
Best Solutions

Point Value: 10 (partial)
Time Limit: 1.00s
Memory Limit: 16M
Added: Nov 13, 2008

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)