SPOJ PROBLEM 4: TRANSFORM THE EXPRESSION (ONP)

Realized the power of STL....

Solution:

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
    char a;
    stack<char> s;
    char arr[1001];
    cin>>arr;
    int len=strlen(arr);
    for(int i=0;i<len;i++)
    {
        if(arr[i]=='(')
             s.push(arr[i]);
        else if(arr[i]==')')
             {
                 while(s.top()!='(')
                 {
                     cout<<s.top();
                     s.pop();
                 }
                 s.pop();
            }
        else if(arr[i]=='+' || arr[i]=='-' ||arr[i]=='*' ||arr[i]=='/' ||arr[i]=='^' )
              s.push(arr[i]);
        else
            cout<<arr[i];  
            
    }
    cout<<endl;
    }
    return 0;
}

The problem would be made more difficult if expression wasn't in the RNP form 
like ((a^b+c)/(d/e))           RNP form: (((a^b)+c)/(d/e))

Code for that keeping my preference order as (+,-)->(*,/)  not considering ^:

#include<bits/stdc++.h>
using namespace std;
int main()
{
    char a;
    stack<char> s;
    char arr[1001];
    cin>>arr;
    int len=strlen(arr);
    for(int i=0;i<len;i++)
    {
        if(arr[i]=='(')
             s.push(arr[i]);
        else if(arr[i]==')')
             {
                 while(s.top()!='(')
                 {
                     cout<<s.top();
                     s.pop();
                 }
                 s.pop();
            }
          else if(arr[i]=='+' || arr[i]=='-')
                {
                   while(s.top()!='(')
                   {
                           if(s.top()=='*' || s.top()=='/'||s.top()=='+' || s.top()=='-')
                               {
                                   cout<<s.top();
                                   s.pop();
                               }
                           else
                               break;
                   }
                  s.push(arr[i]);
                 }
        else if(arr[i]=='*' || arr[i]=='/')
                {
                   while(s.top()!='(')
                   {
                           if(s.top()=='/' || s.top()=='*')
                               {
                                   cout<<s.top();
                                   s.pop();
                               }
                           else
                               break;
                   }
                  s.push(arr[i]);
                }
        else
            cout<<arr[i];  
            
    }
}

SPOJ PROBLEM 3885: COINS GAME (MCOINS)

Nice and easy dp problem!!!!!!

First memorize state for all n and then use it for further simulation.
consider boolen array of size as specified
Mark arr[0]=0
for any i ;
Now three conditions possible :
arr[i]=1       if arr[i-1]=0
arr[i]=1       if arr[i-K]=0          ===>>>> Use up these conditions to memorize your array
arr[i]=1       if arr[i-L]=0

These conditions is such that if boy loses on i-1/i-k/i-l position then he could win next up by sweeping up 1/k/l coins and will win the game.!!!

SOLUTION TO CODEOJ PROBLEM : ITS BIT GAME (AASF PC)

http://www.codeoj.com/problemshow.jsp?q=PRACTICEP28&c=PRACTICE

#include <bits/stdc++.h>
#define MAX 1001
using namespace std;

int main() {
    int t;
    cin>>t;
    while(t--)
    {

        int arr[MAX]={0};
 
        long long int n,x;
        cin>>n>>x;
        int i=0;
        while(n!=0)
        {
            arr[i]=n%2;
            n=n/2;
            i++;
        }
        int arr2[MAX];
        fill(arr2,arr2+1000,2);      //marked non flips with 2
        int len1=i;
        for(int j=0;j<len1;j++)
          {
            if(arr[j]==1)
                 arr2[j]=0;
          }
        int arr1[MAX]={0};
        i=0;
        while(x!=0)
        {
            arr1[i]=x%2;
            x=x/2;
            i++;
        }
        int len2=i;
        i=0;
        int y=0;
        while(y<len2)
        {
            if(arr2[i]==2)
               {  arr2[i]=arr1[y];   y++;  i++;  }
              else
                 i++;
        }
        for(int u=i;u<1000;u++)
        {
            if(arr2[u]==2)
                arr2[u]=0;
        }
        long long int res=0;
        for(int f=0;f<1000;f++)
        {
            res=res+(arr2[f]*pow(2,f));
        }
        cout<<res<<endl;
                
    }
    // your code goes here
    return 0;
}

SPOJ PROBLEM 18240: GENIE SEQUENCE (KURUK14)

Genie sequence defined in the problem statement of an value n would be like:
   n-1 , (1/n-2) , (2/n-3) , (3/n-4)................................, (1/n-2) , (2/n-3) , (3/n-4) ,n-1

 Note: / defines OR i.e. 1 or n-2

So, count of n-1=2
      count of n-2=2/0  for count=0    count of  1=2  ||  count of 1=1  & count of n-2=1
      and likewise for other elements in array.

check till (n-2)/2   it also being inclusive 
costed me an WA!!!!!!!

Check it out Easy Problem!!!!   

GCD Function>>>

Greatest common divisor of two numbers is highest number smaller than or equal to minimum of two numbers which divides both numbers.
Algo would be like:
 a,b<=10^5
          for(int i=1;i<=min(a,b);i++)
                 {     if((a%i==0)&& (b%i==0))
                                  gcd=i;   }

More optimized algo given by euclid algorithm:
a,b<=10^9
Recursive definition:
int gcd(int a,int b)
{
if(b==0)
     return a;
else
      gcd(b,a%b);
}

Even more optimized algo for very long numbers 
a,b<=10^200
Calling Function: gcd(a,mod(str,a));

int mod(char str[],int d)
{
    int r=0,i;
    for(i=0;str[i];i++)
    {
        r=10*r+(str[i]-'0');
        r=r%d;
    }
    return r;
}
int gcd(int a,int b)
{
    if(b==0)
        return a;
    else
        gcd(b,a%b);
}

So Any gcd could be find out using above mentioned algos according to situations


Findng out lcm using gcd function

lcm(a,b)*gcd(a,b)=a*b;