Phân tích: Bullseye

Đầu tiên, chúng ta cần biết diện tích của vòng đen đầu tiên. Nó có thể được tính bằng cách lấy diện tích của hình tròn màu đen bán kính \(r+1\) cm trừ đi diện tích hình tròn màu trắng bán kính \(r\) cm. Nghĩa là diện tích là \((r+1)^2\pi - r^2\pi\) cm\(^2\). Khai triển ra ta được \((2r+1)\pi\) cm\(^2\). Vì \(1\) mL sơn phủ được diện tích \(\pi\) cm\(^2\), chúng ta cần chính xác \(2r+1\) mL sơn để vẽ vòng đen đầu tiên. Đối với vòng đen thứ hai, chúng ta làm tương tự: lấy diện tích hình tròn đen bán kính \(r+3\) cm trừ đi diện tích hình tròn trắng bán kính \(r+2\) cm, do đó chúng ta cần \(2r+5\) mL để vẽ. Tổng quát, chúng ta cần chính xác \((r+2k-1)^2 - (r+2k-2)^2 = 2r+4k-3\) mL sơn để vẽ vòng đen thứ \(k\).

Với tập dữ liệu nhỏ, chúng ta biết rằng câu trả lời chắc chắn nhỏ hơn \(t = 1000\), vì vậy chúng ta có thể thử thêm từng vòng đen một cho đến khi tổng lượng sơn đã dùng (bao gồm cả vòng tiếp theo) vượt quá \(t\), sau đó dừng lại và xuất ra số lượng vòng đen đã vẽ được.

Tuy nhiên, cách này không hoạt động tốt với tập dữ liệu lớn vì câu trả lời có thể lớn hơn rất nhiều! Điều này có thể thấy qua ví dụ thứ tư (chúng tôi đã cố ý đưa ra ví dụ này để giúp các thí sinh, nhưng hóa ra nhiều người vẫn thất bại ở tập dữ liệu lớn do tràn số nguyên). Làm thế nào chúng ta có thể cải thiện thuật toán?

Chìa khóa nằm ở chỗ: nếu bạn có thể vẽ tối đa \(k\) vòng đen bằng \(t\) mL sơn, thì chắc chắn bạn cũng có thể vẽ \(1\) vòng, \(2\) vòng, ... cho đến \(k-1\) vòng. Vì vậy, thay vì tìm kiếm câu trả lời một cách tuyến tính, chúng ta có thể thực hiện tìm kiếm nhị phân trên câu hỏi "Có thể sử dụng \(t\) mL sơn để vẽ \(k\) vòng đen hay không?" để tìm câu trả lời hiệu quả hơn. Câu hỏi còn lại là cần bao nhiêu sơn để vẽ \(k\) vòng đen.

Nhìn lại lượng sơn cần thiết để vẽ từng vòng đen riêng lẻ, dễ dàng nhận thấy chúng tạo thành một cấp số cộng: \(2r+1, 2r+5, 2r+9, \dots, 2r+4k-3\). Khi đó tổng lượng sơn đơn giản là tổng của cấp số cộng này, bằng \((2r+1 + 2r+4k-3) \times k \div 2 = (2r+2k-1)k\) mL. Điều này là đủ để giải quyết hoàn toàn bài toán.

Dưới đây là lời giải hoàn chỉnh bằng Python để tham khảo:

num_cases = int(raw_input())
for casenum in range(1, num_cases+1):
  r, t = [int(z) for z in raw_input().split()]
  res, lo, hi = 0, 1, t
  while lo <= hi:
    mid = (lo + hi) / 2
    if mid * (2 * r + 2 * mid - 1) > t:
      hi = mid - 1
    else:
      lo, res = mid + 1, mid
  print "Case #%d: %d" % (casenum, res)

Bạn có thể nghĩ rằng mình cần các thư viện số nguyên lớn để giải quyết tập dữ liệu lớn, nhưng thực tế thì không nhất thiết. Ví dụ, số thực dấu phẩy động độ chính xác kép (double precision) là đủ để kiểm tra điều kiện một cách chính xác. Một cách thanh lịch hơn là tìm khoảng đầu tiên có độ dài tăng theo hàm mũ sao cho tồn tại một giá trị trong khoảng đó không thỏa mãn điều kiện. Việc tìm khoảng này mất thời gian logarit. Sau đó, chúng ta thực hiện tìm kiếm nhị phân trên đó và tính toán kết quả. Dưới đây là một đoạn mã C++ mô tả thuật toán mà không sử dụng bất kỳ thư viện số nguyên lớn nào.

// Check if we can draw k black rings.
bool Check(long long r, long long t, long long k) {
  return 2 * k * k + (2 * r - 1) * k <= t;
}

// Find the maximum number of black rings that can be drawn.
long long Solve(long long r, long long t) {
  long long left = 0, right = 1;
  // Find the range that the answer lies in.
  while(Check(r,t,right)) {
    left = right;
    right *= 2;
  }

  // Binary search on the range [left, right) for the answer.
  while(right - left > 1) {
    long long k = (left + right) / 2;
    if (Check(r, t , k))
      left = k;
    else
      right = k;
  }
  return left;
}

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