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

Trò chơi hoán vị

Đề bài

Mô tả

Có n đứa trẻ đứng thành vòng tròn và chơi một trò chơi. Số của các đứa trẻ theo chiều kim đồng hồ tạo thành một hoán vị a1,a2,…,an của các số từ 1 đến n (mỗi số xuất hiện đúng một lần).

Trò chơi gồm m lượt. Ở mỗi lượt, người dẫn hiện tại đang đứng ở vị trí i sẽ đếm ai người theo chiều kim đồng hồ, bắt đầu từ người kế tiếp. Người cuối cùng được đếm tới sẽ trở thành người dẫn mới.

Nói cách khác, nếu người dẫn đang ở vị trí i thì người dẫn mới sẽ ở vị trí ((i−1+ai)modn)+1.

Cho các số l1,l2,…,lm là vị trí của người dẫn ở đầu mỗi lượt. Đứa trẻ ở vị trí l1 là người dẫn đầu tiên.

Hãy khôi phục một hoán vị a1,a2,…,an sao cho dãy người dẫn ở đầu mỗi lượt đúng bằng l1,l2,…,lm. Nếu có nhiều đáp án, in ra bất kỳ đáp án nào. Nếu không tồn tại hoán vị thỏa mãn, in ra −1.

Dữ liệu vào

  • Dòng đầu chứa hai số nguyên n,m.
  • Dòng thứ hai chứa m số nguyên l1,l2,…,lm.

Dữ liệu ra

In ra một hoán vị gồm n số a1,a2,…,an thỏa mãn điều kiện. Nếu có nhiều đáp án, in ra bất kỳ. Nếu không có hoán vị nào thỏa mãn, in ra −1.

Ràng buộc

  • 1≤n,m≤100
  • 1≤li≤n

Ví dụ

Input Output Giải thích
4 5
2 3 1 4 4		 3 1 2 4 Từ vị trí 2, đếm a2=1 tới vị trí 3. Từ 3, đếm a3=2 vòng qua tới 1. Từ 1, đếm a1=3 tới 4. Từ 4, đếm a4=4 quay lại 4. Dãy người dẫn là 2 3 1 4 4.
3 3
3 1 2		 -1 Không tồn tại hoán vị nào tạo ra dãy người dẫn 3 1 2.
2 2
2 2		 1 2 Từ vị trí 2, đếm a2=2 quay lại chính vị trí 2.

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.46 awk 1.3.4 gcc 16.1.0 csc 6.12.0.200 g++ 16.1.0 g++-themis 16.1.0 g++17 16.1.0 g++20 16.1.0 g++23 16.1.0 clang++ 22.1.6 dmd 2.112.0 dart 3.12.1 gforth 0.7.3 gfortran 12.2.0 go 1.26.3 groovyc 5.0.6 javac 25.0.3 node 26.2.0 kotlinc 2.3.21 sbcl 2.2.9 lua 5.4.8 nim 2.2.10 fpc 3.2.2 fpc-themis 3.2.2 perl 5.36.0 php 8.5.6 pike 8.0 pypy3 7.3.23 python3 3.14.5 racket 8.7 ruby 4.0.5 rustc 1.96.0 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 tclsh 8.6 bun 1.3.14 deno 2.8.1 v 0.5.1 zig 0.16.0