মঙ্গলবার, ৩০ অক্টোবর, ২০১৮

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;
}
এই সময়ে কোন মন্তব্য নেই:
এতে সদস্যতা: পোস্টগুলি (Atom)

Factory Pattern

Factory Method  is a creational design pattern that provides an interface for creating objects in a superclass but allows subclasses to alte...