Submission #2283235
Source Code Expand
#include <bits/stdc++.h> using namespace std; typedef vector<int> VI; typedef vector<VI> VVI; typedef vector<string> VS; typedef pair<int, int> PII; typedef long long LL; typedef pair<LL, LL> PLL; #define ALL(a) (a).begin(),(a).end() #define RALL(a) (a).rbegin(), (a).rend() #define PB push_back #define EB emplace_back #define MP make_pair #define SZ(a) int((a).size()) #define SORT(c) sort((c).begin(),(c).end()) #define FOR(i,a,b) for(int i=(a);i<(b);++i) #define REP(i,n) FOR(i,0,n) #define FF first #define SS second template<class S, class T> istream& operator>>(istream& is, pair<S,T>& p){ return is >> p.FF >> p.SS; } const double EPS = 1e-10; const double PI = acos(-1.0); const LL MOD = 1e9+7; double C[1010][1010]; double ps[1010], qs[1010]; int main(){ cin.tie(0); ios_base::sync_with_stdio(false); LL x, p; cin >> x >> p; if(p == 100){ cout << (x+1)/2 << endl; return 0; } if(x > 10) return 1; ps[0] = qs[0] = 1.; REP(i,1000){ ps[i+1] = ps[i] * p / 100.; qs[i+1] = qs[i] * (100-p) / 100.; } for(int i=1;i<1000;++i){ C[i][0] = ps[i]; C[i][i] = qs[i]; for(int j=1;j<i;++j) C[i][j] = C[i-1][j] * qs[1] + C[i-1][j-1] * ps[1]; } const int MAX = 10020; vector<vector<double>> xs(2, vector<double>(MAX)); int crt = 0, nxt = 1; xs[crt][MAX/2+x] = 1.; int px = MAX/2; double ans = 0.; REP(t,MAX/2-20){ fill(ALL(xs[nxt]), 0); REP(a,MAX){ if(a-1 >= 0) xs[nxt][a-1] += xs[crt][a] * p / 100.; if(a+1<MAX) xs[nxt][a+1] += xs[crt][a] * (100.-p) / 100.; } swap(crt, nxt); if(xs[crt][px] < EPS && xs[crt][px-1] < EPS && xs[crt][px+1] < EPS) ++px; else if(xs[crt][px] > xs[crt][px-1] && xs[crt][px] > xs[crt][px+1]) ; else if(xs[crt][px-1] > xs[crt][px] && xs[crt][px-1] > xs[crt][px+1]) --px; else if(xs[crt][px+1] > xs[crt][px-1] && xs[crt][px+1] > xs[crt][px]) ++px; ans += (t+1) * xs[crt][px]; xs[crt][px] = 0.; } cout << fixed << setprecision(9) << ans << endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | A - Takahashi is Missing! |
User | okaduki |
Language | C++14 (GCC 5.4.1) |
Score | 500 |
Code Size | 2068 Byte |
Status | RE |
Exec Time | 285 ms |
Memory | 7680 KB |
Judge Result
Set Name | Sample | Dataset1 | Dataset2 | Dataset3 | ||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 200 / 200 | 300 / 300 | 0 / 200 | ||||||||||||
Status |
|
|
|
|
Set Name | Test Cases |
---|---|
Sample | subtask_01_ex1.txt, subtask_03_ex2.txt, subtask_04_ex3.txt |
Dataset1 | subtask_01_02.txt, subtask_01_03.txt, subtask_01_04.txt, subtask_01_ex1.txt, subtask_02_01.txt, subtask_02_02.txt, subtask_02_03.txt |
Dataset2 | subtask_01_02.txt, subtask_01_03.txt, subtask_01_04.txt, subtask_01_ex1.txt, subtask_03_01.txt, subtask_03_02.txt, subtask_03_03.txt, subtask_03_04.txt, subtask_03_05.txt, subtask_03_ex2.txt |
Dataset3 | subtask_01_02.txt, subtask_01_03.txt, subtask_01_04.txt, subtask_01_ex1.txt, subtask_02_01.txt, subtask_02_02.txt, subtask_02_03.txt, subtask_03_01.txt, subtask_03_02.txt, subtask_03_03.txt, subtask_03_04.txt, subtask_03_05.txt, subtask_03_ex2.txt, subtask_04_01.txt, subtask_04_02.txt, subtask_04_03.txt, subtask_04_04.txt, subtask_04_05.txt, subtask_04_06.txt, subtask_04_07.txt, subtask_04_08.txt, subtask_04_09.txt, subtask_04_ex3.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
subtask_01_02.txt | AC | 1 ms | 256 KB |
subtask_01_03.txt | AC | 1 ms | 256 KB |
subtask_01_04.txt | AC | 1 ms | 256 KB |
subtask_01_ex1.txt | AC | 1 ms | 256 KB |
subtask_02_01.txt | AC | 1 ms | 256 KB |
subtask_02_02.txt | AC | 1 ms | 256 KB |
subtask_02_03.txt | AC | 1 ms | 256 KB |
subtask_03_01.txt | AC | 282 ms | 7680 KB |
subtask_03_02.txt | AC | 285 ms | 7680 KB |
subtask_03_03.txt | AC | 284 ms | 7680 KB |
subtask_03_04.txt | AC | 282 ms | 7680 KB |
subtask_03_05.txt | AC | 282 ms | 7680 KB |
subtask_03_ex2.txt | AC | 284 ms | 7680 KB |
subtask_04_01.txt | RE | 1 ms | 256 KB |
subtask_04_02.txt | RE | 1 ms | 256 KB |
subtask_04_03.txt | RE | 1 ms | 256 KB |
subtask_04_04.txt | RE | 1 ms | 256 KB |
subtask_04_05.txt | RE | 1 ms | 256 KB |
subtask_04_06.txt | RE | 1 ms | 256 KB |
subtask_04_07.txt | RE | 1 ms | 256 KB |
subtask_04_08.txt | RE | 1 ms | 256 KB |
subtask_04_09.txt | RE | 1 ms | 256 KB |
subtask_04_ex3.txt | RE | 1 ms | 256 KB |