Bắn cung

Xem PDF
Tác giả:
huyhau6a2
Dạng bài
Điểm: 200 Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Bạn Huy đang tập bắn cung để chuẩn bị cho thi olympic. Hôm đó, mẹ của Huy ghi ra thông tin gồm \(n\) dòng, dòng thứ \(i\) ghi \(2\) số, khoảng cách tới tâm và số điểm nhận được. Số điểm nhận được là số vòng tròn không chứa nó, nếu nằm trong cạnh sẽ được tính là chứa. Gọi \(r\) là chênh lệch bán kính của mỗi vòng tròn. Hãy tìm \(r\) với các thông tin mẹ Huy đã viết.

Input

  • Dòng \(1\) gồm số \(n\). không quá \(10^5\).
  • \(n\) dòng tiếp theo, mỗi dòng gồm 2 số chỉ thông tin ở dòng đó (theo đề bài) không quá \(10^9\).

Output

  • Nếu không tìm được \(r\) hoặc thông tin bị lỗi, xuất ERROR, nếu không hãy xuất ra số \(r\) nhỏ nhất thỏa mãn.

Example

Test 1

Input 
3
9 0
10 0
11 1
Output 
10

Bình luận


  • 0
    duongnguyen0210    9:30 p.m. 2 Tháng 6, 2023

    cho tôi hỏi chênh lệch bán kính mỗi vòng tròn là gì thế :V


    • 1
      tunangoo    6:05 p.m. 26 Tháng 8, 2022 ← đã chỉnh sửa

      Bài này không cần chặt nhị phân mà chỉ cần tham lam 1 for là AC mà?

      1 phản hồi

      • 1
        huyhau6a2    8:58 p.m. 17 Tháng 1, 2022

        Hint cuối:

        • Đầu tiên ta xét thì với n thì với mỗi giá trị k thì số vòng tròn bao hàm nó sẽ là (k-1)//n
        • Tiếp đó với mỗi n thì thông tin sẽ thỏa mãn khi mỗi k có kết quả đúng với thông số 2 nhập vào
        • Ta thấy vậy có thể dùng chặt nhị phân để tính. Code:
        • Khi phân tích tiếp thì với n tăng thì số vòng tròn bao hàm mỗi số k sẽ giảm, điều kiện đó giúp ta có thể thay đổi l, r. Gọi tl là số phần tử sao cho kết quả của công thức lớn hơn thông số 2, tr ngược lại
        • Khi tl và tr đều >0 thì sẽ bị lỗi ERROR, dừng chặt nhị phân ngay lập tức, khi tl>0, tr==0 thì ta sẽ đặt l=mid+1, không nếu tl==0, tr>0 thì r=mid-1
        • Thay đổi l, r thì hơi lằng nhằng nha hmm.
        • Tiếp đó là phần thông tin thỏa mãn: khi tl và tr đều bằng 0 thì tất cả thông tin thỏa mãn, cập nhật giá trị nhỏ nhất thỏa mãn, vậy là bài toán đã được giải quyết. Có vấn đề gì các bạn cứ comment nha

        • 0
          huyhau6a2    8:59 p.m. 5 Tháng 1, 2022

          Bài này ta sẽ chặt nhị phân theo hàm số k:

          • Gọi F(k) là true hoặc false:
            • F(k) true khi thỏa mãn hết điều kiện trên, không thì là false
          • Bạn có thể giới hạn trong khoảng k tới 10^12 cung được, không vấn đề gì hết nha
          1 phản hồi

          • -5
            tktuanleanh    6:42 p.m. 9 Tháng 12, 2021

            Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.