This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub beet-aizu/library
// verification-helper: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1197 #include <bits/stdc++.h> using namespace std; #define call_from_test #include "../../tools/dice.cpp" #undef call_from_test signed main(){ cin.tie(0); ios::sync_with_stdio(0); vector<int> ts(6); do{ for(int i=0;i<6;i++) cin>>ts[i]; int sum=0; for(int t:ts) sum+=t; if(sum==0) break; auto check= [&](Die<int> d)->int{ for(int i=0;i<6;i++) if(d.fs[i]<0) return 0; int a=d.top()+d.bottom(); int b=d.east()+d.west(); int c=d.south()+d.north(); if(a>b+c) return 0; if(b>(a+1)+c) return 0; if(c>(a+1)+b) return 0; return 1; }; string ans(sum,'Z'); sort(ts.begin(),ts.end()); do{ Die d; for(int i=0;i<6;i++) d.fs[i]=ts[i]; if(!check(d)) continue; string res(sum,'Z'); int flg=0; for(int i=0;i<sum;i++){ string B="ENSW"; string R="WSNE"; for(int j=0;j<4;j++){ d.roll(B[j]); d.bottom()--; if(check(d)){ res[i]=B[j]; break;; } d.bottom()++; d.roll(R[j]); } flg|=res[i]<ans[i]; if(flg) continue; if(res[i]>ans[i]) break; } if(flg) ans=res; }while(next_permutation(ts.begin(),ts.end())); int p,q; cin>>p>>q; p--; if(ans[0]!='Z') cout<<ans.substr(p,q-p)<<endl; else cout<<"impossible"<<endl; }while(1); return 0; }
#line 1 "test/aoj/1197.test.cpp" // verification-helper: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1197 #include <bits/stdc++.h> using namespace std; #define call_from_test #line 1 "tools/dice.cpp" #line 3 "tools/dice.cpp" using namespace std; #endif //BEGIN CUT HERE template<typename T=int> struct Die{ array<T, 6> fs; int &top() {return fs[0];} int &south() {return fs[1];} int &east() {return fs[2];} int &west() {return fs[3];} int &north() {return fs[4];} int &bottom(){return fs[5];} void roll(char c){ //the view from above // N //W E // S string b("EWNSRL"); int v[6][4]={{0,3,5,2}, {0,2,5,3}, {0,1,5,4}, {0,4,5,1}, {1,2,4,3}, {1,3,4,2}}; for(int k=0;k<6;k++){ if(b[k]!=c) continue; int t=fs[v[k][0]]; fs[v[k][0]]=fs[v[k][1]]; fs[v[k][1]]=fs[v[k][2]]; fs[v[k][2]]=fs[v[k][3]]; fs[v[k][3]]=t; } } using ll = long long; ll hash(){ ll res=0; for(int i=0;i<6;i++) res=res*256+fs[i]; return res; } bool operator==(const Die &d) const{ for(int i=0;i<6;i++) if(fs[i]!=d.fs[i]) return 0; return 1; } }; template<typename T> vector<Die<T>> makeDice(Die<T> d){ vector<Die<T>> res; for(int i=0;i<6;i++){ Die t(d); if(i==1) t.roll('N'); if(i==2) t.roll('S'); if(i==3) t.roll('S'),t.roll('S'); if(i==4) t.roll('L'); if(i==5) t.roll('R'); for(int k=0;k<4;k++){ res.emplace_back(t); t.roll('E'); } } return res; } //END CUT HERE #ifndef call_from_test signed main(){ return 0; } #endif #line 8 "test/aoj/1197.test.cpp" #undef call_from_test signed main(){ cin.tie(0); ios::sync_with_stdio(0); vector<int> ts(6); do{ for(int i=0;i<6;i++) cin>>ts[i]; int sum=0; for(int t:ts) sum+=t; if(sum==0) break; auto check= [&](Die<int> d)->int{ for(int i=0;i<6;i++) if(d.fs[i]<0) return 0; int a=d.top()+d.bottom(); int b=d.east()+d.west(); int c=d.south()+d.north(); if(a>b+c) return 0; if(b>(a+1)+c) return 0; if(c>(a+1)+b) return 0; return 1; }; string ans(sum,'Z'); sort(ts.begin(),ts.end()); do{ Die d; for(int i=0;i<6;i++) d.fs[i]=ts[i]; if(!check(d)) continue; string res(sum,'Z'); int flg=0; for(int i=0;i<sum;i++){ string B="ENSW"; string R="WSNE"; for(int j=0;j<4;j++){ d.roll(B[j]); d.bottom()--; if(check(d)){ res[i]=B[j]; break;; } d.bottom()++; d.roll(R[j]); } flg|=res[i]<ans[i]; if(flg) continue; if(res[i]>ans[i]) break; } if(flg) ans=res; }while(next_permutation(ts.begin(),ts.end())); int p,q; cin>>p>>q; p--; if(ans[0]!='Z') cout<<ans.substr(p,q-p)<<endl; else cout<<"impossible"<<endl; }while(1); return 0; }