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 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ừ (trên cùng) đến (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á và 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ừ đến lần. Mọi bộ bài đều có lá.
Dữ liệu ra
Với mỗi bộ test, in ra số thứ tự của bộ test (bắt đầu từ ) ở dạng Case i, tiếp theo là dòng Number of shuffles = k với 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 đó là lần xáo có lỗi và là vị trí của lỗi. Các lần xáo được đánh số từ , và 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í ). Trong ví dụ ở trên, các lá ở vị trí và (lá và lá ) bị sai, nên . Liệt kê mọi lỗi theo thứ tự 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ừ đến ).
Ràng buộc
- Số bộ test từ đến .
- Mỗi bộ bài là một hoán vị của , nhận được từ bộ bài sau lần xáo xen kẽ (), 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á và ở vị trí , bị đổi chỗ. Bộ 2 là một lần xáo hoàn hảo. Bộ 3 là lần xáo với lỗi ở các lần , , . |
| 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: 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 bộ bài kết thúc bằng , đổi thành ). |
https://oj.chuyentin.pro/problem/icpcwf05_d
Bình luận