SHARE
TWEET

problema

a guest May 21st, 2019 71 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <fstream>
  3. #include <cstring>
  4. #include <map>
  5. #include <algorithm>
  6. #include <string>
  7.  
  8. using namespace std;
  9.  
  10. ifstream fin("catchy.in");
  11. ofstream fout("catchy.out");
  12.  
  13. #define NMAX 100000
  14.  
  15. int banner[NMAX],poz;
  16. int n,m,maxx,minn,ind,fr[NMAX],k;
  17. char cuv[NMAX][30];
  18. char sir[NMAX],sep[]=" ,:;)(.?!><}{",*p;
  19. char mat[NMAX][30];
  20. int nrcuv;
  21.  
  22. int cauta(char cuv[],int k,char mat[NMAX][30])
  23. {
  24.     for(int i=1; i<=k; i++)
  25.         if(strcmp(mat[i],cuv)==0)
  26.             return i;
  27.     return 0;
  28. }
  29.  
  30. int binar(char a[])
  31. {
  32.     int st=1,dr=nrcuv,mij;
  33.     while(st<=dr)
  34.     {
  35.         mij=(st+dr)/2;
  36.         if(strcmp(cuv[mij],a)==0)
  37.             return mij;
  38.         if(strcmp(cuv[mij],a)>0)
  39.             dr=mij-1;
  40.         else st=mij+1;
  41.     }
  42.     return 0;
  43. }
  44.  
  45.  
  46.  
  47. int main()
  48. {
  49.     fin>>n;
  50.     fin.get();
  51.     for(int i=1; i<=n; i++)
  52.     {
  53.         fin.getline(sir,NMAX);
  54.         p=strtok(sir,sep);
  55.         while(p)
  56.         {
  57.             poz=cauta(p,nrcuv,cuv);
  58.             if(poz==0)
  59.             {
  60.                 nrcuv++;
  61.                 strcpy(cuv[nrcuv],p);
  62.                 banner[nrcuv]=1;
  63.             }
  64.             else
  65.                 banner[poz]++;
  66.             p=strtok(NULL,sep);
  67.         }
  68.     }
  69.  
  70.     for(int i=1; i<nrcuv; i++)
  71.         for(int j=i+1; j<=nrcuv; j++)
  72.             if(strcmp(cuv[i],cuv[j])>0)
  73.             {
  74.                 swap(cuv[i],cuv[j]);
  75.                 swap(banner[i],banner[j]);
  76.             }
  77.  
  78.     fin>>m;
  79.     fin.get();
  80.     for(int i=1; i<=m; i++)
  81.     {
  82.         fin.getline(sir,NMAX);
  83.         k=0;
  84.         p=strtok(sir,sep);
  85.         while(p)
  86.         {
  87.             int poz=cauta(p,k,mat);
  88.             if(poz==0)
  89.             {
  90.                 k++;
  91.                 strcpy(mat[k],p);
  92.                 fr[k]=1;
  93.             }
  94.             else
  95.                 fr[poz]++;
  96.             p=strtok(NULL,sep);
  97.         }
  98.  
  99.         bool ok=1;
  100.         minn=999999999;
  101.         for(int j=1; j<=k; j++)
  102.         {
  103.             poz=binar(mat[j]);
  104.             if(poz==0 || banner[poz]<fr[j])
  105.             {
  106.                 ok=0;
  107.                 break;
  108.             }
  109.             minn=min(minn,banner[poz]/fr[j]);
  110.         }
  111.  
  112.         if(ok==1)
  113.         {
  114.             if(minn>maxx)
  115.             {
  116.                 ind=i;
  117.                 maxx=minn;
  118.             }
  119.         }
  120.     }
  121.  
  122.     fout<<ind<<endl<<maxx;
  123.  
  124.     return 0;
  125. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top