はまやんはまやんはまやん

hamayanhamayan's blog

HSI [AtCoder Regular Contest 085 C]

https://beta.atcoder.jp/contests/arc085/tasks/arc085_a

解法

https://beta.atcoder.jp/contests/arc085/submissions/1759526

「有効なのが来るまでカードを引く期待値は、有効なカードを引く確率の逆数になる。」
これを知っているかどうかが問題である。
ACできる確率は、1/2^Mであるがめ、試行を行う期待値は2^Mとなる。
1回の試行で1900M+100(N-M)msかかるので、回数の期待値にこの時間をかければ答え。

int N, M;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> M;
 
    int time = 1900 * M + 100 * (N - M);
    int x = 1;
    rep(i, 0, M) x *= 2;
 
    int ans = time * x;
    cout << ans << endl;
}