trang chủ / đề bài / icpcwf05_d

Xáo bài hoàn hảo (cNteSahruPfefrlefe)

Đề bài

Mô tả

Preston Digitation là một ảo thuật gia chuyên về các trò ảo thuật với lá bài. Có một việc Preston chưa bao giờ làm thật chuẩn: xáo xen kẽ hoàn hảo (perfect in-shuffle). Một lần xáo xen kẽ hoàn hảo chia bộ bài 52 lá thành hai nửa rồi đan xen hai nửa một cách hoàn hảo, sao cho lá trên cùng của nửa dưới trở thành lá trên cùng của bộ bài sau khi xáo. Nếu đánh số các lá từ 0 (trên cùng) đến 51 (dưới cùng), bộ bài sau một lần xáo xen kẽ hoàn hảo sẽ như sau:

26 0 27 1 28 2 29 3 30 4 31 5 32 6 ... 51 25

Preston nhận thấy mỗi lần xáo anh mắc nhiều nhất một lỗi. Chẳng hạn, hai lá 2 và 28 có thể bị đổi chỗ cho nhau, khi đó bộ bài sau khi xáo trông như sau:

26 0 27 1 2 28 29 3 30 4 31 5 32 6 ... 51 25

Đổi chỗ hai lá bài kề nhau như vậy là loại lỗi duy nhất mà Preston mắc phải. Sau một lần xáo, anh dễ dàng biết mình có mắc lỗi hay không và mắc ở đâu, nhưng sau nhiều lần xáo thì việc này ngày càng khó. Anh muốn bạn viết chương trình xác định các lỗi của anh (nếu có).

Dữ liệu vào

Dữ liệu gồm nhiều bộ test. Dòng đầu tiên chứa một số nguyên là số bộ test. Mỗi bộ test gồm đúng một dòng chứa các lá bài của một bộ bài (từ trên xuống dưới) đã được xáo từ 1 đến 10 lần. Mọi bộ bài đều có 52 lá.

Dữ liệu ra

Với mỗi bộ test, in ra số thứ tự của bộ test (bắt đầu từ 1) ở dạng Case i, tiếp theo là dòng Number of shuffles = k với k là số lần xáo đã dùng cho bộ test đó. Nếu không có lỗi nào trong các lần xáo, in ra dòng

No error in any shuffle

Ngược lại, in ra một số dòng dạng

Error in shuffle n at location m

trong đó n là lần xáo có lỗi và m là vị trí của lỗi. Các lần xáo được đánh số từ 1, và m là vị trí đầu tiên (vị trí nhỏ hơn) trong hai lá bị đổi chỗ ở lần xáo đó (lá trên cùng ở vị trí 0). Trong ví dụ ở trên, các lá ở vị trí 4 và 5 (lá 2 và lá 28) bị sai, nên m=4. Liệt kê mọi lỗi theo thứ tự n tăng dần. Lần xáo nào không có lỗi thì không in dòng nào cho lần đó. Nếu có nhiều cách giải thích, hãy chọn cách có ít lỗi nhất (mọi bộ test đều có duy nhất một cách giải thích với số lỗi ít nhất, xét trên mọi số lần xáo từ 1 đến 10).

Ràng buộc

  • Số bộ test từ 1 đến 100.
  • Mỗi bộ bài là một hoán vị của 0,1,…,51, nhận được từ bộ bài 0,1,…,51 sau k lần xáo xen kẽ (1≤k≤10), mỗi lần có nhiều nhất một lỗi đổi chỗ hai lá kề nhau ngay sau khi đan xen.

Ví dụ

Input Output Giải thích
3
26 0 27 1 2 28 29 3 30 4 31 5 32 6 33 7 34 8 35 9 36 10 37 11 38 12 39 13 40 14 41 15 42 16 43 17 44 18 45 19 46 20 47 21 48 22 49 23 50 24 51 25
26 0 27 1 28 2 29 3 30 4 31 5 32 6 33 7 34 8 35 9 36 10 37 11 38 12 39 13 40 14 41 15 42 16 43 17 44 18 45 19 46 20 47 21 48 22 49 23 50 24 51 25
49 26 43 40 37 34 31 28 25 22 19 16 13 10 7 4 1 51 48 45 42 39 36 33 24 27 30 21 18 15 12 9 6 3 0 50 47 44 41 38 35 32 29 46 23 20 17 2 11 8 5 14
Case 1
Number of shuffles = 1
Error in shuffle 1 at location 4
Case 2
Number of shuffles = 1
No error in any shuffle
Case 3
Number of shuffles = 9
Error in shuffle 3 at location 3
Error in shuffle 7 at location 11
Error in shuffle 8 at location 38
Bộ 1 là bộ bài trong đề: một lần xáo, hai lá 2 và 28 ở vị trí 4, 5 bị đổi chỗ. Bộ 2 là một lần xáo hoàn hảo. Bộ 3 là 9 lần xáo với lỗi ở các lần 3, 7, 8.
3
24 49 21 46 18 43 15 40 12 37 9 34 6 31 3 28 0 25 50 22 47 19 44 16 41 13 38 10 35 7 32 4 29 1 26 51 23 48 20 45 17 42 14 39 11 36 8 33 5 30 2 27
0 26 27 1 28 2 29 3 30 4 31 5 32 6 33 7 34 8 35 9 36 10 37 11 38 12 39 13 40 14 41 15 42 16 43 17 44 18 45 19 46 20 47 21 48 22 49 23 50 24 51 25
39 26 13 0 40 27 14 1 41 28 15 2 42 29 16 3 43 30 17 4 44 31 18 5 45 32 19 6 46 33 20 7 47 34 21 8 48 35 22 9 49 36 23 10 50 37 24 11 25 38 12 51
Case 1
Number of shuffles = 10
No error in any shuffle
Case 2
Number of shuffles = 1
Error in shuffle 1 at location 0
Case 3
Number of shuffles = 2
Error in shuffle 1 at location 50
Error in shuffle 2 at location 50
Ví dụ tự thêm. Bộ 1: 10 lần xáo hoàn hảo. Bộ 2: một lần xáo, hai lá trên cùng bị đổi chỗ. Bộ 3: hai lần xáo, lần nào hai lá dưới cùng cũng bị đổi chỗ (sau lần 1 bộ bài kết thúc bằng … 51 25, đổi thành … 25 51).

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.402 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.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0