Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /*
- weak weak we ak we akwea weak we
- weak weak we ak weak weak we ak we
- weakweak we ak wea ak we akwe
- wea we ak we ak we akwe
- wea we ak we ak we akwe
- wea eak weak we ak we ak we
- wea wea ak we ak weak we
- we
- we ak wea ak weak we
- we ak wea weak wea eak we
- we ak we ak wea wea we we
- weak we ak we we we we
- we we ak we we we we
- we wea weak wea wea weak weak
- weak wea akw weak weak
- */
- using namespace std;
- #include <vector>
- #include <queue>
- #include <algorithm>
- #include <cmath>
- #include <utility>
- #include <bitset>
- #include <set>
- #include <string>
- #include <stack>
- #include <iomanip>
- #include <map>
- #include <memory.h>
- #include <deque>
- #define pb push_back
- #define pii pair<int,int>
- #define F first
- #define S second
- #define LL long long
- #define mid (LB+RB)/2
- #define vvl vector <vector<LL>>
- #define vl vector <LL>
- #define mkp make_pair
- //iterators
- #define iter(x) x.begin(),x.end()
- #define aiter(a,n) a,a+n
- //loops
- #define REP(n) for (int ___=n;___--;)
- #define REP0(i,n) for (int i=0;i<n;++i)
- #define REP1(i,n) for (int i=1;i<=n;++i)
- #define FOR(i,b,l,k) for (int i=b;i!=l;i+=k)
- #define forEach(i,v) for (auto i:v)
- /*
- yungyao so weeeeeeeeeeeeeeeeeeeeeeeeeeak
- 8e7 so dian
- FHVirus so dian
- youou so dian
- KYW so dian
- hubert so dian
- jass so dian
- tingyu so dian
- panda so dian
- */
- //IO
- #include <iostream>
- #define theyRSOOOOOOOOODIAN ios_base::sync_with_stdio(false),cin.tie(0);
- //testing some stuff, still under construction
- //a lot more useful while debug
- inline void print(vector <int> v){
- for (auto i:v)
- cout << i << ' ';
- cout << '\n';
- }
- inline void print(vector <int> v,char sep,char end){
- for (auto i:v)
- cout << i << sep;
- cout << end;
- }
- //constants
- #include <climits>
- const LL maxn = 0,mod = 1e9 + 7;
- //workspace
- //gcd
- int gcd(int x,int y){
- return x % y ? gcd(y,x%y) : y;
- }
- struct hash_{
- int operator()(vector <int> s)const{
- LL ret = 0;
- for (auto i:s) ret = (ret * 53 + i) % mod;
- return ret;
- }
- };
- #include <unordered_map>
- unordered_map <vector<int>,bool,hash_> vis;
- struct Node{
- vector <int> f;
- int method; //0 for emptying cup i, 1 for filling cup i, 2 for pouring cup i to j
- int i,j;
- };
- unordered_map <vector<int>,Node,hash_> father;
- #include <fstream>
- inline void solve(){
- int n,t;
- ofstream fout;
- fout.open("papabeard2.txt");
- cin >> n;
- vector <int> l(n);
- REP0(i,n) cin >> l[i];
- cin >> t;
- fout << "由" << n << "個量杯,容量分別為";
- REP0(i,n) fout << l[i] << (i != n-1 ? ", " : ",");
- fout << "量出" << t << "單位的水\n";
- queue <pair<vector<int>,int>> bfs;
- bfs.push({vector<int>(n),0});
- vis[vector<int>(n)] = true;
- int g = l[0],mx = l[0];
- for (int i=1;i<n;++i) {mx = max(mx,l[i]);g = gcd(g,l[i]);}
- if (t > mx || t % g){
- fout << "不存在方式可以量出t單位的水\n";
- return;
- }
- vector <int> v_copy;
- while (bfs.size()){
- auto [v,d] = bfs.front(); bfs.pop();
- for (auto e:v){
- if (e == t){
- stack <Node> sk;
- while (v != vector<int>(n)){
- sk.push(father[v]);
- v = father[v].f;
- }
- fout << "共需" << d << "步\n";
- for (int s=1;sk.size();sk.pop(),++s){
- auto [fr,m,i,j] = sk.top();
- fout << "第" << s << "步:";
- if (!m){
- fout << "清空量杯" << i+1 << '\n';
- }
- else if (m == 1){
- fout << "裝滿量杯" << i+1 << '\n';
- }
- else{
- fout << "將量杯" << i+1 << "的水倒入量杯" << j+1 << '\n';
- }
- }
- return;
- }
- }
- for (int i=0;i<n;++i){
- for (int j=0;j<n;++j){
- if (i == j){
- v_copy = v;
- v_copy[i] = 0;
- if (!vis[v_copy]){
- bfs.push(mkp(v_copy,d+1));
- vis[v_copy] = true;
- father[v_copy] = {v,0,i,-1};
- }
- v_copy = v;
- v_copy[i] = l[i];
- if (!vis[v_copy]){
- bfs.push(mkp(v_copy,d+1));
- vis[v_copy] = true;
- father[v_copy] = {v,1,i,-1};
- }
- }
- else{
- v_copy = v;
- if (v[i] + v[j] <= l[j]){
- v_copy[i] = 0;
- v_copy[j] = v[i] + v[j];
- }
- else{
- v_copy[i] = v[i] + v[j] - l[j];
- v_copy[j] = l[j];
- }
- if (!vis[v_copy]){
- bfs.push(mkp(v_copy,d+1));
- vis[v_copy] = true;
- father[v_copy] = {v,2,i,j};
- }
- }
- }
- }
- }
- }
- signed main(){
- //theyRSOOOOOOOOODIAN
- //for (int ;cin;)//use in multi-testcases and end in EOF problems
- //int t,i=1;for (cin >> t;i<=t;++i)//use in multi-testcases problems
- //cout << "Case #" << i << ": ",//use in Google, FB competitions
- solve();//always used
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement