বৃহস্পতিবার, ৩১ অক্টোবর, ২০১৯

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);
    }
}

এই সময়ে কোন মন্তব্য নেই:
এতে সদস্যতা: পোস্টগুলি (Atom)

Factorization with prime Sieve

vector <int> prime; char sieve[1000009]; int N=1000009; void primeSieve ( ) { sieve[0] = sieve[1] = 1; prime.push_back(2); ...

  • UVA 10139 - Factovisors
    #include<bits/stdc++.h> using namespace std; main() {     long long n,m;     while(cin>>n>>m)     {         if(m==...
  • Count square numbers in a range(n,m)
    Input : n = 5, m = 100 Output : 8 The numbers with odd factors are 9, 16, 25, 36, 49, 64, 81 and 100 Input : n = 8, m = 65 Output : 6 ...
  • UVA 443 - Humble Numbers
    #include<bits/stdc++.h> using namespace std; vector<long long>vec; void calc() {     long i,i1,i2,i3;     for(i=0;i<31...