CS2023_GYM - Editorial

editorial
,
1

PROBLEM LINK:

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

Author: himanshu154
Tester: jay_1048576
Editorialist: iceknight1093

DIFFICULTY:

TBD

PREREQUISITES:

None

PROBLEM:

N people (including Om) stand for an election, which has M voters.
What’s the minimum number of votes Om needs to receive to ensure that he has always has strictly more votes than any other contestant?

EXPLANATION:

If Om receives x votes, clearly the worst case is when a single other candidate receives all of the remaining M-x votes.

So, for Om to have strictly more votes than any other contestant, x \gt M-x must hold.
This means 2x \gt M, i.e, x should be strictly more than half of M.

From here, it can be seen that:

  • If M is even, the smallest valid x is \frac{M}{2} + 1.
  • If M is odd, the smallest valid x is \frac{M+1}{2}.

Both cases can be put together into the simple formula

\left \lfloor \frac{M}{2} \right\rfloor + 1

where \left \lfloor \ \cdot \ \right\rfloor denotes the floor function.

TIME COMPLEXITY

\mathcal{O}(1) per testcase.

CODE:

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