Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

VOEXC - Trao đổi

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/voexc


Austin và Agrron vừa đào được một túi gồm N thỏi kim loại quý. Thỏi thứ k chứa A[k] gram vàng và B[k] gram bạc. Họ muốn chia phần trước khi chia tay nhau, nhưng có một vài rắc rối xảy ra. Đó là Austin chỉ quan tâm đến vàng, trong khi Agrron chỉ quan tâm đến bạc (với 1 người thích vàng, bao nhiêu bạc cũng là vô nghĩa và ngược lại). Sau khi chia xong, ngay lập tức họ sẽ loại bỏ phần kim loại họ không thích (phần này người kia không thể lấy được).

 

Để đảm bảo công bằng, họ có thể tách một số thỏi kim loại ra thành 2 phần. Với mỗi thỏi, họ có thể tách nó ra theo bất kì tỉ lệ nào, và mỗi người có thể chọn phần mình muốn (lưu ý, việc tách thỏi kim loại không làm thay đổi tỉ lệ phân bổ vàng-bạc trong 2 thỏi nhỏ hơn. Chẳng hạn, với 1 thỏi chứa 6 gram vàng và 4 gram bạc, có thể tách nó thành 2 thỏi, mỗi thỏi chứa 3 gram vàng và 2 gram bạc, trong khi không thể tách nó thành 2 thỏi, một thỏi chứa 6 gram vàng và thỏi còn lại chứa 4 gram bạc).

 

Xác định số gram vàng (bạc) nhiều nhất mà người nhận được ít hơn có thể có sau quá trình trao đổi này, nếu họ chọn phương án tối ưu.

Input

  • Dòng đầu tiên chứa một số nguyên N là số thỏi kim loại.
  • N dòng tiếp theo, mỗi dòng chứa 2 số nguyên A[i], B[i] là số gram vàng và bạc có trong thỏi thứ i.

 

Output

  • Một dòng duy nhất là đáp số bài toán. Kết quả được chấp nhận nếu chênh lệch không quá 10^-6 so với đáp số tối ưu.

 

Giới hạn

  • 0 < N ≤ 100000.
  • 0 ≤ A[i],B[i] ≤ 1000.
  • Trong 20% số test, chỉ có đúng 1 viên đá có lẫn cả vàng và bạc (tức là trong N – 1 viên, A[i] = 0 hoặc B[i] = 0).

Example

Input:

2

10 3

6 10

Output:

10.000

Giải thích: Austin lấy thỏi thứ nhất và Agrron lấy thỏi thứ hai, mỗi người được 10 gram có ích. Các đáp số 9.999999 hoặc 10.000001 cũng được chấp nhận.


Input:

1

30 15

Output:

10.0

Giải thích: Tách thỏi kim loại theo tỉ lệ 1/3 và 2/3. Austin lấy phần nhỏ hơn (có 1/3 * 30 = 10 gram vàng), thỏi kia thuộc về Agrron (có 2/3 * 15 = 10 gram bạc).


Được gửi lên bởi:VOJ Team
Ngày:2011-12-23
Thời gian chạy:0.600s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:C C++ 4.3.2 CPP PAS-GPC PAS-FPC
Nguồn bài:Nguyễn Vương Linh

hide comments
2018-01-07 03:19:56
để cho chắc các mem thử in ra 7 chữ số tận cùng nhé (6 đc 90 7 đc 100)
2012-01-01 14:57:19 vn_army
ps ơi xem cho em test cuối tle hay wa mà 90 mãi :(
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.