Vòng số nguyên tố
Đề bài
Một vòng tròn chứa $2 \times n$ vòng tròn nhỏ (xem hình vẽ). Các vòng tròn nhỏ được đánh số từ $1$ đến $2 \times n$ theo chiều kim đồng hồ. Cần điền các số tự nhiên từ $1$ đến $2 \times n$, mỗi số vào một vòng tròn nhỏ, sao cho tổng của hai số trên hai vòng tròn nhỏ liên tiếp là số nguyên tố. Số điền ở vòng tròn nhỏ $1$ luôn là số $1$.
Input: số nguyên dương $n$ $(1 < n < 10)$.
Output:
- Dòng đầu tiên ghi ra số $k$ là số cách tìm được.
- $k$ dòng tiếp theo, mỗi dòng ghi ra 1 cách điền các số vào các vòng tròn nhỏ (số ở vòng 1, vòng 2, …, vòng $2n$). Cách điền nào có thứ tự từ điển nhỏ hơn thì xếp trước. Nếu $k > 10000$ thì chỉ cần ghi ra $10000$ cách đầu tiên.
44
1 2 3 8 5 6 7 4
1 2 5 8 3 4 7 6
1 4 7 6 5 8 3 2
1 6 7 4 3 8 5 2Lưu ý: vì là vòng tròn nên ô $2n$ cũng kề với ô $1$ – tổng của số cuối và số $1$ cũng phải là số nguyên tố. Ở dòng đầu, $k$ là tổng số cách (kể cả khi chỉ in 10000 cách).
Lời mở đầu
Bài này là "hoán vị có điều kiện": ta cần liệt kê các hoán vị của $2, 3, \dots, 2n$ (số 1 đứng cố định ở đầu) sao cho hai số kề nhau có tổng nguyên tố. Mình sẽ đi từ cách sinh mọi hoán vị (chỉ qua được $n$ nhỏ), tới quay lui có cắt nhánh, rồi thêm một nhận xét chẵn lẻ để chạy nhanh gấp đôi.
Link này chỉ học viên đã tham gia tổ chức mới vào được. Học viên nên ưu tiên nộp ở đây vì sẽ được chấm nhanh hơn.
Nộp bài trên CLUE OJLộ trình lời giải, bấm vào từng phần để nhảy tới:
Bộ testBộ test chính thức có gì?
| Test | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|
| n | 4 | 3 | 2 | 5 | 6 | 7 | 8 | 9 |
| Số cách k | 4 | 2 | 2 | 96 | 1.024 | 2.880 | 81.024 | 770.144 |
| Số dòng cách in ra | 4 | 2 | 2 | 96 | 1.024 | 2.880 | 10.000 | 10.000 |
Bộ test có 8 test, mỗi giá trị $n$ từ 2 đến 9 đúng một test. Hai test cuối có $k > 10000$ nên chỉ in 10000 cách, nhưng dòng đầu vẫn là tổng số cách thật. Đề không chia subtask, mình tự chia 2 mức theo độ lớn của $n$ (giới hạn 1 giây):
| Mức | Điều kiện | Test | Cách 1 (hoán vị) | Cách 2 (quay lui) | Cách 3 (+ chẵn lẻ) |
|---|---|---|---|---|---|
| 1 | $n \le 6$ | 1–5 | 5/5 | 5/5 | 5/5 |
| 2 | $7 \le n \le 9$ | 6–8 | 0/3 | 3/3 | 3/3 |
Ý tưởngĐiền lần lượt từng ô, sai là quay lui ngay
Ta điền số cho ô $2, 3, \dots, 2n$ theo thứ tự. Ở ô $i$, thử các số $v$ từ nhỏ đến lớn mà:
- $v$ chưa được dùng (mảng đánh dấu
dd[v]); - $a_{i-1} + v$ là số nguyên tố.
Nếu thoả thì điền $v$, gọi đệ quy sang ô $i + 1$; gọi xong thì bỏ đánh dấu $v$ (quay lui). Khi đã điền tới ô $2n$ thì kiểm tra thêm cặp "khép vòng" $a_{2n} + a_1$.
Vì đề bắt in $k$ trước các cách, mà $k$ chỉ biết khi đã quay lui xong, ta lưu tạm tối đa 10000 cách vào một xâu rồi mới in. Em chọn $n$ rồi bấm Tiếp để xem cây quay lui (nút đỏ = ngõ cụt, nút xanh = một cách hợp lệ):
Cách 1Sinh mọi hoán vị – O((2n−1)!·n)
Giữ $a_1 = 1$, dùng next_permutation sinh mọi hoán vị của $a_2..a_{2n}$ (tự động theo thứ tự từ điển), với mỗi hoán vị kiểm tra $2n$ cặp kề nhau.
for kiểm tra được gộp vào bước ở dòng if(!nt(...)); các bước tạo xâu s gộp vào bước lưu.j = (i == m) ? 1 : i + 1: ô kề sau ô cuối là ô 1 (vòng tròn).next_permutation(a + 2, a + m + 1)chỉ hoán vị đoạn $a_2..a_m$, số 1 đứng yên.
Có $(2n-1)!$ hoán vị: $n = 6$ là $11! \approx 4 \cdot 10^7$ – vừa kịp; $n = 7$ đã là $13! \approx 6 \cdot 10^9$ – hết cứu.
Kết quả chạy thật: Bản C++ đúng 5/8 test, quá thời gian ở test 6–8; test đúng chạy lâu nhất 0.22s.
Cách 2Quay lui + cắt nhánh
Kiểm tra điều kiện nguyên tố ngay khi điền từng ô: chỉ cần một cặp sai là bỏ cả nhánh phía sau. Các số nguyên tố đến $4n$ được tính sẵn vào mảng nt[] để tra trong $O(1)$.
if(!dd[v] && nt[a[i - 1] + v]): chỉ đi tiếp khi $v$ chưa dùng và tạo tổng nguyên tố với ô trước – đây là chỗ cắt nhánh.if(i < m) Try(i + 1);còn ô thì đi sâu tiếp;else if(nt[a[m] + a[1]])là ô cuối thì kiểm tra cặp khép vòng.kkiểulong longvà vẫn tăng sau khi đã đủ 10000 cách; chỉ việc lưu là dừng ở 10000.
Kết quả chạy thật: Bản C++ đúng 8/8 test; test đúng chạy lâu nhất 0.62s. Còn bản Python đúng 7/8 test, quá thời gian ở test 8; test đúng chạy lâu nhất 0.96s.
Cách 3Thêm nhận xét chẵn lẻ
Tổng hai số kề nhau $\ge 1 + 2 = 3$, mà số nguyên tố lớn hơn 2 đều lẻ. Tổng lẻ thì hai số phải khác tính chẵn lẻ. Vì $a_1 = 1$ lẻ, nên dọc theo vòng: ô lẻ chứa số lẻ, ô chẵn chứa số chẵn. Vậy ở ô $i$ chỉ cần thử $v$ cùng tính chẵn lẻ với $i$ – vòng for nhảy bước 2, bớt một nửa số lần thử ở mỗi tầng.
Chỉ khác cách 2 ở dòng for: v bắt đầu từ 2 (ô chẵn) hoặc 3 (ô lẻ) và tăng 2 mỗi lần.
Kết quả chạy thật: Bản C++ đúng 8/8 test; test đúng chạy lâu nhất 0.37s. Còn bản Python đúng 7/8 test, quá thời gian ở test 8; test đúng chạy lâu nhất 0.61s.
Tổng kếtKết quả chạy thật trên bộ test
| Cách | Ngôn ngữ | Đúng | Lâu nhất | Ghi chú |
|---|---|---|---|---|
| 1. Sinh mọi hoán vị | C++ | 5/8 | > 1s | Quá thời gian test 6–8 (n = 7, 8, 9) |
| 2. Quay lui + cắt nhánh | C++ | 8/8 | 0.62s | Full |
| Python | 7/8 | > 1s | Quá thời gian test 8 (n = 9) | |
| 3. Quay lui + chẵn lẻ | C++ | 8/8 | 0.37s | Full |
| Python | 7/8 | > 1s | Quá thời gian test 8 (n = 9) |
Nhận xét
Đăng nhận xét