Guest User

Untitled

a guest
Jan 19th, 2019
96
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.87 KB | None | 0 0
  1. #pragma comment(linker,"/STACK:300000000")
  2. #define _CRT_SECURE_NO_WARNINGS
  3. #pragma warning(disable:4800)
  4.  
  5. #include <iostream>
  6. #include <vector>
  7. #include <string>
  8. #include <algorithm>
  9. #include <cmath>
  10. #include <map>
  11. #include <set>
  12. #include <iomanip>
  13. #include <memory.h>
  14. #include <cstdio>
  15. #include <sstream>
  16. #include <deque>
  17. #include <bitset>
  18. #include <numeric>
  19. #include <ctime>
  20. #include <queue>
  21.  
  22. using namespace std;
  23.  
  24. #define show(x) cout << #x << " = " << (x) << endl;
  25. void showTime() { cerr << (double)clock()/CLOCKS_PER_SEC << endl; }
  26. #define fori(i,n) for(int i = 0; i < (n); i++)
  27. #define forab(i,a,b) for(int i = (a); i <= (b); i++)
  28. #define sz(v) int((v).size())
  29. #define all(v) (v).begin(),(v).end()
  30. const double pi = 3.1415926535897932384626433832795;
  31. template<class T> T abs(const T &a) { return a >= 0 ? a : -a; };
  32. template<class T> T sqr(const T &x) { return x * x; }
  33. typedef pair<int,int> ii;
  34. typedef long long ll;
  35. #define FILENAME "cylinders"
  36. ///////////////////////////////////////
  37.  
  38. int need, n;
  39. int a[40];
  40.  
  41. struct state
  42. {
  43.     int volume, scale;
  44. };
  45. state q[40*200000];
  46. int ql = 0, qr = -1;
  47. int dist[40][200000];
  48. int scaleIndex[200500];
  49.  
  50. void push(state &st)
  51. {
  52.     q[++qr] = st;
  53. }
  54.  
  55. state get()
  56. {
  57.     return q[ql++];
  58. }
  59.  
  60. void dotry(state &to, int d)
  61. {
  62.     if(to.volume < 0 || to.volume > a[n-1])
  63.         return;
  64.     if(dist[to.scale][to.volume] == -1)
  65.     {
  66.         dist[to.scale][to.volume] = d;
  67.         push(to);
  68.     }
  69. }
  70.  
  71. int main()
  72. {
  73. #ifdef TEDDY_BEARS
  74.     freopen("input.txt","r",stdin);
  75.     freopen("output.txt","w",stdout);
  76. #else
  77.     freopen(FILENAME".in","r",stdin);
  78.     freopen(FILENAME".out","w",stdout);
  79. #endif
  80.     cin >> n;
  81.     fori(i,n)
  82.         cin >> a[i];
  83.     fori(i,n)
  84.         fori(j,100500)
  85.             dist[i][j] = -1;
  86.     sort(a,a+n);
  87.     memset(scaleIndex,-1,sizeof(scaleIndex));
  88.     fori(i,n)
  89.         scaleIndex[a[i]] = i;
  90.     cin >> need;
  91.  
  92.     state cur;
  93.     cur.scale = 0;
  94.     cur.volume = 0;
  95.     push(cur);
  96.     dist[0][0] = 0;
  97.  
  98.     while(ql <= qr)
  99.     {
  100.         cur = get();
  101.         state to;
  102.         int toDist = dist[cur.scale][cur.volume]+1;
  103.  
  104.         //pour to first
  105.         to.volume = cur.volume;
  106.         fori(i,n)
  107.         {
  108.             to.scale = i;
  109.             dotry(to,toDist);
  110.         }
  111.         //pour to second
  112.         to.scale = cur.scale;
  113.         fori(i,n)
  114.         {
  115.             to.volume = a[i];
  116.             dotry(to,toDist);
  117.         }
  118.         //exch to scale in first
  119.         fori(i,n)
  120.         {
  121.             int diff = a[i]-a[cur.scale];
  122.             to.scale = i;
  123.             to.volume = cur.volume-diff;
  124.             dotry(to,toDist);
  125.         }
  126.         //exch to scale in second
  127.         fori(i,n)
  128.         {
  129.             int diff = a[i]-cur.volume;
  130.             to.scale = i;
  131.             to.volume = a[cur.scale]-diff;
  132.             dotry(to,toDist);
  133.         }
  134.     }
  135.     int inf = int(1e9);
  136.     int mi = inf;
  137.     int I = -1;
  138.     fori(i,n)
  139.         if(a[i] == need)
  140.         {
  141.             I = i;
  142.             break;
  143.         }
  144.     if(I != -1)
  145.     {
  146.         fori(i,a[n-1]+1)
  147.             if(dist[I][i] != -1)
  148.                 mi = min(mi,dist[I][i]);
  149.     }
  150.     fori(i,n)
  151.         if(dist[i][need] != -1)
  152.             mi = min(mi,dist[i][need]);
  153.     if(mi == inf)
  154.         cout << "IMPOSSIBLE";
  155.     else
  156.         cout << mi;
  157. }
Add Comment
Please, Sign In to add comment