Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
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 |