PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: negativecode
Tester: sushil2006
Editorialist: iceknight1093
DIFFICULTY:
Cakewalk
PREREQUISITES:
None
PROBLEM:
There are N bottles, each with a capacity of X liters. The i-th bottle has A_i liters of water initially.
You can transfer water between bottles. What’s the minimum number of bottles needed to store all the water?
EXPLANATION:
Let \text{total} denote the total amount of water with us.
This can be computed as \text{total} = A_1 + A_2 + \cdots + A_N.
Each bottle can carry X liters of this water, so we need \frac{\text{total}}{X} bottles to carry all the water; plus maybe one extra if \text{total} is not a multiple of X since there will be a little bit leftover.
This can be represented by the ceiling function: the answer is
TIME COMPLEXITY:
\mathcal{O}(N) per testcase.
CODE:
Editorialist's code (PyPy3)
for _ in range(int(input())):
n, x = map(int, input().split())
a = list(map(int, input().split()))
total = sum(a)
reqd = (total + x - 1) // x
print(reqd)