BALLSAG - Ball Stacking Again

no tags 

The XYZ TV channel is developing again a new game show, where a contestant has to make a
choice in order to get a prize. The game consists of a triangular stack of balls, each of them having an
integer value, as the following example shows:

The contestant must choose exactly one ball and his prize is the sum of the value of that ball and
the balls directly on top of it. Notice that the prize can be negative!
Your friend is going to participate on the game show, and he wants you to develop a program that
can tell the maximum prize possible.

Input

Each test case is described using several lines. The first line contains an integer N representing
the number of rows of the stack ( 0 < N < 1001). The i-th of the next N lines contains i integers Bij ( -
1000 <= Bij <= 1000 for 1 <= j <= i <= N); the number Bij is the value of the j-th ball in the i-th row of
the stack (the first row is the topmost one, and within each row the first ball if the leftmost one). After
each test case there is a blank line.
The last test case is followed by a line containing one zero.

Output

For each test case output a line with an integer representing the maximum prize a contestant can
make from the stack.

Example

Input:
2
-2
1 -10

3
1
-5 3
6 -4 1
0

Output: -1
5

Note:
On the first test case, the optimal solution is to take the ball with value 1, making you remove the ball
with value -2, resulting in -1.
On the second test case the best option is to take the ball with value 1 on the bottom row, resulting in
1+3+1 = 5.

hide comments
Satyaki Upadhyay: 2014-10-29 09:13:12

Last edit: 2014-10-29 09:22:27
vishwas: 2013-06-22 03:52:42

Last edit: 2013-06-22 03:54:40
ZODI91: 2012-08-22 16:03:47

easy one :)

PANKAJ SAINI: 2012-07-12 03:10:48

hey, what is happening there,
I used DP which cannot give a wrong answer, and tested on lot many test cases too...

but getting wrong answer..

any special trick??

npsabari: 2012-06-28 21:30:11

Any Tricky Case? Got many WA :(
Though it is just DP!
@problem setter: can you tell me in what case my code goes wrong..
code id: 7229327

EDIT: Little trick! Everyone getting WA, try to write bruteforce code and check with small inputs.

Last edit: 2012-09-07 20:35:29
Noszály Csaba: 2012-06-06 07:23:13

hi,
I interpret the interpretation of Mitch as follows: for
each element compute the union of (and the sum of its
values) elements which can be reached by left up or right
up moves (if the move can be done) + the value of actual
node. The answer is the maximum of these values. Am i miss
something?
regards, ncs

--> nevermind, found a mistake (return an int
instead a bool in a method :() in my prog.
Mitch's explanation is really fix the description.

Last edit: 2012-06-06 08:20:19
Mitch Schwartz: 2012-02-11 14:02:46

Yes, I also found the text confusing but managed to guess the meaning. The text uses the term "directly on top of" so I'll use the same term, even though it's a bit misleading. Consider this triangle

1
2 3
4 5 6
7 8 9 10
11 12 13 14 15

1 has no balls directly on top of it.
2 has 1 directly on top of it.
5 has 1,2,3 directly on top of it.
8 has 1,2,3,4,5 directly on top of it.
13 has 1,2,3,4,5,6,8,9 directly on top of it.

Hope this helps everyone understand.
@thanks man.

Last edit: 2012-02-11 16:40:59
Ikhaduri: 2012-02-11 08:41:32

fix the problem description, it's impossible to understand.

Tornike Mandzulashvili: 2012-02-11 06:59:45

What "on the top" means ?

Last edit: 2012-02-11 07:00:03

Added by:Paulo Costa
Date:2012-02-09
Time limit:0.858s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:ICMC-USP