Connection Status:
Competition Arena > Truckloads

Truckloads

SRM 284 · 2006-01-21 · by dgoodman

SRM 284 · 2006-01-21 · by dgoodman · Recursion, Simple Math
Class Name: Truckloads
Return Type: int
Method Name: numTrucks
Arg Types: (int, int)
Problem Statement

Problem Statement

We have a pile of crates at our warehouse that we want to load onto trucks. Our plan is to divide the pile in half forming two smaller piles, then continuing dividing each of the small piles in half until we get piles that will fit on a truck. (Of course, when we divide an odd number of crates in "half", one of the resulting piles will have one more crate than the other.) Our problem is to determine how many trucks we will need to ship the crates.

Create a class Truckloads that contains a method numTrucks that is given numCrates (the number of crates at the warehouse) and loadSize (the maximum number of crates that will fit in a truck) and that returns the number of trucks required.

Constraints

  • numCrates will be between 2 and 10,000, inclusive.
  • loadSize loadSize will be be between 1 and (numCrates - 1), inclusive.
Examples
0)
14
3
Returns: 6

After the first division we have two piles each with 7 crates. Each of these piles must be divided giving us 2 piles of 3 and 2 piles of 4. The piles with 4 crates must be further divided giving us 2 piles of 3 and 4 piles of 2. Each of these piles fits into a truck, so we need 6 trucks.

1)
15
1
Returns: 15

We will eventually end up with 15 piles, each with just 1 crate.

2)
1024
5
Returns: 256

1024 divides in half very nicely. We eventually end up with 256 piles, each containing 4 crates.

3)
10000
79
Returns: 128
4)
894
22
Returns: 64

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

Coding Area

Language: C++17 · define a public class Truckloads with a public method int numTrucks(int numCrates, int loadSize) · 41 test cases · 2 s / 256 MB per case

Submitting as anonymous