TopCoder problem "TrueSpace" used in SRM 412 (Division II Level One)



Problem Statement

    In some filesystems, the disk space used by a file is not always equal to the file's size. This is because the disk is divided into clusters of equal size, and each cluster can only be used by a single file. For example, if the cluster size is 512 bytes, and we have a file of size 600 bytes, it would have to be stored in two clusters. Those two clusters cannot be shared with any other files, so the file ends up using 1024 bytes of disk space.



You are given a int[] sizes, where each element is the size of a single file, and an int clusterSize, the cluster size of the filesystem. Return the total disk space used by the given files.
 

Definition

    
Class:TrueSpace
Method:calculateSpace
Parameters:int[], int
Returns:long
Method signature:long calculateSpace(int[] sizes, int clusterSize)
(be sure your method is public)
    
 

Constraints

-sizes will contain between 1 and 50 elements, inclusive.
-clusterSize will be between 1 and 1,048,576, inclusive.
-Each element of sizes will be between 0 and 1,000,000,000, inclusive.
 

Examples

0)
    
{600}
512
Returns: 1024
From the problem statement.
1)
    
{16,32,128,128,0}
32768
Returns: 131072
We waste a lot of space here. (Note that we don't need any clusters for a file of size 0.)
2)
    
{4096, 33792, 76800}
1024
Returns: 114688
We don't waste any space here.
3)
    
{1000000000, 1000000000, 1000000000, 1000000000,
 1000000000, 1000000000, 1000000000, 1000000000,
 1000000000, 1000000000, 1000000000, 1000000000,
 1000000000, 1000000000, 1000000000, 1000000000,
 1000000000, 1000000000, 1000000000, 1000000000,
 1000000000, 1000000000, 1000000000, 1000000000,
 1000000000, 1000000000, 1000000000, 1000000000,
 1000000000, 1000000000, 1000000000, 1000000000,
 1000000000, 1000000000, 1000000000, 1000000000,
 1000000000, 1000000000, 1000000000, 1000000000,
 1000000000, 1000000000, 1000000000, 1000000000,
 1000000000, 1000000000, 1000000000, 1000000000,
 1000000000, 1000000000}

1048576
Returns: 50017075200
4)
    
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}
8
Returns: 0

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=8477

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=13503&pm=8477

Writer:

Eryx

Testers:

PabloGilberto , Olexiy , Andrew_Lazarev , ivan_metelsky

Problem categories:

Simple Math