ICPC Preli 2017

C. Residential Area
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define sf1(a) scanf("%ld",&a)
#define sf2(a,b) scanf("%ld%ld",&a,&b)
#define sf3(a,b,c) scanf("%ld%ld%ld",&a,&b,&c)
#define pf1(a) printf("%ld",a)
#define pf2(a,b) printf("%ld%ld",a,b)
#define pf3(a,b,c) printf("%ld%ld%ld",a,b,c)
int main()
{
    long ts,cs=1;
    scanf("%ld",&ts);
    while(ts--)
    {
        long n,a=0,b=1,i,j,k,x,cnt=0;
        set<long>st;
        long s[20][20]= {0};
        scanf("%ld",&n);
        for(i=0; i<n; i++)
        {
            for(j=0; j<n; j++)
            {
                cin>>s[i][j];
            }
        }
        x=n-4;
        if(n<=4)
        {
            printf("Case %ld: 0\n",cs++);
            continue;
        }
        if(n==10)
        {
            for(i=0; i<n; i++)
            {
                for(j=0; j<n; j++)
                {
                    st.insert(s[i][j]);
                }
                if(st.size()==10)
                    cnt++;
                st.clear();
            }
            for(i=0; i<n; i++)
            {
                for(j=0; j<n; j++)
                {
                    st.insert(s[j][i]);
                }
                if(st.size()==10)
                    cnt++;
                st.clear();
            }
        }
        for(i=0; i<n-1; i++)
        {
            for(j=0; j<x; j++)
            {
                for(k=j; k<j+5; k++)
                {
                    st.insert(s[a][k]);
                    st.insert(s[b][k]);
                }
                if(st.size()==10)
                {
                    cnt++;
                }
                st.clear();
            }
            a++,b++;
        }
        st.clear();
        a=0,b=1,i=0,k=0,j=0;
        for(i=0; i<n-1; i++)
        {
            for(j=0; j<x; j++)
            {
                for(k=j; k<j+5; k++)
                {
                    st.insert(s[k][a]);
                    st.insert(s[k][b]);
                }
                if(st.size()==10)
                {
                    cnt++;
                }
                st.clear();
            }
            a++,b++;
        }
        printf("Case %ld: %ld\n",cs++,cnt);
    }
    return 0;
}

D. Connecting To One
#include <bits/stdc++.h>
using namespace std;
#define ll long long
struct node
{
    ll nod,cost;
    node(ll a,ll b)
    {
        nod=a;
        cost=b;
    }
    bool operator<(const node &p)const
    {

        return p.cost>cost;
    }
};
vector<pair<ll,ll> >graph[100001];
ll n,m;
ll u,v,c;
priority_queue<node>q;
ll visited[100001];
void djixtra()
{
    visited[1]=10000000000;
    q.push(node(1,10000000000));
    while(!q.empty())
    {
        node source=q.top();
        q.pop();
        ll s=source.nod;
        ll nie_asche=source.cost;
        for(ll i=0;i<graph[s].size();i++)
        {
            ll adj=graph[s][i].first;
            ll adj_cost=graph[s][i].second;
            ll update_hobe=min(adj_cost,nie_asche);
            if(visited[adj]<update_hobe)
            {
                visited[adj]=update_hobe;
                q.push(node(adj,update_hobe));
            }
        }
    }
}
vector<ll>ase;
int main()
{
    ll tes;
    scanf("%lld",&tes);
    for(ll cas=1; cas<=tes; cas++)
    {
        printf("Case %lld:\n",cas);
        scanf("%lld%lld",&n,&m);
        for(ll i=1; i<=n; i++)
        {
            graph[i].clear();
            visited[i]=LLONG_MIN;
        }
        ase.clear();
        for(ll i=1; i<=m; i++)
        {
            scanf("%lld%lld%lld",&u,&v,&c);
            graph[u].push_back(make_pair(v,c));
            graph[v].push_back(make_pair(u,c));
        }
        djixtra();
        ll qu;
        for(ll i=1;i<=n;i++)
        {
            if(visited[i]!=10000000000 && visited[i]!=LLONG_MIN)
            {
                ase.push_back(visited[i]);
            }
        }
        sort(ase.begin(),ase.end());
//        for(ll i=0;i<ase.size();i++)
//        {
//            cout<<ase[i]<<" ";
//        }
        scanf("%lld",&qu);
        for(ll j=1;j<=qu;j++)
        {
            scanf("%lld",&u);
             ll index=upper_bound(ase.begin(),ase.end(),u-1)-ase.begin();
             printf("%lld\n",ase.size()-index);
        }
    }
    return 0;
}
F. Coldplay
#include <bits/stdc++.h>
#include <math.h>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
using namespace std;
#define  fr(i,a)  for(i=0;i<a;i++)
#define  tc(i,t)  for(i=1;i<=t;i++)
#define  cln(x)   memset(x,0,sizeof(x))
#define  clr(x)   memset(x,-1,sizeof(x))
main()
{
    int p,q,y;
    while(~scanf("%d%d%d",&p,&q,&y))
    {
        int x=(y*52)*5*p;
        int z=(y*52)*2*q;
        printf("%d\n",x+z);
    }
    return 0;
}

I.Repeated Digit Sum

#include <bits/stdc++.h>
using namespace std;
main()
{
    long ts,cs=1;
    cin>>ts;
    while(ts--)
    {
        long rs,sum=0,sum1=0,i;
        string s,s1;
        cin>>s>>s1;
        for(i=0;i<s.size();i++)
        {
            sum=sum*10+s[i]-48;
            sum=sum%9;
        }
        if(sum==0)
            sum=9;
        for(i=0;i<s1.size();i++)
        {
            sum1=sum1*10+s1[i]-48;
            sum1=sum1%6;
        }
        if(sum1==0)
            sum1=6;
        rs=pow(sum,sum1)+.000000000000001;
        rs=rs%9;
        if(rs==0)
            rs=9;
        printf("Case %ld: %ld\n",cs++,rs);
    }
}

UVA 12802 - Gift From the Gods

#include <bits/stdc++.h>
#define sf1(a) scanf("%ld",&a)
#define sf2(a,b) scanf("%ld%ld",&a,&b);
#define sf3(a,b,c) scanf("%ld%ld%ld",&a,&b,&c);
using namespace std;
main()
{
    while(1)
    {
        long i,n,n1,rev=0,flag=0;
        cin>>n;
        n1=n;
        while(n!=0)
        {
            rev=rev*10+n%10;
            n/=10;
        }
        cout<<n1*2<<endl;
        for(i=2;i<rev;i++)
        {
            if(rev%i==0)
            {
                flag=1;
                break;
            }
        }
        if((flag==0)&&(rev==n1))
          break;
    }
}

How to find n when there sum is given and the series is 1+2+3+.........n=sum??

মনে করো একটা সিরিজ আছে ১+২+৩............+ N =SUM
মনে করি SUM দেওয়া আছে N বের করা লাগবে
যেখানে SUM=10^18 হতে পারে
লুপ চালিয়ে করলে টাইম লিমিট যাবে+ বের করা সম্ভব না
তাই জন্য বাইনারি সার্চ সহজ নিয়ম
কোডঃ-


#include<bits/stdc++.h>
#define LL long long
using namespace std;
int main()
{
    long ts;
    scanf("%ld",&ts);
    while(ts--)
    {
        unsigned long long s,k,hi=6074000999,low=0,mid,ans,x,xx;
        scanf("%llu",&s);
        while(hi>=low)
        {
            mid=(hi+low)/2;
            ans=1;
            if(mid%2==0)
            {
                ans=ans*(mid/2)*(mid+1);
            }
            else
            {
                ans=ans*(mid)*((mid+1)/2);
            }
            if(ans<=s)
            {
                low=mid+1;
                x=mid;
            }
            else
                hi=mid-1;
        }
        cout<<x<<endl;
    }
    return 0;
}

UVA 1197 - The Suspects

#include<bits/stdc++.h>
using namespace  std;
long long  par[50010],vis[50010];
long long find(long long s)
{
    if(par[s]==s)
    {
        return s;
    }
    return par[s]=find(par[s]);
}
void unionkorlam(long long x,long long y)
{
    if(find(x)!=find(y))
        par[find(y)]=find(x);
}
main()
{
    long long n,m,cs=1;
    while(cin>>n>>m)
    {
        if(n==0&&m==0)
            break;
        long i,n1,a,aa,xx,yy,j,cnt=0;
        for(i=0;i<=n;i++)
            par[i]=i;
        for(i=1;i<=m;i++)
        {
            cin>>n1;
            cin>>a;
            xx=find(a);
            for(j=1;j<n1;j++)
            {
                cin>>aa;
                yy=find(aa);
                if(xx!=yy)
                {
                    unionkorlam(a,aa);
                }
            }
        }
        xx=find(0);
        for(i=0;i<n;i++)
        {
            if(xx==find(i))
            {
                cnt++;
            }
        }
        cout<<cnt<<endl;
    }
}

UVA-10583 Ubiquitous Religions

#include<bits/stdc++.h>
using namespace  std;
long long  par[50010],vis[50010];
long long find(long long s)
{
    if(par[s]==s)
    {
        return s;
    }
    return par[s]=find(par[s]);
}
void unionkorlam(long long x,long long y)
{
    if(find(x)!=find(y))
        par[find(y)]=find(x);
}
main()
{
    long long n,m,cs=1;
    while(cin>>n>>m)
    {
        if(n==0&&m==0)
            break;
        long long i,a,b,cnt=0;
        for(i=1; i<=n; i++)
        {
            vis[i]=0;
            par[i]=i;
        }
        for(i=1; i<=m; i++)
        {
            cin>>a>>b;
            unionkorlam(a,b);
        }
        for(i=1; i<=n; i++)
        {
            long long xx=find(i);
            if(vis[xx]==0)
            {
                cnt++;
                vis[xx]=1;
            }
        }
        printf("Case %lld: ",cs++);
        cout<<cnt<<endl;

    }
}

UVA 11690 - Money Matters

# include<sstream>
# include<bits/stdc++.h>
using namespace std;
long par[50010];
long find(long xx)
{
    if(par[xx]==xx)
        return xx;
    return par[xx]=find(par[xx]);
}
void unionkorlam(long a,long b)
{
    if(find(a)!=find(b))
    {
        par[find(b)]=find(a);
    }
}
main()
{
    long ts;
    cin>>ts;
    while(ts--)
    {
        long n,m,i,x,y,tot[50010]={0},flag=0,ar[50010]={0},yy;
        cin>>n>>m;
        for(i=0;i<n;i++)
        {
            cin>>ar[i];
            par[i]=i;
        }
        for(i=0;i<m;i++)
        {
            cin>>x>>y;
            unionkorlam(x,y);
        }
        for(i=0;i<n;i++)
        {
            yy=find(i);
            tot[yy]+=ar[i];
        }
        for(i=0;i<n;i++)
        {
            if(tot[i]<0)
            {
                flag=1;
            }
        }
        if(flag==1)
        {
            cout<<"IMPOSSIBLE"<<endl;
        }
        else
            cout<<"POSSIBLE"<<endl;
    }
}

UVA 11094 - Continents

#include <bits/stdc++.h>
using namespace std;
#define mxx 25;
//string s[25];
char s[25][25],x;
int vis[25][25],n,m,cnt;
int floodfill(int i1,int j1)
{
    int cnt=1;
    if(j1==m)
        j1=0;
    else if(j1==-1)
        j1=m-1;
    if(i1<0||i1>=n||j1<0||j1>=m)
         return 0;
    if(vis[i1][j1])
         return 0;
    if(s[i1][j1] != x)
        return 0;
    vis[i1][j1]=1;
    cnt+=floodfill(i1,j1+1);
    cnt+=floodfill(i1-1,j1);
    cnt+=floodfill(i1,j1-1);
    cnt+=floodfill(i1+1,j1);
    return cnt;
}
int main()
{
    while(cin>>n>>m)
    {
        int i,a,b,j,ans=0,mx=0;
        for(i=0;i<n;i++)
        {
            cin>>s[i];
        }
        cin>>a>>b;
        x=s[a][b];
        floodfill(a,b);
        for(i=0;i<n;i++)
        {
            for(j=0;j<m;j++)
                {
                    if(s[i][j]==x)
                    {
                        cnt=0;
                        ans=floodfill(i,j);
                        mx=max(mx,ans);
                    }
                }
        }
        cout<<mx<<endl;
        for(i=0;i<n;i++)
        {
            for(j=0;j<m;j++)
            vis[i][j]=0;
        }
    }
}