GCD2-GCD2

GCD2

Given below c++ code is for GCD2 Spoj.

/*
===================================================
Name :- Nishant Raj
Email :- raj.nishant360@gmail.com
College :- Indian School of Mines
Branch :- Computer Science and Engineering
Time :- 02 June 2016 (Thursday) 11:26
===================================================*/
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int mod(char s[], int divider){
    int r = 0;
    for(int i = 0 ;s[i] ; i++){
        r = r*10 + s[i] - 48;
        r = r % divider;
    }
    return r;
}
int gcd(int a , int b){
    return b == 0 ? a : gcd(b , a%b);
}
int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        int a;
        char b[259];
        scanf("%d %s",&a , b);
        if(a == 0){
            printf("%s\n" , b);
            continue;
        }
        printf("%d\n", gcd(a , mod(b , a)));
    }
    return 0;
}

INS14A-BSTRING

BSTRING

Given below c++ code is for ins14a spoj or bstring spoj.

Hint :- Think of bringing all one's to it median in windows of 'm' ones.

/*
===================================================
Name :- Nishant Raj
Email :- raj.nishant360@gmail.com
College :- Indian School of Mines
Branch :- Computer Science and Engineering
Time :- 18 October 2015 (Sunday) 22:05
===================================================*/
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair < int , int >
#define pb push_back
#define mp make_pair
#define mod 1000000009

int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        char s[50009];
        ll m;
        scanf("%lld %s" , &m ,s);
        int n = strlen(s);
        vector<ll> position;
        position.pb(0);
        for(int i = 0 ; i < n ; i++)
            if(s[i] == 49)
                position.pb(i+1);
        ll median = m/2 + 1;
        ll left = 0 , right = 0;
        for(int i = 0 ; i < median ; i++)
            left += position[i];
        for(int i = median + 1 ; i<=m ; i++)
            right += position[i];
        ll ans = right - left + (2*median - m - 1)*position[median];
        int var_median = median;
        for(int i = m+1 , j = 1 ; i < position.size() ;j++, i++){
            left -= position[j];
            left += position[var_median];
            var_median++;
            right -= position[var_median];
            right += position[i];
            ll temp = right - left + (2*median - m - 1)*position[var_median];
            ans = min(ans , temp);
        }
        ans -= (m*m + 2*median*(median - 1) - 2*m*median + m)/2;
        printf("%lld\n", ans);
    }
    return 0;
}

OPSL-Operation Searchlight

Operation Searchlight

Given below c++ code is for OPSL spoj or Operation Searchlight spoj .

This is an easy problem & should be in tutorial class , here you should know sieve and how to calculate LCM of numbers.

DEADFR-Dead Fraction

Dead Fraction

Below given code is for deadfr spoj or dead fraction spoj.

Source : - http://www.basic-mathematics.com/converting-repeating-decimals-to-fractions.html

How this problem can be solved :- 

Step 1:

Let x equal the repeating decimal you are trying to convert to a fraction

Step 2:

Examine the repeating decimal to find the repeating digit(s)

Step 3:

Place the repeating digit(s) to the left of the decimal point

Step 4:

Place the repeating digit(s) to the right of the decimal point

Step 5:

Subtract the left sides of the two equations.Then, subtract the right sides of the two equations

As you subtract, just make sure that the difference is positive for both sides

Now let's practice converting repeating decimals to fractions with two good examples

Example #1:

What rational number or fraction is equal to 0.55555555555

Step 1:

x = 0.5555555555 

Step 2:

After examination, the repeating digit is 5

Step 3:

To place the repeating digit ( 5 ) to the left of the decimal point, you need to move the decimal point 1 place to the right

Technically, moving a decimal point one place to the right is done by multiplying the decimal number by 10.

When you multiply one side by a number, you have to multiply the other side by the same number to keep the equation balanced

Thus, 10x = 5.555555555

Step 4:

Place the repeating digit(s) to the right of the decimal point

Look at the equation in step 1 again. In this example, the repeating digit is already to the right, so there is nothing else to do.

x = 0.5555555555

Step 5:

Your two equations are:

10x = 5.555555555

   x = 0.5555555555

10x - x = 5.555555555 − 0.555555555555

9x = 5

Divide both sides by 9

x = 5/9

What you have to consider in problem ?

1. If given fraction is 0.2154... then

        Case 1-  '4' can be repeating 

        Case 2- '54' can be repeating 

        Case 3- '154' can be repeating 

        Case 4- '2154' can also be repeating  

So you have to check for all case and print the one with lowest denominator.

2. If ans is '1' then print "1/1" .

RIVALS-Rivals

Rivals

Given below code is for RIVAL spoj.

Hint :- simple math and inverse modulo problem

#include <bits/stdc++.h>
using namespace std ;
#define LL long long
#define MOD 1000000007
LL arr[2000009];
void pre()
{
    arr[0] = 1;
    arr[1] = 1;
    for(LL i = 2 ; i<=2000000 ; i++)
        arr[i] = (arr[i-1] * i)%MOD;
}
LL inv_mod(LL x)
{
    LL a = 1 , p = x , n = 1000000005;
    while(n) 
    {
        if(n&1)
            a = (a*p)%MOD;
        p = (p * p )%MOD;
        n>>=1;
    }
    return a;
}
int main()
{
    int t;
    pre() ;
    scanf("%d",&t);
    while(t--)
    {
        int x , y;
        scanf("%d%d",&x , &y);
        LL temp = (inv_mod(arr[x]) * inv_mod(arr[y]))%MOD;
        LL res = (arr[x+y] * temp)%MOD;
        printf("%lld\n",res);
    }
    return 0;
}

TETRASUM-Sum of Tetranacci numbers

Sum of Tetranacci numbers

Given below code is for TETRASUM spoj sum of tetranacci numbers spoj.

#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000007
#define gc getchar_unlocked
class matrix
{
public:
    long long m[4][4];
};
matrix multiply(matrix a , matrix b)
{
    matrix temp;
    for(int i = 0 ; i < 4 ; i++)
        for(int j = 0 ; j < 4 ; j++)
        {
            temp.m[i][j] = 0;
            for(int k = 0 ; k < 4 ; k++){
                temp.m[i][j] = (temp.m[i][j] + a.m[i][k] *b.m[k][j]);
                if(temp.m[i][j] >= MOD) temp.m[i][j] %= MOD;
            }
        }
    return temp;
}
matrix arr[32];
void pre()
{
    arr[0].m[0][0] = 0 ; arr[0].m[0][1] = 0 ; arr[0].m[0][2]  = 0 ; arr[0].m[0][3] = 1;
    arr[0].m[1][0] = 1 ; arr[0].m[1][1] = 0 ; arr[0].m[1][2]  = 0 ; arr[0].m[1][3] = 1;
    arr[0].m[2][0] = 0 ; arr[0].m[2][1] = 1 ; arr[0].m[2][2]  = 0 ; arr[0].m[2][3] = 1;
    arr[0].m[3][0] = 0 ; arr[0].m[3][1] = 0 ; arr[0].m[3][2]  = 1 ; arr[0].m[3][3] = 1;
    matrix temp;
    for(int pos = 1 ; pos <= 29 ; pos++){
        for(int i = 0 ; i < 4 ; i++)
            for(int j = 0 ; j < 4 ; j++)
            {
                arr[pos].m[i][j] = 0;
                for(int k = 0 ; k < 4 ; k++){
                    arr[pos].m[i][j] = (arr[pos].m[i][j] + arr[pos-1].m[i][k] *arr[pos-1].m[k][j]);
                    if(arr[pos].m[i][j] >= MOD) arr[pos].m[i][j] %= MOD;
                }
            }
    }
}
matrix nth_Term(int n)
{
    int count = 0 ;
    matrix a;
    a.m[0][0] = 1 ; a.m[0][1] = 0 ; a.m[0][2] = 0 ; a.m[0][3]= 0;
    a.m[1][0] = 0 ; a.m[1][1] = 1 ; a.m[1][2] = 0 ; a.m[1][3]= 0;
    a.m[2][0] = 0 ; a.m[2][1] = 0 ; a.m[2][2] = 1 ; a.m[2][3]= 0;
    a.m[3][0] = 0 ; a.m[3][1] = 0 ; a.m[3][2] = 0 ; a.m[3][3]= 1;
    if(n<=2)
        return a;
    n-=2;
    while(n)
    {
        if(n&1){
            a = multiply(a,arr[count]);
        }
        count++;
        n>>=1;
    }
    return a;
}
int main()
{
    int t ;
    pre();
    scanf("%d",&t);
    matrix temp;
    long long res1 = 0 , res2 , n_1 , n_t , n_2 ;
    int m , n , res;
    long long inv = 333333336;
    while(t--)
    {
        scanf("%d%d", &m , &n);
        if(n == m)
        {
            temp = nth_Term(n);
            printf("%lld\n" , temp.m[3][2]);
            continue;
        }
        if(n<=2)
            res1 = 0;
        else
        {
            temp = nth_Term(n-1);
            n_1 = temp.m[3][2];
            temp = multiply(temp,arr[0]);
            n_t = temp.m[3][2];
            temp = multiply(temp,arr[1] );
            n_2 = temp.m[3][2];
            res1 = (n_2 + (n_t<<1) + n_1 -1);
            res1 = (res1*inv)%MOD;
        }
        if(m<=3)
            res2 = 0;
        else
        {
            m--;
            temp = nth_Term(m-1);
            n_1 = temp.m[3][2];
            temp = multiply(temp,arr[0]);
            n_t = temp.m[3][2];
            temp = multiply(temp,arr[1]);
            n_2 = temp.m[3][2];
            res2 = (n_2 +  (n_t<<1) + n_1 - 1 );
            res2 = (res2*inv)%MOD;
        }
        res = (res1 - res2 + MOD)%MOD;
        printf("%d\n",res);
    }
    return 0;
}

FIBOSUM-Fibonacci Sum

Fibonacci Sum

given below code is for fibosum spoj or fibonacci sum spoj.

here you should know how to calculate fibonacci number in log(n) time

#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000007
#define ULL unsigned long long 
void mul(ULL a[][2] , ULL b[][2])
{
    ULL res[2][2];
    memset(res , 0 , sizeof res);
    for(int i = 0 ; i < 2 ; i ++)
        for(int j = 0 ; j < 2 ; j++)
            for(int k = 0 ; k < 2 ; k++)
                res[i][j] = (res[i][j] + a[i][k]*b[k][j]) % MOD;
    for(int i = 0 ; i < 2 ; i++)
        for(int j = 0 ; j < 2 ; j++)
            a[i][j] = res[i][j];
}
ULL  power( ULL  n)
{
    ULL  fib[2][2] = { {1 , 1} , { 1 , 0}},temp[2][2] = { {1 , 0 } , { 0 , 1}};
    while(n)
    {
        if(n&1)
            mul(temp , fib);
        mul(fib , fib);
        n>>=1;
    }
    return temp[0][1];
}
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        ULL l , r;
        cin>>l>>r;
        cout<<(power(r+2) - power(l+1) + MOD)%MOD<<endl;
    }
    return 0;
}

BUILDTOW-Build the Tower

Build the Tower

given below code is for BUILDTOW spoj or build the tower spoj.

Here you have to calculate fibonacci  sequence in log n time and then formula for 

a(n) = fibonacci(n+1)*fibonacci(n+2) - 1;

#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000007
#define ULL unsigned long long 
void mul(ULL a[][2] , ULL b[][2])
{
    ULL res[2][2];
    memset(res , 0 , sizeof res);
    for(int i = 0 ; i < 2 ; i ++)
        for(int j = 0 ; j < 2 ; j++)
            for(int k = 0 ; k < 2 ; k++)
                res[i][j] = (res[i][j] + a[i][k]*b[k][j]) % MOD;
    for(int i = 0 ; i < 2 ; i++)
        for(int j = 0 ; j < 2 ; j++)
            a[i][j] = res[i][j];
}
ULL  power( ULL  n)
{
    ULL  fib[2][2] = { {1 , 1} , { 1 , 0}},temp[2][2] = { {1 , 0 } , { 0 , 1}};
    while(n)
    {
        if(n&1)
            mul(temp , fib);
        mul(fib , fib);
        n>>=1;
    }
    return temp[0][1];
}
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        ULL n ;
        cin>>n;
        cout<<"$"<<((power(n+1)*power(n+2))%MOD - 1 + MOD)%MOD<<endl; 
    }
    return 0;
}

OHANISER-Ohani And The Series

Ohani And The Series

Given below code is for OHANISER spoj or Ohani And The Series spoj.

#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define MOD 1000000007
LL pow_mod(int n)
{
    LL a = 1 , p = 2;
    while(n)
    {
        if(n&1)
            a = (a*p)%MOD;
        p = (p*p)%MOD;
        n>>=1;
    }
    return a;
}
int main()
{
    int t , j = 1;
    cin>>t;
    while(t--)
    {
        LL n;
        cin>>n;
        if(n==1)
        {
            cout<<"Case "<<j<<": "<<1<<endl;
            j++;
            continue;
        }
        if(n == 2)
        {
            cout<<"Case "<<j<<": "<<3<<endl;
            j++;
            continue;
        }
        cout<<"Case "<<j<<": "<<((n+1) * (pow_mod(n-2)))%MOD<<endl;
        j++;
    }
    return 0;
}

COMDIV - Number of common divisors

Number of common divisors

Given below code is for comdiv spoj or number of common divisor spoj.

Hint :- > sieve and the number of common divisor of two number will be the number of divisor of its GCD.

#include <bits/stdc++.h>
using namespace std;
int prime[100000];
bool check[1000009];
void pre()
{
    for(int i = 3 ; i<=1000 ; i+=2)
    {
        if(!check[i])
        {
            for(int j = i*i ; j<=1000000 ; j+=i)
                check[j] = true;
        }
    }
    int j  = 1;
    prime[0] = 2;
    for(int i = 3; i <=1000000 ; i+=2)
        if(!check[i])
            prime[j++] = i;
}
int main()
{
    pre();
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        long long  gcd = __gcd(a,b);
        long long  res = 1;
        if(gcd == 1)
        {
            printf("1\n");
            continue;
        }
        for(int i = 0 ;i <= 78500 && prime[i] < gcd  && gcd; i++)
        {
            int count = 0;
            while(gcd%prime[i] == 0)
            {
                count++;
                gcd/=prime[i];
            }
            res *= (count + 1);
        }
        if(gcd > 1)
            res *= 2;
        printf("%lld\n",res);
    }
    return 0;
}

HPYNOSII-Happy Numbers II

Happy Numbers II

Given below code is for HPYNOSII spoj or Happy Numbers II spoj .

Initial array i have computed it from wikipedia where all happy numbers below 1000 are given.

#include <bits/stdc++.h>
using namespace std;
#define gc getchar_unlocked
int res[1001]={0,1,0,0,0,0,0,5,0,0,1,0,0,2,0,0,0,0,0,4,0,0,0,3,0,0,0,0,3,0,0,2,3,0,0,0,0,0,0,0,0,0,0,0,4,0,0,0,0,4,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,0,5,0,0,0,0,0,0,0,0,3,0,0,3,0,0,0,2,0,0,0,0,4,0,0,4,0,0,3,0,0,1,0,0,2,0,0,0,0,0,4,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,3,2,0,0,5,0,0,0,0,0,5,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,3,0,0,0,0,0,0,0,0,3,0,0,0,0,0,0,0,0,0,0,0,4,0,4,0,3,5,0,0,0,0,0,0,0,0,0,3,0,0,0,0,3,0,0,0,0,0,0,0,0,0,0,3,0,0,0,0,0,0,5,0,0,0,3,0,0,0,0,0,5,0,0,5,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,5,5,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,3,0,0,0,0,0,0,0,0,0,0,3,0,5,0,0,0,0,0,0,0,2,3,0,0,0,0,0,0,0,2,0,0,5,0,0,0,0,0,5,3,0,0,0,0,0,5,0,0,5,0,5,0,0,0,0,0,0,4,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,6,0,0,0,0,0,5,0,0,6,0,5,5,0,0,0,0,0,0,0,5,0,0,6,0,0,0,4,0,0,5,0,0,0,0,5,5,0,0,0,0,6,0,0,0,0,0,0,4,0,0,0,0,4,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,4,0,0,0,0,0,3,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,3,0,0,0,0,6,0,0,0,0,0,0,0,0,4,0,0,0,0,0,0,0,0,4,0,0,4,0,0,0,0,0,6,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,6,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,3,0,0,0,0,0,0,6,0,3,4,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,0,0,0,0,0,0,0,0,3,0,0,0,0,5,5,0,0,0,0,0,0,0,0,5,0,0,6,0,5,5,0,0,0,0,0,3,0,0,0,0,6,0,0,0,6,0,3,4,0,0,0,0,0,0,0,0,4,0,0,0,0,0,3,0,5,0,0,0,0,0,0,2,0,0,5,0,0,0,0,0,0,0,0,0,0,6,0,0,0,0,0,5,0,0,0,0,0,0,0,0,3,0,0,0,0,0,0,3,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,5,0,0,6,0,0,0,0,0,0,0,0,4,0,0,0,0,0,0,0,0,0,0,0,0,3,0,5,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,4,0,0,0,0,0,3,0,0,6,0,0,0,0,0,0,0,0,3,0,0,0,2,0,0,0,0,0,0,0,0,0,0,0,4,0,3,0,0,0,0,0,0,0,0,0,0,0,0,4,0,0,5,0,0,0,0,0,0,0,0,0,0,4,0,0,0,0,0,0,0,0,0,0,0,0,2,0,0,5,0,0,0,0,0,0,0,0,0,0,4,0,0,0,0,0,0,4,0,0,0,0,0,0,4,0,0,0,0,0,0,0,0,0,0,6,0,4,0,0,4,0,0,3,0,0,4,0,3,5,0,0,0,0,0,0,0,3,0,5,0,0,0,0,0,0,0,5,5,0,0,0,0,6,0,0,4,0,0,0,0,0,6,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,6,0,0,0,0,0,3,0,0,6,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,6,0,0,0,0,0,0,0,0,6,0,1,};
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n;
        scanf("%d",&n);
        if(n<=1000)
        {
            if(res[n])
                printf("%d\n",res[n]);
            else
                printf("-1\n");
            continue;
        }
        int sum = 0,r;
        while(n)
        {
            r= n%10;
            sum+=r*r;
            n/=10;
        }
        if(sum==1)
        {
            printf("1\n");
        }
        else{
            if(res[sum])
                printf("%d\n",res[sum]+1);
            else
                printf("-1\n");
        }
    }
    return 0;
}

DIVISION-Divisiblity by 3

Divisiblity by 3

Below given c++ code for division spoj or Divisiblity by 3 spoj.

First see the divisibility of number ‘X’ by three when written in binary form .

A binary number is a multiple of 3 if and only if the alternating sum of its bits is also a multiple of 3

let see for some ‘X’:-

4   = 100       1 - 0 + 0 = 1, not multiple of 3

6   = 110       1 - 1 + 0 = 0, multiple of 3

78  = 1001110   1 - 0 + 0 - 1 + 1 - 1 + 0 = 0, multiple of 3

109 = 1101101   1 - 1 + 0 - 1 + 1 - 0 + 1 = 1, not multiple of 3

Now we have to find how many numbers exist in decimal form(base 10) such that when converted into binary(base 2) form has N length and is divisible by 3.(I will call this n as binary length)

Now let’s start with length N=1;

N=1 = 0 ->divisible by 3  total = 1;

N=2  then (00) & (11) is divisible by 3 , Total = 2;

N=3 We can see that all number of binary length less than 3 will present in it

                                            1-> 000

                                            2-> 011

                                            3-> 110

For N=3 total 3 number are possible.

Similarly we will get for all other number. Now will se how to calculate it for large number ,for that we have to find relation between them. Let’s derive that ->

N=1 ->1

N=2 ->2        (2*1)

N=3 ->3        (2*1)*2 - 1

N=4 -> 6       (2^2 -1)*2

N=5 ->11      (2^3 – 2^1)*2 - 1

N=6 ->22      (2^4 – 2^2 -1) *2

N=7 ->43      (2^5 – 2^3 – 2^1)*2 - 1

From the above we can find out that if ‘N’ is even then:-

Total number divisible by three will be given by->   2^n-1  - (2 + 2³ + 2⁵ +…….+ 2^n-3)

Similarly for odd one-> 2^n-1  - (1+2 + 2³ + 2⁵ +…….+ 2^n-3)

On reducing the above we will get

For EVEV ->  (2ⁿ + 2)/3

ODD -> (2ⁿ + 1)/3

Hence our complexity reduces to O(log n) because we can find (a^b MOD P) in logarithmic time. 

#include <bits/stdc++.h>
using namespace std;
#define ULL unsigned long long 
#define MOD 1000000007
#define INV 333333336 //Inverse modulo of 3 with 1000000007
ULL pow_mod(ULL n)
{
    ULL x=1,p=2;
    while(n)
    {
        if(n&1)
            x=(x*p)%MOD;
        p=(p*p)%MOD;
        n>>=1;
    }
    return x;
}
int main()
{
    ULL n,result;
    while(scanf("%llu",&n)!=EOF)
    {
        if(n&1){
            result = ((pow_mod(n)+1)*INV)%MOD;
            printf("%llu\n",result);
        }
        else{
            result = ((pow_mod(n)+2)*INV)%MOD;
            printf("%llu\n",result);
        }
    }
    return 0;
}

VENOM-Touch of Venom

Touch of Venom

Given below c++ code is for venom spoj or touch the venom spoj.

 Explanation:- 

 Let H= Health, P = Poison, A = Heal Value

 Let Hero survived for “X” step (here we can see that answer will be odd position because health decreases on only odd position we will see this below)

 Now writing step from 1 

  At fifth step you can calculate the relation between “X” and “n” by observing its values.

  X=  n + n – 1  ->  2n -1

  Now at X position we got an equation whose value should be less than or equal to zero.

From above formula we will get value of "n" but actual value will be ceil(n) because we are checking for zero or less then zero.

Our answer will be X = 2n-1

#include <bits/stdc++.h>
using namespace std;
#define LL long long 
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int h,p,a;
        scanf("%d%d%d",&h,&p,&a);
        if(h<=p)
        {
            printf("1\n");
            continue;
        }
        double y,z,d;
        LL result=0;
        y= p - 2*a;
        z= 2*(a-h);
        d= sqrt(y*y - 4*p*z);
        result = ceil((-1*y + d)/(2*p));
        result = result + (result-1);
        printf("%lld\n",result);
    }
    return 0;
}

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

CRAN01-An Experiment by Penny

An Experiment by Penny

Below given c++ code is for CRAN01 spoj or An experiment by penny.

Here to find the logic you can test it for some small test by pen & paper. For myself I have checked for approx. 20 test cases then I got the logic .

Logic is maximum corner distance from given point is the minimum time to fill the entire box.

For example I am taking a grid of 7 x 7 and starting position as (4,5).

Here in the above table there are four corners coloured as yellow green black & blue and the starting position is red coloured box. Now the corners coloured with yellow and black are at maximum distances = 7 So here answer will be 7 .I get this logic from observation so if you want to clear your logic please use pen & paper and draw some small test cases or use brute-force.

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n,m,x,y;
        scanf("%d%d%d%d",&n,&m,&x,&y);
        int r1,r2,r3,r4,result;
        r1 = abs(x-1) + abs(y-1);
        r2 = abs(x-1) + abs(y-m);
        r3 = abs(x-n) + abs(y-1);
        r4 = abs(x-n) + abs(y-m);
        result = max(r1,max(r2,max(r3,r4)));
        printf("%d\n",result);
    }
    return 0;
}

here also python 2.7 code is for CRAN01 spoj or An experiment by penny.

import sys,math
t=int(sys.stdin.readline())
while t:
    n,m = map(int,sys.stdin.readline().split())
    x,y = map(int,sys.stdin.readline().split())
    r1 = abs(x-1) + abs(y-1)
    r2 = abs(x-1) + abs(y-m)
    r3 = abs(x-n) + abs(y-1)
    r4 = abs(x-n) + abs(y-m)
    result = max(r1,max(r2,max(r3,r4)))
    sys.stdout.write(str(result))
    sys.stdout.write("\n")
    t=t-1

POTIONS-Potions Class

Potions Class

Below given python code for potions spoj or potions class spoj.
In question a function is given for range query and seeing the number of query(q<100000) every query should be done in constant time O(1).Now having a look on function and trying to simplify it.

Now “w” is constant so taking it outside of summation

Now subtracting and adding “x” to  “i”  sp,

Now rearranging the above we get  

Since “x” is constant so taking it out of summation and taking common with

Now owr answer will be :..

If you have any problem in understanding the above logic you can mail me @ raj.nishant360@gmail.com

Below is Python 2.7 implementation of above logic.

import sys
t=int(sys.stdin.readline())
while t:
    n,q=map(int,sys.stdin.readline().split())
    s=raw_input().split()
    cum=[]
    cum2=[]
    for i in range(0,n+1):
        cum.append(0)
        cum2.append(0)
    for i in range(1,n+1):
        cum[i]=cum[i-1] + int(s[i-1])
        cum2[i]=cum2[i-1]+i*(int(s[i-1]))
    for i in range(0,q):
        w,x,y,z=map(int,sys.stdin.readline().split())
        lower = y+x
        higher = z+x
        result=(cum2[higher]-cum2[lower-1] + (w-x)*(cum[higher]-cum[lower-1]))%1000000007
        sys.stdout.write(str(result))
        sys.stdout.write("\n")
    t=t-1

DCEPC11B-Boring Factorials

Boring Factorials

given below code for dcepc11b spoj or boring factorial spoj.

here the problem is based on two main concepts 

1 -> Wilson’s Theorem 

2 -> Inverse modulo (It can be found by Extended Euclidean Algorithm , Fermat’s Little Theorem ,Euler’s Theorem)

here in this problem i have used Fermat's theorem 

Wilson’s Theorem 

According to Wilson's Theorem     for all prime n;(for proof of Wilson's Theorem click on link)

Now from this we can write :

Here my solution get accepted in 1.83 sec can any body help me in optimizing this solution or any other solution which get accepted in lower time please mail me @ raj.nishant360@gmail.com

#include <bits/stdc++.h>
using namespace std;
#define LL long long
LL pow_mod(LL a,LL b,LL m)
{
 LL x=1,y=a;
 while(b>0)
 {
  if(b & 1)
   x=(x*y)%m;
  y=(y*y)%m;
  b>>=1;
 }
 return x;
}
int main()
{
 int t;
 scanf("%d",&t);
 while(t--)
 {
  LL n,p,i,result=-1,temp;
  scanf("%lld%lld",&n,&p);
  if(n>=p)
  {
   printf("0\n");
   continue;
  }
  for(i=n+1;i<p;i++)
  {
   temp=pow_mod(i,p-2,p);
   result=(result*temp)%p;
  }
  printf("%lld\n",p+result);
 }
 return 0;
}

aps-Amazing Prime Sequence

Amazing Prime Sequence

given below c code for aps spoj or amazing prime sequence.

If you have any quarry you can mail me @ raj.nishant360@gmail.com

#include <bits/stdc++.h>
int p[10000009];
long long res[10000009];
void pre()
{
 for(int i=2;i<=10000000;i++)
 {
  if(!p[i])
  {
   for(int j=i+i;j<=10000000;j+=i)
    if(!p[j])
     p[j]=i;
   res[i]=res[i-1]+i;
  }
  else
   res[i]=res[i-1]+p[i];
 }
}
int main()
{
 int t;
 pre();
 scanf("%d",&t);
 while(t--)
 {
  int n;
  scanf("%d",&n);
  printf("%lld\n",res[n]);
 }
 return 0;
}

WPC5I-LCM

LCM

given below c code for wpc5i spoj or lcm spoj.

If you have any problem you can ask me @ raj.nishant360@gmail.com

#include <bits/stdc++.h>
using namespace std;
int main()
{
 int t;
 scanf("%d",&t);
 while(t--)
 {
  int n,m;
  scanf("%d%d",&n,&m);
  map<int ,int>mp1,mp2,result;
  map<int ,int>::iterator t;
  for(int i=2;i*i<=n;i++)
  {
       while(n%i==0)
       {
           mp1[i]+=1;
           n/=i;
        }
  }
  if(n>1)
     mp1[n]+=1;
  for(int i=2;i*i<=m;i++)
  {
        while(m%i==0)
        {
            mp2[i]+=1;
            m/=i;
        }
  }
  if(m>1)
     mp2[m]+=1;
  long long k=1;
  for(t=mp1.begin();t!=mp1.end();t++)
  {
       if(t->second > mp2[t->first])
           result[t->first]=t->second;
  } 
  for(t=mp2.begin();t!=mp2.end();t++)
  {
       if(t->second > mp1[t->first] && result[t->first] < t->second)
            result[t->first]=t->second;
  }
  for(t=result.begin();t!=result.end();t++)
       for(int i=0;i<t->second;i++)
            k*=(long long)(t->first);
  printf("%lld\n",k);
 }
 return 0;
}

INS14B-TRISQRS

TRISQRS

Given below code is for ins14b spoj or trisqrs spoj.

Here the area of largest triangle possible in a square is (N*N)/2;

So we have to count the total number of divisors of  (N*N)/2.

My algorithm is very time consuming if any one can suggest me more fast algorithm for finding total number of divisors of a number please comment or mail me @ :-> raj.nishant360@gmail.com .That will be very help full to me.

#include <bits/stdc++.h>
using namespace std;
int num[1000009]={0};
void pre()
{
 for(int i=2;i<=1000;i++)
 {
  if(!num[i])
  for(int j=i*i;j<=1000000;j+=i)
   if(!num[j])
    num[j]=i;
 }
}
int main()
{
 int t;
 pre();
 scanf("%d",&t);
 while(t--)
 {
  int n;
  scanf("%d",&n);
  if(n&1){
   printf("0\n");
   continue;}
  n*=n;
  n>>=1;
  cout<<n<<endl;
  map<int ,int >mp;
  map<int ,int >::iterator t;
  if(num[n]!= 0)
   while(n%num[n] == 0)
   {
    mp[num[n]]+=1;
    if(num[n] == 0)
     break;
    n/=num[n];
    if(num[n]==0)
     break;
   }
  mp[n]+=1;
  int result =1;
  for(t=mp.begin();t!=mp.end();t++)
   result *= (t->second + 1);
  printf("%d\n",result);
 }
 return 0;
}