結果
問題 | No.425 ジャンケンの必勝法 |
ユーザー |
|
提出日時 | 2016-09-22 23:55:48 |
言語 | C++11 (gcc 13.3.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,632 bytes |
コンパイル時間 | 1,080 ms |
コンパイル使用メモリ | 97,628 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-11-17 15:15:14 |
合計ジャッジ時間 | 5,325 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 WA * 1 |
other | AC * 14 WA * 4 |
ソースコード
#include <algorithm> #include <bitset> #include <cassert> #include <cctype> #include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <ctime> #include <deque> #include <functional> #include <iomanip> #include <iostream> #include <list> #include <map> #include <numeric> #include <queue> #include <set> #include <sstream> #include <stack> #include <string> #include <utility> #include <vector> #define REP(i,s,n) for(int i=(int)(s);i<(int)(n);i++) using namespace std; typedef long long int ll; typedef vector<int> VI; typedef vector<ll> VL; typedef pair<int, int> PI; const ll mod = 1e9 + 7; typedef vector<vector<double> > matrix; matrix mul(const matrix &a, const matrix &b) { int n = a.size(); int m = a[0].size(); int l = b[0].size(); assert (m == b.size()); matrix ret(n); REP(i, 0, n) { ret[i] = vector<double>(l, 0.0); REP(k, 0, l) { REP(j, 0, m) { ret[i][k] += a[i][j] * b[j][k]; } } } return ret; } int main(void){ int p0, q; cin >> p0 >> q; vector<vector<double> > mat(101); vector<vector<double> > vec(101); // f(p) = p/2 * (1 + f(p - q)) + (1-p)/3 * (1 + f(p + q)) // build matrix double qr = q / 100.0; REP(i, 0, 101) { double pr = i / 100.0; mat[i] = vector<double>(101, 0.0); mat[i][max(0, i - q)] = pr / 2; mat[i][min(100, i + q)] = (1 - pr) / 3; vec[i] = vector<double>(1, pr / 2 + (1 - pr) / 3); } REP(loop_cnt, 0, 100) { matrix sqA = mul(mat, mat); matrix Ab = mul(mat, vec); mat = sqA; REP(i, 0, 101) { vec[i][0] += Ab[i][0]; } } printf("%.10f\n", (vec[p0][0] + 1) / 3); }