프로그램 명: boi_plagiarism
제한시간: 1 초

//작업 중.............

The participants of the World 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 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.

출력

The first and only line of output must contain one integer, the number of pairs of files that will have to be examined.

Constraints

1 N 100 000 1 size(fi) 100 000 000

입출력 예

입력

2
2 1
0
5
1 1 1 1 1
10

출력
In the second example, each file has to be compared to each other (but each pair only once, not twice, of course) 
출처giarism
The participants of the World Programming Competition submitted N solution ?les f1; : : : ; fN to the
grading system. Before accepting the results as ?nal, the jury would like to rule out any possibility
of plagiarism. They have a program that takes two ?les and compares them to decide if they are too
similar to each other.
However, the number of ?les 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 ?le sizes are too
different.
More precisely, the jury decided to fully skip comparing every pair where the size of the smaller ?le
is less than 90% of the size of the larger one. So, the comparison program has to examine only those
distinct pairs of ?les (fi
 0:9 4 size(fj ).
Write a program that computes the number of pairs of ?les that will have to be examined.
Input
The ?rst line of input contains the integer N, the number of solution ?les submitted. The second line
contains N integers size(f1); : : : ;size(fN ), each showing the size of one ?le.
Output
The ?rst and only line of output must contain one integer, the number of pairs of ?les that will have
to be examined.
Constraints
      1  N  100 000
      1  size(fi)  100 000 000
      In test cases worth 50 points, 1  N  2 000.
Examples
Input Output
2
2 1
0
5
1 1 1 1 1
10
In the second example, each ?le has to be compared to each other (but each pair only once, not twice,
of course):
출처:BOI 2011 day2 3/4
[질/답] [제출 현황] [푼 후(0)]
[ 채 점 ] [홈으로]  [뒤 로]