শনিবার, ৬ অক্টোবর, ২০১৮

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...