Codeforces 93 C. Azembler

Codeforces 実装問題

問題

26個のレジスタ(eax,ebx,……,ezx）をもつコンピュータがある。

  • lea x, [y]
  • lea x, [y + z]
  • lea x, [k*y]
  • lea x, [y + k*z]

（ただしx,y,zはレジスタ名、kは1,2,4,8の整数）
の4つの命令を使い、いずれかのレジスタにeax * nの値を作りたい。


そのために必要な命令数の最小値および、そのときの命令を一通りどれか出力せよ。

制約条件

n≦255

方針

全探索+経路復元。


255までのどの値を作るのも、26手はかからないので、
レジスタは常に新しいものに書き込んでいってよい。
これにより状態数が減り、単純に幅優先探索することが可能になる。

ソースコード

int n;
void run(){
  cin>>n;
  vi v(26);
  v[0]=1;
  queue<pair<int,vi> > q;
  map<vi,vi> prev;
  prev[v]=vi(26,0);
  q.push(mp(1,v));
  bool found=0;
  
  while(!q.empty()){
    int cur=q.front().first;
    v=q.front().second; q.pop();
    
    if(v[cur-1]==n){
      vector<string> ans;
      for(;prev[v][0]>0;v=prev[v], cur--){
        vi p=prev[v];
        rep(i,cur)rep(j,cur+1)rep(k,4){
          if(v[cur-1]==p[i]+(p[j]<<k)){
            stringstream ss;
            bool flag=0;
            ss<<"lea e"<<(char)('a'+cur-1)<<"x, [";
            if(i!=cur-1){
              flag=1;
              ss<<"e"<<(char)('a'+i)<<"x";
            }
            if(j<cur){
              if(flag)ss<<" + ";
              if(k)ss<<(1<<k)<<"*";
              ss<<"e"<<(char)('a'+j)<<"x";
            }
            ss<<"]";
            ans.push_back(ss.str());
            goto FOUND;
          }
        }
        FOUND:;
      }
      reverse(all(ans));
      cout<<ans.size()<<endl;
      rep(i,ans.size())cout<<ans[i]<<endl;
      goto END;
    }
    if(!found)rep(i,cur+1)rep(j,cur+1)rep(k,4){
      vi nxt=v;
      nxt[cur]=v[i]+(v[j]<<k);
      if(nxt[cur]>n||prev.count(nxt))continue;
      prev[nxt]=v;
      q.push(mp(cur+1,nxt));
      if(nxt[cur]==n){
        found=1; goto NEXT;
      }
    }
    NEXT:;
  }
  END:;
}