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
2021-12-16 01:09:00 vas14
The stated constraint of C[i] ≤ 10^3 is wrong. I don't know that the actual max value of C[i] is in the input, but got AC with 2*10^3 instead of 10^3.
2020-10-07 20:50:37
Nice problem. Unfortunately so many people in comments are blaming author of this problem and claiming that problem has wrong constraints instead of blaming themselves for not considering that numbers can be equal. In case when all numbers are equal answer could be 10^5 * (10^5 - 1) / 2. It seems that most of them are newbies. )

Last edit: 2020-10-09 22:28:22
2018-08-18 07:23:51
such a creep description!!!!
use long long int
2018-06-13 02:10:46
here, long long int is real!
2018-05-31 09:27:07
int - wa :/
long long int - AC :O
what are you up to mate :3
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.
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
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 :|
2015-09-02 14:23:29 Jaswanth
j<k or j<=k my solution got accepted for j<=k
2015-03-19 17:58:18 iah10
how can we see the test cases..my code is giving runtime error and i would like to know the reason
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.