Sinking TimeProblem code: DCE01 |
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.
A sector can only drown when one 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
"a" will drown when both "b" and "c" are drowned.Input
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(
The next k lines contain the integers denoting the time taken for the sectors in k-th level to drown completely.
Output
Display t lines each having the single integer, the total time after which, the ship will be completely submerged in water.
Example
Input: 1 7 2 3 2 3 1 7 5 9 6 4 6 5 4 7 2 Output: 33
Explanation: 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.
| Author: | uploader0 |
| Date Added: | 14-10-2009 |
| Time Limit: | 1 - 3 sec |
| Source Limit: | 50000 Bytes |
| Languages: | ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.0.0-8, CPP 4.3.2, CS2, D, F#, FORT, GO, HASK, ICK, ICON, JAR, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.1.2, RUBY, SCALA, SCM guile, SCM qobi, ST, TEXT, WSPC |
Comments
SUCCESSFUL SUBMISSIONS FOR THIS PROBLEM:
Fetching successful submissions
For each test case, the first
For each test case, the first line contains three integer
The three integers are n,k and what??
It is the sector number
It is the sector number (1-based) in the lower most level that has taken the damage