PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: Gaurav Somai
Testers: Hriday, Utkarsh Gupta
Editorialist: Nishank Suresh
DIFFICULTY:
786
PREREQUISITES:
None
PROBLEM:
N players play in a single-elimination tournament. Each round takes A minutes, and there is a B-minute break after every round except the last.
How much time does the tournament take?
EXPLANATION:
We are given that N is a power of 2, so let N = 2^k.
Note that the tournament has exactly k rounds.
For these k rounds:
- Each one takes A minutes
- All but the last have a further break of B minutes
This gives us a total time of
k\cdot A + (k-1)\cdot B
The only thing that remains is to correctly compute k.
This can be done in many ways:
- You can iterate k on a loop and check if 2^k = N
- Alternately, most languages have builtin functions to compute this, for example:
-
__lg(N)
orlog2(N)
in C++ -
N.bit_length()-1
in Python
-
Once k is computed, use the formula above.
TIME COMPLEXITY
\mathcal{O}(1) per test case.
CODE:
Setter's code (C++)
#include <bits/stdc++.h>
using namespace std;
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int t;
cin>>t;
while(t--){
int n,a,b;
cin>>n>>a>>b;
int k = log2(n);
int ans = (a*k)+(b*(k-1));
cout<<ans<<"\n";
}
return 0;
}
Editorialist's code (Python)
for _ in range(int(input())):
n, a, b = map(int, input().split())
rounds = n.bit_length() - 1
print((rounds-1)*(a+b) + a)