ACPC10E - Sometimes, a penalty is good!

no tags 

FIFA is considering a few changes to the way it organizes the Football World Cup. Currently, 32 teams compete for the World Title in two stages. During the first stage, known as the groups stage, the 32 teams are split evenly into 8 groups. Every team in the group plays 3 games, one against each team in their own group. Teams are then ranked within their group according to some points system. During the second (and final) stage, the top two teams from each group advance to the knockout stage where eight games are played to determine eight winners who would then play four games to determine four winners, then two games to determine the two winners who would then play the final game to determine the world champion. Needless to say, for the knockout stage to work, the number of teams in that stage has to be a power of two. FIFA is considering adding more groups, adding more teams to groups, and possibly changing the number of teams advancing from each group to the knockout stage. In addition, FIFA is considering having certain teams (previous champion, host country, etc.) advance to the knockout stage directly (without having to play in the groups stage.) But FIFA needs to know how many games will be played if any of these changes are applied. Please help them!

Input

Your program will be tested on one or more test cases. Each test case is specified on a single line made of 4 natural numbers with the following format:
G T A D
Where (G > 0) is the number of groups; T is the number of teams in each group; A is the number of teams advancing from each group to the knockout stage; and D is the number of teams directly advancing to the knockout stage without going through the groups stage. Note that (0 < A ≤ T) and that the four numbers in the input are no larger than 216.
If the total number of teams in the knockout stage is not a power of two, your program must increase them to the closest power of two.
The last test case is followed by a dummy line made of four -1’s.

Output

For each test case, print:
G*A/T+D=X+Y
where G, A, T, and D are as in the input, X is the total number of games, and Y is the number of teams your program determined it must add.

Example

Input:
8 4 2 0
8 4 2 1
-1 -1 -1 -1

Output:
8*2/4+0=63+0
8*2/4+1=79+15

hide comments
nadstratosfer: 2017-09-19 03:01:51

Notice, no match for 3rd place in this problem.

surajmall: 2016-12-10 09:58:45

how can i use log in the programming

pranjalikumar9: 2016-06-08 00:50:18

log +ceil works..but use round with inbuilt functions like pow

SangKuan: 2015-08-28 10:27:50

why log will got wa,and ac without log

Swapnil Borse: 2015-01-08 12:50:42

2^16 is the only thing you need to keep an eye on.. Rest is a piece of cake!!! :)

Aragon!!!: 2014-08-13 20:46:25

bitwise is a gods gift :D

Francis: 2014-05-14 16:25:33

pay attention to overflow

cegprakash: 2013-12-19 08:07:52

For kids..

Paul Draper: 2012-12-01 19:40:52

@Nitesh Vijayvargiya
Even if T=A, all the first stage games are still played (even though they aren't necessary).

saket diwakar: 2012-07-03 08:46:19

easy...


Added by:Omar ElAzazy
Date:2010-11-30
Time limit:2.633s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:ACPC 2010