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

hide comments
ROHIT KUMAR: 2013-08-05 19:39:24

aftr 6 back-2-back WA---->"AC" in 0.02s:)

chk: 2013-08-05 15:19:33

after 4 WAs finally removed from TODO list :D

LeppyR64: 2013-08-03 13:53:08

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
BLANKRK: 2013-07-14 04:45:03

AC...:) 1 runtym error jus due to wrong constraints........

Viktor Fonic: 2013-07-04 08:34:23

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
Ouditchya Sinha: 2013-06-09 14:00:23

@Rajarshi Sarkar : Thank you for the insightful test case. :)

shiva_hellgeek: 2013-05-17 08:44:37

MY 150th problem on spoj. :)

Rajarshi Sarkar: 2013-04-28 10:52:52

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
Spar!k: 2013-04-26 02:04:46

can be solved in n*logn+n

Eduardo Nunes: 2013-04-25 23:13:19

nice one, got 2 WAs just because I thought each number would be different ^_^ easy one with map


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