The participants of theWorld Programming Competition submitted N solution files f1, ..., fN to the
grading system. Before accepting the results as final, the jury would like to rule out any possibility
of plagiarism. They have a program that takes two files and compares them to decide if they are too
similar to each other.
However, the number of files is rather big and it would take too much time to compare all pairs. On
the other hand, many pairs could be quickly eliminated based on the fact that the file sizes are too
different.
More precisely, the jury decided to fully skip comparing every pair where the size of the smaller file
is less than 90% of the size of the larger one. So, the comparison program has to examine only those
distinct pairs of files (fi, fj) where i ≠ j, size(fi) ≦ size(fj) and size(fi) ≧ 0.9．size(fj).
Write a program that computes the number of pairs of files that will have to be examined.
The first line of input contains the integer N, the number of solution files submitted. The second line
contains N integers size(f1), ..., size(fN), each showing the size of one file.
1 ≦ N ≦ 100000
1 ≦ size(fi) ≦ 100000000
The first and only line of output must contain one integer, the number of pairs of files that will have
to be examined.
2 2 1 5 1 1 1 1 1
0 10
In the second example, each file has to be compared to each other (but each pair only once, not twice,
of course).
Migrated from old NTUJ.
BOI2011 Competition day 2
| No. | Testdata Range | Score |
|---|