PCIRCLE spoj – Vòng số nguyên tố

Nguồn đề bài: http://vn.spoj.com/problems/PCIRCLE/

1. Đề bài PCIRCLE spoj

Một vòng tròn chứa 2*n vòng tròn nhỏ (Xem hình vẽ). Các vòng tròn nhỏ được đánh số từ 1 đến 2*n theo chiều kim đồng hồ. Cần điền các số tự nhiên từ 1 đến 2*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ỏ. 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.

Ví dụ

Input:
4

Output:
4
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 2

2. Hướng dẫn PCIRCLE spoj

– Viết sẳn thủ tục sàng số nguyên tố

– Áp dụng thuật toán quay lui để chọn các số, kiểm tra điều kiện dựa trên mảng sàng SNT.

– Vì N<10 nên có thể tính trước kết quả K và bỏ vào mảng hằng. chỉ việc xuất ra. Giúp tiết kiệm được bộ nhớ và thời gian khi quay lui.

3. code tham khảo PCIRCLE spoj

 

Trả lời

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *