Connection Status:
Competition Arena > TrueSpace

TrueSpace

SRM 412 · 2008-07-30 · by Eryx

SRM 412 · 2008-07-30 · by Eryx · Simple Math
Class Name: TrueSpace
Return Type: long
Method Name: calculateSpace
Arg Types: (vector<int>, int)
Problem Statement

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.

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)
{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}
1
Returns: 50000000000
6)
{260844,617641,205960,567972,592354,499766,435409,567914,683671,95617,898318,942144,236648,713334,930102,308390,733928,807120,487516,531978,827868,932072,733863,438663,483441,921054,297557,794280,845828,776964,404638,196631,40792,391314,992076,702782,507926,588927,380611,606595,743208,141150,808570,807098,555953,77029,434842,321403,322303,483226}
435409
Returns: 38751401

a random test case

Submissions are judged against all 81 archived test cases, of which 6 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class TrueSpace with a public method long long calculateSpace(vector<int> sizes, int clusterSize) · 81 test cases · 2 s / 256 MB per case

Submitting as anonymous