Under the moon light, over the smooth dark water surface, Titanic was sailing along. Quite beautifully, wih sparkling light, it seemed to be flying.
But air does not have ice bergs.
A sudden crashing sound and a piece of ice floating by. But the depth is far greater than what it looks on the surface.
Our ship is hit and has taken serious damages. The iceberg has damaged one of the sectors in the lowermost level. ( Where were the Lookers looking from the Look Out?? !! )
The captain has assigned you the job of finding the total time in sinking of the ship.
The ship is considered sunk only when all the sectors at all levels are drowned completely in water.
A ship is represented in sectors as below:
+ + + + + + + + + + + +
n is the number of sectors in the topmost level, k is the number of levels.
The first(topmost) level contains n sectors, 2nd contains n-1 sectors, and the k-th(lowermost) sector contains n-k+1 sectors.
Water starts getting into a sector only when one(or both) of the following conditions are met:
* a neighbor of the sector is completely drowned.
* both the sectors under a sector are completely drowned.
+ a + b c
Here, "a" will drown when both "b" and "c" are completely drowned. OR either of the neighbors ( + ) are completely submerged into water.
The first line contains the number of test cases (about 10). t test cases follow.
For each test case, the first line contains three integers n(<=1000), k(
Display t lines each having the single integer, the total time after which, the ship will be completely submerged in water.
Input: 1 7 2 3 2 3 1 7 5 9 6 4 6 5 4 7 2 Output: 33
The sinking time of all the sectors for this example are:
17 15 12 16 21 27 33 15 11 5 9 16 18
Hence the answer 33.
|Time Limit:||0.20155 - 0.35 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, JAVA, PYTH, CS2, PAS fpc, PAS gpc, RUBY, PHP, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, SQL, TEXT|
Fetching successful submissions