ROOMALLOC - Editorial

editorial
,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: raysh07
Tester: apoorv_me
Editorialist: iceknight1093

DIFFICULTY:

TBD

PREREQUISITES:

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