Entries

スポンサーサイト (この記事を編集する[管理者用])

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/1690-b44f8bfc
この記事にトラックバックする(FC2ブログユーザー)

SRM486 DIV1 EASY/DIV2 MEDIUM - OneRegister (この記事を編集する[管理者用])

Source

TopCoder SRM486 DIV1 EASY (300pt)
TopCoder SRM486 DIV2 MEDIUM (500pt)
Problem Statement
SRM486 DIV1 自分の参加記録

問題概要

初期値と最終値が与えられるので,初期値を最終値にするための必要最小ターンでの,コマンド列のうち辞書順最小のものを求める問題.
各種コマンドは
 + : XをX+Xに変える
 - : XをX-Xに変える
 * : XをX*Xに変える
 / : XをX/Xに変える
初期値と最終値は1以上10億以下.
不可能ならそれを指摘する.

解法

-は使う必要はない,使うとしても/は最初の1回のみ,ということだけ念頭において適当に探索すれば良い.
+でも*でも指数的に増えていくので,大して取りうる値は多くない.
BFSするのが一番問題に合ってると思うが,以下のコードではDFSしている.

C++によるスパゲッティなソースコード
// #includeとusing namespace std;は略

#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

#define ll long long

int res_len; string res;
char now[10000];

void solve(int depth,ll s,ll t){
  
  if(depth >= res_len) return;
  if(s > t) return;
  if(s==t){
    res_len = depth;
    now[depth] = '\0';
    res = now;
    return;
  }

  now[depth]='*';
  if(s>1) solve(depth+1,s*s,t);
  now[depth]='+';
  solve(depth+1,s+s,t);
}

class OneRegister {
public:
string getProgram(int s, int t) {
  int i,j,k;
  res_len = 10000;

  solve(0,s,t);
  now[0]='/'; solve(1,1,t);

  if(res_len==10000) res = ":-(";
  return res;
}

};

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/1690-b44f8bfc
この記事にトラックバックする(FC2ブログユーザー)

Appendix

Recent Articles

ブログ内検索

Ads


(プライバシーポリシー)
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。