Upper bound lower bound

in here A and B are the numbers that i want to search the upper bound and lower bound in a  array
long long lw=lower_bound (v, v+n, A)-v;
long long hi=upper_bound (v, v+n, B)-v;

Inverse mod

long long nic=(ar[n-r]%mod*(ar[r]%mod))%mod;

ans=(ar[n]*bigmod(nic,mod-2))%mod;

nic বলতে nCr এর নিচের পার্ট টুকু কে বোঝানো হচ্ছে 

ইনভারস মডের জন্য

   (A/B)%mod;

=>A%mod/B%mod;

=>(AB^-1)%mod;

for multipicative identity:-

A.B^(mod-1)%mod=1;

=>A*B*bigmod(B,(mod-2),mod);

Area of parallelograms (Light oj 1305 no solution)

problem link:-http://lightoj.com/volume_showproblem.php?problem=1305

#include<stdio.h>
#include<stdlib.h>
int main()
{
    int Ax,Ay,Bx,By,Cx,Cy,Dx,Dy,j=0,TEST,area;
    scanf("%d",&TEST);
    while(TEST--)
    {
        scanf("%d%d%d%d%d%d",&Ax,&Ay,&Bx,&By,&Cx,&Cy);
        Dx=(Ax+Cx)-Bx;
        Dy=(Ay+Cy)-By;
        area=((Ax*By)+(Bx*Cy)+(Cx*Dy)+(Dx*Ay))-((Ay*Bx)+(By*Cx)+(Cy*Dx)+(Dy*Ax));
        area=0.5*area;
        printf("Case %d: %d %d %d\n",++j,Dx,Dy,abs(area));
    }

    return 0;
}

Compute sum of digits in all numbers from 1 to n

Sum of digits of a range(suppose 1-10 ans is 46,1-9 ans is 45)

#include<stdio.h>
#include<algorithm>
#include<iostream>
using namespace std;
long long  b,i,x,v,c,ans,anc,b1;
int j,k,a[20];
main()
{
    while(cin>>b>>b1)
    {
        if(b==-1&&b1==-1)
            break;
        ans=0;
        anc=0;
        k=0;
        x=1;
        j=0;
        while(b!=0)
        {
            a[k]=b%10;
            b/=10;
            k++;
        }
        for (i=1; i<k; i++) x*=10;
        if (k==0) x=0;
        k--;
        while(x!=0)
        {
            v=45*(x/10)*k;
            c=(a[k]*(a[k]-1)/2)*x+v*a[k]+a[k];
            ans+=j*a[k]*x+c;
            j+=a[k];
            x/=10;
            k--;

        }
        ans-=j;
        k=0;
        x=1;
        j=0;
        while(b1!=0)
        {
            a[k]=b1%10;
            b1/=10;
            k++;
        }
        for (i=1; i<k; i++) x*=10;
        k--;
        while(x!=0)
        {
            v=45*(x/10)*k;
            c=(a[k]*(a[k]-1)/2)*x+v*a[k]+a[k];
            anc+=j*a[k]*x+c;
            j+=a[k];
            x/=10;
            k--;
        }
        cout<<anc-ans<<endl;
    }
}

UVA 417 - Word Index

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

main()
{
    map<string,int>mp;
    int i,j,k,l,m,cnt=1;
    string s1,str="abcdefghijklmnopqrstuvwxyz";
    string str2,s2,s3,s4,s5;
    for(i=0; i<str.size(); i++)
    {
        s1=str[i];
        mp[s1]=cnt;
        cnt++;
    }
    for(i=0; i<str.size(); i++)
    {
        for(j=i+1; j<str.size(); j++)
        {
            s2=str[i];
            s2+=str[j];
            mp[s2]=cnt;
            cnt++;
        }
    }
    for(i=0; i<str.size(); i++)
    {
        for(j=i+1; j<str.size(); j++)
        {
            for(k=j+1; k<str.size(); k++)
            {
                s3=str[i];
                s3+=str[j];
                s3+=str[k];
                mp[s3]=cnt;
                cnt++;
            }

        }
    }
    for(i=0; i<str.size(); i++)
    {
        for(j=i+1; j<str.size(); j++)
        {
            for(k=j+1; k<str.size(); k++)
            {
                for(l=k+1; l<str.size(); l++)
                {
                    s4=str[i];
                    s4+=str[j];
                    s4+=str[k];
                    s4+=str[l];
                    mp[s4]=cnt;
                    cnt++;
                }
            }

        }
    }
    for(i=0; i<str.size(); i++)
    {
        for(j=i+1; j<str.size(); j++)
        {
            for(k=j+1; k<str.size(); k++)
            {
                for(l=k+1; l<str.size(); l++)
                {
                    for(m=l+1; m<str.size(); m++)
                    {
                        s5=str[i];
                        s5+=str[j];
                        s5+=str[k];
                        s5+=str[l];
                        s5+=str[m];
                        mp[s5]=cnt;
                        cnt++;
                    }
                }
            }

        }
    }
    while(cin>>str2)
    {
        cout<<mp[str2]<<endl;
    }

}

UVA 11503 - Virtual Friends

#include <bits/stdc++.h>
using namespace std;
long par[200005]={0},res[200005]={0};
long find(long r)
{
    if(par[r]==r)
    {
        return r;
    }
    else
        return find(par[r]);
}
long checkunion(long x,long y)
{
    long u=find(x);
    long v=find(y);
    if(u!=v)
    {
        par[v]=u;
        res[v]+=res[u];
    }
    return res[u]=res[v];
}
main()
{
    long ts;
    cin>>ts;
    while(ts--)
    {
        long n,i,k=1;
        map<string,long>mp;
        string s1,s2;
        cin>>n;
        for(i=1;i<=2*n;i++)
        {
            par[i]=i;
            res[i]=1;
        }
        for(i=1;i<=n;i++)
        {
            cin>>s1>>s2;
            if(mp[s1]==0)
            {
                mp[s1]=k++;
            }
            if(mp[s2]==0)
            {
                mp[s2]=k++;
            }
            long ans=checkunion(mp[s1],mp[s2]);
            cout<<ans<<endl;
        }
    }
}

UVA 10226 Hardwood Species

#include<bits/stdc++.h>
using namespace std;
main()
{
    long ts,cs=1;
    cin>>ts;
     getchar();
     getchar();
    while(ts--)
    {
        if(cs>1)
            cout<<endl;
        cs++;
        string s;
        long i,n=0;
        set<string>st;
        map<string,long>mp;
        set<string>::iterator it;
        while(getline(cin,s)&&s[0])
        {
            mp[s] ++;
            st.insert(s);
            n++;
        }
        for(it = st.begin(); it != st.end(); it++)
        {
            long k=mp[*it];
            double k1=double(k)/double(n);
            k1=k1*100;
            cout << *it;
            printf(" %.4lf\n",k1);
        }
    }
}

UVA 13178 - Is it multiple of 3?

#include<bits/stdc++.h>
using namespace std;
main()
{
    long ts;
    cin>>ts;
    while(ts--)
    {
        long long a,k;
        cin>>a;
        k=a*(a+1)/2;
        if(k%3==0)
        {
            cout<<"YES"<<endl;
        }
        else
            cout<<"NO"<<endl;
    }
}

How to sort some strings in c

#include<bits/stdc++.h>
using namespace std;
main()
{
    long n,i,k,j;
    cin>>n;
    char s[100][100],s1[100];
    for(i=0;i<n;i++)
    {
        cin>>s[i];
    }
    for(i=1;i<=n;i++)
    {
        for(j=0;j<n-i;j++)
        {
            k=strcmp(s[j],s[j+1]);
            if(k>0)
            {
                strcpy(s1,s[j]);
                strcpy(s[j],s[j+1]);
                strcpy(s[j+1],s1);
            }
        }
    }
    for(i=0;i<n;i++)
    {
        cout<<s[i]<<endl;
    }
}

UVA 10685 - Nature

#include<bits/stdc++.h>
#include <vector>
using namespace std;
vector<long>vec[5005];
long cnt=0,vis[5005]={0};
long bfs(long a)
{
    queue<long>q;
    q.push(a);
    cnt=0;
    long u,v,i1;
    while(!q.empty())
    {
        u=q.front();
        q.pop();
        for(i1=0;i1<vec[u].size();i1++)
        {
            v=vec[u][i1];
            if(vis[v]==0)
            {
                cnt++;
                vis[v]=1;
                q.push(v);
            }
        }
    }
    return cnt;
}
main()
{
    long n,m;
    while(cin>>n>>m)
    {
        long i;
        string s,s1;
        map<string,long>mp;
        if(n==0&&m==0)
            break;
        for(i=1;i<=n;i++)
        {
            cin>>s;
            mp[s]=i;
        }
        for(i=1;i<=m;i++)
        {
            cin>>s>>s1;
            vec[mp[s]].push_back(mp[s1]);
            vec[mp[s1]].push_back(mp[s]);
        }
        long ans=0,mx=0;
        for(i=1;i<=n;i++)
        {
            if(vis[i]==0)
            {
                ans=bfs(i);
                vis[i]=1;
                mx=max(mx,ans);
                ans=0;
            }
        }
        if(mx==0)
        {
            cout<<1<<endl;
        }
        else
            cout<<mx<<endl;
        for(i=1;i<=n;i++)
        {
            vec[i].clear();
            vis[i]=0;
        }
    }
}

2nd shortest path by using dijkstra

#include<bits/stdc++.h>

using namespace std;

#define ll long long

#define sl(n) scanf("%lld", &n)

#define sf(n) scanf("%lf", &n)

#define si(n) scanf("%d", &n)

#define ss(n) scanf("%s", n)

#define pii pair <int, int>

#define pll pair <ll, ll>

map <ll, vector <ll> > ed;

map <ll, vector <ll> > cost;

ll d[5050], sd[5050];

priority_queue < pll, vector <pll>, greater<pll> > pq, tpq;

void dijk(ll src, ll dst)

{

    pq.push(pll(0, src));

    d[src] = 0;

    while(pq.empty() == false)

    {

        pll temp = pq.top();

        pq.pop();

        ll u = temp.second;

        ll dis = temp.first;

        for (ll i = 0; i < ed[u].size(); i++)

        {

            ll v = ed[u][i];

            if (dis < d[v] - cost[u][i])

            {

                sd[v] = d[v];

                d[v] = dis + cost[u][i];

                pq.push(pll(d[v], v));

 //               cout << "a " << u << " " << dis << " " << v << " " << d[v] << endl;

            }

            else if (dis < sd[v] - cost[u][i] && dis != d[v] - cost[u][i])

            {

                sd[v] = dis + cost[u][i];

                pq.push(pll(sd[v], v));

   //             cout << "b " << u << " " << dis << " " << v << " " << d[v] << endl;

            }

        }

    }

}

int main ()

{

 //   freopen("inl.txt", "r", stdin);

    // freopen("outl.txt", "w", stdout);

    //  ios_base::sync_with_stdio(0); // no printf/scanf must be present

    ll cs, t, i, j, k, n, x, y, z, ans, q, m;

    sl(t);

    for (cs = 1; cs <= t; cs++)

    {

        sl(n);

        sl(m);

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

            d[i] = sd[i] = LLONG_MAX;

        ed.clear();

        cost.clear();

        while (pq.empty() == false)

            pq.pop();

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

        {

            sl(x);

            sl(y);

            sl(z);

            ed[x].push_back(y);

            ed[y].push_back(x);

            cost[x].push_back(z);

            cost[y].push_back(z);

        }

        dijk(1, n);

        printf("Case %lld: %lld\n", cs, sd[n]);

    }

    return 0;

}

Dequeue operation

insert element at back-    q.push_back(element); /push in right
insert element at front-    q.push_front(element); / push in left
remove last element   -                  q.pop_back();  /pop in right
remove first element       -               q.pop_front();  /pop in left
examine last element       -       q.back() / see right/last element
examine first element       -       q.front() / see left/first element

ক্যাপশন যোগ করুন

By using pair shortest path in bfs

long dx[]={1,0,-1,0};
long dy[]={0,1,0,-1};
long row,col;
string s[100];
long bfs(long x,long y)
{
    queue< pair<long,long> >q;
    pair<long,long>pr;
    long dis[30][30]={0},vis[30][30]={0},x1,y1,i1;
    dis[x][y]=0;
    vis[x][y]=1;
    q.push(make_pair(x,y));
    while(!q.empty())
    {
        pr=q.front();
        x1=pr.first;
        y1=pr.second;
        for(i1=0;i1<4;i1++)
        {
            x1=pr.first+dx[i1];
            y1=pr.second+dy[i1];
            if((x1>=0&&x1<row)&&(y1>=0&&y1<col)&&(vis[x1][y1]==0)&&(s[x1][y1]!='m')&&(s[x1][y1]!='#'))
            {
                dis[x1][y1]=dis[pr.first][pr.second]+1;
                q.push(make_pair(x1,y1));
                vis[x1][y1]=1;
                if(s[x1][y1]=='h')
                {
                    return dis[x1][y1];
                }
            }
        }
        q.pop();
    }
}

UVA 11518 - Dominos 2

#include<bits/stdc++.h>
#define fr(i,m) for(int i=0;i<m;i++)
using namespace std;
long vis[12010]={0},cnt=0;
vector<long>vec[100010];
long dfs(long n)
{
    long i1;
    if(vis[n]==1)
    return 0;
    if(vis[n]==0)
    cnt++;
    vis[n]=1;
    for(i1=0;i1<vec[n].size();i1++)
    {
        dfs(vec[n][i1]);
    }
    return cnt;
}
main()
{
    long ts;
    cin>>ts;
    while(ts--)
    {
        long a,b,c,x,y,x1,ans=0,i;
        cin>>a>>b>>c;
        for(i=0;i<b;i++)
        {
            cin>>x>>y;
            vec[x].push_back(y);
        }
        for(i=0;i<c;i++)
        {
            cin>>x1;
            cnt=0;
            ans+=dfs(x1);
        }
        cout<<ans<<endl;
        for(i=0;i<10010;i++)
        {
            vis[i]=0;
            vec[i].clear();
        }
    }
}

UVA 11244 Counting Stars

#include<stdio.h>
#include<string.h>
int main()
{
    long n,m;
    while(~scanf("%ld%ld",&n,&m))
    {
        long i,j,count=0;
        char a[200][200]={0};
        if(n==0&&m==0)
        break;
        for(i=0;i<n;i++)
        scanf("%s",a[i]);
        for(i=0;i<n;i++)
        {
            for(j=0;j<m;j++)
            if(a[i][j]=='*')
            {
                if(a[i-1][j-1]!='*'&&a[i-1][j]!='*'&&a[i-1][j+1]!='*'&&a[i][j-1]!='*'&&a[i][j+1]!='*'&&a[i+1][j-1]!='*'&&a[i+1][j]!='*'&&a[i+1][j+1]!='*')
                count++;
            }
        }
        printf("%ld\n",count);
    }
    return 0;
}

Graph related prblm

uva problem :
352,459,469,572,871,260,10336,10946,11244,11518,383,429,762,10009,10116.
lightoj problem:
1094,1066,1111,1141,1174,1238,1257,1337,1049.
# ALGORITHM: Minimum Spanning Tree ?? ???????? ?
Uva problem: 10034,534,544,10048,1174
Lightoj problem: 1002,1029,1040,1041,1059,1123
# ALGORITHM: Minimum Spanning Tree/Dijkstra/Floyd Warshall ?? ???????? ?
Lightoj problems:
Dijkstra/Floyd Warshall : 1002,1019,1099,1174,1281
Minimum Spanning Tree (Repeated): 1002,1029,1040,1041,1059,1123
Uva problems:
Minimum Spanning Tree/Dijkstra/Floyd Warshall :
10986,10034,534,544,10048,1174
Uva: Tropics BFS/MST/Dijkstra/Floyd Warshall and Level 1,2,3,4 Must try
http://uhunt.felix-halim.net/id/166232
Codeforces: Breadth First Search-- solved>2500 Must try
http://codeforces.com/problemset/tags/dfs%20and%20similar?order=BY_SOLVED_DESC

UVA 10946 You want what filled?

#include<bits/stdc++.h>
using namespace std;
long i,cnt=0,vis[55][55]={0},x,y,j,k,x1,y2;
long dx[]={-1,0,0,1};
long dy[]={0,-1,1,0};
string s[100];
void dfs(long i1,long j1,char ch1)
{
    cnt++;
    vis[i1][j1]=1;
    long i2;
    for(i2=0; i2<4; i2++)
    {
        long x1=i1+dx[i2];
        long y1=j1+dy[i2];
        if(((x1>=0&&x1<x)&&(y1>=0&&y1<y))&&vis[x1][y1]==0)
        {
            if(s[x1][y1]==ch1)
            {
                vis[x1][y1]=1;
                dfs(x1,y1,ch1);
            }
        }
    }
}
main()
{
    long cs=1;
    while(cin>>x>>y)
    {
        if(x==0&&y==0)
        {
            break;
        }
        vector<char>vec[2505];
        map<long,long>mp;
        long ar[2502]={0},k=0,j,jj;
        mp.clear();
        for(i=0;i<x;i++)
        {
            for(j=0;j<y;j++)
                vis[i][j]=0;
        }
        for(i=0;i<x;i++)
        {
                cin>>s[i];
        }
        for(i=0;i<x;i++)
        {
            for(j=0;j<y;j++)
            {
                if(s[i][j]!='.'&&vis[i][j]==0)
                {
                    char ch=s[i][j];
                    cnt=0;
                    dfs(i,j,ch);
                    vec[cnt].push_back(ch);
                    if(mp[cnt]==0)
                    {
                        ar[k++]=cnt;
                        mp[cnt]=1;
                    }
                }
            }
        }

        sort(ar,ar+k);
        cout<<"Problem "<<cs++<<":"<<"\n";
        for(j=k-1;j>=0;j--)
        {
            sort(vec[ar[j]].begin(),vec[ar[j]].end());
            long k1=vec[ar[j]].size();
            for(jj=0;jj<k1;jj++)
            {
                cout<<vec[ar[j]][jj]<<" "<<ar[j]<<endl;
            }
            vec[ar[j]].clear();
        }

    }
}