Introduction to competitive programming

Problem :

#include<bits/stdc++.h>
using namespace std;
class Solution 
{
 
	public:
    	bool isHappy(int n) 
	{
		map<int,int>a;
		while(a[n]!=1)
		{
			a[n]=1;
        		int sum=0,res=0;
			while(n)
			{
				res=n%10;
				sum+=(res*res);
				n/=10;
			}
			if(sum==1)
			return true;
			else
			{
				n=sum;
			}
		}
		return false;
    	}
};
int main()
{
	Solution s;	
	cout<<s.isHappy(19)<<endl;
	cout<<s.isHappy(301)<<endl;
}

Problem :

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define ll long long
#define rl(x) scanf("%lld",&x)
ll  a1[105];
ll  arr1[2000000];
int main()
{
 ll n,temp1=0,v,ans=0;
 rl(n);
 for(int i=0;i<n;i++)
 rl(a1[i]);
 for(int a=0;a<n;a++)
     if(a1[a])
            for(int b=0;b<n;b++)
        for(int c=0;c<n;c++)
           arr1[temp1++]=(a1[a]*(a1[b]+a1[c]));
        sort(arr1,arr1+temp1);
 for(int d=0;d<n;d++)
           for(int e=0;e<n;e++)
       for(int f=0;f<n;f++)
              {
    v=a1[d]*a1[e]+a1[f];
    ans+=(upper_bound(arr1,arr1+temp1,v))-(lower_bound(arr1,arr1+temp1,v));
              }
 cout<<ans<<endl;
 
} 
 

Problem :

#include<iostream>
using namespace std;
long long phi(long long n) 
{ 
 long  long result = n; 
        for(long  long i=2;i*i <= n;i++) 
        { 
  if (n%i==0) 
  result-=result/i; 
         while (n%i==0) 
  n/=i; 
        } 
        if (n>1) 
 result-=result/n; 
        return result; 
} 
int main()
{
 long long t,n;
 cin>>t; 
 while(t--)
 {
  cin>>n;
  cout<<phi(n)<<endl;
 }
} 

Problem :

#include<iostream>
using namespace std;
long long phi(long long n) 
{ 
	long  long result = n; 
        for(long  long i=2;i*i <= n;i++) 
        { 
		if (n%i==0) 
		result-=result/i; 
        	while (n%i==0) 
		n/=i; 
        } 
        if (n>1) 
	result-=result/n; 
        return result; 
} 
int main()
{
	long long t,n;
	cin>>t;	
	while(t--)
	{
		cin>>n;
		cout<<phi(n)<<endl;
	}
} 

Problem:

The problem is a simple application of BFS,even though the problem can be solved in different methods BFS is easy to implement>
The algorithm is to keep track of all the neighbouring vertices in a queue by checking the boundary cases and incrementing the corresponding distace.Whenever we find the destination point we return the distace at that point

Below code is the c++ implementation for the above problem

 
    #include<set>
    #include<map>
    #include<list>
    #include<stack>
    #include<queue>
    #include<cmath>
    #include<vector>
    #include<cstdio>
    #include<cctype>
    #include<deque>
    #include<bitset>
    #include<utility>
    #include<climits>
    #include<cstdlib>
    #include<cstring>
    #include<iomanip>
    #include<iostream>
    #include<algorithm>
    using namespace std;
    //#include<sai> tHe lAzY PrOgRmMeR :)
    #define rl(T) scanf("%lld",&T)
    #define ri(T) scanf("%d",&T)
    #define rs(T) scanf("%s",T)
    #define rc(T) scanf("%c",&T)
    #define loop(i,a,n) for(long long i=a;i<n;i++)
    #define loopn(i,a,n) for(long long i=1;i<=n;i++)
    #define ll long long
    int x[10]={0,-1,-1,-2,-2,2,2,1,1};
    int y[10]={0,-2,2,-1,1,-1,1,-2,2};
    using namespace std;
    int bfs(int a1,int b1,int a2,int b2)
    {
         int moves[9][9],vis[9][9],m,n;
         pair<int,int>p1;
         queue< pair<int,int> >q;
         p1.first=a1;
         p1.second=b1;
         q.push(p1);
         memset(moves,0,sizeof moves);
         memset(vis,0,sizeof vis);
         vis[a1][b1]=0;
         while(!q.empty())
         {
             p1=q.front();
             q.pop();
             if(p1.first==a2 && p1.second==b2)
             return moves[a2][b2];
             for(int i=1;i<=8;i++)
             {
                 m=p1.first+x[i],n=p1.second+y[i];
                 if(m>8 || m<1 || n>8 || n<1)
                 continue;
                 else
                 {
                     vis[m][n]=1;
                     moves[m][n]=moves[p1.first][p1.second]+1;
                     q.push(make_pair(m,n));
                 }
             }
         }
    }
    int main()
    {
       char a1,a2;
       ll b1,b2,t;
       rl(t);
       while(t--)
       {
          cin>>a1>>b1>>a2>>b2;
          cout<<bfs(a1-'a'+1,b1,a2-'a'+1,b2)<<endl;
       } 
    }