Phân tích

Chuẩn bị

Hy vọng bạn đã ghi nhớ lời Fair Warning mà chúng tôi nhắc lại một cách rất “fair” trong bài Fair and Square năm nay: chúng tôi coi số nguyên lớn là kiến thức có thể dùng trong thi. Nếu ngôn ngữ không hỗ trợ sẵn, bạn nên chuẩn bị một thư viện xử lý chúng.

Ban đầu, bài toán có vẻ liên quan đến phân số vì bóng có thể chạm tường ở các vị trí lẻ. Tuy nhiên, ta có thể đưa về số nguyên bằng cách tỉ lệ hóa. Ta tỉ lệ hóa thời gian sao cho có \(V_X\) đơn vị trong một giây, và tỉ lệ hóa khoảng cách dọc sao cho có \(V_X\) đơn vị mới tương ứng với 1 đơn vị cũ. Khi đó, tốc độ dọc không đổi, tốc độ ngang giảm đi \(V_X\) lần, khoảng cách ngang giữ nguyên và khoảng cách dọc tăng lên \(V_X\) lần. Trong cài đặt, điều này có nghĩa là ta thu nhỏ \(V_X\) về 1 và tăng \(A\) lên \(A \times V_X\) — khi đó bóng sẽ di chuyển một số nguyên đơn vị theo chiều dọc và 1 đơn vị theo chiều ngang trong mỗi đơn vị thời gian (và do đó sẽ chạm các tường dọc tại các thời điểm nguyên).

Giả định trên coi \(V_X\) dương. Nếu \(V_X = 0\), bóng không bao giờ chạm tường dọc, kết quả là DRAW. Nếu \(V_X < 0\), ta lật ngược bảng qua trục \(Y\) và tráo đổi hai đội. Tương tự, ta có thể giả định \(V_Y>0\): nếu \(V_Y=0\), đặt mọi cây vợt tại đúng điểm va chạm duy nhất sẽ bảo đảm hòa; nếu \(V_Y<0\), lật bàn theo chiều dọc.

Bóng sẽ chạm một tường dọc nhất định sau mỗi \(2B\) đơn vị thời gian. Vị trí va chạm có thể tính bằng cách: nếu không có tường ngang, bóng sẽ chạm tại \(Y + (B - X)V_Y\), và sau đó là các khoảng cách \(2BV_Y\). Trong thực tế, cứ sau \(2A\) đơn vị chiều dọc, bóng sẽ quay lại vị trí cũ (lấy modulo \(2A\)). Nếu giá trị này lớn hơn \(A\), bóng đang đi ngược lại và vị trí thực tế là \(2A\) trừ đi giá trị đó.

Nhiều lần nảy

Giờ đã biết cách tính vị trí va chạm, liệu ta chỉ cần mô phỏng xem ai thua trước? Không: bóng có thể nảy quá nhiều lần. Ngay cả trong tập nhỏ, số lần nảy có thể tới \(10^{11}\), vượt xa khả năng mô phỏng.

Vị trí các cây vợt được xác định trước: vợt của một người chơi phải ở đúng điểm va chạm khi đến lượt họ. Câu hỏi là liệu người chơi có đủ thời gian để di chuyển đến điểm va chạm tiếp theo hay không. Với \(N\) người chơi và tốc độ vợt \(V\), người chơi có thể di chuyển quãng đường tối đa \(2BVN\) trước lượt tiếp theo. Trong cùng thời gian đó, bóng di chuyển \(2BV_YN\) đơn vị, nhưng vị trí bóng được tính "modulo \(2A\) có phản xạ" như đã nói ở trên.

Nếu khoảng cách bóng di chuyển, lấy modulo \(A\), không lớn hơn khoảng cách vợt đi được, vợt luôn tới kịp. Trường hợp thú vị là khi không thỏa điều đó; hiệu ứng phản xạ vẫn có thể giúp. Chẳng hạn, nếu mỗi lần nảy bóng dịch \(A+1\) và lần va chạm đầu ở \(A/2\), các lần kế tiếp lần lượt ở \(A/2-1\), \(A/2+2\), v.v., nên những lần đầu vẫn khá gần nhau. Ta có thể tính chính xác tập vị trí va chạm cho phép vợt đuổi kịp; tập ấy là hai khoảng theo modulo \(2A\).

Vì vậy, câu hỏi trở thành: bóng nảy được bao lâu mà không chạm tập cấm gồm hai khoảng? Điều này dễ quy về tránh một khoảng cho trước. Ta thu được bài toán số học thuần túy: với cấp số cộng \(I+KS\) theo modulo \(2A\), tìm phần tử đầu tiên rơi vào một khoảng đã cho.

Thuật toán Euclid

Có nhiều cách giải; ở đây dùng một cách tương tự thuật toán Euclid. Trước hết, dịch mọi thứ theo modulo \(2A\) để \(I=0\) và xét dãy \(KS\). Ta cũng dịch/lật bài toán để \(S\le A\); nếu chưa thỏa thì lại lật theo chiều dọc. Khi đó bóng nảy ít nhất hai lần trước khi cuộn qua biên \(2A\).

Ta tính xem khi nào bóng vượt qua điểm bắt đầu của khoảng cấm (bằng phép chia nguyên). Nếu lúc đó bóng rơi vào khoảng cấm, ta dừng lại. Nếu không, bóng sẽ đi hết vòng \(2A\), quay lại vị trí \(P < S\). Lúc này khoảng cấm sẽ ngắn hơn \(S\).

Câu hỏi then chốt là giá trị \(P\). Nếu khoảng cấm có dạng \([kS+a,kS+b]\), ta dễ tính rằng tập các \(P\) khiến vòng kế tiếp rơi vào khoảng là \([a,b]\). Nếu \(P\) thuộc khoảng ấy, đáp án lại được tính nhanh. Nếu không, ta đi thêm một vòng đầy đủ và sau khi cuộn sẽ va chạm tại \(2P?mod S\). Đây chính là bài toán ban đầu: làm việc theo modulo \(S\), tăng thêm \(P\) sau mỗi vòng, và hỏi khi nào đi vào \([a,b]\).

Vì vậy, dùng đệ quy để biết cần bao nhiêu vòng đầy đủ mới ở vị trí có thể rơi vào khoảng cấm ban đầu. Ta cộng số vòng đầy đủ ấy, rồi xử lý phần đầu của vòng cuối để thực sự chạm khoảng.

Độ phức tạp

Các số có tối đa \(D \approx 200\) chữ số. Các phép toán mất \(O(D^2 \log D)\). Mỗi bước đệ quy tương tự thuật toán Euclid, modulo giảm ít nhất một nửa, nên có tối đa \(O(D)\) bước. Tổng độ phức tạp là \(O(D^3 \log D)\), đủ nhanh để vượt qua giới hạn thời gian.

Dựa trên phân tích chính thức của Google Code Jam.