SUMITR - Sums in a Triangle
Let us consider a triangle of numbers in which a number appears in the first line, two numbers appear in the second line etc. Develop a program which will compute the largest of the sums of numbers that appear on the paths starting from the top towards the base, so that:
- on each path the next number is located on the row below, more precisely either directly below or below and one place to the right;
- the number of rows is strictly positive, but less than 100;
- all numbers are positive integers between 0 and 99.
Take care about your fingers, do not use more than 256 bytes of code.
Input
In the first line integer n - the number of test cases (equal to about 1000). Then n test cases follow. Each test case starts with the number of lines which is followed by their content.
Output
For each test case write the determined value in a separate line.
Example
Input: 2 3 1 2 1 1 2 3 4 1 1 2 4 1 2 2 3 1 1 Output: 5 9Warning: large Input/Output data, be careful with certain languages
hide comments
|
ashishranjan28:
2016-10-29 12:16:17
lol...
|
|
umohan:
2016-08-26 20:28:27
no submission in java |
|
nonushikhar:
2016-05-28 10:38:28
this is good XD Last edit: 2016-05-28 12:02:48 |
|
Akash Shinde:
2016-01-22 18:01:32
What's the point of 256 B?
|
|
CounterNormalize:
2016-01-16 13:42:18
Finally AC!!! phewwww |
|
Divyansh Shukla:
2015-11-10 18:17:06
Code size restriction of 256B is really wrong. |
|
kuszi:
2015-08-29 16:56:28
@Fz Just a kind of a puzzle. You will find more like this here: http://www.spoj.com/SHORTEN/.
|
|
Mohit Bindal:
2015-08-26 17:32:06
Bakwas...!!!
|
|
Liquid_Science:
2015-06-23 19:25:45
Near to impossible in java :( |
|
SangKuan:
2015-06-20 12:43:30
250b,may be can smaller |
Added by: | kuszi |
Date: | 2004-12-01 |
Time limit: | 2s |
Source limit: | 256B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: NODEJS PERL6 VB.NET |
Resource: | 6-th International Olympiad In Informatics July 3-10. 1994. Stockholm - Sweden, Problem 1 |