Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
北京大学《ACM-ICPC竞赛训练》暑期课面向全球招生。容量有限,报名从速!
Language:
Approximations
Time Limit: 2000MSMemory Limit: 131072K
Total Submissions: 366Accepted: 23

Description

For any decimal fraction, we can obtain a set of approximations of different accuracy by mean of rounding. Take 0.2503 for example, we have the following approximations:

  • 0.2503
  • 0.250
  • 0.25
  • 0.3
  • 0.

If two fractions A and B can both be rounded to C, we call C a common approximation of A and B. Two fractions may have more than one common approximations, each having a distinct accuracy. For example, 0.2503 and 0.2504 have common approximations 0.250 and 0.25. The accuracy of the former is 10−3, while that of the latter is 10−2. Among all common approximations of two fractions, there is one that has the highest accuracy, and we call it the most accurate common approximation (MACA) of the two fractions. By this definition, the MACA of 0.2503 and 0.2504 is 0.250.

Given N fractions Ai (1 ≤ iN) in the range [0, 0.5), find a fraction x that maximizes the sum of −log10 (the accuracy of the MACA of Ai and x). Report that maximized sum.

Input

The first line contains one integer N. N ≤ 100000.
Each of the next N lines contains a decimal fraction Ai. The total number of digits of the N decimal fractions doesn't exceed 400000. There is always a radix point, so zero is "0." instead of "0".

Output

One integer, the maximized sum.

Sample Input

4
0.250
0.2506
0.25115
0.2597

Sample Output

11

Hint

x = 0.25115.

Source

[Submit]   [Go Back]   [Status]   [Discuss]

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator