Đổi chỗ ngồi
Đề bài
Mô tả
Kỳ thi Lập trình Sinh viên Quốc tế (ICPC) là cuộc thi mà các thí sinh tham gia theo đội. Cuộc thi không chỉ thử thách kỹ năng thuật toán và kỹ năng giải quyết vấn đề của thí sinh mà còn đòi hỏi sự phối hợp và đoàn kết giữa các thành viên trong đội.
Hôm nay, bên cạnh sự kiện chính, các thí sinh ICPC còn có cơ hội tham gia một trò chơi nhỏ. Có tổng cộng người tham gia, ban tổ chức chuẩn bị chiếc ghế, xếp thành hai hàng, mỗi hàng ghế. Hai hàng ghế đối diện nhau, các ghế trên mỗi hàng được đánh số từ đến từ trái sang phải, nên ghế thứ của hàng thứ nhất đối diện với ghế thứ của hàng thứ hai. Người chơi được đánh số từ đến .
Ban đầu, mỗi người chọn một ghế để ngồi. người ngồi trên ghế khác nhau, nên có đúng một ghế trống. Trò chơi diễn ra như sau: ở mỗi lượt, mọi người bầu chọn một người đang ngồi ở hàng không chứa ghế trống. Người được chọn sẽ di chuyển sang ghế trống.
Mục tiêu của trò chơi là sau không quá lượt, các điều kiện sau được thỏa mãn:
- Người ban đầu ngồi ở ghế thứ của hàng thứ nhất bây giờ ngồi ở ghế thứ của hàng thứ hai.
- Người ban đầu ngồi ở ghế thứ của hàng thứ hai bây giờ ngồi ở ghế thứ của hàng thứ nhất.
Dù là một trò chơi đơn giản, nó vẫn rất thử thách. Để thắng, mọi người phải hợp tác với nhau. Là một thành viên trong đội, bạn cũng muốn góp sức! Cho cách ngồi ban đầu, hãy tìm một cách để mọi người thắng trò chơi, hoặc cho biết không thể đạt được mục tiêu.
Dữ liệu vào
- Dòng đầu tiên chứa số nguyên () là số ghế trên mỗi hàng.
- Dòng thứ trong hai dòng tiếp theo chứa số nguyên () mô tả cách ngồi ban đầu: nếu thì là số hiệu người ngồi ở ghế thứ của hàng thứ ; ngược lại, ghế thứ của hàng thứ trống.
Dữ liệu đảm bảo các giá trị đôi một khác nhau.
Dữ liệu ra
Nếu không có cách nào thắng trò chơi, in ra một số nguyên .
Ngược lại, dòng đầu tiên in số nguyên () là số lượt cần dùng. Dòng tiếp theo in số nguyên (), trong đó là số hiệu người di chuyển sang ghế trống ở lượt thứ .
Nếu có nhiều cách, in ra cách bất kỳ.
Ràng buộc
- , các giá trị đôi một khác nhau
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 1 1 0 |
1 1 |
Người chuyển từ hàng thứ nhất sang ghế trống đối diện. |
| 3 2 0 1 3 5 4 |
11 3 2 5 3 4 5 3 4 5 1 4 |
Sau lượt, hàng thứ nhất là và hàng thứ hai là . Đây chỉ là một đáp án đúng, còn nhiều đáp án khác. |
| 2 1 2 3 0 |
-1 | Ví dụ bổ sung (không có trong đề gốc): với không thể thắng trò chơi. |
Bình luận