CUTCAKE - Eat all the brownies !
BrownieDude was given the job of cutting cake at a party for serving the guests. But BrownieDude is both lazy and hungry, so he wants to cut the cake into maximum number of pieces with minimum number of cuts and go off to eating brownies.
The host of the party says that BrownieDude can cut the cake into unequal pieces but cannot cut in more than one plane. (Only vertical cuts are allowed.) Given the number of guests, find the number of cuts sufficient to generate the cake pieces.
Input
First line contains 't', the number of test cases. 't' lines follow. (1 ≤ t ≤ 1000)
Each line denotes the number of guests. (1 ≤ n ≤ 1011)
Output
One number denoting the number of cuts.
Note: It is guaranteed that an integer solution will always exist.
Example
Input: 2 1 2 Output: 0 1
Explanation for test cases: If there is only one guest, there is no need to cut the cake. If there are 2 guests, the cake can be cut into 2 pieces in 1 cut.
hide comments
Girish Rathi:
2014-01-24 19:21:14
the cake can even be square or circular but think about getting maximum cut in each step.. |
|
Girish Rathi:
2014-01-24 18:40:51
12th mathematics.... Last edit: 2014-01-24 19:19:59 |
|
sarelfeniel:
2014-01-24 08:56:32
Dumb mistake but easy easy problem. Classical discrete mathematics problem! |
|
Abhinav Gupta:
2014-01-23 20:28:16
AC :) Learned something new. Last edit: 2014-01-24 09:46:24 |
|
Abhinav Gupta:
2014-01-23 20:18:15
Where it is given that cake is circular in shape?? |
|
rb:
2014-01-21 21:02:50
A/C in 1st attempt. |
|
Alei Reyes:
2014-01-15 22:37:49
This problem was first solved in 1826, by the Swiss mathematician Jacob Steiner
|
|
Ouditchya Sinha:
2014-01-09 15:06:21
Not as simple as it looks! :) |
Added by: | Pandian |
Date: | 2013-12-19 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All |