trang chủ / đề bài / icpcwf20_a

Tim mạch

Đề bài

Mô tả

Ảo thuật gia lừng danh Cardoni có một bộ 21 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ừ 1 đến 21. Sau đó Cardoni chia 21 lá bài, ngửa mặt, lần lượt theo từng hàng theo thứ tự từ 1 đến 21, thành một lưới 3 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 3 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 24 lá bài với 8 hàng và 3 cột, và luôn nhặt cột được chỉ ra là cột thứ hai để chia lại, thì số 5 cuối cùng nằm ở vị trí ổn định hàng 4, cột 3, còn số 20 nằm ở vị trí ổn định hàng 5, cột 1. 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 2 của hàng 4 hoặc hàng 5. 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 r và c, số hàng và số cột dùng trong trò ảo thuật. Các lá bài được đánh số từ 1 đến r·c 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 p, i, j và s, trong đó:

  • cột do khán giả chỉ ra phải được nhặt lên là cột thứ p,
  • với giá trị p này, mọi lá bài cuối cùng đều tới vị trí ổn định ở hàng i, cột j,
  • s 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ị p phải được chọn sao cho vị trí ổn định (i,j) 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í (i,j) và (i0,j0) là |i−i0|+|j−j0|. Nếu có nhiều giá trị p cho cùng khoảng cách nhỏ nhất, hãy chọn p nhỏ nhất.

Ràng buộc

  • 2≤r,c≤106.

Ví dụ

Input Output Giải thích
7 3 2 4 2 3 Trò ảo thuật gốc với 21 lá bài: nhặt cột được chỉ ra thứ hai, mọi lá bài tới hàng 4, cột 2 (chính tâm của lưới) sau nhiều nhất 3 lần lặp.
8 3 1 1 1 3 Với p=2 có hai vị trí ổn định (hàng 4 cột 3 và hàng 5 cột 1) nên không dùng được. Với p=1 vị trí ổn định là hàng 1 cột 1, với p=3 là hàng 8 cột 3; cả hai cách các vị trí tâm (hàng 4 hoặc 5, cột 2) một khoảng 4, nên chọn p=1.

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