# ROOMALLOC - Editorial

Author: raysh07
Tester: apoorv_me
Editorialist: iceknight1093

TBD

None

# PROBLEM:

Teams from N colleges attend jadavpur University’s fest. The i-th team has A_i members.
Each room can accommodate two people, and students from different colleges will not stay in the same room.
What’s the minimum number of moves needed to accommodate everyone?

# EXPLANATION:

Since people from different colleges won’t share a room, we can find the number of rooms needed for each college separately and add them up to get the overall answer.

So, look at a college team with A_i members. Since each room can hold two people:

• If A_i is even, \frac{A_i}{2} rooms will suffice.
• If A_i is odd, \frac{A_i + 1}{2} rooms are needed (one extra room for the extra person).

This can be written as \left\lceil \frac{A_i}{2} \right\rceil, where \left\lceil \ \ \right\rceil denotes the ceiling function.
The overall answer is thus

\sum_{i=1}^N \left\lceil \frac{A_i}{2} \right\rceil

# TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

# CODE:

Editorialist's code (Python)
for _ in range(int(input())):
n = int(input())
print(sum([(x+1)//2 for x in map(int, input().split())]))

1 Like