DuongNhi99

COLLECT

Dec 10th, 2020 (edited)
109
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.10 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int N = 1005;
  5.  
  6. typedef pair<int, pair<int, int> > piii;
  7.  
  8. int n, k;
  9. int z, s, m, z0, s0, m0;
  10. int change[N][6];
  11.  
  12. queue<int> qx, qy, qz;
  13. map<piii, int> ma;
  14. vector<piii> res;
  15.  
  16. void solve() {
  17.     while(!qx.empty()) {
  18.         int z = qx.front(); qx.pop();
  19.         int s = qy.front(); qy.pop();
  20.         int m = qz.front(); qz.pop();
  21.  
  22.         if(z >= z0 && s >= s0 && m >= m0) {
  23.             res.push_back(make_pair(z, make_pair(s, m)));
  24.             continue;
  25.         }
  26.  
  27.         int step = ma[make_pair(z, make_pair(s, m))];
  28.         if(step >= k) continue;
  29.  
  30.         for(int i = 1;  i <= n; ++i) {
  31.             if(z >= change[i][1] && s >= change[i][2] && m >= change[i][3]) {
  32.                 int nz = z - change[i][1] + change[i][4];
  33.                 int ns = s - change[i][2] + change[i][5];
  34.                 int nm = m - change[i][3] + change[i][6];
  35.  
  36.                 if(nz > 4 || ns  > 4 || nm  > 4) continue;
  37.  
  38.                 piii state = make_pair(nz, make_pair(ns, nm));
  39.                 if(!ma.count(state)) {
  40.                     ma[state] = step + 1;
  41.                     qx.push(nz);
  42.                     qy.push(ns);
  43.                     qz.push(nm);
  44.                 }
  45.             }
  46.         }
  47.     }
  48.  
  49.     if(res.size() == 0)
  50.         cout << -1 << '\n';
  51.     else {
  52.         sort( res.begin(), res.end());
  53.  
  54.         cout << res.size() << '\n';
  55.         for(auto x : res)
  56.             cout << x.first << ' ' << x.second.first << ' ' << x.second.second << ' ' << ma[x] << '\n';
  57.     }
  58. }
  59.  
  60. int main() {
  61. //#ifdef LOCAL
  62. //    freopen("in.txt", "r", stdin);
  63. //#else
  64. //    freopen("COLLECT.inp", "r", stdin);
  65. //    freopen("COLLECT.out", "w", stdout);
  66. //#endif
  67.     ios_base::sync_with_stdio(false);
  68.     cin.tie(nullptr);
  69.  
  70.     cin >> k;
  71.     cin >> z >> s >> m >> z0 >> s0 >> m0;
  72.     n = 1;
  73.     while(cin >> change[n][1] >> change[n][2] >> change[n][3] >> change[n][4] >> change[n][5] >> change[n][6])
  74.         ++n;
  75.  
  76.     qx.push(z);
  77.     qy.push(s);
  78.     qz.push(m);
  79.     ma[make_pair(z, make_pair(s, m))] = 0;
  80.  
  81.     solve();
  82.  
  83.     return 0;
  84. }
  85.  
Add Comment
Please, Sign In to add comment