Phân tích

Điều đầu tiên cần nhận thấy trong bài toán này là cả \(P_D\) và \(P_G\) đều có phạm vi từ 0 đến 100, vì vậy hãy bắt đầu bằng cách xử lý một số trường hợp dễ dàng. Nếu người chơi ẩn danh của chúng ta đã thắng 100% tổng số ván của mình (\(P_G = 100\)) nhưng lại không thắng 100% số ván hôm nay (\(P_D < 100\)), thì rõ ràng đã có điều gì đó không ổn với máy tính thống kê. Tương tự, nếu \(P_G = 0\) nhưng \(P_D > 0\), thống kê cũng không hợp lệ.

Các trường hợp \(P_D = P_G = 0\) hoặc \(P_D = P_G = 100\) cũng rất dễ, và câu trả lời cho cả hai đều là "Possible" — chúng có nghĩa là tất cả các ván đấu từ trước đến nay đều kết thúc với cùng một kết quả (tương ứng là thua hoặc thắng).

Mấu chốt ở đây là một khi chúng ta đã loại trừ trường hợp \(P_G\) bằng 0 hoặc 100, chúng ta không cần lo lắng về nó nữa! Thật vậy, giả sử chúng ta có một giải pháp đưa ra tỷ lệ thắng hàng ngày chính xác, và nó bao gồm \(W\) ván thắng và \(L\) ván thua hôm nay. Để có được tỷ lệ thắng toàn cầu là \(P_G\), chẳng hạn, chúng ta có thể giả định rằng chúng ta đã thắng tổng cộng \((W + L) \times P_G\) ván và thua tổng cộng \((W + L) \times (100 - P_G)\) ván. Vì \(1 \le P_G \le 99\), các con số này lần lượt lớn hơn \(W\) và \(L\), vì vậy chúng có thể đạt được (bằng cách chơi thêm một số lượng ván cực kỳ lớn trong quá khứ với tỷ lệ thắng phù hợp).

Bộ dữ liệu nhỏ có thể được giải quyết bằng cách duyệt vét cạn tất cả các giá trị có thể có của \(D\) từ 1 đến \(N\) và tất cả các số ván thắng có thể có từ 0 đến \(D\), rồi kiểm tra xem có giá trị nào dẫn đến tỷ lệ thắng chính xác là \(P_D\) hay không.

Giải quyết bộ dữ liệu lớn có thể đòi hỏi một số kiến thức toán học. Một cách để giải bài toán là trực tiếp tìm số ván tối thiểu chúng ta cần chơi để đạt được tỷ lệ thắng \(P_D\) và chỉ cần xác minh rằng số này \(\le N\). Nếu chúng ta gọi \(W\) là số ván chúng ta đã thắng hôm nay, thì chúng ta muốn giải phương trình \(W / D = P_D / 100\) để tìm giá trị nhỏ nhất của \(D\) sao cho \(W\) là số nguyên.

Từ đây, dễ dàng thấy \(D = 100 \times W / P_D\). Do đó, nếu chúng muốn tối thiểu hóa \(D\), chúng ta cần tìm giá trị \(W\) nhỏ nhất sao cho vế phải là số nguyên. Để làm điều này, chúng ta chia 100 và \(P_D\) cho ước chung lớn nhất của chúng (gọi giá trị này là \(g\)) để chúng trở nên nguyên tố cùng nhau, và \(W\) sẽ tối thiểu khi nó bằng \(P_D / g\). Thay vào và triệt tiêu các hạng tử cho chúng ta biết rằng \(D = 100 / g\) là số ván ít nhất mà chúng ta phải chơi.

Một cách đơn giản hơn để giải bài toán này là duyệt vét cạn. Chúng ta có thể thử tất cả các giá trị có thể có của \(D\) từ 1 đến \(N\) và kiểm tra xem có giá trị nào có thể dẫn đến tỷ lệ thắng chính xác \(P_D\) hay không bằng cách kiểm tra \(D \times P_D \equiv 0 \pmod{100}\), dừng vòng lặp ngay khi tìm thấy một giá trị \(D\) ứng cử viên hoặc vượt quá \(N\) ván. Mặc dù lúc đầu giải pháp này có vẻ là \(O(N)\) và sẽ bị quá thời gian đối với bộ dữ liệu lớn, nhưng trên thực tế vòng lặp này sẽ chạy tối đa 100 lần, bất kể giá trị của \(N\) là bao nhiêu, vì vậy giải pháp này sẽ đủ nhanh. Những lập trình viên nhận ra giải pháp đơn giản này sớm đã được đền đáp bằng thời gian nộp bài rất nhanh.

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