Cân đĩa (Đề tự luyện HSG Tin 9 – Bài 1)
Đề bài
Cân đĩa. Cô bán hàng có một cân đĩa và $K$ quả cân nặng $1, 3, 9, \dots, 3^{K-1}$ gam (mỗi loại đúng một quả). Để cân một giỏ nặng $m$ gam, giỏ đặt ở đĩa trái, các quả cân được đặt lên đĩa trái hoặc đĩa phải (hoặc không dùng) sao cho cân thăng bằng. Với mỗi giỏ trong $N$ giỏ, tính số quả cân ít nhất cần dùng, hoặc in $-1$ nếu không cân được.
Dữ liệu vào: dòng 1 gồm $N, K$ $(1 \le N \le 10^5;\ 1 \le K \le 40)$; dòng 2 gồm $m_1, m_2, \dots, m_N$ $(1 \le m_i \le 10^{18})$.
Kết quả: $N$ dòng, dòng $i$ là số quả cân ít nhất cho giỏ $i$, hoặc $-1$.
- Subtask 1 (30%): $N \le 100$ và $K \le 8$.
- Subtask 2 (30%): $m_i \le 10^6$.
- Subtask 3 (40%): không ràng buộc thêm.
4 4
7 20 40 1003
4
4
-1Quả cân $1, 3, 9, 27$. Giỏ $7$ g: trái = giỏ + $3$, phải = $9 + 1$ (3 quả). Giỏ $20$ g: trái = giỏ + $9 + 1$, phải = $27 + 3$ (4 quả). Giỏ $40$ g: phải = $1 + 3 + 9 + 27$ (4 quả). Giỏ $100$ g: không cân được.
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ân đĩaLời mở đầu
Trước hết hãy "dịch" chuyện cân đĩa sang ngôn ngữ toán. Mỗi quả cân $3^j$ có đúng ba lựa chọn: đặt ở đĩa phải, đặt ở đĩa trái (cùng giỏ), hoặc không dùng. Ta gán cho nó một hệ số $c_j$ lần lượt là $+1$, $-1$, $0$. Cân thăng bằng nghĩa là
$m + (\text{tổng đĩa trái}) = (\text{tổng đĩa phải})$, tức là $m = c_0 \cdot 1 + c_1 \cdot 3 + c_2 \cdot 9 + \dots + c_{K-1} \cdot 3^{K-1}$.
Số quả cân dùng chính là số hệ số $c_j$ khác $0$. Ví dụ giỏ $7$ gam: $7 = 9 - 3 + 1$, tức là $(c_3, c_2, c_1, c_0) = (0, +1, -1, +1)$.
Hình 1. Mỗi cách cân thăng bằng ứng với một dãy hệ số $+1, -1, 0$ cho các quả cân.
Cách 1Thử mọi cách đặt quả cân – O(N · 3^K) · 30%
Mỗi quả cân có 3 lựa chọn nên có tất cả $3^K$ cách đặt. Với $K \le 8$ chỉ có $3^8 = 6561$ cách, và $N \le 100$ giỏ thì tổng cộng chưa tới một triệu phép thử. Ta viết hàm đệ quy thu(j, lech, d): đang xét quả cân thứ $j$, lech = (tổng đĩa phải) − (tổng đĩa trái, kể cả giỏ), d = số quả đã dùng. Khi xét hết $K$ quả, nếu lech = 0 thì cân thăng bằng và ta cập nhật đáp án nhỏ nhất.
#include <bits/stdc++.h>
using namespace std;
int K, best;
long long w[45], m;
// xet qua can thu j; lech = (tong dia phai) - (tong dia trai, gom ca gio); d = so qua can da dung
void thu(int j, long long lech, int d) {
if (j == K) {
if (lech == 0 && (best < 0 || d < best)) best = d;
return;
}
thu(j + 1, lech, d); // khong dung qua can 3^j
thu(j + 1, lech + w[j], d + 1); // dat len dia phai
thu(j + 1, lech - w[j], d + 1); // dat len dia trai (cung gio)
}
int main() {
int n;
cin >> n >> K;
w[0] = 1;
for (int j = 1; j < K; j++) w[j] = w[j - 1] * 3;
for (int i = 0; i < n; i++) {
cin >> m;
best = -1;
thu(0, -m, 0); // ban dau dia trai co gio nang m
cout << best << '\n';
}
return 0;
}import sys
def main():
data = sys.stdin.buffer.read().split()
n, K = int(data[0]), int(data[1])
w = [3 ** j for j in range(K)]
out = []
for i in range(n):
m = int(data[2 + i])
best = -1
# moi trang thai: (lech = dia phai - dia trai, so qua can da dung); ban dau dia trai co gio nang m
cur = [(-m, 0)]
for j in range(K):
nxt = []
for lech, d in cur:
nxt.append((lech, d)) # khong dung qua can 3^j
nxt.append((lech + w[j], d + 1)) # dat len dia phai
nxt.append((lech - w[j], d + 1)) # dat len dia trai (cung gio)
cur = nxt
for lech, d in cur:
if lech == 0 and (best < 0 or d < best):
best = d
out.append(best)
print("\n".join(map(str, out)))
main()Cách 2Liệt kê trước một lần, tra bảng – O(3^14 + N) · 60%
Khi $m \le 10^6$, quả cân quá nặng không bao giờ giúp được: nếu dùng quả $3^j$ thì các quả nhỏ hơn cộng lại chỉ được tối đa $1 + 3 + \dots + 3^{j-1} = \frac{3^j - 1}{2}$, nên độ lệch hai đĩa (không kể giỏ) ít nhất là $3^j - \frac{3^j - 1}{2} = \frac{3^j + 1}{2}$. Với $j = 14$ con số này là $2\,391\,485 > 10^6$. Vậy chỉ cần dùng tối đa $14$ quả nhỏ nhất: $k = \min(K, 14)$.
Ta liệt kê một lần tất cả $3^{k} \le 3^{14} = 4\,782\,969$ cách đặt, mỗi cách cho một giá trị $g$ = (tổng đĩa phải) − (tổng đĩa trái). Cách đặt đó cân thăng bằng được giỏ nặng đúng $g$ gam. Lưu ans[g] = số quả ít nhất, rồi mỗi giỏ chỉ việc tra bảng. Mẹo liệt kê nhanh: bắt đầu từ danh sách $\{0\}$, mỗi lần thêm quả $3^j$ thì mỗi phần tử $x$ sinh thêm $x + 3^j$ và $x - 3^j$.
#include <bits/stdc++.h>
using namespace std;
const int MAXM = 1000000;
int ans[MAXM + 1];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, K;
cin >> n >> K;
int k = min(K, 14); // 3^14 > 2 * 10^6: qua can lon hon khong giup can duoc m <= 10^6
// liet ke moi cach dat k qua can: gt = (tong dia phai) - (tong dia trai, khong ke gio)
vector<long long> gt(1, 0);
vector<int> d(1, 0);
long long w = 1;
for (int j = 0; j < k; j++, w *= 3) {
int c = gt.size();
for (int t = 0; t < c; t++) {
gt.push_back(gt[t] + w); d.push_back(d[t] + 1); // dat 3^j len dia phai
gt.push_back(gt[t] - w); d.push_back(d[t] + 1); // dat 3^j len dia trai
}
}
for (int v = 1; v <= MAXM; v++) ans[v] = -1;
for (size_t t = 0; t < gt.size(); t++)
if (gt[t] >= 1 && gt[t] <= MAXM && (ans[gt[t]] < 0 || d[t] < ans[gt[t]])) ans[gt[t]] = d[t];
for (int i = 0; i < n; i++) {
long long m;
cin >> m;
cout << (m <= MAXM ? ans[m] : -1) << '\n';
}
return 0;
}import sys
def main():
data = sys.stdin.buffer.read().split()
n, K = int(data[0]), int(data[1])
MAXM = 1000000
k = min(K, 14) # 3^14 > 2 * 10^6: qua can lon hon khong giup can duoc m <= 10^6
# liet ke moi cach dat k qua can: gt = (tong dia phai) - (tong dia trai, khong ke gio)
gt = [0]; d = [0]
w = 1
for j in range(k):
c = len(gt)
for t in range(c):
g = gt[t]; e = d[t] + 1
gt.append(g + w); d.append(e) # dat 3^j len dia phai
gt.append(g - w); d.append(e) # dat 3^j len dia trai
w *= 3
ans = [-1] * (MAXM + 1)
for t in range(len(gt)):
g = gt[t]
if 1 <= g <= MAXM and (ans[g] < 0 or d[t] < ans[g]):
ans[g] = d[t]
out = []
for i in range(n):
m = int(data[2 + i])
out.append(ans[m] if m <= MAXM else -1)
sys.stdout.write("\n".join(map(str, out)) + "\n")
main()ans ra, các em sẽ thấy mỗi giá trị $g$ chỉ xuất hiện đúng một lần trong $3^k$ cách đặt! Tức là mỗi giỏ cân được theo đúng một cách duy nhất. Cách 3 sẽ giải thích vì sao.Cách 3Hệ cơ số 3 cân bằng – O(N log m) · 100%
Nhìn vào đẳng thức $m = c_0 + 3c_1 + 9c_2 + \dots$, mọi số hạng trừ $c_0$ đều chia hết cho $3$. Vậy $c_0 \equiv m \pmod 3$, và vì $c_0 \in \{-1, 0, 1\}$ nên $c_0$ bị xác định duy nhất:
- $m \bmod 3 = 0$ → $c_0 = 0$ (không dùng quả $1$ gam), còn lại $m' = m / 3$.
- $m \bmod 3 = 1$ → $c_0 = +1$ (quả $1$ gam ở đĩa phải), còn lại $m' = (m - 1)/3$.
- $m \bmod 3 = 2$ → $c_0 = -1$ (quả $1$ gam ở đĩa trái cùng giỏ), còn lại $m' = (m + 1)/3$.
Sau khi chia cho $3$, các quả $3, 9, 27, \dots$ trở thành $1, 3, 9, \dots$ và ta lặp lại đúng bài toán đó với $m'$. Đây chính là cách viết $m$ trong hệ cơ số 3 cân bằng (các chữ số là $-1, 0, 1$). Vì mỗi bước chỉ có một lựa chọn, cách cân là duy nhất — nên "ít nhất" cũng chính là số chữ số khác $0$. Nếu quá trình cần tới chữ số thứ $K+1$ trở đi (tức là phải dùng quả $3^K$ mà thầy không có) thì in $-1$.
Với giỏ $20$ gam: $20 \bmod 3 = 2$ → $-1$, còn $7$; $7 \bmod 3 = 1$ → $+1$, còn $2$; $2 \bmod 3 = 2$ → $-1$, còn $1$; $1 \bmod 3 = 1$ → $+1$, còn $0$. Bốn chữ số $(+1, -1, +1, -1)$ ứng với $27 - 9 + 3 - 1 = 20$: dùng $4$ quả, cần $4 \le K$ quả nên cân được.
Code rất ngắn. Lưu ý: ta không cần tính $3^K$ (với $K = 40$ thì $3^{40}$ đã vượt long long), chỉ cần đếm số chữ số soChuSo rồi so với $K$.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, K;
cin >> n >> K;
string out;
for (int i = 0; i < n; i++) {
long long m;
cin >> m;
int dem = 0, soChuSo = 0; // dem: so qua can dung; soChuSo: can toi qua can 3^(soChuSo-1)
while (m > 0) {
long long r = m % 3;
if (r == 0) m /= 3; // khong dung qua can nay
else if (r == 1) { dem++; m /= 3; } // qua can dat o dia phai
else { dem++; m = m / 3 + 1; } // qua can dat o dia trai (cung gio)
soChuSo++;
}
if (soChuSo > K) out += "-1\n";
else out += to_string(dem) + "\n";
}
cout << out;
return 0;
}import sys
def main():
data = sys.stdin.buffer.read().split()
n, K = int(data[0]), int(data[1])
out = []
for i in range(n):
m = int(data[2 + i])
dem = 0; soChuSo = 0 # dem: so qua can dung; soChuSo: can toi qua can 3^(soChuSo-1)
while m > 0:
q, r = divmod(m, 3)
if r == 0: # khong dung qua can nay
m = q
elif r == 1: # qua can dat o dia phai
dem += 1; m = q
else: # qua can dat o dia trai (cung gio)
dem += 1; m = q + 1
soChuSo += 1
out.append(-1 if soChuSo > K else dem)
sys.stdout.write("\n".join(map(str, out)) + "\n")
main()long long: với $K = 40$ thì $3^{40} \approx 1{,}2 \cdot 10^{19}$ bị tràn số. Cách đếm số chữ số như trên tránh được hoàn toàn chuyện này.Bộ test chấm "bắt" những lỗi nào?
Bộ test có 30 test: Subtask 1 có 10 test ($N \le 100$, $K \le 8$; gồm ví dụ, $K = 1$, $m$ quanh $3280 = \frac{3^8 - 1}{2}$), Subtask 2 có 9 test ($N \approx 10^5$, $m \le 10^6$, $K$ từ $13$ đến $40$), Subtask 3 có 11 test ($N \approx 10^5$, $m$ tới $10^{18}$, ba test $K = 40$). Mỗi test trộn: $m$ ngẫu nhiên, $m$ sát giới hạn $\frac{3^K - 1}{2}$, các giá trị đặc biệt như $\frac{3^p \pm 1}{2}$, $3^p - 1$, và $m$ không cân được dù chỉ có $\le K$ chữ số hệ 3 thường. Điểm tính theo từng test (thang 100%).
| Cách làm | Sub 1 (10 test) | Sub 2 (9 test) | Sub 3 (11 test) | Điểm |
|---|---|---|---|---|
| Cách 1 – Thử mọi cách đặt | Đúng 10/10 | TLE 0/9 | TLE 0/11 | 30 |
| Cách 2 – Liệt kê trước, tra bảng | Đúng 10/10 | Đúng 9/9 | WA 0/11 | 60 |
| Cách 3 – Hệ 3 cân bằng (chuẩn) | Đúng 10/10 | Đúng 9/9 | Đúng 11/11 | 100 |
Sai: tính $3^K$ bằng long long (tràn khi $K = 40$) | Đúng 10/10 | WA 7/9 | WA 8/11 | 82,4 |
| Sai: "cân được" khi $m$ có $\le K$ chữ số hệ 3 thường | WA 3/10 | WA 6/9 | WA 4/11 | 43,5 |
| Sai: tham lam từ quả lớn, nhầm $>$ thành $\ge$ | WA 2/10 | WA 0/9 | WA 0/11 | 6 |
| Sai: chỉ đặt quả cân ở đĩa phải | WA 1/10 | WA 0/9 | WA 0/11 | 3 |
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: Cách 1 đúng 10/10 test Subtask 1 và quá thời gian (hơn 3 giây) ở toàn bộ 20 test còn lại; Cách 2 đúng 19/19 test của hai subtask đầu và sai cả 11 test Subtask 3 (bảng chỉ tới $10^6$); Cách 3 đúng 30/30 test, test lâu nhất chạy khoảng 0,04 giây. Lời giải Python của Cách 3 cũng đúng 30/30 test, chạy tối đa khoảng 0,6 giây với CPython. Ví dụ của đề khá "hiền": $K = 4$ nhỏ và không có giỏ nào nặng trong khoảng $(40, 80]$, nên lời giải tràn số, lời giải dùng sai điều kiện "cân được" và lời giải tham lam nhầm dấu $\ge$ đều vẫn ra đúng — nhớ tự nghĩ thêm test nha!
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