Bắn cung

Tác giả:

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

Output

Bình luận

0
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

4 bình luận nữa