oj mrJudge
Toggle navigation
  • Login
    • Forget Password
      Login
User Image

Hello, Stranger

Guest
  • Analysis Mode
  • Problems
    • All Problems
    • Latest Problems
  • Join Us Now
  • Registration
  • Contact Us
  • Infomation
  • About
    • Terms of Use
    • Technical Specifications
    • Credits

highways Batch , stdin/stdout

Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

highway.html

Problem Statement

Time limit: 1s, Memory limit: 128MB

In Parrebia, there is a circular wasteland measuring 2 Really Long Miles (RLM) in diameter, which, 1000 years after the Really Devastating Event, has been colonised by 220 tribes. The tribes own cities evenly spaced along the perimeter of the wasteland, with the cities numbered clockwise from 0 to 220 - 1 starting from the Northernmost city. N (N ≥ 4) of these cities are under the control of the massive conglomerate Parrebian Toller (PTOL), which has built straight highways between every pair of cities it controls and has lined every highway evenly and densely with toll booths.

Toller has decided to embark on its millenium project, Toller ME, where every toll booth along every highway is upgraded to provide WiFi service. For every pair of booths on any two distinct, intersecting highways, however, there is a possibility that their WiFi signals may interfere. Note that two highways do not intersect if they share the same endpoint. To correct for this, Toller must conduct expensive tests on every such pair of booths. It is not difficult to see that the cost to conduct experiments for every pair of possibly interfering booths along any two intersecting highways is proportional to the product of their lengths.

To aid Toller in its calculations, find the average product of lengths of a pair of intersecting highways in units of RLM2.

Subtasks

  • Subtask 1 (5%): N ≤ 50
  • Subtask 2 (10%): N ≤ 100
  • Subtask 3 (30%): N ≤ 1000
  • Subtask 4 (55%): N ≤ 200000
  • Subtask 5 (0%): Sample Input

Input

The input consists of N + 1 lines. The first line contains N, the number of cities under Toller's control. The next N lines contain the numerical identifiers of each city, one per line.

Output

Your program should output a single line containing a single number rounded to 3 decimal places, which is the average product of lengths of a pair of intersecting highways in units of RLM2.

Sample Input

4
0
262144
524288
786432

Sample Output

4.000

Sample Output Explanation

Only the highways (0, 524288) and (262144, 786432) intersect, and since each of them is a diameter of the wasteland, their lengths are 2 RLM each. The product of their lengths is 2 RLM × 2 RLM = 4 RLM2. Since there is only one pair of intersecting highways, the program prints 4 / 1 = 4.000 (3 decimal places).

diagram.png

Tags

Math

Subtasks and Limits

Subtask Score #TC Time Memory Scoring
1551s128MBMinimum
21051s128MBMinimum
33051s128MBMinimum
45551s4MBMinimum
5011s128MBMinimum

Judge Compile Command

g++-8 ans.cpp -o highways -Wall -Wshadow -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512

Accepted Submissions

subIDUserTimeMax Time

Past Submissions

subIDUserTimeScore
mrJudge 09.05.20
Copyright © 2020 mrJudge. All rights reserved.