Advertisement
Guest User

Untitled

a guest
Oct 10th, 2019
107
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.42 KB | None | 0 0
  1. #include <fstream>
  2. #include <vector>
  3. #include <algorithm>
  4.  
  5. using namespace std;
  6.  
  7. ifstream cin("test.in");
  8. ofstream cout("test.out");
  9.  
  10. struct pr
  11. {
  12. int first, second;
  13. bool third;
  14. };
  15.  
  16. vector < pr > v(370);
  17. vector < pair<int, int> > John;
  18. vector < bool > JohnFrecventa(370);
  19. int maxx;
  20. int s, nr;
  21.  
  22. bool cmp(pair<int, int> a, pair<int, int> b)
  23. {
  24. if(a.first != b.first)
  25. return a.first < b.first;
  26. return a.second > b.second;
  27. }
  28.  
  29. void backt(int poz, int val, int limita)
  30. {
  31. if(s == val || nr == 4)
  32. return ;
  33.  
  34. // cout << poz << ' ' << val << ' ' << limita << '\n';
  35.  
  36. // if(poz == 3 && val == 150 && limita == 4)
  37. // cout << "AICI " << s << ' ' << nr << '\n';
  38.  
  39. for(int i = 0 ; i < John.size() ; i++)
  40. {
  41.  
  42.  
  43. if(s + John[i].second <= val && !JohnFrecventa[i]
  44. && John[i].first >= poz && John[i].first <= limita )
  45. {
  46. s += John[i].second, nr++;
  47. JohnFrecventa[i] = 1;
  48.  
  49. if(s == val && nr <= 4)
  50. return;
  51.  
  52. backt(poz, val, limita);
  53.  
  54. if(s == val && nr <= 4)
  55. return;
  56. nr--;
  57. s -= John[i].second;
  58. JohnFrecventa[i] = 0;
  59. }
  60. }
  61.  
  62.  
  63. return ;
  64. }
  65.  
  66. void rez()
  67. {
  68. char ch;
  69. int poz;
  70. int val, limita;
  71. while(cin >> ch )
  72. {
  73. if(ch == 'F')
  74. {
  75. cin >> poz >> limita >> val;
  76. v[poz].first = val, v[poz].second = limita,
  77. v[poz].third = 0;
  78. }
  79.  
  80. else break;
  81. }
  82.  
  83. //v[poz].first = val, v[poz].second = limita, v[poz].third = 0;
  84. cin >> poz >> val;
  85. John.push_back(make_pair(poz, val));
  86.  
  87. while(cin >> ch >> poz >> val )
  88. John.push_back(make_pair(poz, val));
  89.  
  90. //cout << "JON " << John.size() << '\n';
  91. sort(John.begin(), John.end(), cmp);
  92.  
  93.  
  94.  
  95. for(int i = 1 ; i <= 365 ; i++)
  96. if(v[i].first)
  97. {
  98. s = 0, nr = 0;
  99. backt(i, v[i].first, v[i].second);
  100.  
  101. if(s == v[i].first && nr <= 4)
  102. v[i].third= 1;
  103. //cout << v[i].third << ' ' << i << ' ' <<
  104. // v[i].first << ' ' << s << " " << nr << '\n';
  105.  
  106. }
  107.  
  108. }
  109.  
  110. void print()
  111. {
  112. for(int i = 1 ; i <= 365 ; i++)
  113. if(!v[i].third && v[i].first)
  114. cout << i << ' ';
  115. }
  116.  
  117. int main()
  118. {
  119. rez();
  120. print();
  121. return 0;
  122. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement