APPROB-GETTING AN AP

GETTING AN AP

Below given python code for APPROB spoj or GETTING AN AP spoj.

For understanding write some small test case like for 3 ,4, 5, you will get the logic if you are unable to get you can mail me @  raj.nishant360@gmail.com

Here I am explaining you little bit about question .
Let’s take N=3 so the content in the three boxes will be as follow

1	1	1
2	2	2
3	3	3
	4	4
	5	5
	6	6
		7
		8
		9

So from the table we are first counting the AP with non-negative common difference.
1-> we choose “1” from the first raw.  Then total possible AP will be
                   

1->	1	1	1
2->	1	2	3
3->	1	3	5
4->	1	4	7
5->	1	5	9

For “1” (selected in first row) there are total five AP possible
For “1” (selected in first row) there will be no AP possible with negative common difference
2-> For “2”  (selected in first row)

1->	2	2	2
2->	2	3	4
3->	2	4	6
4->	2	5	8

So for  “2” (selected in first row) we will have total four AP as shown in table.
For two no AP exits in table for negative common differencs.

2-> For “3”  (selected in first row)

1->	3	3	3
2->	3	4	5
3->	3	5	7
4->	3	6	9

So for “3” (selected in first row) we will have four AP as shown in table.
Here for three there will be one AP with negative common difference.

3

2

1

So for “3” (selected in first row) we will have total five AP .
Now for N=3;
We will sum all the possible AP  (5+5+4) = 14;
Now total probability of selecting random number from three boxes will be->
(1/N)*(1/2N)*(1/3N) = 1/6N³
So our answer will be = 14 *(1/6N³) = 14*(1/162) = 7/81;
Now we generalize the above concept. Let “X” be any number in 2^nd column and “I” be any number in 1^st column the AP will exist if an only if bellow condition is satisfied for non-negative common difference.
X  + (X-I) <=3N  ->  2X – I <=3N   -> X <=(3N + I)/2  Floor of this will give maximum X for which AP can be formed . Total AP (with non-negative common difference ) can be formed by choosing “I” will be
MAX (“X”) for given “I” till which AP can be constructed -  “I” +1(I,I,I will itself form an AP with CD=0)
So it will be  (3N +I)/2 – I +1    ->         (  (3N+2) – i)/2 ; Floor of this will give you the total number of AP possible for selected “I” in first column .
F(i) = (  (3N+2) – i)/2
This is for non-negative common difference for negative try yourself .
Now if we select N=5 then total number of divisor will be (calculated by F1)
N = 1 -> F(1) = 8;
N= 2 -> F(2) = 7;
N= 3 -> F(3) = 7;
N= 4 ->F(4)=  6;
N= 5 ->F(5) = 6;
This is for non-negative CD for negative CD
N = 1 -> 0;
N= 2  -> 0;
N= 3  -> 1;
N= 4  -> 1;
N= 5  -> 2;
As series are forming in both the case CD +ive and –ive so we can easily calculate the sum in O(1) time

from fractions import gcd
import sys
t=int(sys.stdin.readline())
while t:
    n=int(sys.stdin.readline())
    if n&1:
        start = (3*n+1)//2
        st = (n-1)//2
        end = (3*n - n +2)//2
        total = 6*n*n*n
        result = start + 2*(((start-1)*start)//2 - ((end-1)*end)//2)
        result = result + st + (st-1)*st
        g= gcd(total,result)
        l=""
        l=l+str(result//g)+"/"+str(total//g)
        print (l)
    else :
        start = (3*n+1)//2
        st = (n-1)//2
        end = (3*n - n +2)//2
        total = 6*n*n*n
        result =2*(((start+1)*start)//2 - ((end-1)*end)//2)
        result = result + st*(st+1)
        g= gcd(total,result)
        l=""
        l=l+str(result//g)+"/"+str(total//g)
        print (l)
    t-=1