Advertisement
Guest User

Untitled

a guest
May 22nd, 2019
81
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.75 KB | None | 0 0
  1. /*
  2. ID: hasanma1
  3. TASK: milk3
  4. LANG: C++
  5. */
  6. #include<bits/stdc++.h>
  7. using namespace std;
  8.  
  9. int state[21][21][21];
  10.  
  11. typedef struct
  12. {
  13. int capacity;
  14. int milk;
  15. } buk;
  16.  
  17. buk b[3];
  18.  
  19. bool solve(int f, int t)
  20. {
  21. if(f == t || b[f].milk == 0 || b[t].capacity == b[t].milk) return false;
  22.  
  23. int tm = b[t].capacity - b[t].milk;
  24.  
  25. if(b[f].milk > tm) // t bucket can be filled
  26. {
  27. b[f].milk -= tm;
  28. b[t].milk = b[t].capacity;
  29. }
  30. else // f bucket is empty
  31. {
  32. b[t].milk += b[f].milk;
  33. b[f].milk = 0;
  34. }
  35. return true;
  36. }
  37.  
  38. int dfs(int x, int y, int z)
  39. {
  40. if(state[x][y][z]) return 0;
  41.  
  42. state[x][y][z] = 1;
  43. int p,q,r;
  44. for(int i = 0; i < 3; i++)
  45. {
  46. for(int j = 0; j < 3; j++)
  47. {
  48. p = b[0].milk;
  49. q = b[1].milk;
  50. r = b[2].milk;
  51.  
  52. if(solve(i,j))
  53. {
  54. dfs(b[0].milk, b[1].milk, b[2].milk);
  55. }
  56.  
  57. // back to the original state
  58. b[0].milk = p;
  59. b[1].milk = q;
  60. b[2].milk = r;
  61. }
  62. }
  63. return 0;
  64. }
  65.  
  66. int main()
  67. {
  68. freopen("milk3.in", "r", stdin);
  69. freopen("milk3.out", "w", stdout);
  70. for(int i = 0; i < 3; i++)
  71. {
  72. cin >> b[i].capacity;
  73. b[i].milk = 0;
  74. }
  75.  
  76. int tot = b[2].capacity;
  77. b[2].milk = tot; // c bucket is full
  78.  
  79. int lis[21];
  80. memset(lis, 0, sizeof(lis));
  81. memset(state, 0, sizeof(state));
  82.  
  83. dfs(0,0,tot);
  84.  
  85. for(int i = 0; i <= tot; i++)
  86. {
  87. for(int j = 0; j <= tot; j++)
  88. {
  89. if(state[0][i][j])
  90. {
  91. lis[j] = 1;
  92. }
  93. }
  94. }
  95.  
  96. for(int i = 0; i < tot; i++)
  97. {
  98. if(lis[i])
  99. cout << i << " ";
  100. }
  101. cout << tot << endl;
  102. return 0;
  103. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement