# BIN_BAT - Editorial

Author: Gaurav Somai
Testers: Hriday, Utkarsh Gupta
Editorialist: Nishank Suresh

786

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) or log2(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)

1 Like