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 Format         

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 Format

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

Sample Input


10 3 1 5 9

1. 1


hide comments
sudhanshu6324: 2018-08-18 07:23:51

such a creep description!!!!
use long long int

cosmicray001: 2018-06-13 02:10:46

here, long long int is real!

mag1x_: 2018-05-31 09:27:07

int - wa :/
long long int - AC :O
what are you up to mate :3

nadstratosfer: 2017-10-22 22:48:34

I vaguely remember a video from Google on YT about how their job interviews look like, and this problem was being solved there - couldn't bother to watch until the optimal solution then, and haven't looked for it now because there's an elegant O(n) one with Python's SL they certainly didn't employ solving in C. Anyway 0 doesn't matter, order doesn't matter, just watch out for X/2.

vengatesh15: 2017-02-18 20:15:37

forget to consider 0 that cost me 2 WA but easy one did in O(n) time and O(n) space

siddharth_0196: 2016-06-18 19:38:30

Last edit: 2016-11-11 08:49:19
robin_0: 2015-09-30 08:01:44

I don't get it :/
I assumed that the ans may be large so took long long int to store that .
But T , X other variables are within 10^4 so int must be enough :/
But guess what WA
and again when I resubmitted by changing all to long long int I got AC :|
Why SPOJ you do like this :/
Codeforces is better in these respects :|

Jaswanth: 2015-09-02 14:23:29

j<k or j<=k my solution got accepted for j<=k

iah10: 2015-03-19 17:58:18

how can we see the test code is giving runtime error and i would like to know the reason

Abhinandan Agarwal: 2015-02-24 23:28:14

Constraints are correct, if you want include the test case, but declare the variable- which is supposed to store the answer, as long long, because answer can be large

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