Đồng Tiền Xu Giả (FCOIN)
Đề bài
Đồng tiền xu giả
Có $n$ $(n \ge 2)$ đồng tiền xu trong đó có đúng một đồng tiền giả. Đồng tiền giả này có khối lượng nhẹ hơn so với các đồng tiền thật (tất cả các đồng tiền thật có khối lượng bằng nhau). Sử dụng cân thăng bằng, cân sẽ cho ta biết bên nào nặng hơn, bên nào nhẹ hơn hoặc hai bên bằng nhau. Để tìm đồng tiền giả ta đánh số các đồng tiền từ $1$ đến $n$, sau đó tiến hành cân một số lần, mỗi lần cân là đặt một lượng đồng xu bằng nhau lên đĩa bên trái và đĩa bên phải. Kết quả của các lần cân được ghi lại.
Yêu cầu: Xác định đồng xu giả sử dụng các kết quả được ghi chép lại.
Dữ liệu: Vào từ file văn bản FCOIN.INP theo khuôn dạng:
- Dòng đầu là hai số nguyên $n$ và $k$ trong đó $n$ là số đồng tiền xu, $k$ là số lần cân được ghi chép lại.
- Tiếp theo là $k$ dòng mô tả $k$ lần cân, mỗi dòng mô tả một lần cân. Lần cân thứ $i$ có dạng: Bắt đầu bằng số nguyên $s_i$ $(1 \le s_i \le \frac{n}{2})$ là số đồng xu được đặt lên bên phải và bên trái. Tiếp theo là $s_i$ số nguyên là số hiệu các đồng xu được đặt bên trái và $s_i$ số nguyên là số hiệu các đồng xu được đặt bên phải. Cuối cùng là một số mô tả kết quả lần cân đó, số $0$ nếu cân thăng bằng, số $1$ nếu bên trái nặng hơn, số $2$ nếu bên phải nặng hơn. Dữ liệu đảm bảo đúng đắn và tổng $s_1 + s_2 + \dots + s_k$ không vượt quá $10^5$.
Kết quả: Ghi ra file văn bản FCOIN.OUT một số nguyên là số hiệu đồng xu giả hoặc ghi ra số $0$ nếu không thể tìm ra đồng xu giả.
Ràng buộc:
- Có 30% số test của bài có $n \le 3$;
- Có 40% số test khác của bài có $n \le 100$;
- Có 30% số test còn lại của bài có $n \le 10^9$.
Ví dụ: (khung trái là nội dung FCOIN.INP, khung phải là nội dung FCOIN.OUT)
2 1
1 1 2 126 2
1 1 2 0
2 1 2 3 4 00FCOIN.INP / FCOIN.OUT. Các code bên dưới dùng mẹo if (fopen("FCOIN.INP", "r")) { freopen(...); freopen(...); } (Python: if os.path.exists("FCOIN.INP")): có file thì đọc/ghi file, không có thì đọc bàn phím và in ra màn hình. Nhờ vậy cùng 1 code nộp được cả lên hệ thống chấm đọc từ bàn phím lẫn khi thi chấm bằng file.Lời mở đầu
Bài này mình được một bạn học viên hỏi nên sẵn tiện mình viết bài giải chi tiết để nhiều bạn được tham khảo luôn. Hy vọng mang đến được giá trị cho các bạn 😇. Bạn nào muốn thử nộp bài để hệ thống chấm xem có đúng hay không thì link bài đây nhé:
Link này công khai, 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é. Chưa có tài khoản thì tạo tài khoản rồi đăng nhập nộp bài thử hen.
Nộp bài trên NTUCoderLộ trình lời giải, bấm vào từng phần để nhảy tới:
Ý tưởngNhìn kỹ test mẫu – rồi đừng tin nó hoàn toàn
Một kinh nghiệm mình chia sẻ đến các bạn đó là hãy nhìn vào các test ví dụ mẫu đề đưa ra để qua đó ta phần nào hình dung được những trường hợp và tư tưởng xử lý vấn đề. Tuy nhiên cũng cảnh báo là đừng tin nó hoàn toàn nhé, vì nhiều bài sẽ cố tình đưa ra test ví dụ khiến ta hình dung sai về tư tưởng giải quyết đúng cho bài đó. Cũng như một điều chắc chắn là nó sẽ không bao giờ đưa ra đầy đủ các trường hợp, những trường hợp ví dụ mẫu đưa ra chỉ là tiêu biểu nhất thôi, còn lại tự ta phải suy nghĩ những trường hợp khác, nhất là những trường hợp đặc biệt, vì các test case lúc nào cũng sẽ có những trường hợp đó, nếu chúng ta bỏ sót là sai ngay.
Ví dụ 1: cân đúng 1 đồng mỗi bên mà bị lệch
Ở ví dụ đầu tiên ta thấy rằng nếu ở lần cân nào mà chỉ cân 1 đồng tiền mỗi bên mà ở lần cân đó có sự chênh lệch nặng nhẹ thì rõ ràng ngay lập tức đã tìm ra được đồng tiền giả: chính là đồng ở bên nhẹ hơn. Ta có thể dừng và kết luận luôn, không cần đọc tiếp dữ liệu input nữa (nếu còn).
Ví dụ 2: cân luôn thăng bằng
Còn ở ví dụ thứ 2, khi cân luôn ở trạng thái cân bằng tức là không có trường hợp nào khiến cân bị lệch, nghĩa là không có trường hợp nào nghi vấn đồng xu giả. Qua 2 lần cân xác định được các đồng xu $1, 2, 3, 4$ đều là đồng xu thật, trong khi đó có đến $N = 6$ đồng xu, nghĩa là còn 2 đồng xu $5, 6$ chưa xác minh được thật hay giả. Lúc này ta sẽ kết luận $0$ tức là không thể tìm được.
Vậy ta có thể suy nghĩ tiếp: nếu cũng ở tình huống 2 này mà ta lại có thêm 1 lần cân xác định được đồng 5 là đồng thật, ví dụ 2 1 2 4 5 0 (cân 2 đồng $1, 2$ với $4, 5$ và cân thăng bằng). Như thế tuy không có dữ kiện về đồng xu giả nhưng lúc này số lượng đồng xu xác định là thật có đến 5 đồng. Trong khi ta có tổng cộng 6 đồng ⇒ 1 đồng còn lại chắc chắn là đồng giả, vì đề bài luôn đảm bảo có đúng 1 đồng giả.
Và ta có thể tìm ra được đồng đó bằng cách nào? Lúc này nó quy về bài toán có các số từ $1$ đến $N$ nhưng bị thiếu đi 1 số, hỏi số bị thiếu là số nào? Cách đơn giản nhất là tính tổng các số từ $1$ đến $N$ trừ cho tổng các số đang có, kết quả chính là số còn thiếu. Tổng từ $1$ đến $N$ tính nhanh bằng công thức cấp số cộng:
Khi $N = 6$: $6 \cdot 7 / 2 = 21$. Tổng các đồng thật $1 + 2 + 3 + 4 + 5 = 15$ ⇒ $21 - 15 = 6$, đồng 6 là đồng xu giả. Nếu lần cân cuối lại xác định đồng thật là 6 thì $1 + 2 + 3 + 4 + 6 = 16$ ⇒ $21 - 16 = 5$, đồng 5 là đồng giả. Các bạn nhìn ra quy luật rồi hen? Công thức này vẫn chạy tốt khi $n$ lên tới $10^9$ (nhớ dùng long long), ta không cần mảng $n$ phần tử nào cả.
Cái bẫy mà test trên web không bắt
Đến đây ta có thể nghĩ ra cách làm gồm 2 bước:
- Đọc dữ liệu, lần cân nào chỉ cân 1 đồng mỗi bên mà bị lệch (kết quả 1 hay 2) thì đồng ở bên nhẹ hơn là đồng giả, kết luận và dừng.
- Nếu đọc hết mà không gặp tình huống 1: đếm số đồng thật. Bằng $N - 1$ thì đồng giả = tổng $1..N$ − tổng các đồng thật. Khác $N - 1$ (tức là nhỏ hơn $N - 1$, vì có đúng 1 đồng giả nên số đồng thật tối đa chỉ là $N - 1$) thì kết luận $0$.
Nhưng hãy suy nghĩ kỹ xem kết luận $0$ như thế có ổn không? Code ban đầu của mình cũng xử lý theo đúng 2 trường hợp này thôi và nộp thì code vẫn AC. Nhưng sau đó mình thấy cũng có gì đó kỳ kỳ, không được chắc chắn. Nên mình thử tự đưa ra 1 số test thì phát hiện trường hợp khiến code mình bị sai. Qua đó có thể thấy test case bài này trên web còn yếu (chỉ có 10 test), thường muốn chắc chắn là các bài phải có cả 50, 60 hay thậm chí hàng trăm test case. Bạn nào code đã AC thì thử test với trường hợp sau nhé:
5 2
2 1 2 4 5 2
2 1 3 4 5 2Với trường hợp này thì tình huống 1 không thỏa vì chẳng có lần nào chỉ cân 1 đồng. Tình huống 2 thì số đồng xu thật chỉ có 2 đồng là $4, 5$, khác $N - 1 = 4$ nên sẽ kết luận $0$. Trong khi đó các bạn xem nhé:
| Lần cân | Dòng input | Bên nhẹ (chứa đồng giả) | Bên nặng (toàn đồng thật) |
|---|---|---|---|
| 1 | 2 1 2 4 5 2 | {1, 2} | {4, 5} |
| 2 | 2 1 3 4 5 2 | {1, 3} | {4, 5} |
| Kết luận | Đồng giả nằm trong cả {1, 2} lẫn {1, 3} ⇒ chỉ có thể là đồng 1 | ||
Vì theo nguyên tắc chỉ có duy nhất 1 đồng xu giả, mà trong cả 2 lần cân bị lệch thì đồng 1 đều nằm ở bên nhẹ, nên đồng 1 chính là đồng xu giả. Đáp án đúng là 1 chứ không phải $0$!
- Thăng bằng ⇒ mọi đồng trên cân đều thật.
- Bị lệch ⇒ bên nặng toàn đồng thật, đồng giả chắc chắn nằm bên nhẹ.
Em nhập $n$ và các lần cân (mỗi lần cân viết đúng như 1 dòng input, các lần cân cách nhau bởi dấu ;) rồi bấm Tiếp để xem từng lần cân loại trừ dần các đồng xu:
Cách 1Subtask n ≤ 100: thử từng đồng là đồng giả
Phần này mình viết thêm cho các bạn mới làm quen: với 70% số test có $n \le 100$, ta cứ giả sử lần lượt từng đồng $f = 1, 2, \ldots, n$ là đồng giả rồi kiểm tra xem giả sử đó có khớp với tất cả các lần cân không:
- Nếu $f$ nằm bên trái thì bên trái nhẹ hơn ⇒ kết quả phải là
2(bên phải nặng hơn). - Nếu $f$ nằm bên phải ⇒ kết quả phải là
1. - Nếu $f$ không lên cân ⇒ hai bên toàn đồng thật ⇒ kết quả phải là
0.
Đếm số đồng $f$ khớp hết: đúng 1 đồng thì in đồng đó, còn lại (nhiều đồng cùng khớp, không phân biệt được) thì in $0$. Cách này đúng theo định nghĩa nên rất dễ tin, mình còn dùng nó làm code đối chứng cho Cách 2.
#include <bits/stdc++.h>
using namespace std;
int main() {
if (fopen("FCOIN.INP", "r")) {
freopen("FCOIN.INP", "r", stdin);
freopen("FCOIN.OUT", "w", stdout);
}
int n, k;
cin >> n >> k;
vector<vector<int>> L(k), R(k);
vector<int> res(k);
for(int t = 0; t < k; ++t){
int s;
cin >> s;
L[t].resize(s);
R[t].resize(s);
for(int i = 0; i < s; ++i) cin >> L[t][i];
for(int i = 0; i < s; ++i) cin >> R[t][i];
cin >> res[t];
}
int cnt = 0, ans = 0;
for(int f = 1; f <= n; ++f){
bool ok = true;
for(int t = 0; t < k && ok; ++t){
int expect = 0;
for(int x : L[t]) if(x == f) expect = 2;
for(int x : R[t]) if(x == f) expect = 1;
if(expect != res[t]) ok = false;
}
if(ok){
cnt++;
ans = f;
}
}
if(cnt == 1) cout << ans;
else cout << 0;
return 0;
}import sys, os
if os.path.exists("FCOIN.INP"):
sys.stdin = open("FCOIN.INP", "r")
sys.stdout = open("FCOIN.OUT", "w")
data = sys.stdin.read().split()
idx = 0
n, k = int(data[0]), int(data[1])
idx = 2
L, R, res = [], [], []
for _ in range(k):
s = int(data[idx]); idx += 1
L.append(set(map(int, data[idx:idx + s]))); idx += s
R.append(set(map(int, data[idx:idx + s]))); idx += s
res.append(int(data[idx])); idx += 1
cnt = ans = 0
for f in range(1, n + 1): # giả sử đồng f là đồng giả
ok = True
for t in range(k):
expect = 2 if f in L[t] else (1 if f in R[t] else 0)
if expect != res[t]:
ok = False
break
if ok:
cnt += 1
ans = f
print(ans if cnt == 1 else 0)Độ phức tạp: với mỗi đồng $f$ phải duyệt lại toàn bộ các lần cân ⇒ $O(n \cdot (s_1 + \dots + s_k))$. Với $n \le 100$ thì tối đa khoảng $100 \cdot 2 \cdot 10^5 = 2 \cdot 10^7$, chạy ngon. Nhưng với $n = 10^9$ thì vòng for theo $f$ thôi đã chạy không nổi rồi ⇒ cần cách khác.
Cách 2Set chứa đồng thật + Map đếm đồng nghi ngờ – AC với n ≤ 10⁹
Vậy nên để xét được trường hợp đặc biệt ở trên thì ta cần phải thống kê số lần xuất hiện của từng đồng xu trong nhóm nghi có đồng giả ở mỗi lần cân (tức là nhóm các đồng xu ở bên cân bị nhẹ hơn). Rồi với từng đồng xu đó ta xét qua nhóm các đồng xu đã xác định là thật (bên cân nặng hơn hay các lần cân thăng bằng): nếu đồng xu đó đã có bên nhóm các đồng xu thật thì ta loại bỏ nó khỏi nhóm nghi ngờ. Sau cùng:
- Nếu nhóm nghi ngờ chỉ còn 1 đồng duy nhất thì đó là đáp án.
- Nếu nhóm nghi ngờ có nhiều hơn 1 đồng thì xét số lần xuất hiện của từng đồng so với $Z$, với $Z$ là số lần cân bị mất thăng bằng. Đồng nào xuất hiện đủ $Z$ lần và chỉ có 1 đồng duy nhất như vậy thì đó là đáp án, còn từ 2 đồng trở lên thì kết luận không thể tìm ra đồng xu giả.
Cũng lưu ý các bạn là ở từng lần cân thì các đồng xu được chọn cân ngẫu nhiên, nên chắc chắn sẽ có những đồng đã được cân ở các lần trước đó, ta phải xử lý không xét trùng. Như ví dụ ở trên thì 2 lần cân đều xác định các đồng xu thật là $\{4, 5\}$. Lần đầu ta bỏ $\{4, 5\}$ vào tập hợp, lần sau bỏ vào nữa thì tập hợp phải tự bỏ qua những đồng đã có. Như thế sau cùng muốn biết có bao nhiêu đồng xu thật chỉ cần lấy kích cỡ tập hợp ra là xong. Tiện nhất là dùng:
settrong STL C++ chứa các đồng thật: dữ liệu cứ liên tục đổ vào, nó chỉ giữ các phần tử phân biệt, cuối cùng gọise.size()là biết ngay có bao nhiêu đồng thật.mapvới key là số hiệu đồng xu, value là số lần đồng đó nằm ở bên nhẹ: với mỗi đồng bên nhẹ, ta tìm nó trong set, tìm thấy thì đó là đồng thật, bỏ qua; không thấy thì đồng đó "có thể" là đồng giả, tăngmp[x]thêm 1 (chưa có trong map thìmp[x]++tự tạo mới với giá trị 1).
Cứ thế sau cùng ta kiểm tra:
se.size() == n - 1⇒ tìm được đồng xu giả bằng công thức tổng.- Ngược lại xét qua map (chỉ những đồng không nằm trong set):
size == 0⇒ in $0$;size == 1⇒ đó là đồng giả;size > 1⇒ tìm những đồng có số lần xuất hiện bằng $Z$, đúng 1 đồng thì in nó, nhiều hơn thì in $0$.
Source code cho các bạn tham khảo nếu làm theo tư tưởng mình trình bày ở trên:
#include <bits/stdc++.h>
using namespace std;
int main() {
if (fopen("FCOIN.INP", "r")) {
freopen("FCOIN.INP", "r", stdin);
freopen("FCOIN.OUT", "w", stdout);
}
ios::sync_with_stdio(0);
cin.tie(0);
long long n, k, z = 0;
cin >> n >> k;
set<int> se;
set<int>::iterator its;
map<int, int> mp, mp2;
map<int, int>::iterator itm;
while(k--){
int s;
cin >> s;
vector<int> a(s), b(s);
for(int i = 0; i < s; ++i){
cin >> a[i];
}
for(int i = 0; i < s; ++i){
cin >> b[i];
}
int res;
cin >> res;
if(res == 0){
for(int i = 0; i < s; ++i){
se.insert(a[i]);
se.insert(b[i]);
}
}
else if(res == 1){
z++;
if(s == 1){
cout << b[0];
return 0;
}
for(int i = 0; i < s; ++i){
se.insert(a[i]);
if(se.find(b[i]) == se.end()){
mp[b[i]]++;
}
}
}
else{
z++;
if(s == 1){
cout << a[0];
return 0;
}
for(int i = 0; i < s; ++i){
se.insert(b[i]);
if(se.find(a[i]) == se.end()){
mp[a[i]]++;
}
}
}
}
if(se.size() == n - 1){
long long sum = 0;
for(its = se.begin(); its != se.end(); ++its){
sum += *its;
}
cout << (n * (n + 1)) / 2 - sum;
}
else{
for(itm = mp.begin(); itm != mp.end(); ++itm){
if(se.find(itm->first) == se.end()){
mp2.insert({itm->first, itm->second});
}
}
if(mp2.size() == 0){
cout << 0;
}
else if(mp2.size() == 1){
cout << mp2.begin()->first;
}
else{
vector<int> c;
for(itm = mp2.begin(); itm != mp2.end(); ++itm){
if(itm->second == z){
c.push_back(itm->first);
}
}
if(c.size() == 1){
cout << c[0];
}
else{
cout << 0;
}
}
}
return 0;
}import sys, os
if os.path.exists("FCOIN.INP"):
sys.stdin = open("FCOIN.INP", "r")
sys.stdout = open("FCOIN.OUT", "w")
input = sys.stdin.read
data = list(map(int, input().split()))
idx = 0
n, k = data[idx], data[idx + 1]
idx += 2
se = set()
mp = {}
z = 0
for _ in range(k):
s = data[idx]
idx += 1
a = data[idx:idx + s]
idx += s
b = data[idx:idx + s]
idx += s
res = data[idx]
idx += 1
if res == 0:
for i in range(s):
se.add(a[i])
se.add(b[i])
elif res == 1:
z += 1
if s == 1:
print(b[0])
sys.exit(0)
for i in range(s):
se.add(a[i])
if b[i] not in se:
mp[b[i]] = mp.get(b[i], 0) + 1
else:
z += 1
if s == 1:
print(a[0])
sys.exit(0)
for i in range(s):
se.add(b[i])
if a[i] not in se:
mp[a[i]] = mp.get(a[i], 0) + 1
if len(se) == n - 1:
total = n * (n + 1) // 2
sum_se = sum(se)
print(total - sum_se)
else:
mp2 = {key: val for key, val in mp.items() if key not in se}
if len(mp2) == 0:
print(0)
elif len(mp2) == 1:
print(next(iter(mp2)))
else:
c = [key for key, val in mp2.items() if val == z]
if len(c) == 1:
print(c[0])
else:
print(0)Giải thích một số chỗ trong code ở trên:
- Bạn nào chưa biết về cấu trúc dữ liệu
mapvàsettrong STL C++ thì xem code sẽ không hiểu đâu, nên các bạn chưa biết thì phải tìm hiểu về 2 cấu trúc dữ liệu này nhé rồi quay lại đây xem code mới hiểu rõ được. - Mặc dù ở mỗi lần cân bị lệch ta đều chỉ đưa vào
mpnhững đồng bên nhẹ không nằm trong set (se.find(b[i]) == se.end()nghĩa là đồngb[i]không nằm trong set), nhưng ở bước cuối khise.size() != n - 1thì để chắc ăn ta vẫn quay lại mapmpđể bỏ qua những đồng đã có trong set. Bởi vì lỡ lúc xét thì đồng đó chưa có trong set, nhưng các lần cân tiếp theo đồng đó lại được xác định là thật, nên khúc cuối này phải xét lại thêm lần nữa cho chắc. - Theo lẽ đồng nào trong map mà đã có trong set thì ta sẽ xóa ra khỏi map. Nhưng việc đang duyệt con trỏ vào từng phần tử trong map rồi đi xóa phần tử đó sẽ rất có khả năng gây ra lỗi khi con trỏ duyệt qua phần tử tiếp theo, chỗ này mình ngán lắm vì rất dễ văng lỗi. Nên giải pháp an tâm nhất là tạo map mới
mp2, phần tử nào trongmpkhông nằm trong set thì đưa quamp2. Sau cùngmp2chỉ toàn những đồng có khả năng là đồng giả, rồi xét số lượng phần tử của nó như đã nói ở trên, cần thì tạo vectorcchứa các đồng có số lần xuất hiện bằngz.
Đánh giá độ phức tạp
Gọi $S = s_1 + s_2 + \dots + s_k \le 10^5$ (đừng nhầm với $n$ là số đồng xu ở đầu input nhé, ý nghĩa khác nhau đấy).
- Không gian: khi dùng các cấu trúc dữ liệu STL như
vector,set,mapthì bộ nhớ thường được cấp phát dư ra để xài linh động, nên ta chỉ tính tương đối theo dữ liệu đưa vào. Mảnga,bchứa các đồng ở 2 đĩa cân;setvàmapcộng lại cũng tối đa bằng tổng số đồng xu ở các đĩa cân ⇒ $O(4S)$, tức $O(S)$. - Thời gian: đọc dữ liệu $O(2S)$; vì kết quả cân nằm ở cuối dòng nên đọc xong mới duyệt lại các đồng để đưa vào set/map, thêm $O(2S)$ nữa. Mỗi thao tác
insert/findtrên set, map tốn $O(\log S)$ (chưa tính chi phí cân bằng cây), bước kết luận duyệt set/map mất $O(S)$. Tổng cộng cỡ $O(S \log S)$.
Trường hợp xấu nhất $S = 10^5$ thì số phép tính cỡ vài triệu, tính luôn chi phí cân bằng cây thì vẫn rất xa ngưỡng $10^8$ phép tính cho 1 giây, nên yên tâm không sợ bị TLE nhé.
fopen / os.path.exists và đổi exit(0) thành sys.exit(0)); Cách 1 và bản Python của nó là mình viết thêm. Cả 4 bản đã được kiểm tra với 300 bộ test ngẫu nhiên ($2 \le n \le 9$, 1–4 lần cân, dữ liệu sinh từ 1 đồng giả thật sự, khoảng 1/4 số test có đáp án $0$) và các test đặc biệt ở trên: khớp 100%. Với $n = 10^9$, $S = 10^5$ (100 lần cân, mỗi lần 1000 đồng mỗi bên), bản C++ Cách 2 chạy khoảng 0.3 giây, bản Python khoảng 0.2 giây; kiểm tra thêm chế độ đọc/ghi file FCOIN.INP/FCOIN.OUT cũng cho kết quả đúng.