Numbers

#include<iostream>
using namespace std;
void swap(char*a,char*b){
  char c;
  c=*a;
  *a=*b;
  *b=c;
}
void permute(string s,int i,int n)
{
  if(i==n)
    cout<<s<<"\n";
  else{
    for(int j=i;j<s.length();j++){
      swap(s[i],s[j]);
      permute(s,i+1,n);
      swap(s[i],s[j]);
    }
  }
}
int main(){
  string s;
  cin>>s;
  permute(s,0,s.length());
  return 0;}

string

#include<iostream>
using namespace std;
void swap(char*a,char*b){
  char c;
  c=*a;
  *a=*b;
  *b=c;
}
void permute(string s,int i,int n)
{
  if(i==n)
    cout<<s<<"\n";
  else{
    for(int j=i;j<s.length();j++){
      swap(s[i],s[j]);
      permute(s,i+1,n);
      swap(s[i],s[j]);
    }
  }
}
int main(){
  string s;
  cin>>s;
  permute(s,0,s.length());
  return 0;}

Alphabets

#include <stdio.h>
#include <string.h>
void swap (char *x,char *y){
  char temp;
  temp=*x;
  *x=*y;
  *y=temp;
}
void permute(char *a,int i ,int n){
  int j;
  if (i==n)
    printf("%s\n",a);
  else{
    for(j=i ;j<=n;j++)
    {
      swap((a+i),(a+j));
      permute(a,i+1,n);
      swap((a+i),(a+j));
    }}}
int main(){
  char a[20];
  int n;
  scanf("%s",a);
  n=strlen(a);
  permute(a,0,n-1);
  getchar();
  return 0;
}

Possible paths

#include <iostream>
using namespace std;

int main() {
int t;
cin>>t;
while(t--){
    int n;
    cin>>n;
    int graph[n][n];
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            cin>>graph[i][j];
        }
    }
    int u,v,k;
    cin>>u>>v>>k;
    int count[n][n][k+1];
    for(int e=0;e<=k;e++){
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                count[i][j][e]=0;
                if(e==0&&i==j)
                    count[i][j][e]=1;
                if(e==1&&graph[i][j])
                    count[i][j][e]=1;
                if(e>1){
                    for(int a=0;a<n;a++){
                        if(graph[i][a])
                            count[i][j][e]+=count[a][j][e-1];
                    }
                }
            }
        }
    }
    cout<<count[u][v][k]<<endl;
}
return 0;
}

Knight Walk

#include <bits/stdc++.h>
using namespace std;
struct dist
{
    int x,y,d;
};
bool issafe(int x,int y,int n,int m)
{
    if(x>0 && x<=n && y>0 && y<=m)
    return true;
    return false;
}
void find(int s1,int s2,int d1,int d2,int n,int m)
{
    int visited[30][30];
    memset(visited,0,sizeof(visited));
    int i,j,x,y;
    struct dist p,z;
    p.x = s1;
    p.y = s2;
    p.d = 0;
    queue<struct dist>q;
    q.push(p);
    while(q.empty()==false)
    {
        p = q.front();
        //cout<<p.x<<" "<<p.y<<" ";
        q.pop();
        if(p.x==d1 && p.y==d2)
        {
            cout<<p.d<<endl;
            return;
        }
        int xMove[8] = {  2, 1, -1, -2, -2, -1,  1,  2 };
        int yMove[8] = {  1, 2,  2,  1, -1, -2, -2, -1 };
        for(i=0;i<8;i++)
        {
            x = p.x + xMove[i];
            y = p.y + yMove[i];
            if(issafe(x,y,n,m)==true && visited[x][y]==0)
            {
                z.x = x;
                z.y = y;
                z.d = p.d + 1;
                q.push(z);
                visited[x][y] = 1;
            }
        }
    }
    cout<<-1<<endl;
}
int main() {
    int t,i,j,n,m,s1,s2,d1,d2;
    cin>>t;
    while(t--)
    {
        cin>>n>>m;
        cin>>s1>>s2>>d1>>d2;
        find(s1,s2,d1,d2,n,m);
    }
return 0;
}

SUPER TWO LETTER STRINGS

#include<bits/stdc++.h>
using namespace std;
int main()
{
   long int i,j,dp[11][10001];
    for(i=1;i<=10;i++)
    {
        dp[i][0]=1;
        dp[i][1]=1;
        for(j=2;j<=10000;j++)
        {
            if(j>i)
               {
                 dp[i][j]=(2*dp[i][j-1]-dp[i][j-i-1]+1000000007)%1000000007;
               }
            else
              {
                  dp[i][j]=(2*dp[i][j-1])%1000000007;
              }
        }
    }
    int t,n,p;
    cin>>t;
    while(t--)
    {
        cin>>n>>p;
        cout<<dp[p][n]<<endl;
    }
}

Rectangular Land

#include <algorithm>
#include <bitset>
#include <cassert>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <iterator>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
using namespace std;


/* Prewritten code begins */
#define REP(i,n)    for(int i=0; i<(n); ++i)
#define FOR(i,a,b)  for(int i=(a); i<=(b); ++i)
/* Prewritten code ends */

const int maxN = 505;
string s[maxN];
int range[maxN][maxN];
int main() {
 int R, C, lastC, res = 0;
 cin >> R >> C;
 REP(r,R) cin >> s[r];
 REP(c,C) range[0][c] = s[0][c] == '.' ? 0 : maxN;
 FOR(r,1,R-1) REP(c,C) if(s[r][c] == '.') range[r][c] = min(range[r-1][c], r); else range[r][c] = maxN;
 REP(r1,R) FOR(r2,r1+1,R-1) {
  lastC = -1;
  REP(c,C) {
   if(s[r1][c] == '.' && s[r2][c] == '.') {
    if(range[r2][c] <= r1) {
     if(lastC != -1) res = max(res, 2*(r2-r1-1)+2*(c-lastC+1));
     else lastC = c;
    }
   } else {
    lastC = -1;
   }
  }
 }
 if(res == 0) cout << "impossible" << endl;
 else cout << res << endl;
 return 0;
}

Minimum number

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

int findSolution(vector<int> &ratings)
{
    int size = ratings.size();
    if(size==0)
        return 0;

    vector<int> leftToRight(size);
    vector<int> rightToLeft(size);
    int sum;

    leftToRight[0] = 1;
    for(int i=1;i<size;i++)
    {
        if(ratings[i]>ratings[i-1])
            leftToRight[i] = leftToRight[i-1]+1;

        else
            leftToRight[i] = 1;
    }

    sum=leftToRight[size-1];
    rightToLeft[size-1] = 1;

    for(int i=size-2;i>=0;i--)
    {
        if(ratings[i]>ratings[i+1])
            rightToLeft[i] = rightToLeft[i+1]+1;

        else
            rightToLeft[i] = 1;

        sum+=(leftToRight[i]>rightToLeft[i]?leftToRight[i]:rightToLeft[i]);
    }

    return sum;
}

int main()
{
    int n,i;
    cout<<"";
    cin>>n;

    vector<int> a(n);
    cout<<""<<endl;
    for(i=0;i<n;i++)
    {
        cin>>a[i];
    }

    cout<<""<<endl;
    cout<<findSolution(a)<<endl;

    return 0;
}

MAGICAL WORDS

#include <iostream>
using namespace std;
bool ispalindrome(string input)
{
    if( input == string(input.rbegin(), input.rend()))
    {
        return true;
    }
    else
    {
        return false;
    }
}
int counts(string s)
{
    int tot = 0;
    string temp;
    int n = s.length();
    for(int i = 0; i < n; i++)
    {
        for(int j = 1; j <= n - i; j++)
        {
            temp = s.substr(i,j);
            if(ispalindrome(temp))
            {
                tot += temp.length()*temp.length();
            }
        }
    }   
    return tot;
}
int main()
{
    string s;
    int t;
    cin >> t;
    while(t-- && t <= 100)
    {
        cin >> s;
        if(s.length() >= 1 && s.length() <= 1000)
        cout << counts(s)<<endl;
    }
    return 0;
}

LET'S BEGIN!

#include<iostream>

using namespace std;

#define MAX 1000005

int ans[MAX], count=0;

int solve(int X)
{
    //cout<<X<<endl;
    count++;
    if(ans[X]!=0){
        return ans[X];
    }


    int i, j, result=10*MAX, minResult = 10*MAX;
    if(X<2){
        return MAX*10;
    }

    result = solve(X-7) + 1;
    if(minResult > result){
        minResult = result;
    }
    result = solve(X-5) + 1;
    if(minResult > result){
        minResult = result;
    }
    result = solve(X-3) + 1;
    if(minResult > result){
        minResult = result;
    }
    result = solve(X-2) + 1;
    if(minResult > result){
        minResult = result;
    }

    ans[X] = minResult;
    //cout<<count<<" "<<X<<" = "<<ans[X]<<endl;
    return ans[X];

}

int main()
{
    int T;
    ans[2] = ans[3] = ans[5] = ans[7] = 1;
    cin>>T;
    while(T--)
    {
        int X, minstep=MAX*10;
        cin>>X;
        minstep = solve(X);

        if(minstep ==10*MAX )
            minstep=-1;
        cout<<minstep<<endl;
        //cout<<count<<endl;

    }
}

THE MAXIMUM SUB ARRAY

#include<bits/stdc++.h>

using namespace std;

int main()

{

    int t,n,i,j,k;

    cin>>t;

    while(t--)

    {

        cin>>n;

        int a[n];

        int sum=0;

        for(i=0;i<n;i++)

        {

            cin>>a[i];

            if(a[i]>0)

            sum+=a[i];

        }

        j=0;

        k=0;

        for(i=0;i<n;i++)

        {

            j+=a[i];

            if(j<0)

            j=0;

            k=max(k,j);

        }

        if(k==0&&sum==0)

        {

            sum=INT_MIN;

            for(i=0;i<n;i++)

            sum=max(sum,a[i]);

            k=sum;

        }

        cout<<k<<" "<<sum<<"\n";

    }

}

The colorful street

#include <iostream>

#include<bits/stdc++.h>

using namespace std;

int main() {

int num;

cin >> num;

while(num--){

    int n;

    cin>>n;

   vector<int> a(n,0);

       vector<int> b(n,0);

           vector<int> c(n,0);

   for(int i=0;i<n;i++){

     cin>>a[i]>>b[i]>>c[i];

   

}

    vector<vector<int>>dp (3,vector<int>(n,0));

    dp[0][0]=a[0];

    dp[1][0]=b[0];

    dp[2][0]=c[0];

    

    for(int i=1;i<n;i++){

        dp[0][i]=a[i]+min(dp[1][i-1],dp[2][i-1]);

               dp[1][i]=b[i]+min(dp[0][i-1],dp[2][i-1]);

                      dp[2][i]=c[i]+min(dp[1][i-1],dp[0][i-1]);

        

        

    }

    cout<<min(dp[0][n-1],min(dp[1][n-1],dp[2][n-1]))<<endl;

    

}

}

STUDIOUS LITTLE JHOOL

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int t,i,j,k,n;
    cin>>t;
    while(t--)
    {
        cin>>n;
        j=n;
        k=0;
        if(j%2!=0)
        {
            cout<<"-1\n";
            continue;
        }
        while(j>0)
        {
            if(j%12==0)
            {
                k+=j/12;
                break;
            }
            if(j%10==0)
            {
                if((j>=60)&&(j-60)%10==0)
                {
                    j=j-60;
                    k+=5;
                }
                k+=j/10;
                break;
            }
            j=j-12;
            k++;
        }
        if(j<0)
        cout<<"-1\n";
        else
        cout<<k<<"\n";
    }
}

CHOOSING THE JUDGES

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int t;
    cin>>t;
    int p=t;
    while(t--)
    {
        int n;
        cin>>n;
        long long  int a[n+1];
        long long int dp[n+1];
        for(int i=0;i<n;i++)
        {
            cin>>a[i];
        }
        dp[0]=a[0];
        dp[1]=max(a[0],a[1]);
        for(int i=2;i<n;i++)
        {
           
           
            dp[i]=max(dp[i-1],dp[i-2]+a[i]);
           
        }
        cout<<"Case "<<p-t<<": "<<dp[n-1]<<endl;
       
    }
}

MARK & TOYS

MARK & TOYS

#define _CRT_SECURE_NO_DEPRECATE
#include<sstream>
#include<iostream>
#include<numeric>
#include<sstream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<memory>
#include<string>
#include<vector>
#include<cctype>
#include<list>
#include<queue>
#include<deque>
#include<stack>
#include<map>
#include<complex>
#include<set>
#include<algorithm>

using namespace std;

typedef unsigned long long      ui64;
typedef long long               i64;
typedef vector<int>             VI;
typedef vector<bool>            VB;
typedef vector<VI>              VVI;
typedef vector<string>          VS;
typedef pair<int,int>           PII;
typedef map<string,int>         MSI;
typedef set<int>                SI;
typedef set<string>             SS;
typedef complex<double>         CD;
typedef vector< CD >            VCD;
typedef map<int,int>            MII;
typedef pair<double,double>     PDD;

#define PB                      push_back
#define MP                      make_pair
#define X                       first
#define Y                       second
#define FOR(i, a, b)            for(int i = (a); i < (b); ++i)
#define RFOR(i, a, b)           for(int i = (a) - 1; i >= (b); --i)
#define CLEAR(a, b)             memset(a, b, sizeof(a))
#define SZ(a)                   int((a).size())
#define ALL(a)                  (a).begin(), (a).end()
#define RALL(a)                 (a).rbegin(), (a).rend()
#define INF                     (2000000000)

#ifdef _DEBUG
#define eprintf(...) fprintf (stderr, __VA_ARGS__)
#else
#define eprintf(...) assert (true)
#endif

const double PI = acos(-1.0);

int main() {
 int n,k;
 scanf("%d%d",&n,&k);
 VI a(n);
 FOR(i,0,n) {
  scanf("%d",&a[i]);
 }
 
 sort(ALL(a));
 FOR(i,0,n) {
  k -= a[i];
  if(k<0) {
   cout << i << endl;
   return 0;
  }
 }
 cout << n << endl;
 return 0;
}

HUNGER GAMES

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int N,ans=0,a;
    vector<int>v;
    cin>>N;
    for(int i=0;i<N;i++)
    {
        cin>>a;
        v.push_back(a);
    }
    sort(v.begin(),v.end());
    for(int i=0;i<N-2;i++)
    {
        ans=max(ans,v[i+2]-v[i]);
    }
    cout<<ans;
}

SHERLOCK AND THE BEAST

#include <string>
#include <vector>
#include <map>
#include <list>
#include <iterator>
#include <set>
#include <queue>
#include <iostream>
#include <sstream>
#include <stack>
#include <deque>
#include <cmath>
#include <memory.h>
#include <cstdlib>
#include <cstdio>
#include <cctype>
#include <algorithm>
#include <utility> 
using namespace std;
 
#define FOR(i, a, b) for(int i = (a); i < (b); ++i)
#define RFOR(i, b, a) for(int i = (b) - 1; i >= (a); --i)
#define REP(i, N) FOR(i, 0, N)
#define RREP(i, N) RFOR(i, N, 0)
 
#define ALL(V) V.begin(), V.end()
#define SZ(V) (int)V.size()
#define PB push_back
#define MP make_pair
#define Pi 3.14159265358979

typedef long long Int;
typedef unsigned long long UInt;
typedef vector <int> VI;
typedef pair <int, int> PII;



int main()
{
  
 int T;
 cin>>T;
 REP(tests,T)
 {
  int n;
  cin>>n;
  
  int res = -1;
  
  for (int i = 0; i <= n; ++i)
  {
   if (i % 5 == 0)
   {
    int j = n - i;
    
    if (j % 3 == 0)
    {
     res = i;
     break;
    }
   }
  }
  
  if (res == -1)
  {
   cout << -1 << endl;
   continue;
  }
  
  REP(i,n-res)
   putchar('5');
  REP(i,res)
   putchar('3');
  puts("");
 }

 
 return 0;
}

The Enlightened Ones

#include <bits/stdc++.h>
using namespace std;
int ok(int mid, int* pos, int K, int N)
{
 int i;
 int pr_ra=pos[0]+2*mid;
 for (i=1;i<N;i++)
 {
  
  if(pr_ra>=pos[i])
   continue;
  else
  {
   pr_ra=pos[i]+2*mid;
   K--;
  }
  if(!K)
   return 0;
 }
 return 1;
}
int main()
{
 int N, K;
 cin>>N>>K;
 int* pos=new int[N];
 int i;
 for(i=0;i<N;i++)
  cin>>pos[i];
 sort(pos,pos+N);
 int hi=10000000;
 int lo=0;
 int mid;
 while(lo<=hi)
 {
  mid=(lo+hi)/2;
  if(ok(mid,pos,K, N))
  {
   if(!ok(mid-1,pos,K, N))
   {
    break;
   }
   else
    hi=mid-1;
  }
  else
  {
   lo=mid+1;
  }
 }
 cout<<mid<<"\n";
 return 0;
}

Missing Soldiers

#include <bits/stdc++.h>
using namespace std;
#define LL long long int
vector<pair<int, int>> ev;
bool compare(pair<int, int> a, pair<int, int> b) {
    if (a.first != b.first) return a.first < b.first;
    return a.second < b.second;
}
int main() {
    int n, i;
    cin >> n;
    for (i=0;i<n;i++) {
        int x, y, d;
        cin >> x >> y >> d;
        ev.push_back({x, x+d});
    }
    sort(ev.begin(), ev.end(), compare);
    LL op = 0, cl = -1, ans = 0;
    for (auto it : ev) {
        if (cl < it.first) {
            ans += cl - op + 1;
            op = it.first;
            cl = it.second;
        } else cl = max(cl, it.second * 1LL);
    }
    ans += cl - op + 1;
    cout << ans << '\n';
    return 0;
}

Bishu and Soldiers

#include <bits/stdc++.h>
using namespace std;
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n,i;
    cin>>n;
    vector<int>v(n);
    for(i=0;i<n;i++)
    cin>>v[i];
    sort(v.begin(),v.end());
    int q;
    cin>>q;
    while(q--)
    {
        int p,sum=0,j=0;
      cin>>p;
      for(i=0;i<n;i++)
      {
          if(v[i]>p)
          break;
          sum+=v[i];
          j++;
        }  
        cout<<j<<" "<<sum<<"\n";
    }
    return 0;
}

Match makers

#include <iostream>
#include <algorithm>
 
using namespace std;
 
int main() {
 int n,t;
 cin >> t;          // Reading input from STDIN
 while(t--){
     cin>>n;
     int gl[n],b[n];
     for(int i=0;i<n;i++){
         cin>>gl[i];
     }
     for(int i=0;i<n;i++){
         cin>>b[i];
     }
     sort(gl,gl+n);
     sort(b,b+n);
     int j=n-1,c=0;
     for(int i=0;i<n;i++){
         if(gl[i]% b[j] ==0 || b[j]% gl[i] == 0){
             c++;
         }
        j = j-1; 
     }
     cout<<c<<endl;}
  return 0;  }

Counting Triangles

#include<iostream>
#include<bits/stdc++.h>
#include<map>
using namespace std;
main()
{
long long n,count=0;
cin>>n;
array<long long , 3> val;
map<array<long long , 3>,long long> cnt;
while(n--)
{
cin>>val[0]>>val[1]>>val[2];
sort(val.begin(),val.end());
cnt[val]++;
}
for(auto i=cnt.begin();i!=cnt.end();++i)
{
if(i->second==1)
count++;
}
cout<<count<<endl;
}

Strassen Algorithm

#include <iostream>
using namespace std;
int main()
{
int avi[50][50],b[50][50],c,d,i,size,k,p[50][50],sum=0;
  
  cin>>size;
  
  for(c=0;c<size;c++ ) 
  { 
    for(d=0;d<size;d++) 
    { 
      cin>>avi[c][d];
    } 
  } 
   for(c=0;c<size;c++ ) 
  { 
    for(d=0;d<size;d++) 
    { 
      cin>>b[c][d];
    } 
  } 
   for(c=0;c<size;c++ ) 
  { 
    for(d=0;d<size;d++) //00*00+ 01*10 , 00*01 + 01*11
    { 
      for(k=0;k<size;k++) 
      { 
       sum=sum+avi[c][k]*b[k][d];
        }
      p[c][d]=sum;
      sum=0;
    } 
  } 
     for(c=0;c<size;c++ ) 
  { 
    for(d=0;d<size;d++) 
    { 
      cout<<p[c][d]<<" ";
    } cout<<endl;
  } 
 return 0;
}

Sort me this way !

#include <stdio.h>
int main()
{
int avi,b[10],i,j,tem,o,d[10],c=0;
  o=0;
  scanf("%d",&avi);
  for(i=0;i<avi;i++) { 
    scanf("%d",&b[i]);
  }  for(i=0;i<avi;i++) 
    { 
      if(b[i]<0) { d[o]=b[i]; b[i]=b[i]-d[o]*2;o++;c++;}
  }
    for(i=0;i<avi;i++) 
    { 
  for(j=i+1;j<avi;j++)
  { 
    
if(b[i]>b[j]) 
{ 
  tem=b[j];
  b[j]=b[i];
  b[i]=tem;
} 
  } 
    } 
    for(i=0;i<avi;i++) {
      for(j=0;j<c;j++) { 
      if(b[i]+d[j]==0) 
    { 
      b[i]=d[j];
    } 
    } 
    }
    for(i=0;i<avi;i++) { 
        
      printf("%d ",b[i]);
    } 

  
 return 0;
}