Lật nón lá (Đề tự luyện HSG Tin 9 – Bài 1)
Đề bài
Lật nón lá. Có $N$ chiếc nón lá xếp thành vòng tròn, đánh số $1..N$ theo chiều kim đồng hồ (nón $N$ đứng cạnh nón $1$). Mỗi chiếc nón đang ngửa (0) hoặc úp (1). Mỗi lượt, thầy Sơn chọn hai chiếc nón đứng cạnh nhau và lật cả hai. Tính số lượt ít nhất để mọi chiếc nón đều ngửa, hoặc in $-1$ nếu không thể.
Dữ liệu vào: dòng 1 là $N$ $(2 \le N \le 10^6)$; dòng 2 là xâu $N$ ký tự 0/1.
Kết quả: số lượt lật ít nhất, hoặc $-1$.
- Subtask 1 (20%): $N \le 20$.
- Subtask 2 (30%): $N \le 5000$.
- Subtask 3 (50%): không ràng buộc thêm.
12
1001011000004Các nón $1, 4, 6, 7$ đang úp. Lật lần lượt các cặp $(1,2)$, $(2,3)$, $(3,4)$, $(6,7)$ thì mọi nón đều ngửa. Không có cách nào ít hơn $4$ lượt.
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 Lật nón láLời mở đầu
Thoạt nhìn bài giống một trò chơi phải "thử nhiều đường đi". Nhưng chỉ cần ba nhận xét nhỏ, bài toán trở nên rất gọn.
Nhận xét 1 – Chẵn lẻ. Mỗi lượt lật hai chiếc nón: nếu cả hai đang úp thì số nón úp giảm $2$; nếu cả hai đang ngửa thì tăng $2$; nếu một úp một ngửa thì không đổi. Vậy tính chẵn lẻ của số nón úp không bao giờ thay đổi. Muốn về $0$ nón úp (số chẵn) thì lúc đầu số nón úp phải chẵn. Nếu lẻ: in ngay $-1$.
Nhận xét 2 – Mỗi cặp lật nhiều nhất một lần. Thứ tự các lượt lật không ảnh hưởng tới kết quả cuối cùng (mỗi chiếc nón chỉ quan tâm nó bị lật chẵn hay lẻ lần). Lật một cặp hai lần thì như không lật. Vậy một cách làm tối ưu chỉ là chọn ra một tập các cặp kề nhau, mỗi cặp lật đúng một lần. Có $N$ cặp: $(1,2), (2,3), \dots, (N-1,N)$ và cặp "nối vòng" $(N,1)$.
Nhận xét 3 – Một khi đã biết cặp $(N,1)$ có lật hay không thì mọi thứ bị "ép". Giả sử đã quyết định xong cặp $(N,1)$. Nón $1$ chỉ còn thuộc một cặp chưa quyết định là $(1,2)$: nếu sau khi xét cặp $(N,1)$ mà nón $1$ còn úp thì bắt buộc lật $(1,2)$, ngược lại bắt buộc không lật. Tiếp tục với nón $2$ và cặp $(2,3)$, … Đi hết vòng là ra đúng một tập cặp. Vậy chỉ có đúng hai phương án (không lật / có lật cặp $(N,1)$), chọn phương án ít lượt hơn.
Hình 1. Ví dụ của đề (nón úp tô nâu). Phương án A chính là bốn lượt trong phần giải thích; phương án B dùng đúng tám cặp còn lại.
Ba cách làm dưới đây đi từ "thử hết mọi trạng thái" tới công thức $O(N)$.
Cách 1BFS trên mọi trạng thái – O(2^N · N) · 20%
Coi trạng thái cả vòng nón là một số nhị phân $N$ bit (bit $i$ bằng $1$ nếu nón $i$ đang úp). Từ một trạng thái, có $N$ cách lật (chọn một cặp kề nhau) – tức là XOR với một "mặt nạ" có hai bit $1$ cạnh nhau. Bài toán thành: tìm đường đi ngắn nhất từ trạng thái ban đầu tới trạng thái $0$ trên đồ thị $2^N$ đỉnh — đúng việc của BFS.
Với $N \le 20$ có khoảng $10^6$ trạng thái, mỗi trạng thái thử $N$ cách lật: khoảng $2\cdot10^7$ phép tính. Cách này chưa cần hiểu gì về bài, nhưng không chạy nổi khi $N$ lớn (số trạng thái tăng gấp đôi mỗi khi $N$ tăng $1$).
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
string s;
cin >> n >> s;
// moi trang thai = 1 so nhi phan N bit (bit i = 1: non i dang up)
int start = 0;
for (int i = 0; i < n; i++)
if (s[i] == '1') start |= 1 << i;
vector<int> d(1 << n, -1); // d[u] = so lan lat it nhat de tu start toi u
queue<int> q;
q.push(start);
d[start] = 0;
while (!q.empty()) {
int u = q.front(); q.pop();
if (u == 0) { // tat ca deu ngua
cout << d[u] << '\n';
return 0;
}
for (int i = 0; i < n; i++) { // lat cap (i, i+1), non cuoi canh non dau
int v = u ^ (1 << i) ^ (1 << ((i + 1) % n));
if (d[v] == -1) {
d[v] = d[u] + 1;
q.push(v);
}
}
}
cout << -1 << '\n';
return 0;
}import sys
from collections import deque
def main():
data = sys.stdin.read().split()
n = int(data[0])
s = data[1]
# moi trang thai = 1 so nhi phan N bit (bit i = 1: non i dang up)
start = 0
for i in range(n):
if s[i] == '1':
start |= 1 << i
masks = [(1 << i) | (1 << ((i + 1) % n)) for i in range(n)]
d = [-1] * (1 << n) # d[u] = so lan lat it nhat de tu start toi u
d[start] = 0
q = deque([start])
while q:
u = q.popleft()
if u == 0: # tat ca deu ngua
print(d[u])
return
du = d[u] + 1
for m in masks: # lat cap (i, i+1), non cuoi canh non dau
v = u ^ m
if d[v] == -1:
d[v] = du
q.append(v)
print(-1)
main()Cách 2Cắt vòng ở từng cặp, tham lam trên hàng thẳng – O(N²) · 50%
Trước hết, giả sử nón xếp thẳng hàng (không có cặp $(N,1)$). Nón $1$ chỉ thuộc cặp $(1,2)$, nên nếu nón $1$ úp thì buộc phải lật $(1,2)$. Sau đó nón $2$ chỉ còn cặp $(2,3)$ chưa xét… Cứ thế đi từ trái sang phải: gặp nón úp ở vị trí $i$ thì lật cặp $(i, i+1)$. Cuối cùng nếu nón cuối hàng cũng ngửa là thành công, và số lượt là ít nhất có thể (vì mọi lượt đều bị ép).
Trên vòng tròn, ta "cắt" vòng ở một cặp nào đó (cam kết không bao giờ lật cặp này) để được một hàng thẳng rồi tham lam như trên. Lời giải tối ưu chắc chắn không dùng ít nhất một cặp (nếu dùng cả $N$ cặp thì mỗi nón bị lật đúng $2$ lần, chẳng thay đổi gì — thà không lật). Vậy thử cắt ở từng cặp trong $N$ cặp rồi lấy kết quả nhỏ nhất là chắc chắn đúng.
| Cắt ở cặp | Các cặp phải lật (tham lam) | Số lượt |
|---|---|---|
| (12, 1) | (1,2) (2,3) (3,4) (6,7) | 4 |
| (1, 2) | (4,5) (5,6) (7,8) (8,9) (9,10) (10,11) (11,12) (12,1) | 8 |
| (2, 3) | giống hàng trên | 8 |
| (3, 4) | giống hàng trên | 8 |
| (4, 5) | (6,7) (1,2) (2,3) (3,4) | 4 |
| (5, 6) | (6,7) (1,2) (2,3) (3,4) | 4 |
| (6, 7) | (7,8) (8,9) (9,10) (10,11) (11,12) (12,1) (4,5) (5,6) | 8 |
| (7, 8) … (11, 12) | (1,2) (2,3) (3,4) (6,7) | 4 |
Bảng trên là chạy tay ví dụ của đề. Để ý: dù cắt ở đâu cũng chỉ ra hai bộ cặp khác nhau — bộ 4 cặp và bộ 8 cặp, và $4 + 8 = 12 = N$. Đây chính là gợi ý cho Cách 3.
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
string s;
cin >> n >> s;
int ans = -1;
// thu "cat" vong tron o cap (c-1, c): khong bao gio lat cap nay,
// duoi thanh mot hang thang bat dau tu non c
for (int c = 0; c < n; c++) {
string t = s;
int dem = 0;
for (int k = 0; k + 1 < n; k++) {
int i = (c + k) % n, j = (c + k + 1) % n;
if (t[i] == '1') { // non i dang up: bat buoc lat cap (i, j)
t[i] = '0';
t[j] = (t[j] == '1') ? '0' : '1';
dem++;
}
}
if (t[(c + n - 1) % n] == '0') // non cuoi hang cung phai ngua
if (ans == -1 || dem < ans) ans = dem;
}
cout << ans << '\n';
return 0;
}import sys
def main():
data = sys.stdin.read().split()
n = int(data[0])
s = [1 if c == '1' else 0 for c in data[1]]
ans = -1
# thu "cat" vong tron o cap (c-1, c): khong bao gio lat cap nay,
# duoi thanh mot hang thang bat dau tu non c
for c in range(n):
t = s[c:] + s[:c]
dem = 0
for k in range(n - 1):
if t[k]: # non k dang up: bat buoc lat cap (k, k+1)
t[k] = 0
t[k + 1] ^= 1
dem += 1
if t[n - 1] == 0: # non cuoi hang cung phai ngua
if ans == -1 or dem < ans:
ans = dem
print(ans)
main()Cách 3Hai phương án bù nhau – O(N) · 100%
Theo Nhận xét 3, chỉ có hai phương án:
- Phương án A – không lật cặp $(N,1)$: đây là tham lam trên hàng thẳng $1..N$. Gọi vị trí các nón úp là $p_1 < p_2 < \dots < p_{2m}$. Khi đi từ trái sang, gặp nón úp $p_1$ ta lật $(p_1, p_1+1)$, làm nón $p_1 + 1$ úp, lại phải lật tiếp… "dây chuyền" này chạy tới khi gặp nón úp $p_2$ thì hai cái úp triệt tiêu nhau. Tốn đúng $p_2 - p_1$ lượt. Rồi tới cặp $p_3, p_4$… Vậy $$S = (p_2 - p_1) + (p_4 - p_3) + \dots + (p_{2m} - p_{2m-1}).$$
- Phương án B – có lật cặp $(N,1)$: nó dùng đúng những cặp mà phương án A không dùng. Thật vậy, lấy tất cả $N$ cặp trừ đi các cặp của A: mỗi nón thuộc đúng $2$ cặp của vòng, nên số lần bị lật của mỗi nón đổi từ $k$ thành $2 - k$ — cùng chẵn lẻ với $k$. Vậy bộ cặp "phần bù" cũng làm mọi nón ngửa, và nó có lật cặp $(N,1)$. Do phương án B là duy nhất, nó chính là phần bù, tốn $N - S$ lượt.
Kiểm tra với ví dụ: $p = (1, 4, 6, 7)$, $S = (4 - 1) + (7 - 6) = 4$, $N - S = 8$, đáp án $\min(4, 8) = 4$ — khớp bảng ở Cách 2. Mô phỏng dưới đây chạy tham lam cho cả hai phương án để em thấy chúng bù nhau.
Code chỉ cần duyệt xâu một lần để lấy các vị trí nón úp rồi tính $S$:
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
string s;
cin >> n >> s;
// vi tri cac non dang up (danh so tu 1)
vector<int> p;
for (int i = 0; i < n; i++)
if (s[i] == '1') p.push_back(i + 1);
if (p.size() % 2 == 1) { // moi lan lat, so non up thay doi 0 hoac 2
cout << -1 << '\n';
return 0;
}
// cach A: khong lat cap (N, 1) -> ghep (p1,p2), (p3,p4), ...
long long S = 0;
for (size_t k = 0; k < p.size(); k += 2) S += p[k + 1] - p[k];
// cach B: dung dung nhung cap ma cach A khong dung -> N - S lan
cout << min(S, (long long)n - S) << '\n';
return 0;
}import sys
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0])
s = data[1].decode()
# vi tri cac non dang up (danh so tu 1)
p = [i + 1 for i, c in enumerate(s) if c == '1']
if len(p) % 2 == 1: # moi lan lat, so non up thay doi 0 hoac 2
print(-1)
return
# cach A: khong lat cap (N, 1) -> ghep (p1,p2), (p3,p4), ...
S = sum(p[1::2]) - sum(p[0::2])
# cach B: dung dung nhung cap ma cach A khong dung -> N - S lan
print(min(S, n - S))
main()1000000001 phương án A tốn $9$ lượt còn đáp án đúng chỉ là $1$ (lật cặp $(10, 1)$).Bộ test chấm "bắt" những lỗi nào?
Bộ test có 34 test: Subtask 1 có 12 test ($N \le 20$; gồm ví dụ, $N = 2$, toàn nón úp, 1000…01), Subtask 2 có 10 test ($N \approx 5000$), Subtask 3 có 12 test ($N \approx 10^6$). Mỗi subtask có 2 test số nón úp lẻ; phần lớn các test còn lại có phương án "lật qua cặp $(N,1)$" tốt hơn. Điểm tính theo từng test (thang 100%).
| Cách làm | Sub 1 (12 test) | Sub 2 (10 test) | Sub 3 (12 test) | Điểm |
|---|---|---|---|---|
| Cách 1 – BFS trên $2^N$ trạng thái | Đúng 12/12 | RE 0/10 | RE 0/12 | 20 |
| Cách 2 – Cắt vòng ở từng cặp, $O(N^2)$ | Đúng 12/12 | Đúng 10/10 | TLE 0/12 | 50 |
| Cách 3 – $\min(S, N - S)$ (chuẩn) | Đúng 12/12 | Đúng 10/10 | Đúng 12/12 | 100 |
| Sai: quên in $-1$ khi số nón úp lẻ | WA 10/12 | WA 8/10 | WA 10/12 | 82,3 |
| Sai: chỉ thử cắt ở cặp $(N,1)$ và $(1,2)$ | WA 7/12 | WA 4/10 | WA 5/12 | 44,5 |
| Sai: coi như nón xếp thẳng hàng | WA 6/12 | WA 4/10 | WA 4/12 | 38,7 |
| Sai: đáp án = số nón úp / 2 | WA 6/12 | WA 3/10 | WA 4/12 | 35,7 |
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 12/12 test Subtask 1 và bị lỗi chạy (không cấp phát nổi mảng $2^N$ phần tử) ở toàn bộ 22 test còn lại; Cách 2 đúng 22/22 test của hai subtask đầu và quá thời gian (hơn 3 giây) ở cả 12 test Subtask 3; Cách 3 đúng 34/34 test, test lâu nhất chạy chưa tới 0,02 giây. Lời giải Python của Cách 3 cũng đúng 34/34 test, chạy tối đa khoảng 0,13 giây với CPython. Ví dụ của đề khá "hiền": lời giải quên trường hợp lẻ, lời giải coi như hàng thẳng và lời giải chỉ thử hai chỗ cắt đều vẫn ra đúng $4$ — nên 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