BALLSUM - Ball sum

You have a bag filled with N balls. Each ball has a distinct number from 1 to N printed on it. All the numbers are distinct. You withdraw two balls from the bag and take their sum. You need to calculate the probability that the sum is not greater than the given number K (<= N). The answer should be displayed in the form of p/q (except when the answer is 0 or 1.)

Input

Input consists of various test cases. Each test case consist of two integer inputs, N and K. (0 <= K <= N <= 1000000000) The program stops taking input when N and K equals -1.

Output

Output the result in the form of p/q (except when the answer is 0 or 1.)

Example

Input:
3 2
100 5
10 6
-1 -1

Output:
0
2/2475
2/15

Added by:Prateek Agarwal
Date:2015-12-15
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU JS-MONKEY

hide comments
2017-10-12 19:55:54
Nice problem .. Basic Logic
2017-09-21 02:15:30
Print newline after last result else WA.

mahilewets: Main algo is O(1) but you need the O(logm) bit because of the output format.
2017-09-03 09:30:51
Some people saying you need an O(log(M)) per query algorithm

I think an O(1) per query algorithm is much easier to invent and to implement

Last edit: 2017-09-03 09:31:47
2017-07-03 22:10:43
check for edge cases ..!!!
costed me 2 wa
2017-05-29 13:26:45
nice problem :) use pen and paper...check for odd and even values of k
2017-01-23 07:30:39
AC in 1 go :-) simple maths O(n)
2017-01-20 17:02:09
AC in one
2017-01-13 17:54:20
I am getting tle, can anyone help me?
2016-12-30 12:30:37
Took paper and pen, did some thinking and bingo....AC
2016-12-11 05:57:12 mrx
I don't know why I got TLE. I calculated p and q using maths in O(1) and their gcd using recursion and I used C :/

oh i was declaring long instead of long long :P Sorry !! Easy question !!

Last edit: 2016-12-11 06:57:56
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.