All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian.
The Physics teacher in Tanu's class is teaching concepts of a bouncing ball. The rubber ball that she is using has the property that if the ball is dropped from height H then, it bounces back to maximum height H/F. So after first bounce it rises up to maximum height H/F, after second bounce to maximum height H/F2, after third bounce to maximum height H/F3, and so on.
The class has N children, and the teacher wants to select two children such that when the taller child drops the ball from his height, ball reaches a maximum height equal to the height of the shorter child after some (possibly zero) number of bounces. Note that zero bounces mean heights of the two children will be same. Given the heights of the children in the class Height[i], can you tell how many ways are there for the teacher to select two children for the demonstration? Note that when heights are same, the pair is only counted once (See first example for further clarification).
First line contains T, number of testcases. Then 2*T lines follow, 2 per testcase.
First line of each testcase consists of two space-separated intergers N and F. Second line of each testcase contains N space-separated integers representing the array Height.
For each testcase, print a single line containing the answer to the problem.
- For 40 points: 1 ≤ T ≤ 100, 1 ≤ N ≤ 103, 2 ≤ F ≤ 109, 1 ≤ Height[i] ≤ 109
- For 60 points: 1 ≤ T ≤ 100, 1 ≤ N ≤ 104, 2 ≤ F ≤ 109, 1 ≤ Height[i] ≤ 109
2 2 2
2 1 4
- In the first case, the three pairs are (child 1, child 2), (child 2, child 3) and (child 1, child 3).
- For the second case also, the three pairs are (child 1, child 2), (child 2, child 3) and (child 1, child 3).
|Tags||binary-search, hash-map, ltime17, piyushkumar, simple-easy, sorting|
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.