Bảng đẹp (THT B, C1 & C2 Vòng KVMT 2022)
Xem PDF
Điểm:
1900
Thời gian:
1.5s
Bộ nhớ:
256M
Input:
bàn phím
Output:
màn hình
Một bảng số nguyên không âm được gọi là bảng đẹp nếu tổng các số trong bảng chia hết cho \(9\).
Ví dụ, bảng
\(\begin{bmatrix}
3 & 3 & 3\\
1 & 2 & 6
\end{bmatrix}\)
là một bảng đẹp.
Yêu cầu: Cho bảng số nguyên không âm kích thước \(m × n\), hãy đếm số bộ chỉ số \((x,y,u,v)\) với \(1 \leq x \leq u \leq m;1 \leq y\leq v \leq n\) sao cho bảng số con có ô trái trên \((x,y)\) và ô phải dưới \((u,v)\) là một bảng đẹp.
Input
- Dòng đầu chứa số nguyên \(m, n\)
- Dòng thứ \(i\) \((1 \leq i \leq m)\) trong \(m\) dòng sau chứa \(n\) số nguyên \(a_{(i,1)},a_{(i,2)},..,a_{(i,n)}\) \((a_{(i,j)} \leq 10^9)\).
Output
- In ra một số nguyên là số bộ chỉ số \((x,y,u,v)\) thỏa mãn.
Scoring
- Subtask #1 (\(30\%\) số điểm): \(m, n \leq 5\)
- Subtask #2 (\(40\%\) số điểm): \(m, n \leq 50\)
- Subtask #3 (\(30\%\) số điểm): \(m, n \leq 500\)
Example
Test 1
Input
2 3
3 3 3
1 2 6Output
5
Bình luận
Ai có thể gợi ý cho mình thuật toán tối ưu bài này k ạ, mình nghĩ rất nhiều cách nhưng chỉ được 7 test Python
mảng cộng dồn 2 chiều (chắc tên là vậy) + đếm phân phối