Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

TGSO - Tam giác số

Một nửa ma trận vuông cấp n là một tam giác vuông cân, trên mỗi ô của tam giác có chứa một số nguyên.

Tại một ô của tam giác là (i,j), có thể đi đến 1 trong 3 ô là (i+1,j-1), (i+1,j) và (i+1,j+1). Có thể xem ở hình dưới:

 

(i,j)

 

i+1,j-1

i+1, j

i+1,j-1

Hãy tìm một hành trình từ đỉnh tam giác xuống đáy của tam giác sao cho tổng các ô trên hàng trình đi là lớn nhất.

Input:

- Dòng 1 chứa N (1 <= N <= 100)

- N dòng tiếp theo, dòng thứ i chứa i số nguyên

Output:

- Dòng 1 là số S: tổng giá trị lớn nhất trên hành trình

- N dòng tiếp theo, dòng thứ i chứa giá trị j tức là sẽ đi qua dòng i cột j trên hành trình.

Ví dụ

INPUT

OUTPUT

Giải thích ví dụ

5

3

1 5

7 2 8

8 3 5 6

1 9 3 7 3

32

1

2

1

1

2

Các số được bôi đậm là các số đi trên hành trình


Được gửi lên bởi:Vương Trung Hiếu Nghĩa
Ngày:2016-01-31
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:CPP

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.