Source code for submission s1049

Go to diff to previous submission

fm.cpp

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstdlib>
  4. #include <vector>
  5. #include <map>
  6. #include <set>
  7. #include <string>
  8. #include <cmath>
  9. #include <algorithm>
  10. #include <queue>
  11. #include <utility>
  12.  
  13. using namespace std;
  14.  
  15.  
  16. vector<vector<char> > mapka;
  17. vector<int> intervalac;
  18.  
  19. int AR,AC,TR,TC, mocnina;
  20.  
  21. int spusti(int vrchol, pair<int,int> LH, pair<int,int> PD){
  22. if(PD.first-LH.first==1) {
  23. if(mapka[LH.first][LH.second]=='X') {
  24. intervalac[vrchol] = 1;
  25. return 1;
  26.  
  27. }
  28. else return 0;
  29. }
  30.  
  31. intervalac[vrchol] = spusti(vrchol * 4 + 1, LH, make_pair((LH.first + PD.first) / 2, (LH.second + PD.second) / 2))
  32. + spusti(vrchol * 4 + 2, make_pair((LH.first + PD.first) / 2, LH.second), make_pair (PD.first, (PD.second + LH.second) / 2))
  33. + spusti(vrchol * 4 + 3, make_pair(LH.first, (LH.second + PD.second) / 2), make_pair ((PD.first + LH.first) / 2, PD.second))
  34. + spusti(vrchol * 4 + 4, make_pair((LH.first + PD.first) / 2, (LH.second + PD.second) / 2), PD);
  35.  
  36. return intervalac[vrchol];
  37. }
  38.  
  39. int pocet(int vrchol, pair<int,int> LH, pair<int,int> PD, pair<int,int> HlaLH, pair<int,int> HlaPD){
  40. if(HlaLH.first <= LH.first && HlaLH.second <= LH.second && HlaPD.first >= PD.first && HlaPD.second >= PD.second)
  41. return intervalac[vrchol];
  42. else if (HlaLH.first >= PD.first || HlaLH.second >= PD.second || HlaPD.first <= LH.first || HlaPD.second <= LH.second) return 0;
  43. else {
  44.  
  45. return pocet(vrchol * 4 + 1, LH, make_pair((LH.first + PD.first) / 2, (LH.second + PD.second) / 2), HlaLH, HlaPD)
  46. + pocet(vrchol * 4 + 2, make_pair((LH.first + PD.first) / 2, LH.second), make_pair (PD.first, (PD.second + LH.second) / 2), HlaLH, HlaPD)
  47. + pocet(vrchol * 4 + 3, make_pair(LH.first, (LH.second + PD.second) / 2), make_pair ((PD.first + LH.first) / 2, PD.second), HlaLH, HlaPD)
  48. + pocet(vrchol * 4 + 4, make_pair((LH.first + PD.first) / 2, (LH.second + PD.second) / 2), PD, HlaLH, HlaPD);
  49.  
  50. }
  51.  
  52. }
  53.  
  54. int skus(int x, int y){
  55. int vys = 0;
  56.  
  57. for(int i = x; i + TR < mocnina; i += TR){
  58. for(int j = y; j + TC < mocnina; j += TC){
  59.  
  60. //cout<<"od: ["<<i<<", "<<j<<"] po ["<<i+TR<<", "<<j+TC<<"] to je "<<pocet (0, make_pair(0,0), make_pair(mocnina,mocnina), make_pair(i,j), make_pair(i + TR, j + TC))<<endl;
  61.  
  62. if(pocet (0, make_pair(0,0), make_pair(mocnina,mocnina), make_pair(i,j), make_pair(i + TR, j + TC)) > 0) vys++;
  63. }
  64. }
  65.  
  66. return vys;
  67. }
  68.  
  69.  
  70. int main(){
  71. while(scanf("%d%d%d%d",&AR,&AC,&TR,&TC)!=EOF){
  72.  
  73.  
  74. mapka.clear();
  75. intervalac.clear();
  76.  
  77. mocnina = 1;
  78. while(mocnina < TR+TR+AR+TR+TR) mocnina *= 2;
  79.  
  80. while(mocnina < TC+TC+AC+TC+TC) mocnina *= 2;
  81.  
  82. mapka.resize(mocnina, vector<char> (mocnina,'.'));
  83.  
  84. intervalac.resize(mocnina * mocnina * 2, 0);
  85.  
  86. int pocetK=0;
  87. for(int i = 0; i < AR; i++){
  88. string riadok;
  89. cin>>riadok;
  90. for(int j = 0; j < riadok.size(); j++){
  91. mapka[i + TR * 2][j + TC * 2] = riadok[j];
  92. if(riadok[j] == 'X') pocetK++;
  93. }
  94. }
  95.  
  96. if(TR == 1 && TC == 1) {cout<<pocetK<<endl; continue;}
  97.  
  98. spusti(0,make_pair(0,0), make_pair(mocnina, mocnina));
  99.  
  100. /* for(int i = 0; i < mocnina; i++){
  101.   for(int j=0; j< mocnina; j++){
  102. cout<<mapka[i][j];
  103.  
  104.   }
  105.   cout<<endl;
  106.   }
  107.  
  108.   for(int i =0; i< mocnina * mocnina ; i++){
  109.   cout<<intervalac[i]<<" ";
  110.   }*/
  111.  
  112. int najmensie = 100000000;
  113.  
  114. for(int i = 0; i < TR; i++){
  115. for(int j = 0; j < TC; j++){
  116. najmensie = min(skus(i,j), najmensie);
  117. }
  118.  
  119. }
  120.  
  121. cout<<najmensie<<endl;
  122.  
  123. }
  124.  
  125. }

Diff to submission s1038

fm.cpp

--- c5.s1038.cteam090.fm.cpp.0.fm.cpp
+++ c5.s1049.cteam090.fm.cpp.0.fm.cpp
@@ -71,4 +71,5 @@
   while(scanf("%d%d%d%d",&AR,&AC,&TR,&TC)!=EOF){
     
+    
     mapka.clear();
     intervalac.clear();
@@ -83,4 +84,5 @@
     intervalac.resize(mocnina * mocnina * 2, 0);
     
+    int pocetK=0;
     for(int i = 0; i < AR; i++){
       string riadok;
@@ -88,7 +90,10 @@
       for(int j = 0; j < riadok.size(); j++){
         mapka[i + TR * 2][j + TC * 2] = riadok[j];
+        if(riadok[j] == 'X') pocetK++;
       }
     }
     
+    if(TR == 1 && TC == 1) {cout<<pocetK<<endl; continue;}
+    
     spusti(0,make_pair(0,0), make_pair(mocnina, mocnina));