Here you will find solutions of many problems on spoj. If you want solution of some problem which is not listed in blog or have doubt regarding any spoj problem (which i have solved) or any programming concept (data structure) you can mail me @ raj.nishant360@gmail.com

And my humble request to you all that don't copy the code only try to understand the logic and algorithm behind the code. I have started this because if you tried as hard as you can and still can't find any solution to the problem then you can refer to this.
You can read my answer how to start competitive programming CLICK HERE

Wednesday, June 4, 2014

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/6N3
So our answer will be = 14 *(1/6N3) = 14*(1/162) = 7/81;
Now we generalize the above concept. Let “X” be any number in 2nd column and “I” be any number in 1st 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

No comments:

Post a Comment

Your comment is valuable to us