Advertisement
mickypinata

USACO-T017: Mother's Milk

Nov 28th, 2021
668
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /*
  2. ID: mickyta1
  3. TASK: milk3
  4. LANG: C++
  5. */
  6.  
  7. #include <bits/stdc++.h>
  8. using namespace std;
  9.  
  10. typedef tuple<int, int, int> tiii;
  11.  
  12. const int N = 20 + 5;
  13.  
  14. vector<int> ans;
  15. int limA, limB, limC;
  16. bool visit[6][N][N];
  17.  
  18. bool &visited(int a, int b, int c){
  19.     if(a == 0){
  20.         return visit[0][b][c];
  21.     } else if(a == limA){
  22.         return visit[1][b][c];
  23.     } else if(b == 0){
  24.         return visit[2][a][c];
  25.     } else if(b == limB){
  26.         return visit[3][a][c];
  27.     } else if(c == 0){
  28.         return visit[4][a][b];
  29.     }
  30.     return visit[5][a][b];
  31. }
  32.  
  33. int main(){
  34.     freopen("milk3.in", "r", stdin);
  35.     freopen("milk3.out", "w", stdout);
  36.  
  37.     scanf("%d%d%d", &limA, &limB, &limC);
  38.     queue<tiii> que;
  39.     visited(0, 0, limC) = true;
  40.     que.emplace(0, 0, limC);
  41.     while(!que.empty()){
  42.         int ua = get<0>(que.front());
  43.         int ub = get<1>(que.front());
  44.         int uc = get<2>(que.front());
  45.         que.pop();
  46.         if(ua == 0){
  47.             ans.push_back(uc);
  48.         }
  49.         int va, vb, vc, mve;
  50.         for(int i = 1; i <= 6; ++i){
  51.             va = ua;
  52.             vb = ub;
  53.             vc = uc;
  54.             if(i == 1){ // A -> B
  55.                 mve = min(ua, limB - ub);
  56.                 va -= mve;
  57.                 vb += mve;
  58.             } else if(i == 2){ // B -> A
  59.                 mve = min(ub, limA - ua);
  60.                 vb -= mve;
  61.                 va += mve;
  62.             } else if(i == 3){ // A -> C
  63.                 mve = min(ua, limC - uc);
  64.                 va -= mve;
  65.                 vc += mve;
  66.             } else if(i == 4){ // C -> A
  67.                 mve = min(uc, limA - ua);
  68.                 vc -= mve;
  69.                 va += mve;
  70.             } else if(i == 5){ // B -> C
  71.                 mve = min(ub, limC - uc);
  72.                 vb -= mve;
  73.                 vc += mve;
  74.             } else { // C -> B
  75.                 mve = min(uc, limB - ub);
  76.                 vc -= mve;
  77.                 vb += mve;
  78.             }
  79.             if(!visited(va, vb, vc)){
  80.                 visited(va, vb, vc) = true;
  81.                 que.emplace(va, vb, vc);
  82.             }
  83.         }
  84.     }
  85.     sort(ans.begin(), ans.end());
  86.     for(int i = 0; i < (int)ans.size() - 1; ++i){
  87.         cout << ans[i] << ' ';
  88.     }
  89.     cout << ans.back() << '\n';
  90.  
  91.     fclose(stdin);
  92.     fclose(stdout);
  93.     return 0;
  94. }
  95.  
Advertisement
RAW Paste Data Copied
Advertisement