LCPC12F - Johnny The Gambler

Johnny is a gambling addict. He entered a casino and started playing a game with the dealer. The game is as follows: the dealer deals a sequence of N cards, each card containing a number C[i] and asks Johnny how many pairs (j, k) such that j < k and C[j] + C[k] = X. If Johnny answers correctly he wins, otherwise the dealer wins.

Input

The first line of input contains an integer T, the number of test cases. T test cases follow, Each test case start with the value of 0 ≤ X ≤ 2*103 followed by the number of cards 0 < N ≤ 105 followed by N numbers representing the numbers on the cards 0 ≤ C[i] ≤ 103.

Output

There should be T lines, containing the following format.

k. S

Where k is the test case number (starting at 1), a single period, a single space and S representing the number of valid pairs (j, k) as described above.

Sample

Input
1
10 3 1 5 9

Output
1. 1

Added by:Gareev
Date:2012-10-06
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:LCPC 2012

hide comments
2013-08-05 19:39:24 ROHIT KUMAR
aftr 6 back-2-back WA---->"AC" in 0.02s:)
2013-08-05 15:19:33 chk
after 4 WAs finally removed from TODO list :D
2013-08-03 13:53:08 LeppyR64
Confirmed Constraints: (Verified with AC C program using Assert)
0 <= X <= 2*10^3 (Accurate)
0 < N <= 10^5 (Accurate)
0 <= C[i] < 10^3 (Inaccurate, C[i] can be 1000)
0 <= C[i] <= 10^3 (Accurate)

Last edit: 2013-07-24 13:14:22
2013-07-14 04:45:03 BLANKRK
AC...:) 1 runtym error jus due to wrong constraints........
2013-07-04 08:34:23 Viktor Fonic
Here's a test case that gave me headaches:
1
5 5 2 3 4 5 6

Output should be:
1. 1

Last edit: 2013-07-04 08:34:32
2013-06-09 14:00:23 Ouditchya Sinha
@Rajarshi Sarkar : Thank you for the insightful test case. :)
2013-05-17 08:44:37 shiva_hellgeek
MY 150th problem on spoj. :)
2013-04-28 10:52:52 Rajarshi Sarkar
Numbers can be same.A free test case from my side (as the description is not very clear)
Input
5
4 4 2 2 2 2
Output
6

Both %lld or %d does the work.

Last edit: 2013-04-28 11:03:30
2013-04-26 02:04:46 Spar!k
can be solved in n*logn+n
2013-04-25 23:13:19 Eduardo Nunes
nice one, got 2 WAs just because I thought each number would be different ^_^ easy one with map
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.