Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #pragma comment(linker,"/STACK:300000000")
- #define _CRT_SECURE_NO_WARNINGS
- #pragma warning(disable:4800)
- #include <iostream>
- #include <vector>
- #include <string>
- #include <algorithm>
- #include <cmath>
- #include <map>
- #include <set>
- #include <iomanip>
- #include <memory.h>
- #include <cstdio>
- #include <sstream>
- #include <deque>
- #include <bitset>
- #include <numeric>
- #include <ctime>
- #include <queue>
- using namespace std;
- #define show(x) cout << #x << " = " << (x) << endl;
- void showTime() { cerr << (double)clock()/CLOCKS_PER_SEC << endl; }
- #define fori(i,n) for(int i = 0; i < (n); i++)
- #define forab(i,a,b) for(int i = (a); i <= (b); i++)
- #define sz(v) int((v).size())
- #define all(v) (v).begin(),(v).end()
- const double pi = 3.1415926535897932384626433832795;
- template<class T> T abs(const T &a) { return a >= 0 ? a : -a; };
- template<class T> T sqr(const T &x) { return x * x; }
- typedef pair<int,int> ii;
- typedef long long ll;
- #define FILENAME "cylinders"
- ///////////////////////////////////////
- int need, n;
- int a[40];
- struct state
- {
- int volume, scale;
- };
- state q[40*200000];
- int ql = 0, qr = -1;
- int dist[40][200000];
- int scaleIndex[200500];
- void push(state &st)
- {
- q[++qr] = st;
- }
- state get()
- {
- return q[ql++];
- }
- void dotry(state &to, int d)
- {
- if(to.volume < 0 || to.volume > a[n-1])
- return;
- if(dist[to.scale][to.volume] == -1)
- {
- dist[to.scale][to.volume] = d;
- push(to);
- }
- }
- int main()
- {
- #ifdef TEDDY_BEARS
- freopen("input.txt","r",stdin);
- freopen("output.txt","w",stdout);
- #else
- freopen(FILENAME".in","r",stdin);
- freopen(FILENAME".out","w",stdout);
- #endif
- cin >> n;
- fori(i,n)
- cin >> a[i];
- fori(i,n)
- fori(j,100500)
- dist[i][j] = -1;
- sort(a,a+n);
- memset(scaleIndex,-1,sizeof(scaleIndex));
- fori(i,n)
- scaleIndex[a[i]] = i;
- cin >> need;
- state cur;
- cur.scale = 0;
- cur.volume = 0;
- push(cur);
- dist[0][0] = 0;
- while(ql <= qr)
- {
- cur = get();
- state to;
- int toDist = dist[cur.scale][cur.volume]+1;
- //pour to first
- to.volume = cur.volume;
- fori(i,n)
- {
- to.scale = i;
- dotry(to,toDist);
- }
- //pour to second
- to.scale = cur.scale;
- fori(i,n)
- {
- to.volume = a[i];
- dotry(to,toDist);
- }
- //exch to scale in first
- fori(i,n)
- {
- int diff = a[i]-a[cur.scale];
- to.scale = i;
- to.volume = cur.volume-diff;
- dotry(to,toDist);
- }
- //exch to scale in second
- fori(i,n)
- {
- int diff = a[i]-cur.volume;
- to.scale = i;
- to.volume = a[cur.scale]-diff;
- dotry(to,toDist);
- }
- }
- int inf = int(1e9);
- int mi = inf;
- int I = -1;
- fori(i,n)
- if(a[i] == need)
- {
- I = i;
- break;
- }
- if(I != -1)
- {
- fori(i,a[n-1]+1)
- if(dist[I][i] != -1)
- mi = min(mi,dist[I][i]);
- }
- fori(i,n)
- if(dist[i][need] != -1)
- mi = min(mi,dist[i][need]);
- if(mi == inf)
- cout << "IMPOSSIBLE";
- else
- cout << mi;
- }
Add Comment
Please, Sign In to add comment