Codingame Solution: Bank Robbers

Original Problem

A gang of \(R\) foolish robbers decides to heist a bank. In the bank there are \(V\) vaults (indexed from \(0\) to \(V - 1\)). The robbers have managed to extract some information from the bank's director:

• The combination of a vault is composed of \(C\) characters (digits/vowels).
• The first \(N\) characters consist of digits from \(0\) to \(9\).
• The remaining characters consist of vowels (A, E, I, O, U).
• \(C\) and \(N\) may be the same or different for different vaults.

All the robbers work at the same time. A robber can work on one vault at a time, and a vault can be worked on by only one robber. Robbers deal with the different vaults in increasing order.

A robber tries the combinations at the speed of 1 combination per second. He tries all the possible combinations, i.e. he continues to try the untried combinations even after he has found the correct combination. Once he finishes one vault, he moves on to the next available vault, that is the vault with the smallest index among all the vaults that have not been worked on yet. The heist is finished when the robbers have worked on all the vaults.

Assume it takes no time to move from one vault to another.

You have to output the total time the heist takes.

Input
Line 1: An integer R for the number of robbers.
Line 2: An integer V for the number of vaults.
Next \(V\) lines: For each vault, one line of two space-separated integers \(C\) and \(N\) for the total number of characters (\(C\)) and the total number of digits (\(N\)) in the vault's combination. The vaults are ordered by their index.

Output
Line 1: An integer for the total time the heist takes in seconds.

Constraints
1 ≤ \(R\) ≤ 5
1 ≤ \(V\) ≤ 20
3 ≤ \(C\) ≤ 8
0 ≤ \(N\) ≤ \(C\)

Solution

The number of combinations a code of length \(C\) can form if the first \(N\) characters can be made of 10 digits, followed by 5 vowels is

\[\begin{array}{rl} 10^N \cdot 5^{C - N} &= 5^N \cdot 2^N \cdot 5^C \cdot 5^{-N}\\ &= 2^N \cdot 5^C\\ &= 5^C << N \end{array}\]

Where \(<<\) is the binary left-shift operator. We now need an iterative process. When we track the time every robber works, we allocate each new vault to the one which will finish the first with the previous vault. When we have finished all vaults, we can say that the robber who needs to work the longest this way must be the total amount of time the heist takes.

const R = +readline();
const V = +readline();

const times = [];
let total = 0;

for (let i = 0; i < V; i++) {

  const [C, N] = readline().split` `;

  let ndx = i;

  if (i < R) {
    // Grow times array until every robber has a vault
    times.push(0);
  } else {
    // Find vault which has minimum amount of time (first R rounds it's always the last)
    ndx = times.indexOf(Array.min(...times));
  }
  // Add the time to the robber with the smallest amount of time
  times[ndx]+= 5**C << N;
  // Calculate the total amount of time as the maximum over all robbers
  total = Math.max(total, times[ndx]);
}

print(total);