結果
問題 | No.425 ジャンケンの必勝法 |
ユーザー |
|
提出日時 | 2016-09-22 23:10:43 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 60 ms / 2,000 ms |
コード長 | 1,857 bytes |
コンパイル時間 | 1,272 ms |
コンパイル使用メモリ | 107,980 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-11-17 19:28:31 |
合計ジャッジ時間 | 2,964 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 5 |
other | AC * 18 |
ソースコード
#define _USE_MATH_DEFINES#include <cstdio>#include <iostream>#include <sstream>#include <fstream>#include <iomanip>#include <algorithm>#include <cmath>#include <complex>#include <string>#include <vector>#include <list>#include <queue>#include <stack>#include <set>#include <map>#include <bitset>#include <numeric>#include <limits>#include <climits>#include <cfloat>#include <functional>using namespace std;// 行列の積template <class T>vector<vector<T> > matrixProduct(const vector<vector<T> >& x, const vector<vector<T> >& y){int a = x.size();int b = x[0].size();int c = y[0].size();vector<vector<T> > z(a, vector<T>(c, 0));for(int i=0; i<a; ++i){for(int j=0; j<c; ++j){for(int k=0; k<b; ++k){z[i][j] += x[i][k] * y[k][j];}}}return z;}// 行列の累乗template <class T>vector<vector<T> > matrixPower(const vector<vector<T> >& x, int k){int n = x.size();vector<vector<T> > y(n, vector<T>(n, 0));for(int i=0; i<n; ++i)y[i][i] = 1; // 積の単位元vector<vector<T> > z = x;while(k > 0){if(k & 1)y = matrixProduct(y, z);z = matrixProduct(z, z);k >>= 1;}return y;}int main(){int p0, q;cin >> p0 >> q;vector<vector<double> > mat(102, vector<double>(102, 0.0));mat[101][101] = 1.0;for(int p=0; p<=100; ++p){mat[p][101] += p / 100.0 * (1.0 / 2.0) +(100 - p) / 100.0 * (1.0 / 3.0);mat[p][max(0, p-q)] += p / 100.0 * (1.0 / 2.0);mat[p][min(100, p+q)] += (100 - p) / 100.0 * (1.0 / 3.0);}mat = matrixPower(mat, 100000000);double ans = 1.0 / 3.0 * (1 + mat[p0][101]);printf("%.10f\n", ans);return 0;}