test/aoj/1197.test.cpp

• View this file on GitHub
• Last update: 2020-11-15 18:54:23+09:00
• Problem: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1197

Depends on

• tools/dice.cpp

Code

// 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;
}

Back to top page