Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

2012 Round 1A A問題 - Password Problem (この記事を編集する[管理者用])

Source

Google code jam 2012 Round 1A A問題
Problem Statement

問題概要

B文字のパスワードのうち,すでにA文字を打ち込んだ.打った文字は見えない.
ただし,打ち込んだ文字は間違えているかもしれない.
i文字目が間違えていない確率p[i]が与えられる.
バックスペースk回押すと,最後に入力したk文字を消すことができる.
Enterを1回押すと,間違えていたら,全てが消える.合っていればそれで終了.
パスワードを全部打ち込み終わるまでに押す平均キー数の最小値にする戦略をとった時,その平均キー数求める問題.
smallはAが3以下, Bが100以下.
largeはA, Bは100000以下.

解法

戦略は,  Enterを押して,もう1回全部打ち直す.(この場合B+2回必要)
 バックスペースをk回押して,打ち直す.間違えていたら全部もう1回打つ必要がある.
の2通りだけ考えれば良い.
最初のk文字が全部正しい確率とかは最初に求めておけば良い.

Cによるスパゲッティなソースコード
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

double in[200000];
double mul[200000];

int main(){
  int i,j,k,l,m,n;
  int A, B;
  int size, count=0;
  double res, tmp;

  scanf("%d",&size);
  while(size--){
    scanf("%d%d",&A,&B);
    rep(i,A) scanf("%lf",in+i);
    res = 1e100;

    mul[0] = 1;
    rep(i,A) mul[i+1] = mul[i] * in[i];

    if(res > 1+B+1) res = 1+B+1;
    rep(i,A+1){
      tmp = (2*i+B-A+1) * mul[A-i] + (2*i+B-A+1+B+1) * (1-mul[A-i]);
      if(res > tmp) res = tmp;
    }

    printf("Case #%d: %.10f\n",++count,res);
  }

  return 0;
}

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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