Bit Party

Design a hardware module for the Bit Party problem used in this repository.

You are given:

• r: how many cashiers may be chosen
• b: a total time budget
• c: a list of cashier tuples (m, s, p)

For a target bit count x, cashier (m, s, p) needs

s + min(m, x) * p

time units.

Among all cashiers, take the r smallest such times and add them together. Your task is to output the largest x whose summed time is at most b.

Hardware I/O Encoding

• r is a scalar unsigned 32-bit integer
• b is a scalar unsigned 32-bit integer
• c is a one-dimensional stream of cashier tuples (m, s, p)
• each tuple field is an unsigned 32-bit integer
• the stream length is at most 8
• the output is one unsigned 64-bit integer

Examples

Example 1

• input r = 1, b = 3, c = [(2, 1, 1)]
• output: 2

For x = 2, the only cashier takes 1 + min(2, 2) * 1 = 3, which fits the budget.

Example 2

• input r = 1, b = 3, c = [(5, 2, 1)]
• output: 1

x = 1 takes 3, but x = 2 would take 4, so the largest valid result is 1.

Example 3

• input r = 2, b = 8, c = [(5, 2, 1), (8, 4, 3)]
• output: 0

Even x = 1 needs times 3 and 7, and 3 + 7 = 10, which exceeds the budget.

Source: Google Code Jam 2018 Round 1A - Bit Party