MINCOUNT - Move To Invert

no tags 

A triangle made of coins of height h is as follows
It has h coins at the base and h-1 coins one level above base and so on.(Coins are placed as shown in the figure below)
And at the top most level there will be only one coin
Now given h the task is to invert this triangle by moving minimum number of coins. For example when h=4 triangle is
Invert
For h=4 at least 3 coins must be moved to invert it.

Input

In the first line N will be given and then N lines follow with each line having a integer which is the height of triangle in that test case.00≤h<1010;

Output

For each test case output in a seperate line the minimum number of moves required to invert the triangle. Output fits in long long data type

Example

Inputt:
1
3

Output:
2

hide comments
:(){ :|: & };:: 2010-04-07 05:05:36


I wonder if there is any programmatic solution for this task, since all I used is simple math.

vimal raj sharma old account: 2010-03-21 18:53:56

@Sergey Ushacov

how are u saying that correct ans. for 10000000000 is 7 443 294 631 478 557 525

i think that
"dreivaj (Slash at the moment)"'s
solution is right mine is also giving the same
:)

Zubaidullo: 2010-03-12 06:33:04

yehhhh. I have AC. (i use STADIO.H with float)

Core2Duo: 2010-02-14 14:32:08

The test cases dont seem to be having inputs till 10^10.
The correct ans for 10^10 cannot b stored in long long int in C++, still I get AC!

☻Daniel Alberti Proenza☻: 2010-01-26 13:19:22

What is the correct answer for h = 10 and h = 11?

Super Lại Mạnh Tuấn: 2010-01-20 07:55:31

What is the correct answer for h=6 and h=7 ?

Last edit: 2010-01-20 08:05:41
Sergey Ushacov: 2009-10-07 18:04:36

The correct answer for h = 10000000000 is
7 443 294 631 478 557 525

Javier (dreivaj): 2009-08-28 03:46:11

Some outputs
0 = 0
1 = 0
.......
10000000000 = 16666666668333333333

Last edit: 2009-08-28 03:47:47
LeppyR64: 2009-06-08 16:41:57

top row = 1, second row = 2 3, third row = 4 5 6, fourth row = 7 8 9 10 Solution: move 7 to the left of 2, move 10 to the right of 3, move 1 below 8&9

Last edit: 2009-06-08 16:42:32
~!(*(@*!@^&: 2009-06-03 05:29:50

someone can explain the example in the image? i need 4 moves for h=4 (image), but they need 3.
Edit: thanks Nosaj.

Last edit: 2009-06-11 17:42:24

Added by:Abhilash I
Date:2006-12-16
Time limit:0.325s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO
Resource:IIIT Hyderabad Local Programming Contest