UVA 571 Jugs

///...................SUBHASHIS MOLLICK...................///
///.....DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING....///
///.............ISLAMIC UNIVERSITY,BANGLADESH.............///
///....................SESSION-(14-15)....................///
#include<bits/stdc++.h>
using namespace std;
#define sf(a) scanf("%lld",&a)
#define sf2(a,b) scanf("%lld %lld",&a,&b)
#define sf3(a,b,c) scanf("%lld %lld %lld",&a,&b,&c)
#define pf(a) printf("%lld",a)
#define pf2(a,b) printf("%lld %lld",a,b)
#define pf3(a,b,c) printf("%lld %lld %lld",a,b,c)
#define nl printf("\n")
#define   timesave              ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define ll long long
#define pb push_back
#define MPI map<int,int>mp;
#define fr(i,n) for(i=0;i<n;i++)
#define fr1(i,n) for(i=1;i<=n;i++)
#define frl(i,a,b) for(i=a;i<=b;i++)
/*primes in range 1 - n
1 - 100(1e2) -> 25 pimes
1 - 1000(1e3) -> 168 primes
1 - 10000(1e4) -> 1229 primes
1 - 100000(1e5) -> 9592 primes
1 - 1000000(1e6) -> 78498 primes
1 - 10000000(1e7) -> 664579 primes
large primes ->
104729 1299709 15485863 179424673 2147483647 32416190071 112272535095293 48112959837082048697
*/
//freopen("Input.txt","r",stdin);
//freopen("Output.txt","w",stdout);
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
long pre[1005][1005][4],vis[1005][1005];
struct NODE
{
    long a,b;
};
NODE node,node1;
queue<NODE>q;
long ca,cb,n,k;
void call(long num)
{
    if(vis[node1.a][node1.b]==0)
    {
        vis[node1.a][node1.b]=1;
        pre[node1.a][node1.b][0]=num;
        pre[node1.a][node1.b][1]=node.a;
        pre[node1.a][node1.b][2]=node.b;
        q.push(node1);
    }
}
void print(long aa,long bb)
{
    if(aa==0&&bb==0)
        return;
    print(pre[aa][bb][1],pre[aa][bb][2]);
    k=pre[aa][bb][0];
    if(k==1)
    {
        cout<<"fill A"<<endl;
    }
    else if(k==2)
    {
        cout<<"fill B"<<endl;
    }
    else if(k==3)
    {
        cout<<"empty A"<<endl;
    }
    else if(k==4)
    {
        cout<<"empty B"<<endl;
    }
    else if(k==5)
    {
        cout<<"pour A B"<<endl;
    }
    else if(k==6)
    {
        cout<<"pour B A"<<endl;
    }
}
main()
{
    timesave;
    while(cin>>ca>>cb>>n)
    {
        memset(vis,0,sizeof(vis));
        node.a=0;
        node.b=0;
        vis[0][0]=1;
        q.push(node);
        while(!q.empty())
        {
            node=q.front();
            q.pop();
            if(node.b==n)
                break;
            node1.a=ca;
            node1.b=node.b;
            call(1);
            node1.a=node.a;
            node1.b=cb;
            call(2);
            node1.a=0;
            node1.b=node.b;
            call(3);
            node1.a=node.a;
            node1.b=0;
            call(4);
            k=min(cb-node.b,node.a);
            node1.a=node.a-k;
            node1.b=node.b+k;
            call(5);
            k=min(ca-node.a,node.b);
            node1.a=node.a+k;
            node1.b=node.b-k;
            call(6);
        }
        print(node.a,node.b);
        cout<<"success"<<endl;
        while(!q.empty())
            q.pop();
    }
}

Maximum length of the longest street in the city by using BFS

How to find maximum  length of the longest street in the city by using BFS

Problem link:  https://www.spoj.com/problems/BENEFACT/

Input:
1
6
1 2 3
2 3 4
2 6 2
6 4 6
6 5 5

Output:
12

Explanation:
6+2+4=12
At first start bfs from 1 and find the longest city from 1
And again start with bfs from this longest city and find the longest length
So we need two bfs search.

1st Code:

///...................SUBHASHIS MOLLICK...................///
///.....DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING....///
///.............ISLAMIC UNIVERSITY,BANGLADESH.............///
///....................SESSION-(14-15)....................///
#include<bits/stdc++.h>
using namespace std;
#define sf(a) scanf("%lld",&a)
#define sf2(a,b) scanf("lld%lld",&a,&b)
#define sf3(a,b,c) scanf("lld%lld%lld",&a,&b,&c)
#define pf(a) printf("%lld",a)
#define pf2(a,b) printf("lld%lld",a,b)
#define pf3(a,b,c) printf("lld%lld%lld",a,b,c)
#define nl printf("\n")
#define ll long long
#define pb push_back
#define MPI map<int,int>mp
#define fr(i,n) for(i=0;i<n;i++)
#define fr1(i,n) for(i=1;i<=n;i++)
#define frl(i,a,b) for(i=a;i<=b;i++)
//freopen("Input.txt","r",stdin);
//freopen("Output.txt","w",stdout);
vector<long>vec[50005],cost[50005];
long vis[50005];
long bfs(long source)
{
    queue<long>q;
    memset(vis,0,sizeof(vis));
    long dist[50005]= {0},boroman=0,mx=0;
    dist[source]=0;
    vis[50005]=1;
    q.push(source);
    long i;
    while(!q.empty())
    {
        long u=q.front();
        if(mx<dist[u])
        {
            mx=dist[u];
            boroman=u;
        }
        for(i=0; i<vec[u].size(); i++)
        {
            long v=vec[u][i];
            if(vis[v]==0)
            {
                dist[v]=dist[u]+cost[u][i];
                vis[v]=1;
                q.push(v);
            }
        }
        q.pop();
    }
    return boroman;
}
long bfss(long source)
{
    memset(vis,0,sizeof(vis));
    queue<long>q;
    long dist[50005]= {0},i,mx=0;
    q.push(source);
    vis[source]=1;
    dist[source]=0;
    while(!q.empty())
    {
        long u=q.front();
        vis[u]=1;
        if(mx<dist[u])
        {
            mx=dist[u];
        }
        for(i=0; i<vec[u].size(); i++)
        {
            long v=vec[u][i];
            if(vis[v]==0)
            {
                dist[v]=dist[u]+cost[u][i];
                // mx=max(mx,dist[v]);
                vis[v]=1;
                q.push(v);
            }
        }
        q.pop();
    }
    return mx;
}
main()
{
    long ts;
    cin>>ts;
    while(ts--)
    {
        long n,u,v,d,i;
        cin>>n;
        for(i=1; i<n; i++)
        {
            cin>>u>>v>>d;
            vec[u].push_back(v);
            vec[v].push_back(u);
            cost[u].push_back(d);
            cost[v].push_back(d);
        }
        long boro=bfs(1);
        cout<<bfss(boro)<<endl;
        for(i=0; i<=50005; i++)
        {
            vec[i].clear();
            cost[i].clear();
            vis[i]=0;
        }
    }

}

2nd Code:

#include<iostream>
#include<string>
#include<cmath>
#include<algorithm>
#include<vector>
#include<map>
#include<stack>
#include<cctype>
#include<cmath>
#include<cstring>
#include<queue>
#include<cstdio>
#include<sstream>
using namespace std;
#define pb push_back
#define pi 3.141592653589793238462643383

int dist[50001];
int visited[50001];
int n;
struct node
{
    int i,d;
};
typedef struct node node;
vector<node> v[50001];
int bfs(int start){
    queue<int> q;
    q.push(start);
    int i,j;
    for(i=0;i<=n;i++){
        visited[i]=0;
        dist[i]=0;
    }
    visited[start]=1;
    while(!q.empty()){
        int temp = q.front();
        q.pop();
        for(i=0;i<v[temp].size();i++){
            if(visited[v[temp][i].i]==0){
                visited[v[temp][i].i]=1;
                dist[v[temp][i].i]+=dist[temp]+v[temp][i].d;
                q.push(v[temp][i].i);
            }
        }
    }
    return int(max_element(dist+1,dist+n+1)-dist);
}
int main()
{
 int i,j,t,u1,v1,d;
 node temp;
 scanf("%d",&t);
 while(t>0){
        scanf("%d",&n);
        for(i=1;i<=n;i++)
            v[i].clear();
        for(i=1;i<=n-1;i++){
                scanf("%d%d%d",&u1,&v1,&d);
                temp.i =  v1;
                temp.d = d;
                v[u1].pb(temp);
                temp.i = u1;
                v[v1].pb(temp);
        }
        int start = bfs(1);
        cout<<start<<endl;
        int ans = bfs(start);
        printf("%d\n",dist[ans]);
        t--;
    }
}

UVA 11988 - Broken Keyboard

#include <cstdio>
#include <list>
#include <cstring>
using namespace std;
int main()
{
    char line[100001];
    while (scanf("%s", line) != EOF)
    {
        list<char> l;
        int len = strlen(line);
        list<char>::iterator it = l.begin();
        for (int i = 0; i < len; i++)
        {
            if (line[i] == '[')
            {
                it = l.begin();
            }
            else if (line[i] == ']')
            {
                it = l.end();
            }
            else
            {
                l.insert(it, line[i]);
            }   
        }
        for (it = l.begin(); it != l.end(); it++)
        {
            printf("%c", *it);
        }
        printf("\n");
    }
    return 0;
}

Find the number of continuous sequence of numbers such that their sum is zero.

Find the number of continuous sequence of numbers such that their sum is zero.

For example if the sequence is- 5, 2, -2, 5, -5, 9

There are 3 such sequences

2, -2= (2+-2)=0

5, -5=(5+-5)=0

2, -2, 5, -5=(2+-2+5+-5)=0

so ans is 3;

Problem link:   https://www.spoj.com/problems/CRAN02/\

Hints:

At first we need to comulative sum of the array then sort the sum array and find a pair of same digit.then calculate n*(n+1)/2 and add with result;

Example: 5,2,-2,5,-5,9

Commulative sum array={5,7,5,10,5,14} and add 0 in position 0

So the array is={0,5,7,5,10,5,14} now sort the array.

So the array is={0,5,5,5,7,10,14}

the find pair of same digit 1st pair is 5,5 and 2nd is 5,5 so 2 pairs and (2*(2+1))/2; so the result is (2*3)/2=3

Source Code:

#include<stdio.h>

#include<stdlib.h>

#include<algorithm>

#include<bits/stdc++.h>

using namespace std;

unsigned long long int a[10000100]= {0},b[10000100]= {0},c[10000100]= {0};

int main()

{

    unsigned long long int i,j,k,l=0,n,m,sum=0,r,sum1=0,p,t;

    scanf("%llu",&n);

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

    {

        scanf("%llu",&m);

        sum=0;

        sum1=0;

        for(j=0; j<m; j++)

        {

            scanf("%llu",&a[j]);

            sum=sum+a[j];

            b[j+1]=sum;

        }

        sort(b,b+m+1);

        l=0;

        for(p=0; p<m; p++)

        {

            if(b[p]==b[p+1])

            {

                c[l]++;

            }

            else

            {

                l++;

            }

        }

        for(r=0; r<=l; r++)

        {

            sum1=sum1+(c[r]*(c[r]+1)/2);

        }

        memset(c,0,sizeof(c));

        printf("%llu\n",sum1);

    }

    return 0;

}

Big numbers multiplication mod by big number (10000000000007)

#include<bits/stdc++.h>
#define clr(x)      memset(x,0,sizeof(x))
#define fr(i,x)     for(long long i=0;i<x;i++)
#define ll          long long
#define pi          3.14159265358979323846
using namespace std;

long long bigmul ( long long a, long long b, long long c ) {
    if ( b == 0 ) return 0;
    if ( b & 1 ) {
        return ( a + bigmul ( a, b - 1, c ) ) % c;
    }
    else {
        return ( 2 * bigmul ( a, b / 2, c ) ) % c;
    }
}

int main()
{
    ll a,b;
    ll m=10000000000007;
    while(cin>>a>>b)
    {
        ll x1=bigmul(a,b,m);
        cout<<"X = "<<x1<<endl;
    }
    return 0;
}

UVA 12748 - Wifi Access

///...................SUBHASHIS MOLLICK...................///
///.....DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING....///
///.............ISLAMIC UNIVERSITY,BANGLADESH.............///
///....................SESSION-(14-15)....................///
#include<bits/stdc++.h>
using namespace std;
#define sf(a) scanf("%lld",&a)
#define sf2(a,b) scanf("%lld %lld",&a,&b)
#define sf3(a,b,c) scanf("%lld %lld %lld",&a,&b,&c)
#define pf(a) printf("%lld",a)
#define pf2(a,b) printf("%lld %lld",a,b)
#define pf3(a,b,c) printf("%lld %lld %lld",a,b,c)
#define nl printf("\n")
#define   timesave              ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define ll long long
#define pb push_back
#define MPI map<int,int>mp;
#define fr(i,n) for(i=0;i<n;i++)
#define fr1(i,n) for(i=1;i<=n;i++)
#define frl(i,a,b) for(i=a;i<=b;i++)
/*primes in range 1 - n
1 - 100(1e2) -> 25 pimes
1 - 1000(1e3) -> 168 primes
1 - 10000(1e4) -> 1229 primes
1 - 100000(1e5) -> 9592 primes
1 - 1000000(1e6) -> 78498 primes
1 - 10000000(1e7) -> 664579 primes
large primes ->
104729 1299709 15485863 179424673 2147483647 32416190071 112272535095293 48112959837082048697
*/
//freopen("Input.txt","r",stdin);
//freopen("Output.txt","w",stdout);
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
int main()
{
    int t;
    scanf("%d",&t);
    int I=1;
    int n,y;
    float x,Y,dis;
    while(t--)
    {
        printf("Case %d:\n",I++);
        scanf("%d%d",&n,&y);
        float xx[n],yy[n],rr[n];
        for(int i=0; i<n; i++)
        {
            scanf("%f%f%f",&xx[i],&yy[i],&rr[i]);
        }
        for(int i=0; i<y; i++)
        {
            scanf("%f%f",&x,&Y);
            long flag=0;
            for(int k=0; k<n; k++)
            {
                dis=sqrt(((x - xx[k])*(x - xx[k]))+((Y - yy[k])*(Y - yy[k])));
                if(dis<=rr[k])
                {
                    flag=1;
                    break;
                }
            }
            if(flag)
                printf("Yes\n");
            else
                printf("No\n");
        }
    }
    return 0;
}

UVA 531 - Compromise

PROBLEM TOPICS: LCS_LENGTH & PATH PRINT

#include <iostream>
#include <cstdio>
#include <sstream>
#include <string>
#include <vector>
#define MX 210
using namespace std;

int dp[MX][MX], s[MX][MX];
vector<string> v1, v2;
int m, n;
int flag;
void lcsprint(int i, int j)
{
    if(i == 0 || j == 0)
        return;
    if(s[i][j] == 1)
    {
        lcsprint(i-1, j-1);
        if(flag == 0)
            cout << v1[i-1];
        else
            cout <<" " << v1[i-1];
        flag = 1;
    }
    else if(s[i][j] == 2)
    {
        lcsprint(i-1, j);
    }
    else
        lcsprint(i, j-1);
}


void LCSLength()
{
    int i, j;

    for (i = 0; i <= m; ++i)
        dp[i][0] = 0;

    for (j = 0; j <= n; ++j)
        dp[0][j] = 0;

    for (i = 1; i <= m; ++i)
    {
        for (j = 1; j <= n; ++j)
        {
            if (v1[i-1] == v2[j-1])
            {
                dp[i][j] = dp[i-1][j-1] + 1;
                s[i][j] = 1;
            }
            else if (dp[i-1][j] >= dp[i][j-1])
            {
                dp[i][j] = dp[i-1][j];
                s[i][j] = 2;
            }
            else
            {
                dp[i][j] = dp[i][j-1];
                s[i][j] = 3;
            }
        }
    }
    lcsprint(m, n);
    return;
}


int main()
{
    string s1, s2;

    while(getline(cin, s1))
    {
        // strcpy(a[length1++],temp);
        v1.clear();
        v2.clear();
        istringstream is(s1);
        while(is>>s2)
            v1.push_back(s2);
        while(getline(cin, s1))
        {
            if(s1 == "#")
                break;
            istringstream is(s1);
            while(is>>s2)
                v1.push_back(s2);
        }
        while(getline(cin, s1))
        {
            if(s1 == "#")
                break;
            istringstream is(s1);
            while(is>>s2)
                v2.push_back(s2);
        }
        flag = 0;
        m = v1.size();
        n = v2.size();
        LCSLength();
        printf("\n");
    }
    return 0;
}

UVA 10285 - Longest Run on a Snowboard

///...................SUBHASHIS MOLLICK...................///
///.....DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING....///
///.............ISLAMIC UNIVERSITY,BANGLADESH.............///
///....................SESSION-(14-15)....................///
#include<bits/stdc++.h>
using namespace std;
#define sf(a) scanf("%lld",&a)
#define sf2(a,b) scanf("%lld %lld",&a,&b)
#define sf3(a,b,c) scanf("%lld %lld %lld",&a,&b,&c)
#define pf(a) printf("%lld",a)
#define pf2(a,b) printf("%lld %lld",a,b)
#define pf3(a,b,c) printf("%lld %lld %lld",a,b,c)
#define nl printf("\n")
#define   timesave              ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define ll long long
#define pb push_back
#define MPI map<int,int>mp;
#define fr(i,n) for(i=0;i<n;i++)
#define fr1(i,n) for(i=1;i<=n;i++)
#define frl(i,a,b) for(i=a;i<=b;i++)
/*primes in range 1 - n
1 - 100(1e2) -> 25 pimes
1 - 1000(1e3) -> 168 primes
1 - 10000(1e4) -> 1229 primes
1 - 100000(1e5) -> 9592 primes
1 - 1000000(1e6) -> 78498 primes
1 - 10000000(1e7) -> 664579 primes
large primes ->
104729 1299709 15485863 179424673 2147483647 32416190071 112272535095293 48112959837082048697
*/
//freopen("Input.txt","r",stdin);
//freopen("Output.txt","w",stdout);
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
long dp[105][105],ar[105][105],r,c;
long call(long i1,long j1)
{
    if(dp[i1][j1]!=-1)
        return dp[i1][j1];
    long up=0,down=0,left=0,right=0;
    if(i1!=0&&ar[i1-1][j1]<ar[i1][j1])
    {
        up=call(i1-1,j1)+1;
    }
    if(i1!=r-1&&ar[i1+1][j1]<ar[i1][j1])
    {
        down=call(i1+1,j1)+1;
    }
    if(j1!=0&&ar[i1][j1-1]<ar[i1][j1])
    {
        left=call(i1,j1-1)+1;
    }
    if(j1!=c-1&&ar[i1][j1+1]<ar[i1][j1])
    {
       right=call(i1,j1+1)+1;
    }
    return max(up,max(down,max(left,right)));
}
main()
{
    timesave;
    long ts;
    cin>>ts;
    while(ts--)
    {
       string s;
       long i,j,mx=0;
        memset(dp,-1,sizeof(dp));
        cin>>s>>r>>c;
        for(i=0; i<r; i++)
        {
            for(j=0; j<c; j++)
            {
                cin>>ar[i][j];
            }
        }
        for(i=0; i<r; i++)
        {
            for(j=0; j<c; j++)
            {
                long len=call(i,j);
                mx=max(mx,len);
            }
        }
        cout<<s<<": "<<mx+1<<endl;
    }
}

Find the lexicographically smallest LCS (Longest Common Subsequence)

IF the lcs length is 0 then print :(
INPUT:
3
ab
ba

zxcvbn
hjgasbznxbzmx

you
kghs

OUTPUT:
a
zxb
:(

CODE
///...................SUBHASHIS MOLLICK...................///
///.....DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING....///
///.............ISLAMIC UNIVERSITY,BANGLADESH.............///
///....................SESSION-(14-15)....................///
#include<bits/stdc++.h>
using namespace std;
#define sf(a) scanf("%lld",&a)
#define sf2(a,b) scanf("%lld %lld",&a,&b)
#define sf3(a,b,c) scanf("%lld %lld %lld",&a,&b,&c)
#define pf(a) printf("%lld",a)
#define pf2(a,b) printf("%lld %lld",a,b)
#define pf3(a,b,c) printf("%lld %lld %lld",a,b,c)
#define nl printf("\n")
#define   timesave              ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define ll long long
#define pb push_back
#define MPI map<int,int>mp;
#define fr(i,n) for(i=0;i<n;i++)
#define fr1(i,n) for(i=1;i<=n;i++)
#define frl(i,a,b) for(i=a;i<=b;i++)
/*primes in range 1 - n
1 - 100(1e2) -> 25 pimes
1 - 1000(1e3) -> 168 primes
1 - 10000(1e4) -> 1229 primes
1 - 100000(1e5) -> 9592 primes
1 - 1000000(1e6) -> 78498 primes
1 - 10000000(1e7) -> 664579 primes
large primes ->
104729 1299709 15485863 179424673 2147483647 32416190071 112272535095293 48112959837082048697
*/
//freopen("Input.txt","r",stdin);
//freopen("Output.txt","w",stdout);
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
string a,b;
long cs=1,n,m;
void call()
{
    long dp[n+1][m+1],i,j;
    string s[n+1][m+1];
    for(i=0; i<=n; i++)
    {
        dp[i][0]=0;
        s[i][0]="";
    }
    for(i=0; i<=m; i++)
    {
        dp[0][i]=0;
        s[0][i]="";
    }
    for(i=1; i<=n; i++)
    {
        for(j=1; j<=m; j++)
        {
            if(a[i-1]==b[j-1])
            {
                dp[i][j]=1+dp[i-1][j-1];
                s[i][j]=s[i-1][j-1]+a[i-1];
            }
            else if(dp[i-1][j]>dp[i][j-1])
            {
                dp[i][j]=dp[i-1][j];
                s[i][j]=s[i-1][j];
            }
            else if(dp[i][j-1]>dp[i-1][j])
            {
                dp[i][j]=dp[i][j-1];
                s[i][j]=s[i][j-1];
            }
            else
            {
                dp[i][j]=dp[i-1][j];
                s[i][j]=min(s[i-1][j],s[i][j-1]);
            }
        }
    }
    if(dp[n][m]==0)
        cout<<"Case "<<cs++<<": :("<<endl;
    else
        cout<<"Case "<<cs++<<": "<<s[n][m]<<endl;
}
main()
{
    timesave;
    long ts;
    cs=1;
    cin>>ts;
    while(ts--)
    {
        cin>>a>>b;
        n=a.size(),m=b.size();
        call();
    }
}

Coin Change problem no 1232 light oj

কিছু কয়েন দেওয়া থাকবে আর একটা নাম্বার দেওয়া থাকবে (K)
কাজ হবে ওই কয়েন গুলো দিয়ে নাম্বার টা বানানো যেখানে একটা কয়েন K বার ইউজ করা যাবে
এইরকম ভাবে কয়বার বানানো যাবে

For example, suppose there are three coins 1, 2, 5. Then if K = 5 the possible ways are:

11111

1112

122

5

তাহলে ৪ ভাবে বানাতে পারবো 

Problem link: http://lightoj.com/volume_showproblem.php?problem=1232

#include <bits/stdc++.h>
using namespace std;
#define MOD 100000007
long long dp[10100];
int coin[200];
int n,k;
int main()
{
    int t,cas=0;
    cin>>t;
    while(t--)
    {
        dp[0]=1;
        cin>>n>>k;
        for(int i=0; i<n; i++)
            cin>>coin[i];
        for(int i=0; i<n; i++)
            for(int j=1; j<=k; j++)
                if(coin[i]<=j)
                    dp[j]=(dp[j]+dp[j-coin[i]])%MOD;
        cout<<"Case "<<++cas<<": "<<dp[k]<<endl;
        for(int i=0; i<=k; i++)
            dp[i]=0;
    }
    return 0;
}

Longest path of a Graph by using BFS

Problem link:- https://www.spoj.com/problems/PT07Z
https://www.codechef.com/RC2018/problems/MAXDIS


///...................SUBHASHIS MOLLICK...................///
///.....DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING....///
///.............ISLAMIC UNIVERSITY,BANGLADESH.............///
///....................SESSION-(14-15)....................///
#include<bits/stdc++.h>
using namespace std;
#define sf(a) scanf("%lld",&a)
#define sf2(a,b) scanf("lld%lld",&a,&b)
#define sf3(a,b,c) scanf("lld%lld%lld",&a,&b,&c)
#define pf(a) printf("%lld",a)
#define pf2(a,b) printf("lld%lld",a,b)
#define pf3(a,b,c) printf("lld%lld%lld",a,b,c)
#define nl printf("\n")
#define ll long long
#define pb push_back
#define MPI map<int,int>mp
#define fr(i,n) for(i=0;i<n;i++)
#define fr1(i,n) for(i=1;i<=n;i++)
#define frl(i,a,b) for(i=a;i<=b;i++)
//freopen("Input.txt","r",stdin);
//freopen("Output.txt","w",stdout);
vector<long>vec[100005];
long n;
long bfs(long source)
{
    queue<long>q;
    long dist[100005]= {0},vis[100005]= {0},boroman=0,mx=0;
    dist[source]=0;
    vis[100005]=1;
    q.push(source);
    long i;
    while(!q.empty())
    {
        long u=q.front();
        if(mx<dist[u])
        {
            mx=dist[u];
            boroman=u;
        }
        for(i=0; i<vec[u].size(); i++)
        {
            long v=vec[u][i];
            if(vis[v]==0)
            {
                dist[v]=dist[u]+1;
                vis[v]=1;
                q.push(v);
            }
        }
        q.pop();
    }
    return boroman;
}
long bfss(long source)
{
    queue<long>q;
    long vis[100005]= {0},dist[100005]= {0},i,mx=0;
    q.push(source);
    vis[source]=1;
    dist[source]=0;
    while(!q.empty())
    {
        long u=q.front();
        vis[u]=1;
        if(mx<dist[u])
        {
            mx=dist[u];
        }
        for(i=0; i<vec[u].size(); i++)
        {
            long v=vec[u][i];
            if(vis[v]==0)
            {
                dist[v]=dist[u]+1;
                // mx=max(mx,dist[v]);
                vis[v]=1;
                q.push(v);
            }
        }
        q.pop();
    }
    return mx;
    /*for(i=0; i<n; i++)
    {
        if(i==source)
        {
            printf("%ld\n",mx);
        }
        else
            printf("%ld\n",dist[i]);
    }*/
}
main()
{
    while(scanf("%ld",&n)!=EOF)
    {
        long i,u,v,w,vis[100005]= {0},src;
        for(i=1; i<n; i++)
        {
            scanf("%ld%ld",&u,&v);
            vec[u].push_back(v);
            vec[v].push_back(u);
            vis[u]++,vis[v]++;
        }
        for(i=0; i<n; i++)
        {
            if(vis[i]==1)
            {
                src=i;
                break;
            }
        }
        long boro=bfs(src);
        cout<<bfss(boro)<<endl;
        for(i=0; i<=100000; i++)
        {
            vec[i].clear();
        }
    }

}

Is it a tree or not? By using DFS

Problem Link: https://www.spoj.com/problems/PT07Y/


///...................SUBHASHIS MOLLICK...................///
///.....DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING....///
///.............ISLAMIC UNIVERSITY,BANGLADESH.............///
///....................SESSION-(14-15)....................///
#include<bits/stdc++.h>
using namespace std;
#define sf(a) scanf("%lld",&a)
#define sf2(a,b) scanf("lld",&a,&b)
#define sf3(a,b,c) scanf("lld%lld",&a,&b,&c)
#define pf(a) printf("%lld",a)
#define pf2(a,b) printf("lld",a,b)
#define pf3(a,b,c) printf("lld%lld",a,b,c)
#define nl printf("\n")
#define ll long long
#define pb push_back
#define MPI map<int,int>mp
#define fr(i,n) for(i=0;i<n;i++)
#define fr1(i,n) for(i=1;i<=n;i++)
#define frl(i,a,b) for(i=a;i<=b;i++)
//freopen("Input.txt","r",stdin);
//freopen("Output.txt","w",stdout);
#define M 10005
long vis[M],flag=0;
vector<long>vec[M];
void dfs(long u)
{
    long i,cnt=0,v;
    for(i=0; i<vec[u].size(); i++)
    {
        v=vec[u][i];
        if(vis[v]==1)
        {
            cnt++;
        }
    }
    if(cnt>1)
    {
        flag=1;
    }
    for(i=0; i<vec[u].size(); i++)
    {
        v=vec[u][i];
        if(vis[v]==0)
        {
            vis[v]=1;
            dfs(v);
        }
    }
}
main()
{
    long n,m,q;
    cin>>n>>m;
    long i,u,v;
    for(i=1; i<=m; i++)
    {
        cin>>u>>v;
        vec[u].push_back(v);
        vec[v].push_back(u);
    }
    flag=0;
    if(n!=(m+1))
        flag=1;
    vis[1]=1;
    dfs(1);
    for(i=1; i<=n; i++)
    {
        if(vis[i]==0)
        {
            flag=1;
        }
    }
    if(flag==1)
        cout<<"NO"<<endl;
    else
        cout<<"YES"<<endl;
}

UVA 12716 - GCD XOR

#include <stdio.h>
using namespace std;

int F[30000005] = {};
int main()
{
    for(int i = 1; i <= 30000000; i++)
    {
        for(int j = i *2; i + j <= 30000000; j += i)
        {
            if(((i + j)&(j)) == j)
                F[i + j]++;
        }
    }
    for(int i = 1; i <= 30000000; i++)
        F[i] += F[i-1];
    int testcase, cases = 0, n;
    scanf("%d", &testcase);
    while(testcase--)
    {
        scanf("%d", &n);
        printf("Case %d: %d\n", ++cases, F[n]);
    }
    return 0;
}

ACM ICPC 2018 Preli

Problem set: https://algo.codemarshal.org/contests/icpc-dhaka-preli-18

C. Odd Is Real

#include<bits/stdc++.h>
#define ll long long
#define mx 100005
#define fs first
#define sc second
#define pb push_back
#define mkp make_pair
#define all(cont) cont.begin(), cont.end()
#define rall(cont) cont.rbegin(), cont.rend()
#define II() ( { int a ; read(a) ; a; } )
#define LL() ( { Long a ; read(a) ; a; } )
#define DD() ({double a; scanf("%lf", &a); a;})
#define DB if(0)
#define deb(x) cout << #x " is " << x << endl
#define FI freopen ("input.txt", "r", stdin)
#define FO freopen ("output.txt", "w", stdout)

using namespace std;

typedef long long Long;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vii;
typedef vector<string> vs;
ll fun(ll n)
{
    ll mult = 1;
    ll ret = 0;
    if(n == 0) return 0;

    while(mult <= n){
        ll nw = n/mult;
        ll sq = sqrt(nw);
        ret += (sq + 1)/2;
        mult *= 2ll;
    }
    return ret;
}
int main()
{
int t, tst = 1;
    scanf("%d", &t);
    while(t--)
    {
        ll l, r;
        scanf("%lld %lld", &l, &r);
        printf("Case %d: %lld\n", tst++, fun(r) - fun(l-1));
    }
return 0;
}

J. Yet Another Longest Path Problem


#include<bits/stdc++.h>
using namespace std;
#define sf(a) scanf("%lld",&a)
#define sf2(a,b) scanf("%lld %lld",&a,&b)
#define sf3(a,b,c) scanf("%lld %lld %lld",&a,&b,&c)
#define pf(a) printf("%lld",a)
#define pf2(a,b) printf("%lld %lld",a,b)
#define pf3(a,b,c) printf("%lld %lld %lld",a,b,c)
#define nl printf("\n")
#define   timesave              ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define ll long long
#define pb push_back
#define MPI map<int,int>mp;
#define fr(i,n) for(i=0;i<n;i++)
#define fr1(i,n) for(i=1;i<=n;i++)
#define frl(i,a,b) for(i=a;i<=b;i++)
/*primes in range 1 - n
1 - 100(1e2) -> 25 pimes
1 - 1000(1e3) -> 168 primes
1 - 10000(1e4) -> 1229 primes
1 - 100000(1e5) -> 9592 primes
1 - 1000000(1e6) -> 78498 primes
1 - 10000000(1e7) -> 664579 primes
large primes ->
104729 1299709 15485863 179424673 2147483647 32416190071 112272535095293 48112959837082048697
*/
//freopen("Input.txt","r",stdin);
//freopen("Output.txt","w",stdout);
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
vector<long>vec[100005],vc[100005];
long vis[100005];
void dfs(long u)
{
    for(long ii=0; ii<vec[u].size(); ii++)
    {
        long v=vec[u][ii];
        if(vis[v]==0)
        {
            vis[v]=3-vis[u];
            dfs(v);
            if(vis[v]==1)
            {
               vc[v].push_back(u);
            }
            else
               vc[u].push_back(v);
        }
    }
}
main()
{
    timesave;
    long ts,cs=1;
    scanf("%ld",&ts);
    while(ts--)
    {
        long n;
        scanf("%ld",&n);
        long i,a,b,w,j;
        for(i=1; i<n; i++)
        {
            scanf("%ld%ld",&a,&b);
            vec[b].push_back(a);
            vec[a].push_back(b);
        }
        printf("Case %ld:\n",cs++);
        vis[1]=1;
        dfs(1);
        for(i=1; i<=n; i++)
        {
           //if(vc[i].size()>0)
           for(j=0;j<vc[i].size();j++)
           {
              printf("%ld %ld\n",i,vc[i][j]);
//              cout<<i<<" "<<vc[i][j]<<endl;
           }
        }
        for(i=1;i<=n;i++)
        {
           vis[i]=0;
           vc[i].clear();
           vec[i].clear();
        }
    }
}


G. Subset with GCD K

#include<bits/stdc++.h>
#include<cstring>
using namespace std;
#define nl         printf("\n")
#define case(a,b)  printf("Case %lld: %lld\n",a,b)
#define P(a)       printf("%lld\n",a)
#define SP(a)      printf("%lld ",a)
#define G(a)       scanf("%lld",&a)
#define GG(a,b)    scanf("%lld %lld",&a,&b)
#define pb         push_back
#define DB         printf("I WAS HERE\n")
#define LL         long long
#define zero       0
int main()
{
    LL i;
    LL n;
    G(n);
    long long ar[100005],br[10005];
    for(i=1;i<=n;i++)
    {
       G(ar[i]);
    }
    LL q;
    G(q);
    for(i=1;i<=q;i++)
    {
        G(br[i]);
    }
    LL j;
    for(i=1;i<=q;i++)
    {
        LL cnt=0;
        LL gcd=0;
        for(j=1;j<=n;j++)
        {
            if(ar[j]%br[i]==0)
            {
                gcd=__gcd(ar[j],gcd);
            }
        }
        if(gcd==br[i])
        cout<<"Y"<<endl;
        else
            cout<<"N"<<endl;
    }
    return 0;
}

H. Colorful Balls

#include<bits/stdc++.h>

#include<cstring>

using namespace std;

#define nl         printf("\n")

#define case(a,b)  printf("Case %lld: %lld\n",a,b)

#define P(a)       printf("%lld\n",a)

#define SP(a)      printf("%lld ",a)

#define G(a)       scanf("%lld",&a)

#define GG(a,b)    scanf("%lld %lld",&a,&b)

#define pb         push_back

#define DB         printf("I WAS HERE\n")

#define LL         long long

#define zero       0

long long ar[100005][4],len;

char s[100005];

long long chk[100005];

long long MOD=1000000007 ;

long long mod(long long f, long long s)

{

    return ((f%MOD) * (s%MOD))%MOD;

}

long long sum_mod(long long f, long long s)

{

    return ((f%MOD) + (s%MOD))%MOD;

}

void recap()

{

    long long i;

    long long l=strlen(s);

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

    {

        if(s[i]=='G')

            chk[i+1]=1;

        else if(s[i]=='R')

            chk[i+1]=2;

        else if(s[i]=='B')

            chk[i+1]=3;

        else

            chk[i+1]=0;

    }

    chk[l+1]=4;/// this makes it

}

void precal()

{

    long long i;

    ar[1][1]=0;

    ar[1][2]=1;

    ar[1][3]=1;

    for(i=2; i<=100000; i++)

    {

        ar[i][1]=sum_mod(ar[i-1][2],ar[i-1][3]);

        ar[i][2]=sum_mod(ar[i-1][1],ar[i-1][3]);

        ar[i][3]=sum_mod(ar[i-1][1],ar[i-1][2]);

    }

}

LL kaj[100005];

     //kaj[0]=chk[0]=10;

long long call_calc()

{

    LL i=1;

    LL ret=1;

    /// kaj is working

    /// ekdom w na thakle

    while(i<=len)

    {

        if(kaj[i]==0)

        {

            LL hold=kaj[i-1];

            LL cnt=0;

            while(i<=len&& kaj[i]==0)

            {

                cnt++;

                i++;

            }

        //P(cnt);

            LL lvl=ar[cnt][1]+ar[cnt][2]+ar[cnt][3];

            LL val1=1;

            //P(lvl);

            if(kaj[i]!=hold)/// ager tar soman na

            {

                if(kaj[i]==4)/// pore ar kichu nai

                {

                    val1=sum_mod(ar[cnt][1],sum_mod(ar[cnt][2],ar[cnt][3]));

                }

                else /// pore ache kintu agerta na

                {

                    val1=sum_mod(ar[cnt][1],ar[cnt][3]);//lvl-ar[cnt][2];

                }

               // P(lvl);

            }

            else /// pore ager ta e ache

            {

                val1=sum_mod(ar[cnt][2],ar[cnt][3]);//lvl-ar[cnt][1];

            }

            ret=mod(ret,val1);

        }

        else

            i++;

    }

    return ret;

}

int main()

{

    precal();

    LL i;

    /*for(i=1;i<=6;i++)

    {

        cout<<ar[i][1]<<" "<<ar[i][2]<<" "<<ar[i][3]<<endl;

    }*/

    LL t,cs=1;

    G(t);

    getchar();

    while(t--)

    {

        scanf("%s",s);

        recap();

        len=strlen(s); /// global

        /// len 1 er hisab alada

        LL ans=0;

        if(len==1)

        {

            if(chk[1]==0)

                ans=3;

            else

                ans=0;

            case(cs++,ans);

            continue;

        }

        /// ekdom w na thakle hisab alada

        bool flag=false;

        for(i=1; i<=len; i++)

        {

            if(chk[i]==0)

                flag=true;

        }

        if(flag==false)

        {

           case(cs++,ans);

           continue;

        }

        for(i=2; i<=len+1 ; i++)

        {

            kaj[i]=chk[i];

        }

        if(chk[1]==0)

        {

            long long val1=0,val2=0,val3=0;

            if(kaj[2]!=1)

            {

                kaj[1]=1;

                val1=call_calc();

               //    P(val1);

            }

           // return 0;

            if(kaj[2]!=2)

            {

                kaj[1]=2;

                val2=call_calc();

            }

            if(kaj[2]!=3)

            {

                kaj[1]=3;

                val3=call_calc();

            }

            ans= ((val1%MOD)+ (val2%MOD))%MOD;

            ans=((ans%MOD)+ (val3%MOD))%MOD;

        }

        else

        {

            kaj[1]=chk[1];

            ans= call_calc();

        }

        case(cs++,ans);

    }

    return 0;

}

Segment tree range update and query sum

Problem link: https://www.spoj.com/problems/HORRIBLE/
Input
1
8 6
0 2 4 26
0 4 8 80
0 4 5 20
1 8 8
0 5 7 14
1 4 8

Output:
80
508

AC Code:
#include <iostream>
#include <bits/stdc++.h>
using namespace std;

const int N=100005;
long long int lazy[4*N];
long long int seg[4*N];

void build(int low,int high,int node)
{
    if(low>high)
    return;
    if(low == high)
    {
        seg[node]=0;
        return;
    }
    int mid = low+high>>1;
    build(low,mid,2*node+1);
    build(mid+1,high,2*node+2);
    seg[node]=seg[2*node+1]+seg[2*node+2];
}

void update(int low,int high,int lq,int hq,int node,long long int val)
{
    if(lazy[node])
    {
        seg[node]+=(high-low+1)*lazy[node];
        if(high!=low)
        {
            lazy[2*node+1]+=lazy[node];
            lazy[2*node+2]+=lazy[node];
        }
        lazy[node]=0;
    }
    if(low>hq || high<lq)
    return;
    if(lq<=low && high<=hq)
    {
        seg[node]+=(high-low+1)*val;
        if(high!=low)
        {
            lazy[2*node+1]+=val;
            lazy[2*node+2]+=val;
        }
        return;
    }
    int mid=low+high>>1;
    update(low,mid,lq,hq,2*node+1,val);
    update(mid+1,high,lq,hq,2*node+2,val);
    seg[node]=seg[2*node+1]+seg[2*node+2];
}

long long int query(int low,int high,int lq,int hq,int node)
{
    if(lazy[node])
    {
        seg[node]+=(high-low+1)*lazy[node];
        if(high!=low)
        {
            lazy[2*node+1]+=lazy[node];
            lazy[2*node+2]+=lazy[node];
        }
        lazy[node]=0;
    }
    if(low>hq || high<lq)
    return 0;
    if(lq<=low && high<=hq)
    {
        return seg[node];
    }
    int mid=low+high>>1;
   return query(low,mid,lq,hq,2*node+1)+query(mid+1,high,lq,hq,2*node+2);
}
int main(){
    int t;
    scanf("%d",&t);
    int n,q;
    while(t--)
    {
        memset(seg,0,sizeof(seg));
        memset(lazy,0,sizeof(lazy));
        scanf("%d %d",&n,&q);
        int type;
        int x,y;
        long long int val;
        build(0,n-1,0);
        while(q--)
        {
            scanf("%d",&type);
            //printf("%dhh\n",type);
            if(type)
            {
                scanf("%d %d",&x,&y);
                printf("%lld\n",query(0,n-1,x-1,y-1,0));
            }
            else
            {
                scanf("%d %d %lld",&x,&y,&val);
                update(0,n-1,x-1,y-1,0,val);
            }
        }

    }

    return 0;

}

Euler phi fuction Code

To calculate
G=0;

for(i=1;i<N;i++)

for(j=i+1;j<=N;j++)

{

    G+=gcd(i,j);

}

Use this Phi function




///...................SUBHASHIS MOLLICK...................///
///.....DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING....///
///.............ISLAMIC UNIVERSITY,BANGLADESH.............///
///....................SESSION-(14-15)....................///
#include<bits/stdc++.h>
using namespace std;
#define sf(a) scanf("%lld",&a)
#define sf2(a,b) scanf("%lld %lld",&a,&b)
#define sf3(a,b,c) scanf("%lld %lld %lld",&a,&b,&c)
#define pf(a) printf("%lld",a)
#define pf2(a,b) printf("%lld %lld",a,b)
#define pf3(a,b,c) printf("%lld %lld %lld",a,b,c)
#define nl printf("\n")
#define   timesave              ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define ll long long
#define pb push_back
#define MPI map<int,int>mp;
#define fr(i,n) for(i=0;i<n;i++)
#define fr1(i,n) for(i=1;i<=n;i++)
#define frl(i,a,b) for(i=a;i<=b;i++)
/*primes in range 1 - n
1 - 100(1e2) -> 25 pimes
1 - 1000(1e3) -> 168 primes
1 - 10000(1e4) -> 1229 primes
1 - 100000(1e5) -> 9592 primes
1 - 1000000(1e6) -> 78498 primes
1 - 10000000(1e7) -> 664579 primes
large primes ->
104729 1299709 15485863 179424673 2147483647 32416190071 112272535095293 48112959837082048697
*/
//freopen("Input.txt","r",stdin);
//freopen("Output.txt","w",stdout);
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
#define MAX 4000001
long long i,j;
long long table[MAX],phi[MAX];
void phi_function()
{
    phi[1]=1;
    for(i=2; i<=MAX; i++)
    {
        if(phi[i]==0)
        {
            phi[i]=i-1;
            for(j=i+i; j<=MAX; j+=i)
            {
                if(phi[j]==0)
                    phi[j]=j;
                phi[j]=(phi[j]/i)*(i-1);
            }
        }
    }
}
void pre_calc()
{
    for(i=1; i<MAX; i++)
    {
        for(j=i+i; j<MAX; j+=i)
        {
            table[j]=table[j]+((phi[j/i])*i);
        }
    }
    for(i=2; i<MAX; i++)
    {
        table[i]=table[i-1]+table[i];
    }
}
main()
{
    timesave;
    phi_function();
    pre_calc();
    long long n;
    while(cin>>n)
    {
        if(n==0)
            break;
        cout<<table[n]<<endl;
    }
}

UVA 11424 - GCD - Extreme (I)

///...................SUBHASHIS MOLLICK...................///
///.....DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING....///
///.............ISLAMIC UNIVERSITY,BANGLADESH.............///
///....................SESSION-(14-15)....................///
#include<bits/stdc++.h>
using namespace std;
#define sf(a) scanf("%lld",&a)
#define sf2(a,b) scanf("%lld %lld",&a,&b)
#define sf3(a,b,c) scanf("%lld %lld %lld",&a,&b,&c)
#define pf(a) printf("%lld",a)
#define pf2(a,b) printf("%lld %lld",a,b)
#define pf3(a,b,c) printf("%lld %lld %lld",a,b,c)
#define nl printf("\n")
#define   timesave              ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define ll long long
#define pb push_back
#define MPI map<int,int>mp;
#define fr(i,n) for(i=0;i<n;i++)
#define fr1(i,n) for(i=1;i<=n;i++)
#define frl(i,a,b) for(i=a;i<=b;i++)
/*primes in range 1 - n
1 - 100(1e2) -> 25 pimes
1 - 1000(1e3) -> 168 primes
1 - 10000(1e4) -> 1229 primes
1 - 100000(1e5) -> 9592 primes
1 - 1000000(1e6) -> 78498 primes
1 - 10000000(1e7) -> 664579 primes
large primes ->
104729 1299709 15485863 179424673 2147483647 32416190071 112272535095293 48112959837082048697
*/
//freopen("Input.txt","r",stdin);
//freopen("Output.txt","w",stdout);
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
#define MAX 4000001
long long i,j;
long long table[MAX],phi[MAX];
void phi_function()
{
    phi[1]=1;
    for(i=2; i<=MAX; i++)
    {
        if(phi[i]==0)
        {
            phi[i]=i-1;
            for(j=i+i; j<=MAX; j+=i)
            {
                if(phi[j]==0)
                    phi[j]=j;
                phi[j]=(phi[j]/i)*(i-1);
            }
        }
    }
}
void pre_calc()
{
    for(i=1; i<MAX; i++)
    {
        for(j=i+i; j<MAX; j+=i)
        {
            table[j]=table[j]+((phi[j/i])*i);
        }
    }
    for(i=2; i<MAX; i++)
    {
        table[i]=table[i-1]+table[i];
    }
}
main()
{
    timesave;
    phi_function();
    pre_calc();
    long long n;
    while(cin>>n)
    {
        if(n==0)
            break;
        cout<<table[n]<<endl;
    }
}

UVA 11426 - GCD - Extreme (II)

///...................SUBHASHIS MOLLICK...................///
///.....DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING....///
///.............ISLAMIC UNIVERSITY,BANGLADESH.............///
///....................SESSION-(14-15)....................///
#include<bits/stdc++.h>
using namespace std;
#define sf(a) scanf("%lld",&a)
#define sf2(a,b) scanf("%lld %lld",&a,&b)
#define sf3(a,b,c) scanf("%lld %lld %lld",&a,&b,&c)
#define pf(a) printf("%lld",a)
#define pf2(a,b) printf("%lld %lld",a,b)
#define pf3(a,b,c) printf("%lld %lld %lld",a,b,c)
#define nl printf("\n")
#define   timesave              ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define ll long long
#define pb push_back
#define MPI map<int,int>mp;
#define fr(i,n) for(i=0;i<n;i++)
#define fr1(i,n) for(i=1;i<=n;i++)
#define frl(i,a,b) for(i=a;i<=b;i++)
/*primes in range 1 - n
1 - 100(1e2) -> 25 pimes
1 - 1000(1e3) -> 168 primes
1 - 10000(1e4) -> 1229 primes
1 - 100000(1e5) -> 9592 primes
1 - 1000000(1e6) -> 78498 primes
1 - 10000000(1e7) -> 664579 primes
large primes ->
104729 1299709 15485863 179424673 2147483647 32416190071 112272535095293 48112959837082048697
*/
//freopen("Input.txt","r",stdin);
//freopen("Output.txt","w",stdout);
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
#define MAX 4000001
long long i,j;
long long table[MAX],phi[MAX];
void phi_function()
{
    phi[1]=1;
    for(i=2; i<=MAX; i++)
    {
        if(phi[i]==0)
        {
            phi[i]=i-1;
            for(j=i+i; j<=MAX; j+=i)
            {
                if(phi[j]==0)
                    phi[j]=j;
                phi[j]=(phi[j]/i)*(i-1);
            }
        }
    }
}
void pre_calc()
{
    for(i=1; i<MAX; i++)
    {
        for(j=i+i; j<MAX; j+=i)
        {
            table[j]=table[j]+((phi[j/i])*i);
        }
    }
    for(i=2; i<MAX; i++)
    {
        table[i]=table[i-1]+table[i];
    }
}
main()
{
    timesave;
    phi_function();
    pre_calc();
    long long n;
    while(cin>>n)
    {
        if(n==0)
            break;
        cout<<table[n]<<endl;
    }
}

UVA 10862 - Connect the Cable Wires

#include<stdio.h>
#include<math.h>
#include<string.h>
char f2[5002][1200]= {0};
int main()
{
    long n,m=0;
    {
        char a[100000]= {0},b[100000]= {0},f1[100000]= {0};
        char s1[100000]= {0},s2[100000]= {0};
        {
            long i1,i,k=0,x=0,w=0,p;
            a[0]='0';
            a[1]='\0';
            b[0]='1';
            b[1]='\0';
            f1[0]='0';
            f1[1]='\0';
            for(i1=1; i1<=5001; i1++)
            {
                long l=0,l1=0,e=0,temp=0,j=0,k=0,c=0,d=0,l2,l3,cc,q,qq;
                l=strlen(a);
                l1=strlen(b);
                l2=l;
                l3=l1;
                if(l>l1)
                    l1=l;
                for(i=l2-1; i>=0; i--)
                {
                    s1[e++]=a[i];
                }
                s1[e]=0;
                e=0;
                for(i=l3-1; i>=0; i--)
                {
                    s2[e++]=b[i];
                }
                s2[e]=0;
                for(j=0; j<l1; j++)
                {
                    if(j<l2)
                        q=s1[j]-48;
                    else
                        q=0;
                    if(j<l3)
                        qq=s2[j]-48;
                    else
                        qq=0;
                    cc=q+qq+c;
                    d=cc%10;
                    f1[k++]=d+48;
                    c=cc/10;
                }
                if(c>0)
                    f1[k++]=c+48;
                s1[e]=0;
                long v=0,v1=0;
                for(i=0; i<=strlen(a)-1; i++)
                {
                    b[v++]=a[i];
                }
                for(i=strlen(f1)-1; i>=0; i--)
                {
                    a[v1++]=f1[i];
                }
                a[v1]=0;
                b[v]=0;
                strcpy(f2[m++],f1);
            }
            while(scanf("%ld",&n)!=EOF)
            {
                if(n==0)
                    break;
                else
                {
                    n=2*n;
                    for(i=strlen(f2[n-1])-1; i>=0; i--)
                    {
                        printf("%c",f2[n-1][i]);
                    }
                    printf("\n");
                }
            }
        }
    }
    return 0;
}

UVA 10432 - Polygon Inside A Circle

#include<stdio.h>
#include<math.h>
int main()
{
    double r,n,area;
    while(scanf("%lf%lf",&r,&n)!=EOF)
    {
        area=r*r*n*sin((2.0*M_PI)/n)/2;
        printf("%.3lf\n",area);
    }
    return 0;
}

UVA 300 - Maya Calendar

#include<stdio.h>
#include<string.h>
int main()
{
    long n,i1;
    char aa[20][10]={"pop","no","zip","zotz","tzec","xul","yoxkin","mol","chen","yax","zac","ceh","mac","kankin","muan","pax","koyab","cumhu","uayet"};
    char s[20][10]={"imix","ik","akbal","kan","chicchan","cimi","manik","lamat","muluk","ok","chuen","eb","ben","ix","mem","cib","caban","eznab","canac","ahau"};
    long a,b,a1,b1,c1,d,e,i;
    char c[1000];
    scanf("%ld",&n);
    printf("%ld\n",n);
    for(i1=0;i1<n;i1++)
    {
        scanf("%ld. %s %ld",&a,c,&b);
        a1=b*365;
        for(i=0;i<19;i++)
        {
            if(strcmp(aa[i],c)==0)
            break;
        }
        a1=a1+i*20+a+1;
        b1=(a1-1)/260;
        c1=a1-b1*260;
        d=(c1-1)%20;
        e=(c1-1)%13;
        printf("%ld %s %ld\n",++e,s[d],b1);
    }
    return 0;
}

UVA 902 - Password Search

///...................SUBHASHIS MOLLICK...................///
///.....DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING....///
///.............ISLAMIC UNIVERSITY,BANGLADESH.............///
///....................SESSION-(14-15)....................///
#include<bits/stdc++.h>
using namespace std;
#define sf(a) scanf("%lld",&a)
#define sf2(a,b) scanf("%lld %lld",&a,&b)
#define sf3(a,b,c) scanf("%lld %lld %lld",&a,&b,&c)
#define pf(a) printf("%lld",a)
#define pf2(a,b) printf("%lld %lld",a,b)
#define pf3(a,b,c) printf("%lld %lld %lld",a,b,c)
#define nl printf("\n")
#define   timesave              ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define ll long long
#define pb push_back
#define MPI map<int,int>mp;
#define fr(i,n) for(i=0;i<n;i++)
#define fr1(i,n) for(i=1;i<=n;i++)
#define frl(i,a,b) for(i=a;i<=b;i++)
/*primes in range 1 - n
1 - 100(1e2) -> 25 pimes
1 - 1000(1e3) -> 168 primes
1 - 10000(1e4) -> 1229 primes
1 - 100000(1e5) -> 9592 primes
1 - 1000000(1e6) -> 78498 primes
1 - 10000000(1e7) -> 664579 primes
large primes ->
104729 1299709 15485863 179424673 2147483647 32416190071 112272535095293 48112959837082048697
*/
//freopen("Input.txt","r",stdin);
//freopen("Output.txt","w",stdout);
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
main()
{
   long n;
   string s;
   while(cin>>n>>s)
   {
      map<string,long>mp;
      long i,j,mx=0,sz=s.size();
      string ans;
      for(i=0;i<sz;i++)
      {
         string s1;
         for(j=i;j<i+n;j++)
         {
            s1+=s[j];
         }
         mp[s1]++;
         if(mp[s1]>mx)
         {
            mx=mp[s1];
            ans=s1;
         }
      }
      cout<<ans<<endl;
   }
}