Tim mạch
Đề bài
Mô tả
Ảo thuật gia lừng danh Cardoni có một bộ lá bài được đánh số, ông dùng nó trong một trò ảo thuật như sau.
Một khán giả bí mật chọn một số trong khoảng từ đến . Sau đó Cardoni chia lá bài, ngửa mặt, lần lượt theo từng hàng theo thứ tự từ đến , thành một lưới cột. Khán giả chỉ ra cột nào chứa lá bài đã chọn, rồi ảo thuật gia nhặt bài lên theo từng cột, trong đó cột được chỉ ra là cột được nhặt thứ hai (thứ tự nhặt hai cột còn lại không quan trọng). Bài được nhặt ngửa mặt, bắt đầu từ lá trên cùng của mỗi cột, mỗi lá tiếp theo được đặt ngay bên dưới lá vừa nhặt trước đó. Sau đó bài lại được chia theo từng hàng thành lưới cột, bắt đầu từ lá trên cùng của xấp bài ngửa. Quá trình được lặp lại thêm hai lần nữa; mỗi lần, cột do khán giả chỉ ra là cột thứ hai được ảo thuật gia nhặt. Sau ba lần như vậy, Cardoni tuyên bố: "Ta đã thấu tận trái tim của bạn; lá bài của bạn nằm ở trái tim của màn trình diễn này." Và quả thật, lá bài đã chọn nằm ở "trái tim" của lưới (hàng bốn, cột hai). Hơn nữa, lá bài đã chọn sẽ luôn nằm yên ở vị trí ổn định này dù lặp lại quá trình chỉ cột và chia lại bài thêm bao nhiêu lần nữa.
Trò này luôn thành công, bất kể số được chọn là gì, miễn là cột chứa số bí mật là cột thứ hai được nhặt lên và chia lại.
Cardoni muốn mở rộng trò ảo thuật để dùng số lá bài, số hàng và số cột khác, và thử các thứ tự nhặt cột khác sau khi khán giả chỉ ra một cột. Tuy nhiên đây không phải bài toán tầm thường. Chẳng hạn, khi dùng lá bài với hàng và cột, và luôn nhặt cột được chỉ ra là cột thứ hai để chia lại, thì số cuối cùng nằm ở vị trí ổn định hàng , cột , còn số nằm ở vị trí ổn định hàng , cột . Ngoài ra, cả hai vị trí này đều không phải một trong hai vị trí "trái tim" ở cột của hàng hoặc hàng . Hơn nữa, Cardoni không chắc cần bao nhiêu lần lặp "chỉ cột và chia lại" thì lá bài đã chọn mới tới được vị trí ổn định.
Cho số hàng và số cột của lưới bài, hãy giúp Cardoni bố trí trò ảo thuật sao cho có một vị trí ổn định duy nhất, gần tâm nhất có thể.
Dữ liệu vào
Một dòng duy nhất chứa hai số nguyên và , số hàng và số cột dùng trong trò ảo thuật. Các lá bài được đánh số từ đến và ban đầu được chia theo từng hàng theo thứ tự tăng dần.
Dữ liệu ra
In ra một dòng gồm bốn số nguyên , , và , trong đó:
- cột do khán giả chỉ ra phải được nhặt lên là cột thứ ,
- với giá trị này, mọi lá bài cuối cùng đều tới vị trí ổn định ở hàng , cột ,
- là số lần lặp lớn nhất cần thiết để một lá bài bất kỳ tới được vị trí ổn định.
Giá trị phải được chọn sao cho vị trí ổn định gần nhất có thể với một trong một, hai hoặc bốn vị trí ở tâm của lưới, trong đó khoảng cách giữa hai vị trí và là . Nếu có nhiều giá trị cho cùng khoảng cách nhỏ nhất, hãy chọn nhỏ nhất.
Ràng buộc
- .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 7 3 | 2 4 2 3 | Trò ảo thuật gốc với lá bài: nhặt cột được chỉ ra thứ hai, mọi lá bài tới hàng , cột (chính tâm của lưới) sau nhiều nhất lần lặp. |
| 8 3 | 1 1 1 3 | Với có hai vị trí ổn định (hàng cột và hàng cột ) nên không dùng được. Với vị trí ổn định là hàng cột , với là hàng cột ; cả hai cách các vị trí tâm (hàng hoặc , cột ) một khoảng , nên chọn . |
Bình luận