code with chinmay.c: spoj

Showing posts with label spoj. Show all posts

Saturday, 22 August 2015

SPOJ-MCOINS

hi friends today i will teach u how to deal with ALGORITHMIC GAMES..

the spoj link of the question...

so how to think.....
if for example inputs are

3 4 5
12 3223 12212 34344 43434

We can see that n = 1, 3, 4 are winning positions for the first player, because he can simply take all the coins. For n=0 there are no possible moves — the game is finished — so it is the losing position for the first player, because he can not make a move from it. If n=2 the first player has only one option, to remove 1 coin. If n=5 or 6 a player can move to 2 (by removing 3 or 4 coins), and he is in a winning position. If n=7 a player can move only to 3, 4, 6, but from all of them his opponent can win.

see the table below:
F=false,T=true;
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
F T F T T T T F T F

i think you do it still if have any query ask me... :)

#include<bits/stdc++.h>
using namespace std;
int min(int x,int y)
{
    return (x<y)?x:y;
}
int main()
{
    int n,m,q;
    static bool a[1000000];
    scanf("%d %d %d",&n,&m,&q);
    a[0]=false,a[1]=true,a[n]=true,a[m]=true;
    for(int i=2;i<=1000000;i++)
    {
        if(i>=1)
        {
            if(a[i-1]==true)a[i]=false;
            else {a[i]=true;continue;}
        }
        if(i>=n)
        {
            if(a[i-n]==true)a[i]=false;
            else {a[i]=true;continue;}
        }
        if(i>=m)
        {
            if(a[i-m]==true)a[i]=false;
            else {a[i]=true;continue;}
        }
    }
    while(q--)
    {
        scanf("%d",&n);
        printf("%c",(a[n])?'A':'B');
    }
    return 0;
}

SPOJ-TRGRID

try to solve this as for a square grid...
take the min of the row and column (be x)and find the value for the grid(x,x)

now your answer wont change if the grid is originally a horizontal rectangle but may vary if the grid is vertical rectangle

.. think yourself and u will get what i meant...

#include<bits/stdc++.h>
int min(int x,int y)
{
    return (x<y)?x:y;
}
int max(int x,int y)
{
    return (x>y)?x:y;
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int m,n,x;
        scanf("%d %d",&n,&m);
        x=min(n,m);
        char ch;
        ch=(x&1)?'R':'L';
        if(n>m && m&1)ch='D';
        if(n>m && !(m&1))ch='U';
        printf("%c\n",ch);
    }
    return 0;
}

Friday, 21 August 2015

SPOJ-BYECAKES

#include<bits/stdc++.h>
int min(int x,int y)
{
    return (x<y)?x:y;
}
int max(int x,int y)
{
    return (x>y)?x:y;
}
int main()
{
    double a[9],b[9],m;
    while(1)
    {
        m=0;
        for(int i=0;i<8;i++)
            scanf("%lf",&a[i]);
        if(a[0]==-1)break;
        for(int i=0;i<=3;i++)
        {
            b[i]=ceil(a[i]/a[i+4]);
            m=max(m,b[i]);
        }
        printf("%0.0lf %0.0lf %0.0lf %0.0lf\n",m*a[4]-a[0],m*a[5]-a[1],m*a[6]-a[2],m*a[7]-a[3]);
    }
    return 0;
}

SPOJ-FAVDICE

this a basic maths question
spoj link

solution follows

#include<bits/stdc++.h>
int min(int x,int y)
{
    return (x<y)?x:y;
}
int main()
{
    int t,n;
    scanf("%d",&t);
    double a[100005]={0};
    for(int i=1;i<=100000;i++)
        a[i]+=a[i-1]+(double)((double)1/i);
    while(t--)
    {
        scanf("%d",&n);
        printf("%0.2lf\n",n*a[n] );
    }
    return 0;
}

SPOJ-MISERMAN

hello friends this a new post on dp(dynamic programming)

its a rather a easy program... for novice look through the code and comment

#include<bits/stdc++.h>
int min(int x,int y)
{
    return (x<y)?x:y;
}
int main()
{
    int n,m,a[105][105]={0};
    scanf("%d %d",&n,&m);
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<=m+1;j++)
        {
            if(!j || j==m+1)
                a[i][j]=1000;
            else
                scanf("%d",&a[i][j]);
        }
    }
    for(int i=n-2;i>=0;i--)
    {
        for(int j=1;j<=m;j++)
            a[i][j]+=min(min(a[i+1][j-1],a[i+1][j]),a[i+1][j+1]);
    }
    int x=1000;
    for(int j=1;j<=m;j++)
        x=min(x,a[0][j]);
    printf("%d\n",x);
    return 0;
}

Thursday, 20 August 2015

SPOJ-FIBSUM

hello friends today i will teach how to find fibonacci in O(logn) time...

here the basis is find the fibonacci for n+1th element
and find the fibonacci for m+2th element.
and subtract the two to get the result..

possible bug
1)
use long long to store the values and then apply mod on it... because
suppose..
int x=4294967296(maximum value int can store!!!!)
int y=4294967296(maximum value int can store!!!!)
x=(x+y)%M
this will also show some value but THAT WILL BE GARBAGE .... because on adding u exceeded the limit then again tried to come back in the limit by doing mod...

2)
on subtracting it may happen the value becomes negative and u are applying mod on that so to prevent do this

long long x=(a-b+M)%M
this removes that error...

thats all read the program and comment if u cannot understand..

#include<bits/stdc++.h>
typedef long long ll;
#define M 1000000007
void mult(ll f[][2],ll m[][2])
{
    ll w=(f[0][0]*m[0][0]+f[0][1]*m[1][0])%M;
    ll x=(f[0][0]*m[0][1]+f[0][1]*m[1][1])%M;
    ll y=(f[1][0]*m[0][0]+f[1][1]*m[1][0])%M;
    ll z=(f[1][0]*m[0][1]+f[1][1]*m[1][1])%M;
    f[0][0]=w;
    f[0][1]=x;
    f[1][0]=y;
    f[1][1]=z;
}
void power(ll f[][2],ll n)
{
    ll m[2][2]={{1,1},{1,0}};
    if(n==0 || n==1)
        return;
    power(f,n/2);
    mult(f,f);
    if(n%2)
        mult(f,m);
}
void init(ll f[][2])
{
    f[0][0]=1;
    f[0][1]=1;
    f[1][0]=1;
    f[1][1]=0;
}
int main()
{
    int t,n,m;
    scanf("%d",&t);
    while(t--)
    {
        ll f[2][2],sum=0;
        init(f);
        scanf("%d %d",&n,&m);
        power(f,n);
        ll a=f[0][0];
        init(f);
        power(f,m+1);
        a=(f[0][0]-a+M)%M;
        printf("%lld\n",a);
    }
    return 0;
}

Friday, 7 August 2015

spoj-ABCDEF

SPOJ - ABCDEF

hi friends today i am going to share the solution for abcdef ... the question link is here.

this question can be solved by binary search....

for tutorial on binary search follow these links..

codechef tutorial

topcoder

now as per the formula : a*b+c = d*(f+e) where d cannot be zero

so now what we can do is take all possible calculated value for (a*b+c) and store and similarly for (d*(f+e)) and simply check which all values of group1 matches with group2....

and thus to search for the value of the group1 in group2 we use binary search to get the lower and upper range in group2 this tells us the number of same values in group2 and then just simply add those and u got ur answer...

here in my solution i have optimised it bit more suppose there are repeated values in group1 itself so why searching for same values again and again in group2 so searching the upper bound and storing the result,

now here i have used new functions upper_bound and lower_bound..

these two returns the address

for example: 10 10 10 20 20 30 30 30

lower_bound(on 20):address of 3rd 10

upper_bound(on 20):address of 5th 20

so here is the code ask for any doubt...

#include<bits/stdc++.h>
using namespace std;
std::vector<int> m;
std::vector<int> m1;
int main()
{
 int i,k,j,n,z=0,A[60000]={0};
 cin>>n;
 for(i=0;i<n;i++)
  cin>>A[i];
 for(i=0;i<n;i++)
 {
  for(j=0;j<n;j++)
  {
   for(k=0;k<n;k++)
   {
    z=A[i]*A[j]+A[k];
    m.push_back(z);
    if(A[k]!=0)
    {
     z=(A[i]+A[j])*A[k];
     m1.push_back(z);
    }
   }
  }
 }z=0;
 sort(m.begin(),m.end());
 sort(m1.begin(),m1.end());
 std::vector<int> ::iterator lo1,up1,it,lo,up;
 it=m.begin();
 while(it!=m.end())
 {
  up=upper_bound(m1.begin(),m1.end(),*it);
  lo=lower_bound(m1.begin(),m1.end(),*it);
  up1=upper_bound(m.begin(),m.end(),*it);
  lo1=lower_bound(m.begin(),m.end(),*it);
  z+=(up1-lo1)*(up-lo);
  it=up1;
 }
 printf("%d\n",z);
 return 0;
}

spoj-AIBOHPHOBIA

SPOJ- AIBOHPHOBIA

hello friends this is a solution of aibohphobia spoj link this queston is baisically on "dp" dynamic programming..

now how to solve this problem first of all :

suppose the string is "fftt"

now doing a bottom up approach:

making two dimensional array: first array will store for odd length substring second array even length string array .......

now we now single character is itself palindrome right!!

dp[0][]: 0 | 0 | 0 | 0 [dp[0 or 1][1] is the require answer think!!!]

1-1 2-2 3-3 4-4

dp[1][] 0 | 2 | 0 [2 more character will make "ft" pallindrome]

1-2 2-3 3-4

now starting the loop....

l: length of the substring

i: starting index

j: ending index

now :

#include<bits/stdc++.h>
int max(int a,int b)
{
 return(a>b)?a:b;
}
int min(int a,int b)
{
 return(a<b)?a:b;
}
int main()
{
 int n,t,k=0;
 scanf("%d",&t);
 char s[6105];
 while(t--)
 {
  k=0;
  int dp[2][6105]={0};
  scanf("%s",s+1);
  n=strlen(s+1);
  for(int i=1;i<n;i++)
   dp[1][i]=(s[i]!=s[i+1])?2:0;
  k=1;
  for(int l=2;l<n;l++)
  {
   k=(l&1)?1:0;//0 : single "1" and 1 is double "11"
   for(int i=1;i<n-l+1;i++)
   {
    int j=i+l;
    int x=0;
    if(s[i]==s[j])
     dp[k][i]=dp[k][i+1];
    else
     dp[k][i]=2+dp[k][i+1];
    x=min(1+dp[!k][i+1],1+dp[!k][i]);
    dp[k][i]=min(dp[k][i],x);
   }
  }
  printf("%d\n",dp[k][1]);
 }
 return 0;
}

hope this tutorial was helpful and comment any suggestion... thank you
have a nice day.... :)

code with chinmay.c