UVA 1213 - Sum of Different Primes

///...................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("%d",&a)
#define sf2(a,b) scanf("%d %d",&a,&b)
#define sf3(a,b,c) scanf("%d %d %d",&a,&b,&c)
#define pf(a) printf("%d",a)
#define pf2(a,b) printf("%d %d",a,b)
#define pf3(a,b,c) printf("%d %d %d",a,b,c)
#define sfl(a) scanf("%lld",&a)
#define sfl2(a,b) scanf("%lld %lld",&a,&b)
#define sfl3(a,b,c) scanf("%lld %lld %lld",&a,&b,&c)
#define pfl(a) printf("%lld",a)
#define pfl2(a,b) printf("%lld %lld",a,b)
#define pfl3(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++)
#define tz 100000
/*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 vis[1500];
vector<int>vec;
void sieve()
{
    int i,j;
    for(i=2;i<=1129;i++)
    {
        if(vis[i]==0)
        {
            vec.push_back(i);
            for(j=2*i;j<=1129;j+=i)
            {
                vis[j]=1;
            }
        }
    }
}
int ways[1130][16];
void precalc()
{
    for(int n=0;n<=1120;n++)
    {
        for(int k=0;k<=14;k++)
        {
            ways[n][k]=0;
        }
    }
    ways[0][0]=1;
    for(int i=0;i<vec.size();i++)
    {
        for(int n=1120;n>=vec[i];n--)
        {
            for(int k=1;k<=14;k++)
            {
                ways[n][k]+=(ways[n-vec[i]][k-1]);
            }
        }
    }
}
main()
{
    sieve();
    //cout<<vec.size()<<endl;
    precalc();
    int n,k;
    while(cin>>n>>k)
    {
        if(n==0&&k==0)
            break;
        cout<<ways[n][k]<<endl;
    }
}

UVA 1246 - Find Terrorists

///...................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("%d",&a)
#define sf2(a,b) scanf("%d %d",&a,&b)
#define sf3(a,b,c) scanf("%d %d %d",&a,&b,&c)
#define pf(a) printf("%d",a)
#define pf2(a,b) printf("%d %d",a,b)
#define pf3(a,b,c) printf("%d %d %d",a,b,c)
#define sfl(a) scanf("%lld",&a)
#define sfl2(a,b) scanf("%lld %lld",&a,&b)
#define sfl3(a,b,c) scanf("%lld %lld %lld",&a,&b,&c)
#define pfl(a) printf("%lld",a)
#define pfl2(a,b) printf("%lld %lld",a,b)
#define pfl3(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++)
#define tz 100000
/*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 vis[1003];
int divisor[10005];
vector<int>vec;
void sieve()
{
    int i,j,k;
    vis[1]=1;
    vis[0]=1;
    int sz=1003;
    for(i=2; i<=1003; i++)
    {
        if(vis[i]==0)
        {
            for(j=2*i;j<=sz;j+=i)
            {
                //cout<<j<<endl;
                vis[j]=1;
            }
        }
    }
    divisor[0]=0;
    for(i=1;i<=10005;i++)
    {
        int nm=i,cnt=0;
        for(j=1;j<=sqrt(nm);j++)
        {
            if(nm%j==0)
            {
                cnt++;
                if((nm/j)!=j)
                    cnt++;
            }
        }
        divisor[i]=cnt;
    }
}
main()
{
   // timesave;
    int ts;
    sieve();
    cin>>ts;
    while(ts--)
    {
        int l,h,i,flag=0,chk=0;
        cin>>l>>h;
        for(i=l;i<=h;i++)
        {
            //cout<<i<<" "<<vis[divisor[i]]<<endl;
            if(vis[divisor[i]]==0)
            {
                if(flag==1)
                {
                    printf(" ");
                }
                cout<<i;
                chk=flag=1;
            }
        }
        if(chk==0)
            cout<<-1;
        cout<<endl;
    }
}

UVA 11086 - Composite Prime

///...................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("%d",&a)
#define sf2(a,b) scanf("%d %d",&a,&b)
#define sf3(a,b,c) scanf("%d %d %d",&a,&b,&c)
#define pf(a) printf("%d",a)
#define pf2(a,b) printf("%d %d",a,b)
#define pf3(a,b,c) printf("%d %d %d",a,b,c)
#define sfl(a) scanf("%lld",&a)
#define sfl2(a,b) scanf("%lld %lld",&a,&b)
#define sfl3(a,b,c) scanf("%lld %lld %lld",&a,&b,&c)
#define pfl(a) printf("%lld",a)
#define pfl2(a,b) printf("%lld %lld",a,b)
#define pfl3(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++)
#define tz 100000
/*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 vis[1000100];
vector<int>vec;
void sieve()
{
    int i,j,k;
    vis[1]=1;
    int sz=1000000;
    for(i=2; i<=1000000; i++)
    {
        if(vis[i]==0)
        {
            vec.push_back(i);
            //for(k=sz/i,j=i*k;k>=i;k--,j-=i)
            for(j=2*i;j<=sz;j+=i)
            {
                //cout<<j<<endl;
                vis[j]=1;
            }
        }
    }
}
int chk(int number)
{
    int i,j;
    for(i=0;i<vec.size()&&vec[i]*vec[i]<=number;i++)
    {
        if(number%vec[i] == 0)
        {
            j = number/vec[i];
            if(vis[j]==0)
                return 1;
        }
    }
    return 0;
}
main()
{
    timesave;
    int n;
    sieve();
    while(cin>>n)
    {
        int i,a,cnt=0;
        for(i=0; i<n; i++)
        {
            cin>>a;
            if(chk(a))
             cnt++;
        }
        cout<<cnt<<endl;
    }
}

UVA 990 - Diving for Gold

///...................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("%d",&a)
#define sf2(a,b) scanf("%d %d",&a,&b)
#define sf3(a,b,c) scanf("%d %d %d",&a,&b,&c)
#define pf(a) printf("%d",a)
#define pf2(a,b) printf("%d %d",a,b)
#define pf3(a,b,c) printf("%d %d %d",a,b,c)
#define sfl(a) scanf("%lld",&a)
#define sfl2(a,b) scanf("%lld %lld",&a,&b)
#define sfl3(a,b,c) scanf("%lld %lld %lld",&a,&b,&c)
#define pfl(a) printf("%lld",a)
#define pfl2(a,b) printf("%lld %lld",a,b)
#define pfl3(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++)
#define tz 100000
/*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 t,w,ar[31],br[31],dp[31],mx,n,path[31];
void update()
{
    int i,sum=0;
    for(i=0; i<n; i++)
    {
        if(dp[i])
        {
            sum+=br[i];
        }
    }
    if(sum>mx)
    {
        mx=sum;
        for(i=0; i<n; i++)
        {
            path[i]=dp[i];
        }
    }
}
void call(int i,int baki)
{
    if(i==n)
    {
        update();
        return;
    }
    dp[i]=0;
    call(i+1,baki);
    dp[i]=1;
    if(baki>=3*w*ar[i])
    {
        call(i+1,baki-3*w*ar[i]);
    }
}
int flag=1;
void print()
{
    int i,cnt;
    if(!flag)
        cout<<endl;
    else
        flag=0;
    cout<<mx<<endl;
    cnt=0;
    for(i=0;i<n;i++)
        if(path[i])
            cnt++;
    cout<<cnt<<endl;
    for(i=0;i<n;i++)
    {
        if(path[i])
        {
            cout<<ar[i]<<" "<<br[i]<<endl;
        }
    }
}
main()
{
    flag=1;
    while(cin>>t>>w)
    {
        int i1;
        cin>>n;
        for(i1=0; i1<n; i1++)
        {
            cin>>ar[i1]>>br[i1];
        }
        call(0,t);
        print();
    }
}

LOJ-1129 Using TRIE (Find is the string is prefix of another string)

SETI is receiving some weird signals for the past few days. After converting them to our number system they found out that some numbers are repeating. Due to travelling millions of miles signal gets distorted. Now they asked you check the consistency of their data sets. The consistency is that, no number is the prefix another number in that data set. Let's consider a data set:

1.      123

2.      5123456

3.      123456

In this data set, numbers not consistent, because the first number is the prefix of the third one.

Input starts with an integer T (≤ 50), denoting the number of test cases.

Each case starts with an integer n (1 ≤ n ≤ 10000) denoting the total numbers in their list. Each of the next n lines contains one unique phone number. A number is a sequence of digits and has length from 1 to 10.

input:

2

3

911

97625999

91125426

5

113

12340

123440

12345

98346

output:

Case 1: NO

Case 2: YES

#include<bits/stdc++.h>
using namespace std;
long long n, m, t, cs=1, i, j, last=1, xx, cur, k, x, fl;
string s;

struct trie
{
    bool endmark;
    int next[11];
} r[100009];

void new_trie(int cur)
{
    for(int zz=0; zz<10; zz++)
        r[cur].next[zz]=-1;
    r[cur].endmark=false;
}

void insrt()
{
    cur=0, k=s.size();
    for(int z=0; z<k; z++)
    {
        x=(int)s[z]-48;
        if(r[cur].next[x]==-1)
        {
            r[cur].next[x]=last;
            new_trie(last++);
            cur=r[cur].next[x];
        }
        else
        {
            cur=r[cur].next[x];
            if(r[cur].endmark==true)
                fl=1;
            if(z==k-1)
                fl=1;
        }
        if(fl==1)
            break;
    }
    r[cur].endmark=true;
}

int main()
{
    cin>>t;
    while(t--)
    {
        cin>>n;
        fl=0, last=1;
        new_trie(0);
        for(i=0; i<n; i++)
        {
            cin>>s;
            insrt();
        }
        cout<<"Case "<<cs++<<": ";
        if(fl==1)
            cout<<"NO"<<endl;
        else
            cout<<"YES"<<endl;
    }
    return 0;
}

ICPC DHAKA REGIONAL PRELIMINARY CONTEST, 2019

B. The Social Network

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

#define mx 100005
typedef vector <int> VI;

int n, q;
int par[mx];
VI tmp[mx];
bitset <mx> mark;

int fnd(int u) {
    if (par[u] == u) return u;
    return par[u] = fnd(par[u]);
}

int main() {
//    freopen("../templates/in", "r", stdin);
    int tc; scanf("%d", &tc);
    int t = 0;
    while (tc--) {
        mark = 0;
        scanf("%d %d",&n, &q);
        for (int i = 1; i <= n; i++) {
            par[i] = i;
            tmp[i].clear();
        }

        printf("Case %d:\n", ++t);
        while (q--) {
            int c; scanf("%d", &c);
            if (c == 0) {
                int u, v; scanf("%d %d", &u, &v);
                int pu = fnd(u);
                int pv = fnd(v);
                if (pu == pv) continue;
                if (tmp[pu].size() > tmp[pv].size()) {
                    swap(pu, pv);
                }

                for (auto x : tmp[pu]) tmp[pv].push_back(x);
                par[pu] = pv;
                mark[pv] = 1;
            } else if (c == 1) {
                int u, T;
                scanf("%d %d", &u, &T);
                int pu = fnd(u);
                tmp[pu].push_back(T);
                mark[pu] = 1;
            } else {
                int u, l, r;
                scanf("%d %d %d", &u, &l, &r);
                int pu = fnd(u);
                int ans = 0;
                if (mark[pu]) {
                    sort(tmp[pu].begin(), tmp[pu].end());
                    mark[pu] = 0;
                }

                auto lt = lower_bound(tmp[pu].begin(), tmp[pu].end(), l);
                auto rt = upper_bound(tmp[pu].begin(), tmp[pu].end(), r);

                if (rt > lt) ans = rt - lt;
                printf("%d\n", ans);
            }
        }
    }
}

C. ICGeSi Standings

#include<bits/stdc++.h>

using namespace std;

main()

{

    int ts,cs=1;

    scanf("%d",&ts);

    while(ts--)

    {

        int n,ns[75]= {0},tp[75]= {0},frozen[75][75]= {0},flag=0,i,j,fro_solve[75]= {0};

        scanf("%d",&n);

        int a,b,c,m;

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

        {

            scanf("%d%d%d",&a,&b,&c);

            ns[a]=b;

            tp[a]=c;

            scanf("%d",&m);

            fro_solve[a]=m;

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

            {

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

            }

        }

        int rnk;

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

        {

            cin>>rnk;

            int n_s, t_p;

            if(i==1)

            {

                ns[rnk]+=fro_solve[rnk];

                for(j=1; j<=fro_solve[rnk]; j++)

                {

                    tp[rnk]+=frozen[rnk][j];

                }

                n_s=ns[rnk];

                t_p=tp[rnk];

            }

            else

            {

                if(n_s>=ns[rnk])

                {

                    if(n_s==ns[rnk]&&t_p>tp[rnk])

                    {

                        flag=1;

                    }

                }

                else

                {

                    flag=1;

                }

                for(j=1; j<=fro_solve[rnk]; j++)

                {

                    if(n_s>=ns[rnk])

                    {

                        if(n_s==ns[rnk]&&t_p>tp[rnk])

                        {

                            flag=1;

                            break;

                        }

                        else

                        {

                            if(n_s-1>ns[rnk])

                            {

                                tp[rnk]+=frozen[rnk][j];

                                ns[rnk]+=1;

                            }

                            else if((n_s>ns[rnk])&&(t_p<=(tp[rnk]+frozen[rnk][j])))

                            {

                                tp[rnk]+=frozen[rnk][j];

                                ns[rnk]+=1;

                            }

                            else

                            {

                                break;

                            }

                        }

                    }

                    else

                    {

                        flag=1;

                        break;

                    }

                }

                n_s=ns[rnk];

                t_p=tp[rnk];

            }

        }

        if(flag==0)

        {

            printf("Case %d: We respect our judges :)\n",cs++);

        }

        else

        {

            printf("Case %d: Say no to rumour >:\n",cs++);

        }

    }

}

B. The Social Network

#include<bits/stdc++.h>

using namespace std;

#define max 10000007

int phi[max],sz=10000001;

long long com[max];

void phi_calc()

{

    int  i,j,cnt=0;

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

    {

        if(phi[i]==0)

        {

            phi[i]=i-1;

            for(j=i*2; j<max; j=j+i)

            {

                cnt++;

                if(phi[j]==0)

                {

                    phi[j]=j;

                }

                phi[j]=phi[j]-(phi[j]/i);

            }

        }

    }

    unsigned   long long s,d=0;

    com[1]=1;

    for(s=2; s<max; s++)

    {

        com[s]=com[s-1]+(long long)phi[s];

    }

}

main()

{

    phi_calc();

    int ts,cs=1;

    scanf("%d",&ts);

    while(ts--)

    {

        long long n;

        long long p;

        scanf("%lld%lld",&n,&p);

        long long  ind=lower_bound(com,com+sz,p)-com;

        long long ans=n/ind;

        if(ans==0)

            ans=-1;

        printf("Case %d: %lld\n",cs++,ans);

    }

}

Big fibonacci by matrix expo

Fibonacci sequence is a recursive sequence that depends on the following definition:

Fib(N) = Fib(N-1) + Fib(N-2)
Fib(0) = 0 
Fib(1) = 1

In this problem you have to calculate this simple function. Given N, you have to calculate Fib(N) modulo 1000000007.

Input contains a single line, N (1 ≤ N ≤ 109 ).

#include <bits/stdc++.h> using namespace std;
#define pb push_back #define MX 1e18 #define mod 1000000009 #define ff first #define ss second #define MAX_N 2 typedef long long ll; const ll MATMOD = 1000000007; struct Matrix{ ll mat[MAX_N][MAX_N]; int row , col; Matrix(){ row = MAX_N; col = MAX_N; init(); }; Matrix(int r,int c){ row = r; col = c; init(); } void init(){ memset(mat,0,sizeof mat); } void identity(){ for(int i=0;i<row;i++)mat[i][i] = 1; } void printMatrix(){ for(int i=0;i<row;i++){ for(int j=0;j<col;j++){ cout<<mat[i][j]<<" "; }cout<<endl; } } void getMatrix(){ for(int i=0;i<row;i++){ for(int j=0;j<col;j++){ scanf("%d",&mat[i][j]); } } } }; Matrix matMul(Matrix a, Matrix b){ Matrix c ; for(int i=0;i<MAX_N;i++){ for(int j=0;j<MAX_N;j++){ for(int k=0;k<MAX_N;k++){ c.mat[i][j] = (c.mat[i][j] + (a.mat[i][k] * b.mat[k][j])%MATMOD )%MATMOD; } } } return c; } Matrix matPow(Matrix A, ll p){ Matrix res; res.identity(); while(p){ if(p & 1)res = matMul(res,A); A = matMul(A, A); p >>= 1; } return res; } int main(int argc, char const *argv[]) { Matrix A,C; Matrix x; A.mat[0][0] = 0; A.mat[0][1] = 1; A.mat[1][0] = 1; A.mat[1][1] = 1; C.mat[0][0] = 0; C.mat[1][0] = 1; int n; scanf("%d", &n); x = matPow(A,n); x = matMul(x,C); printf("%lld\n", x.mat[0][0]); return 0; }