| Submit | All submissions | Best solutions | Back to list |
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 |
||||||||
RSS