Codechef•May 28, 2025

Binary Battles

Hazrat Ali

Codechef

In one round, each team will be paired up with and compete against one of the other teams. If there are XX teams before the start of a round, X22X​ matches are held simultaneously during the round between X22X​ pairs of teams. The winning team of each match will move on to the next round, while the losing team of each match will be eliminated. There are no ties involved. The next round will then take place in the same format between the remaining teams. The process will continue until only one team remains, which will be declared the overall winner.

The organizers want to find the total time the event will take to complete. It is given that each round spans AA minutes, and that there is a break of BB minutes between every two rounds (no break after the last round).

For example, consider a case when N=4, A=10 and B=5. The first round will consist of two matches and will take 1010 minutes to complete. Two teams move on to round 2 and the other two get eliminated. Then there is a break of 55 minutes. The two remaining teams compete in round 2, which lasts 1010 more minutes. The team that wins is declared the overall winner. Thus the total time taken is 10+5+10=25 minutes.

Can you help the organizers determine how long the event will take to finish?

Input Format

  • The first line of input will contain a single integer TT, denoting the number of test cases. Then the test cases follow.
  • The first and only line of each test case contains three space-separated integers NN, AA and BB respectively — the number of teams, the duration of each round and the length of the breaks between rounds.

Output Format

For each test case, output on a new line the time taken in minutes for the whole event to finish.

Constraints

  • 1≤T≤105
  • 2≤N≤220
  • 1≤A≤100
  • 1≤B≤100
  • NN is a power of 22.

Sample 1:

Input 
4
4 10 5
16 30 5
32 45 15
1024 23 9

Output
25
135
285
311

Solution
for _ in range(int(input())):
    x,y,s=map(int, input().split())
    i=1
    z=0
    while i<x:
        if 2**i==x:
            z=i
            break
        else:
            i+=1
    print(y*z + s*(z-1))




 

Comments