Advertisement
vfonic

Untitled

Oct 12th, 2014
173
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.55 KB | None | 0 0
  1. #include <algorithm>
  2. #include <cctype>
  3. #include <climits>
  4. #include <cmath>
  5. #include <cstdio>
  6. #include <cstdlib>
  7. #include <cstring>
  8. #include <iostream>
  9. #include <list>
  10. #include <map>
  11. #include <queue>
  12. #include <set>
  13. #include <sstream>
  14. #include <stack>
  15. #include <string>
  16. #include <vector>
  17.  
  18. #define inf 1000000000
  19. #define MAXN 100000
  20. #define swap(a,b) a^=b; b^=a; a^=b;
  21.  
  22. using namespace std;
  23.  
  24. struct state {
  25.     vector<int> a;
  26.     int nr_moves;
  27.     state *previous;
  28.     int i, j;
  29.     state(int _nr_moves, vector<int> _a, int _i = 0, int _j = 0) {
  30.         nr_moves = _nr_moves; a = _a; i = _i; j = _j;
  31.     }
  32. };
  33.  
  34. int maxes[100];
  35. int n;
  36.  
  37. void print(state *s) {
  38.     int br = 0;
  39.     while (s != NULL && br++ < 3) {
  40.         s = s->previous;
  41.         printf("s.nr_moves:%d s->i:%d s->j:%d\n", s->nr_moves, s->i, s->j);
  42.     }
  43. }
  44.  
  45. int main() {
  46.     scanf("%d", &n);
  47.     for (int i = 0; i < n; ++i) {
  48.         scanf("%d", &maxes[i]);
  49.     }
  50.     maxes[n] = INT_MAX;
  51.    
  52.     int where;
  53.     scanf("%d", &where);
  54.     for (int i = 0; i < n; ++i) {
  55.         if (maxes[i] == where) {
  56.             where = i;
  57.             break;
  58.         }
  59.     }
  60.     int cap;
  61.     scanf("%d", &cap);
  62.    
  63.     vector<int> a = vector<int>(n, 0);
  64.     a.push_back(inf);
  65.     ++n;
  66.    
  67.     queue<state> kju;
  68.     kju.push(state(0, a));
  69.     set<string> bio;
  70.     while (!kju.empty()) {
  71.         state s = kju.front(); kju.pop();
  72.        
  73.         if (s.a[where] == cap) {
  74.             print(&s);
  75.             // printf("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa\n");
  76.             return 0;
  77.         }
  78.        
  79.         string key = "";
  80.         char st[10];
  81.         for (int i = 0; i < n-1; ++i) {
  82.             sprintf(st, "%5d#", s.a[i]);
  83.             key += string(st);
  84.         }
  85.         printf("key:%s\n", key.c_str());
  86.         if (bio.find(key) != bio.end()) continue;
  87.         bio.insert(key);
  88.        
  89.         for (int i = 0; i < n; ++i) {
  90.             for (int j = 0; j < n; ++j) {
  91.                 if (i == j) continue;
  92.                 printf("i:%d j:%d\n", i, j);
  93.                
  94.                 // from i to j
  95.                 if (s.a[i] != 0 && s.a[j] != maxes[j]) {
  96.                     printf("ubacujemo vodu!\n");
  97.                     int litres = min(s.a[i], maxes[j] - s.a[j]);
  98.                     a = s.a;
  99.                     a[i] -= litres;
  100.                     a[j] += litres;
  101.                     if (i < n-1) {
  102.                         sprintf(st, "%5d#", a[i]);
  103.                         key.replace(i*6, 6, string(st));
  104.                     }
  105.                     if (j < n-1) {
  106.                         sprintf(st, "%5d#", a[j]);
  107.                         key.replace(j*6, 6, string(st));
  108.                     }
  109.                     printf("key:%s\n", key.c_str());
  110.                    
  111.                     if (bio.find(key) == bio.end()) {
  112.                         state *new_state = new state(s.nr_moves+1, a, i, j);
  113.                         new_state->previous = &s;
  114.                         kju.push(*new_state);
  115.                     }
  116.                    
  117.                     if (i < n-1) {
  118.                         sprintf(st, "%5d#", s.a[i]);
  119.                         key.replace(i*6, 6, string(st));
  120.                     }
  121.                     if (j < n-1) {
  122.                         sprintf(st, "%5d#", s.a[j]);
  123.                         key.replace(j*6, 6, string(st));
  124.                     }
  125.                     printf("key:%s\n", key.c_str());
  126.                 }
  127.             }
  128.         }
  129.     }
  130.    
  131.     return 0;
  132. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement