Cộng có nhớ (Đề tự luyện HSG Tin 12 – Bài 4)
Đề bài
Cộng có nhớ. Thầy Sơn dạy các em nhỏ phép cộng có nhớ: đặt tính thẳng cột (số ít chữ số hơn coi như có thêm các chữ số $0$ bên trái), cộng từ phải sang trái; ở mỗi cột lấy tổng hai chữ số cộng thêm số nhớ từ cột bên phải, nếu kết quả $\ge 10$ thì viết chữ số hàng đơn vị và nhớ 1 sang cột bên trái. Số lần nhớ của phép cộng $a + b$ là số cột phải nhớ 1 sang trái (kể cả cột trái cùng). Ví dụ $75 + 48 = 123$ có $2$ lần nhớ, $2026 + 7 = 2033$ có $1$ lần nhớ, $31 + 405 = 436$ không có lần nhớ nào.
Mỗi bài tập là một phép cộng $a + b$ với $a \in [L_1, R_1]$, $b \in [L_2, R_2]$ (hai bài khác nhau nếu khác $a$ hoặc khác $b$). Có $T$ câu hỏi, mỗi câu cho $L_1, R_1, L_2, R_2, K$: đếm số bài tập có đúng $K$ lần nhớ.
Dữ liệu vào: dòng đầu $T$ ($1 \le T \le 1000$); $T$ dòng sau, mỗi dòng $L_1, R_1, L_2, R_2, K$ ($0 \le L_1 \le R_1 \le 10^9$, $0 \le L_2 \le R_2 \le 10^9$, $0 \le K \le 20$).
Kết quả: $T$ dòng, mỗi dòng là đáp án của một câu hỏi.
- Subtask 1 (20%): $T \le 10$ và $R_1, R_2 \le 1000$.
- Subtask 2 (20%): $K = 0$ ở mọi câu hỏi.
- Subtask 3 (20%): mọi câu hỏi có $L_1 = L_2 = 0$, $R_1 = R_2 = 10^d - 1$ ($1 \le d \le 9$).
- Subtask 4 (40%): không có ràng buộc gì thêm.
3
1 9 1 9 1
120 125 80 85 1
2020 2026 1 7 045
35
39Câu 1: có $45$ bài một chữ số có $a + b \ge 10$. Câu 2: trong $36$ bài, chỉ $125 + 85 = 210$ có $2$ lần nhớ, $35$ bài còn lại có đúng $1$ lần nhớ. Câu 3: trong $49$ bài có $10$ bài phải nhớ một lần (như $2026 + 7$), $39$ bài không nhớ lần nào.
Bạn nào muốn thử nộp bài để hệ thống chấm xem có đúng hay không thì dùng link này nhé. Bộ test có chia subtask và có cả những test "bẫy", nên code đúng ý tưởng nhưng sai chi tiết nhỏ cũng sẽ bị trừ điểm đó.
Nộp bài Cộng có nhớLời mở đầu
Đề bài nghe rất "tiểu học", nhưng $a, b$ lên tới $10^9$ nên số bài tập trong một câu hỏi có thể lên tới khoảng $10^{18}$ — không thể thử từng cặp. Ta cần đếm theo chữ số. Trước khi vào các cách làm, các bạn hãy chơi thử với phép đặt tính một chút để "cảm" được số nhớ chạy thế nào:
Nhận xét 1 – đưa về "góc dưới trái". Gọi $f(A, B)$ là số cặp $(a, b)$ với $0 \le a \le A$, $0 \le b \le B$ có đúng $K$ lần nhớ. Các cặp cần đếm nằm trong "hình chữ nhật" $[L_1, R_1] \times [L_2, R_2]$, nên y hệt tổng tiền tố hai chiều:
$$\text{đáp án} = f(R_1, R_2) - f(L_1 - 1, R_2) - f(R_1, L_2 - 1) + f(L_1 - 1, L_2 - 1),$$với quy ước $f(A, B) = 0$ khi $A < 0$ hoặc $B < 0$ (đề cho phép $L = 0$, đây là một cái bẫy nhỏ!). Đáp án có thể tới khoảng $10^{18}$ nên phải dùng long long.
Nhận xét 2 – cứ coi mọi số có đúng 10 chữ số. Vì $a, b \le 10^9$, ta thêm các chữ số $0$ vào bên trái cho đủ 10 chữ số. Cột $0 + 0$ cộng thêm nhớ cùng lắm bằng $1$ nên không bao giờ sinh thêm lần nhớ — số lần nhớ không đổi. Nhờ vậy mọi cặp $(a, b)$ ứng với đúng một cách chọn 10 cặp chữ số $(x_i, y_i)$.
Nhận xét 3 – nút thắt của bài. Đếm theo chữ số (QHĐ chữ số) thì quen rồi: đi từ chữ số trái nhất sang phải, nhớ xem số đang dựng còn "bám sát" cận trên hay đã nhỏ hơn hẳn. Nhưng số nhớ thì lại chạy theo chiều ngược lại: từ phải sang trái. Muốn biết cột $i$ có nhớ hay không, ta phải biết cột bên phải nó gửi sang bao nhiêu. Hai luồng thông tin ngược chiều nhau — đây chính là chỗ "khó chịu" của bài:
Muốn biết chữ số đang chọn có vượt cận không, phải đi từ trái; muốn biết cột này có nhớ không, phải biết cột bên phải. Lời giải đầy đủ phải "hoà giải" hai chiều này.
Ta sẽ gỡ dần: trước hết bỏ bớt từng khó khăn một (bỏ số nhớ ở Subtask 2, bỏ cận trên ở Subtask 3), rồi mới ghép lại.
Cách 1Vét cạn từng cặp – O(T·R₁·R₂·10) · 20%
Thử mọi $a \in [L_1, R_1]$, mọi $b \in [L_2, R_2]$ và mô phỏng đúng phép đặt tính: lấy chữ số cuối của $a$, $b$ bằng % 10, cộng với số nhớ $c$; nếu tổng $\ge 10$ thì $c = 1$ và tăng bộ đếm, rồi chia $a, b$ cho 10. Vòng lặp dừng khi cả hai số về $0$ — lúc đó nếu còn nhớ 1 thì lần nhớ đó đã được đếm ở cột trái cùng rồi, đúng như định nghĩa.
Với Subtask 1 có tối đa $10 \cdot 1001^2 \approx 10^7$ cặp, mỗi cặp vài phép tính: chạy rất nhanh.
#include <bits/stdc++.h>
using namespace std;
// So lan nho khi dat tinh a + b
int carries(long long a, long long b) {
int c = 0, k = 0;
while (a > 0 || b > 0) {
int s = a % 10 + b % 10 + c; // hai chu so cung cot + so nho tu ben phai
c = (s >= 10) ? 1 : 0;
k += c;
a /= 10; b /= 10;
}
return k;
}
int main() {
int T;
scanf("%d", &T);
while (T--) {
long long L1, R1, L2, R2; int K;
scanf("%lld %lld %lld %lld %d", &L1, &R1, &L2, &R2, &K);
long long ans = 0;
for (long long a = L1; a <= R1; a++)
for (long long b = L2; b <= R2; b++)
if (carries(a, b) == K) ans++;
printf("%lld\n", ans);
}
return 0;
}import sys
def carries(a, b):
c = 0; k = 0
while a > 0 or b > 0:
s = a % 10 + b % 10 + c # hai chu so cung cot + so nho tu ben phai
c = 1 if s >= 10 else 0
k += c
a //= 10; b //= 10
return k
def main():
data = sys.stdin.buffer.read().split()
t = int(data[0]); p = 1; out = []
for _ in range(t):
L1, R1, L2, R2, K = map(int, data[p:p + 5]); p += 5
ans = 0
for a in range(L1, R1 + 1):
for b in range(L2, R2 + 1):
if carries(a, b) == K:
ans += 1
out.append(str(ans))
print("\n".join(out))
main()Cách 2K = 0: QHĐ chữ số "cộng không nhớ" – O(T·10·4·100) · 40%
Khi $K = 0$, phép cộng không được nhớ lần nào. Không có số nhớ nào thì mọi cột đều chỉ là $x + y$, nên điều kiện đơn giản là: mọi cột có $x + y \le 9$. Các cột trở nên độc lập về mặt số nhớ, chỉ còn ràng buộc $a \le A$, $b \le B$ — đúng sân của QHĐ chữ số.
Duyệt các cột từ trái sang phải ($i = 9, 8, \dots, 0$; $da_i$, $db_i$ là chữ số thứ $i$ của $A$, $B$). Trạng thái dp[ta][tb] = số cách chọn các chữ số bên trái, trong đó:
ta = 1nếu phần đã chọn của $a$ trùng khít phần tương ứng của $A$ (đang "bám sát" cận), khi đó chữ số tiếp theo chỉ được chọn $x \le da_i$; nếu chọn $x = da_i$ thì vẫn bám sát, chọn $x < da_i$ thì từ đó về sau $a$ chắc chắn nhỏ hơn $A$, tự do chọn $0..9$ (ta = 0).tbtương tự cho $b$.
Bắt đầu dp[1][1] = 1; mỗi cột thử mọi cặp $(x, y)$ hợp lệ có $x + y \le 9$. Kết thúc, cộng cả 4 trạng thái. Ví dụ $A = 25$, $B = 13$ (chỉ ghi hai cột cuối, các cột trước đều là $0 + 0$):
| Sau cột | (ta, tb) = (1,1) | (1,0) | (0,1) | (0,0) |
|---|---|---|---|---|
| bắt đầu | 1 | 0 | 0 | 0 |
| hàng chục (2 và 1) | 1 (x=2, y=1) | 1 (x=2, y=0) | 2 (x=0..1, y=1) | 2 (x=0..1, y=0) |
| hàng đơn vị (5 và 3) | 1·24 | 1·45 | 2·34 | 2·55 |
Chẳng hạn trạng thái $(0,0)$ ở hàng đơn vị: $x, y$ tự do, số cặp có $x + y \le 9$ là $10 + 9 + \dots + 1 = 55$. Tổng $f(25, 13) = 24 + 45 + 68 + 110 = 247$ cặp cộng không nhớ.
Các câu hỏi $K > 0$ thì vẫn vét cạn như Cách 1 (đủ cho Subtask 1).
#include <bits/stdc++.h>
using namespace std;
int carries(long long a, long long b) {
int c = 0, k = 0;
while (a > 0 || b > 0) {
int s = a % 10 + b % 10 + c;
c = (s >= 10) ? 1 : 0;
k += c;
a /= 10; b /= 10;
}
return k;
}
// g(A, B) = so cap 0 <= a <= A, 0 <= b <= B cong KHONG nho lan nao
long long g(long long A, long long B) {
if (A < 0 || B < 0) return 0;
int da[10], db[10];
for (int i = 0; i < 10; i++) { da[i] = A % 10; A /= 10; db[i] = B % 10; B /= 10; }
long long dp[2][2] = {{0, 0}, {0, 1}}; // dp[ta][tb], bat dau bam sat ca hai
for (int i = 9; i >= 0; i--) {
long long nd[2][2] = {{0, 0}, {0, 0}};
for (int ta = 0; ta < 2; ta++)
for (int tb = 0; tb < 2; tb++) {
if (!dp[ta][tb]) continue;
int mx = ta ? da[i] : 9, my = tb ? db[i] : 9;
for (int x = 0; x <= mx; x++)
for (int y = 0; y <= my && x + y <= 9; y++) // cot nay khong duoc nho
nd[ta && x == mx][tb && y == my] += dp[ta][tb];
}
memcpy(dp, nd, sizeof dp);
}
return dp[0][0] + dp[0][1] + dp[1][0] + dp[1][1];
}
int main() {
int T;
scanf("%d", &T);
while (T--) {
long long L1, R1, L2, R2; int K;
scanf("%lld %lld %lld %lld %d", &L1, &R1, &L2, &R2, &K);
long long ans = 0;
if (K == 0) {
ans = g(R1, R2) - g(L1 - 1, R2) - g(R1, L2 - 1) + g(L1 - 1, L2 - 1);
} else { // con lai: vet can nhu Cach 1
for (long long a = L1; a <= R1; a++)
for (long long b = L2; b <= R2; b++)
if (carries(a, b) == K) ans++;
}
printf("%lld\n", ans);
}
return 0;
}import sys
def carries(a, b):
c = 0; k = 0
while a > 0 or b > 0:
s = a % 10 + b % 10 + c
c = 1 if s >= 10 else 0
k += c
a //= 10; b //= 10
return k
def g(A, B):
# so cap 0 <= a <= A, 0 <= b <= B cong KHONG nho lan nao
if A < 0 or B < 0:
return 0
da = [0] * 10; db = [0] * 10
for i in range(10):
da[i] = A % 10; A //= 10
db[i] = B % 10; B //= 10
dp = [[0, 0], [0, 1]] # dp[ta][tb]
for i in range(9, -1, -1):
nd = [[0, 0], [0, 0]]
for ta in range(2):
for tb in range(2):
v = dp[ta][tb]
if not v:
continue
mx = da[i] if ta else 9
my = db[i] if tb else 9
for x in range(mx + 1):
for y in range(min(my, 9 - x) + 1): # cot nay khong duoc nho
nd[1 if (ta and x == mx) else 0][1 if (tb and y == my) else 0] += v
dp = nd
return dp[0][0] + dp[0][1] + dp[1][0] + dp[1][1]
def main():
data = sys.stdin.buffer.read().split()
t = int(data[0]); p = 1; out = []
for _ in range(t):
L1, R1, L2, R2, K = map(int, data[p:p + 5]); p += 5
if K == 0:
ans = g(R1, R2) - g(L1 - 1, R2) - g(R1, L2 - 1) + g(L1 - 1, L2 - 1)
else: # con lai: vet can nhu Cach 1
ans = 0
for a in range(L1, R1 + 1):
for b in range(L2, R2 + 1):
if carries(a, b) == K:
ans += 1
out.append(str(ans))
print("\n".join(out))
main()Cách 3Không có cận: QHĐ theo số nhớ – O(10·2·11) · 60%
Subtask 3 bỏ đi ràng buộc cận: $a, b$ chạy hết mọi số có tối đa $d$ chữ số, tức là mỗi chữ số tự do từ 0 đến 9. Không còn gì phải nhìn từ trái nữa, ta đi theo đúng chiều của số nhớ: từ phải sang trái.
Gọi h[d][c][k] = số cách điền $d$ cột bên phải (mỗi cột một cặp chữ số) sao cho cột thứ $d$ gửi sang trái số nhớ $c$ và tổng cộng có $k$ lần nhớ. Thêm một cột mới nhận số nhớ $c$ từ bên phải:
- nếu $c = 0$: có $45$ cặp $(x, y)$ với $x + y \ge 10$ (nhớ), $55$ cặp không nhớ;
- nếu $c = 1$: cần $x + y \ge 9$, có $55$ cặp nhớ, $45$ cặp không nhớ.
| d | k = 0 | k = 1 | k = 2 | Tổng |
|---|---|---|---|---|
| 1 | 55 | 45 | 0 | 100 |
| 2 | 55·55 = 3025 | 55·45 + 45·45 = 4500 | 45·55 = 2475 | 10 000 |
Đáp án câu hỏi là h[d][0][K] + h[d][1][K]. Bảng chỉ cần tính một lần. Code dưới đây nhận diện câu hỏi kiểu Subtask 3, câu $K = 0$ dùng Cách 2, còn lại vét cạn.
#include <bits/stdc++.h>
using namespace std;
int carries(long long a, long long b) {
int c = 0, k = 0;
while (a > 0 || b > 0) {
int s = a % 10 + b % 10 + c;
c = (s >= 10) ? 1 : 0;
k += c;
a /= 10; b /= 10;
}
return k;
}
long long g(long long A, long long B) { // Cach 2: so cap khong nho lan nao
if (A < 0 || B < 0) return 0;
int da[10], db[10];
for (int i = 0; i < 10; i++) { da[i] = A % 10; A /= 10; db[i] = B % 10; B /= 10; }
long long dp[2][2] = {{0, 0}, {0, 1}};
for (int i = 9; i >= 0; i--) {
long long nd[2][2] = {{0, 0}, {0, 0}};
for (int ta = 0; ta < 2; ta++)
for (int tb = 0; tb < 2; tb++) {
if (!dp[ta][tb]) continue;
int mx = ta ? da[i] : 9, my = tb ? db[i] : 9;
for (int x = 0; x <= mx; x++)
for (int y = 0; y <= my && x + y <= 9; y++)
nd[ta && x == mx][tb && y == my] += dp[ta][tb];
}
memcpy(dp, nd, sizeof dp);
}
return dp[0][0] + dp[0][1] + dp[1][0] + dp[1][1];
}
int main() {
// h[d][c][k]: so cach dien d cot ben phai (a, b tu do) sao cho cot thu d gui sang trai so nho c, tong k lan nho
static long long h[10][2][12];
h[0][0][0] = 1;
for (int d = 0; d < 9; d++)
for (int c = 0; c < 2; c++)
for (int k = 0; k <= 10; k++) {
long long v = h[d][c][k];
if (!v) continue;
// cot moi nhan so nho c: so cap (x, y) co x + y + c >= 10 la 45 (c = 0) hoac 55 (c = 1)
long long up = (c == 0) ? 45 : 55;
h[d + 1][1][k + 1] += v * up;
h[d + 1][0][k] += v * (100 - up);
}
int T;
scanf("%d", &T);
while (T--) {
long long L1, R1, L2, R2; int K;
scanf("%lld %lld %lld %lld %d", &L1, &R1, &L2, &R2, &K);
long long ans = 0;
int d = 0; long long p = 1;
while (p - 1 < R1 && d < 9) { p *= 10; d++; }
if (L1 == 0 && L2 == 0 && R1 == R2 && R1 == p - 1 && d >= 1) {
ans = (K <= 10) ? h[d][0][K] + h[d][1][K] : 0;
} else if (K == 0) {
ans = g(R1, R2) - g(L1 - 1, R2) - g(R1, L2 - 1) + g(L1 - 1, L2 - 1);
} else {
for (long long a = L1; a <= R1; a++)
for (long long b = L2; b <= R2; b++)
if (carries(a, b) == K) ans++;
}
printf("%lld\n", ans);
}
return 0;
}import sys
def carries(a, b):
c = 0; k = 0
while a > 0 or b > 0:
s = a % 10 + b % 10 + c
c = 1 if s >= 10 else 0
k += c
a //= 10; b //= 10
return k
def g(A, B): # Cach 2: so cap khong nho lan nao
if A < 0 or B < 0:
return 0
da = [0] * 10; db = [0] * 10
for i in range(10):
da[i] = A % 10; A //= 10
db[i] = B % 10; B //= 10
dp = [[0, 0], [0, 1]]
for i in range(9, -1, -1):
nd = [[0, 0], [0, 0]]
for ta in range(2):
for tb in range(2):
v = dp[ta][tb]
if not v:
continue
mx = da[i] if ta else 9
my = db[i] if tb else 9
for x in range(mx + 1):
for y in range(min(my, 9 - x) + 1):
nd[1 if (ta and x == mx) else 0][1 if (tb and y == my) else 0] += v
dp = nd
return dp[0][0] + dp[0][1] + dp[1][0] + dp[1][1]
def main():
# h[d][c][k]: d cot ben phai dien tu do, cot thu d gui sang trai so nho c, tong k lan nho
h = [[[0] * 12 for _ in range(2)] for _ in range(10)]
h[0][0][0] = 1
for d in range(9):
for c in range(2):
for k in range(11):
v = h[d][c][k]
if not v:
continue
up = 45 if c == 0 else 55 # so cap (x, y) co x + y + c >= 10
h[d + 1][1][k + 1] += v * up
h[d + 1][0][k] += v * (100 - up)
data = sys.stdin.buffer.read().split()
t = int(data[0]); p = 1; out = []
for _ in range(t):
L1, R1, L2, R2, K = map(int, data[p:p + 5]); p += 5
d = 0; q = 1
while q - 1 < R1 and d < 9:
q *= 10; d += 1
if L1 == 0 and L2 == 0 and R1 == R2 and R1 == q - 1 and d >= 1:
ans = h[d][0][K] + h[d][1][K] if K <= 10 else 0
elif K == 0:
ans = g(R1, R2) - g(L1 - 1, R2) - g(R1, L2 - 1) + g(L1 - 1, L2 - 1)
else:
ans = 0
for a in range(L1, R1 + 1):
for b in range(L2, R2 + 1):
if carries(a, b) == K:
ans += 1
out.append(str(ans))
print("\n".join(out))
main()Cách 2 thì có cận nhưng không có số nhớ; Cách 3 thì có số nhớ nhưng không có cận. Cách 2 bắt buộc đi từ trái, Cách 3 tự nhiên đi từ phải. Ghép thế nào đây?
Cách 4QHĐ chữ số "đoán trước số nhớ" – O(T·4·10·8·K·18) · 100%
Ý tưởng then chốt: vẫn đi từ trái sang phải để quản lý cận, còn số nhớ thì… đoán trước. Khi đứng ở cột $i$, ta chưa biết cột bên phải gửi sang bao nhiêu, vậy cứ giả sử nó gửi $c_i \in \{0, 1\}$, ghi lời giả sử ấy vào trạng thái, và bắt cột bên phải phải "giữ lời" khi tới lượt nó.
Trạng thái dp[ta][tb][c][k] khi chuẩn bị xử lý cột $i$:
ta,tb: còn bám sát cận $A$, $B$ hay không (như Cách 2);c: số nhớ mà cột $i$ bắt buộc phải gửi sang trái — đây là lời giả sử mà cột $i + 1$ đã đặt ra;k: số lần nhớ đã đếm được (mỗi lời giả sử "gửi 1" được đếm ngay khi đặt ra).
Chuyển trạng thái ở cột $i$: chọn chữ số $x$, $y$ (theo cận như Cách 2) và đoán $c_i$ = số nhớ cột $i - 1$ gửi sang. Lựa chọn hợp lệ khi và chỉ khi nó giữ đúng lời: $[x + y + c_i \ge 10] = c$. Khi đó sang trạng thái (ta', tb', c_i, k + c_i).
Khởi đầu: cột trái cùng có thể gửi ra ngoài $0$ hoặc $1$ (nếu $1$ thì đó cũng là một lần nhớ), nên dp[1][1][0][0] = 1 và dp[1][1][1][1] = 1. Kết thúc: cột đơn vị không có ai bên phải gửi số nhớ, nên ở $i = 0$ chỉ cho đoán $c_0 = 0$. Đáp án là tổng các dp[ta][tb][0][K].
Tăng tốc: mỗi trạng thái mà thử cả 100 cặp chữ số thì hơi chậm. Ta chia $x$ thành 3 loại so với $da_i$ ($x < da_i$, $x = da_i$, $x > da_i$), $y$ tương tự, và đếm trước cnt[ex][ey][ci][co] = số cặp $(x, y)$ thuộc từng loại, với số nhớ vào $c_i$ cho ra số nhớ $co$. Trạng thái bám sát chỉ được dùng loại 0, 1; trạng thái tự do dùng cả 3 loại.
Các bạn xem bảng QHĐ thay đổi qua từng cột (mô phỏng dùng số chữ số bằng số chữ số của số lớn hơn cho gọn — thêm các cột $0 + 0$ ở trước không làm thay đổi kết quả):
Mỗi lần gọi $f$ có $10$ cột, mỗi cột tối đa $8 \cdot 21$ ô, mỗi ô thử tối đa $3 \cdot 3 \cdot 2 = 18$ lựa chọn: khoảng $30\,000$ phép tính; mỗi câu hỏi gọi $f$ bốn lần, $T = 1000$ câu: cỡ $10^8$ phép tính đơn giản, C++ chạy chưa tới $0{,}1$ giây.
#include <bits/stdc++.h>
using namespace std;
// f(A, B, K) = so cap (a, b) voi 0 <= a <= A, 0 <= b <= B co dung K lan nho
// QHD chu so tu trai sang phai, "doan truoc" so nho tu cot ben phai gui sang
long long f(long long A, long long B, int K) {
if (A < 0 || B < 0) return 0;
int da[10], db[10];
for (int i = 0; i < 10; i++) { da[i] = A % 10; A /= 10; db[i] = B % 10; B /= 10; }
// dp[ta][tb][c][k]: ta, tb = dang "bam sat" can tren; c = so nho cot hien tai PHAI gui sang trai
static long long dp[2][2][2][22], nd[2][2][2][22];
memset(dp, 0, sizeof dp);
dp[1][1][0][0] = 1;
if (K >= 1) dp[1][1][1][1] = 1; // cot trai cung nho 1 ra ngoai
for (int i = 9; i >= 0; i--) {
// cnt[ex][ey][ci][co]: so cap chu so (x, y) theo loai so voi chu so can tren
// ex = 0: x < da[i], 1: x = da[i], 2: x > da[i]
long long cnt[3][3][2][2] = {};
for (int x = 0; x < 10; x++)
for (int y = 0; y < 10; y++)
for (int ci = 0; ci < 2; ci++) {
int ex = x < da[i] ? 0 : (x == da[i] ? 1 : 2);
int ey = y < db[i] ? 0 : (y == db[i] ? 1 : 2);
cnt[ex][ey][ci][x + y + ci >= 10]++;
}
memset(nd, 0, sizeof nd);
for (int ta = 0; ta < 2; ta++)
for (int tb = 0; tb < 2; tb++)
for (int c = 0; c < 2; c++)
for (int k = 0; k <= K; k++) {
long long v = dp[ta][tb][c][k];
if (!v) continue;
for (int ex = 0; ex < (ta ? 2 : 3); ex++)
for (int ey = 0; ey < (tb ? 2 : 3); ey++)
for (int ci = 0; ci < 2; ci++) {
if (i == 0 && ci == 1) continue; // cot don vi khong co so nho tu ben phai
if (k + ci > K) continue;
long long w = cnt[ex][ey][ci][c];
if (!w) continue;
nd[ta && ex == 1][tb && ey == 1][ci][k + ci] += v * w;
}
}
memcpy(dp, nd, sizeof dp);
}
long long res = 0;
for (int ta = 0; ta < 2; ta++)
for (int tb = 0; tb < 2; tb++) res += dp[ta][tb][0][K];
return res;
}
int main() {
int T;
scanf("%d", &T);
while (T--) {
long long L1, R1, L2, R2; int K;
scanf("%lld %lld %lld %lld %d", &L1, &R1, &L2, &R2, &K);
long long ans = f(R1, R2, K) - f(L1 - 1, R2, K) - f(R1, L2 - 1, K) + f(L1 - 1, L2 - 1, K);
printf("%lld\n", ans);
}
return 0;
}import sys
def build_tables():
# TR[da*10+db][ta*2+tb][c] = danh sach (ci, nta*2+ntb, so cap chu so)
TR = []
for da in range(10):
for db in range(10):
per = []
for ta in range(2):
for tb in range(2):
row = [{}, {}]
for x in range(da + 1 if ta else 10):
for y in range(db + 1 if tb else 10):
nt = (1 if (ta and x == da) else 0) * 2 + (1 if (tb and y == db) else 0)
for ci in range(2):
co = 1 if x + y + ci >= 10 else 0
key = (ci, nt)
row[co][key] = row[co].get(key, 0) + 1
per.append([[(ci, nt, w) for (ci, nt), w in row[c].items()] for c in range(2)])
TR.append(per)
return TR
TR = build_tables()
def f(A, B, K):
# so cap (a, b), 0 <= a <= A, 0 <= b <= B, co dung K lan nho
if A < 0 or B < 0:
return 0
da = [0] * 10
db = [0] * 10
for i in range(10):
da[i] = A % 10; A //= 10
db[i] = B % 10; B //= 10
# trang thai s = (ta*2 + tb)*2 + c ; dp[s][k]
dp = [None] * 8
z = [0] * (K + 1)
st = list(z); st[0] = 1
dp[6] = st # ta = tb = 1, c = 0
if K >= 1:
st = list(z); st[1] = 1
dp[7] = st # cot trai cung nho 1 ra ngoai
for i in range(9, -1, -1):
tri = TR[da[i] * 10 + db[i]]
nd = [None] * 8
last = (i == 0)
for s in range(8):
v = dp[s]
if v is None:
continue
for ci, nt, w in tri[s >> 1][s & 1]:
if ci and last:
continue
ns = nt * 2 + ci
t = nd[ns]
if t is None:
t = list(z); nd[ns] = t
if ci:
for k in range(K):
if v[k]:
t[k + 1] += v[k] * w
else:
for k in range(K + 1):
if v[k]:
t[k] += v[k] * w
dp = nd
res = 0
for s in (0, 2, 4, 6):
if dp[s] is not None:
res += dp[s][K]
return res
def main():
data = sys.stdin.buffer.read().split()
t = int(data[0])
out = []
p = 1
for _ in range(t):
L1 = int(data[p]); R1 = int(data[p + 1]); L2 = int(data[p + 2]); R2 = int(data[p + 3]); K = int(data[p + 4])
p += 5
ans = f(R1, R2, K) - f(L1 - 1, R2, K) - f(R1, L2 - 1, K) + f(L1 - 1, L2 - 1, K)
out.append(str(ans))
sys.stdout.write("\n".join(out) + "\n")
main()Bây giờ hãy chạy tay từng dòng của lời giải chuẩn (mô phỏng giới hạn $T \le 2$, $R \le 9999$, $K \le 3$ cho số bước vừa phải; các ô của bảng dp bằng 0 được bỏ qua đúng như dòng if (!v) continue;):
Bộ test chấm "bắt" những lỗi nào?
| Cách làm | Sub 1 | Sub 2 | Sub 3 | Sub 4 | Điểm |
|---|---|---|---|---|---|
| Cách 1 – vét cạn từng cặp | Đúng | TLE | TLE | TLE | 20 |
| Cách 2 – K = 0: QHĐ chữ số không nhớ | Đúng | Đúng | TLE | TLE | 40 |
| Cách 3 – thêm QHĐ số nhớ khi không có cận | Đúng | Đúng | Đúng | TLE | 60 |
| Cách 4 – đoán trước số nhớ (lời giải chuẩn) | Đúng | Đúng | Đúng | Đúng | 100 |
| Sai: đếm số cột có $x + y \ge 10$, quên số nhớ dây chuyền | 1/7 | Đúng | 0/6 | 0/10 | 22,9 |
| Sai: $L = 0$ thì coi $f(-1, \cdot)$ như $f(0, \cdot)$ | 6/7 | 3/7 | 0/6 | 1/10 | 29,7 |
| Sai: chỉ xét 9 chữ số (quên $10^9$ có 10 chữ số) | Đúng | 3/7 | Đúng | 2/10 | 56,6 |
Sai: bảng đếm kiểu int | Đúng | 0/7 | 0/6 | 0/10 | 20 |
Ghi chú của mình: các cách C++ ở trên đã được chấm thử với đúng bộ test của bài: 30 test (subtask 1: 7 test, subtask 2: 7 test, subtask 3: 6 test, subtask 4: 10 test), chấm kiểu "đúng test nào được điểm test đó". Mỗi test từ subtask 2 trở đi có $T = 1000$ câu hỏi với khoảng rất lớn nên vét cạn không thể qua; mọi test subtask 3 và 4 có nhiều câu $K > 0$ nên Cách 2 không "ăn ké" được; mọi test subtask 4 có cận tuỳ ý nên Cách 3 cũng không. Nhiều test có $L = 0$, có cận đúng bằng $10^9$, có các số toàn chữ số 9 (số nhớ dây chuyền rất dài) để bắt các lỗi chi tiết. Lời giải chuẩn chạy dưới $0{,}1$ giây. Bản Python của lời giải chuẩn nên nộp bằng PyPy 3.
Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này. Anh em đọc chắc cũng mỏi mắt luôn chứ 😅 vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 🤪. Vậy nên đừng tiếc gì cho mình một lời bình luận hoặc chia sẻ bài viết để động viên mình nè. Chúc anh em học tốt và gặt hái nhiều thành công 😇
- Không biết học gì trước, học gì sau, học lan man nên kiến thức bị hổng.
- Bí bài không ai gỡ, ngồi cả buổi vẫn không ra rồi bỏ cuộc.
- Code chạy được nhưng không đủ điểm, không biết sai ở đâu, chậm ở đâu.
- Không có đề thi thử và người chấm, nên không biết mình đang ở mức nào.
- Dễ nản giữa chừng khi không có ai theo sát.
- Lộ trình 111 buổi video sắp sẵn từ dòng code đầu tiên đến đề HSG thật của các tỉnh.
- Thầy trực tiếp gỡ bí, chữa bài cho từng em qua nhóm Zalo riêng.
- Hệ thống chấm bài tự động 24/7 và thi thử HSG hằng tuần để biết chính xác mình đang ở đâu.
- Đóng học phí một lần, thầy kèm lâu dài: từ thi chuyên Tin đến HSG quốc gia và cả khi lên đại học.
Nhận xét
Đăng nhận xét