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
|
vas14:
2021-12-16 01:09:00
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. |
|
lighted:
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 |
|
sudhanshu6324:
2018-08-18 07:23:51
such a creep description!!!!
|
|
cosmicray001:
2018-06-13 02:10:46
here, long long int is real! |
|
mag1x_:
2018-05-31 09:27:07
int - wa :/
|
|
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 |
|
robin_0:
2015-09-30 08:01:44
I don't get it :/
|
|
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 cases..my code is giving runtime error and i would like to know the reason |
| 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 |
RSS