Bài 2. Bảng số (HSG THPT Thành phố Huế 2026)

Xem dạng PDF

Gửi bài giải

Điểm: 1,00 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 256M
Input: stdin
Output: stdout

Tác giả:
Nguồn bài:
HSG THPT Thành phố Huế 2026
Dạng bài
Ngôn ngữ cho phép
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Trong giờ giải lao, giáo viên đưa ra một trò chơi với bảng hình chữ nhật. Bảng này được chia thành ~N \times M~ ô, trên mỗi ô ghi một số nguyên dương hoặc đặt một chiếc đinh nhọn. Một bạn học sinh thả một viên bi từ phía trên bảng, khi rơi xuống viên bi lăn theo quy tắc: từ ô ~(i, j)~ lăn xuống một trong số các ô ~(i+1, j-1), (i+1, j), (i+1, j+1)~. Ban đầu, học sinh đó được tặng một số điểm. Mỗi lần viên bi đi qua một ô:

• Nếu ô đó có giá trị số, học sinh sẽ được cộng thêm điểm ghi trên ô.

• Nếu ô đó có đinh, số điểm hiện tại của học sinh sẽ giảm đi một nửa hoặc gần một nửa (phần nguyên của số điểm khi chia cho 2).

Khi viên bi chạm đáy bảng, tổng điểm sẽ được ghi nhận. Tính số điểm ít nhất và nhiều nhất mà học sinh có thể nhận được khi viên bi chạm đáy.

Dữ liệu vào

Gồm các dòng:

  • Dòng 1: Chứa hai số nguyên ~N, M (1 \le N, M \le 1000)~.
  • Dòng 2: Chứa số nguyên ~b~ là số điểm ban đầu của học sinh ~(0 \le b < 30000)~.
  • ~N~ dòng tiếp theo mô tả bảng hình chữ nhật kích thước ~N \times M~, trong đó nếu ô có giá trị 0 có nghĩa là ô có đinh, ngược lại là các số trên ô (các số này nguyên dương và bé hơn hoặc bằng 30000).

Kết quả

Dòng 1: Ghi số điểm ít nhất có thể nhận được khi viên bi chạm đáy. Dòng 2: Ghi số điểm nhiều nhất có thể nhận được khi viên bi chạm đáy.

Ví dụ

Input 1

5 5
100
1 7 5 10 2
6 8 4 1 9
9 6 0 7 14
10 18 3 2 0
5 0 6 11 10

Output 1

28
148

Đường đi cho điểm nhỏ nhất là (1,5) → (2,4) → (3,3) → (4,3) → ~(5,2): 100 + 2 = 102, + 1 = 103~, gặp đinh còn ~52, + 3 = 55~, gặp đinh còn 28.


Chương trình đọc dữ liệu từ bàn phím (stdin) và ghi kết quả ra màn hình (stdout).


Đang tải...