Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

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

Source

TopCoder SRM462 DIV1 EASY (250pt)
TopCoder SRM462 DIV2 MEDIUM (500pt)
Problem Statement
SRM462 参加記録

問題概要

0,1からなる50文字以下の文字列がある.
Bを正の実数として,それをB進数として読むとageとなる.
Bを求める問題.存在しない,複数存在するならそれを指摘する.

解法

2分探索.コーナーケースに注意する問題.
本番の正解率は提出者のうち,Div1で10%以下,Div2で4%以下.

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

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

class AgeEncoding {
public:
double getRadix(int age, string str) {
  int i,loop;
  double a,b,c,d;

  while(str.size() && str[0]=='0') str=str.substr(1);
  if(age==1 && str=="1") return -2;
  if(age==1 && str.size()>1 && str[str.size()-1]=='1') return -1;

  a=0; b=100000;
  rep(loop,100){
    c=(a+b)/2;
    d=0;
    rep(i,str.size()){
      d *= c;
      if(str[i]=='1') d+=1;
    }
    if(age < d) b=c; else a=c;
  }

  if(a>99999) a=-1;
  if(a<0.5-1e-9)  a=-1;

  return a;
}

};

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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