trang chủ / bài tập / foxdinner

Bữa tối của cáo

Đề bài

Mô tả

n con cáo, con cáo thứ i có tuổi là ai. Cần xếp các con cáo ngồi vào một số bàn tròn sao cho:

  1. Mỗi con cáo ngồi vào đúng một bàn.
  2. Mỗi bàn có ít nhất 3 con cáo.
  3. Tổng tuổi của hai con cáo ngồi cạnh nhau ở mọi bàn đều là số nguyên tố.

Nếu k con cáo f1,f2,,fk ngồi quanh một bàn theo chiều kim đồng hồ thì fifi+1 (với 1ik1) là cạnh nhau, và f1,fk cũng là cạnh nhau.

Hãy chỉ ra một cách xếp hợp lệ, hoặc kết luận không tồn tại.

Dữ liệu vào

  • Dòng đầu chứa số nguyên n — số lượng cáo.
  • Dòng thứ hai chứa n số nguyên a1,a2,,an — tuổi của các con cáo.

Dữ liệu ra

  • Nếu không tồn tại cách xếp hợp lệ, in ra một dòng duy nhất Impossible.
  • Ngược lại, dòng đầu in số nguyên m — số bàn được sử dụng. Tiếp theo, in m dòng, mỗi dòng bắt đầu bằng số k — số cáo ở bàn đó, theo sau là k chỉ số (từ 1 đến n) của các con cáo ngồi quanh bàn theo chiều kim đồng hồ.

Nếu có nhiều đáp án hợp lệ, in ra một đáp án bất kỳ.

Ràng buộc

  • 3n200
  • 2ai104

Ví dụ

Input Output Giải thích
4
3 4 8 9
1
4 1 2 4 3
Tuổi quanh bàn lần lượt là 3,4,9,8; các tổng kề nhau 7,13,17,11 đều là số nguyên tố.
5
2 2 2 2 2
Impossible Không thể vì 2+2=4 không phải số nguyên tố.
12
2 3 4 5 6 7 8 9 10 11 12 13
1
12 1 2 3 6 5 12 9 8 7 10 11 4
Có thể xếp tất cả vào một bàn duy nhất gồm 12 cáo.

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.400 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.2 gforth 0.7.3 gfortran 12.2.0 go 1.27.0 groovyc 5.1.1 javac 25.0.4 node 26.8.1 julia 1.12.7 kotlinc 2.4.10 lean 4.33.1 sbcl 2.2.9 lua 5.4.9 nim 2.2.10 fpc 3.2.2 fpc-themis 3.2.2 perl 5.36.0 php 8.5.10 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.14.7 racket 8.7 ruby 4.0.6 rustc 1.98.0 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.3.3 tclsh 8.6 bun 1.4.0 deno 2.9.6 v 0.5.2 zig 0.16.0