Advertisement
Guest User

problema

a guest
May 21st, 2019
89
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.39 KB | None | 0 0
  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. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement