Submission #2283198


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];
  }

  vector<vector<double>> xs(2, vector<double>(1020));
  int crt = 0, nxt = 1;
  xs[crt][510+x] = 1.;

  int px = 510;
  double ans = 0.;
  REP(t,500){
	FOR(a,1,1019)
	  xs[nxt][a] = xs[crt][a+1] * p / 100. + xs[crt][a-1] * (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 200
Code Size 1957 Byte
Status RE
Exec Time 7 ms
Memory 7424 KB

Judge Result

Set Name Sample Dataset1 Dataset2 Dataset3
Score / Max Score 0 / 0 200 / 200 0 / 300 0 / 200
Status
AC × 2
RE × 1
AC × 7
AC × 9
WA × 1
AC × 12
WA × 1
RE × 10
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 6 ms 7424 KB
subtask_03_02.txt AC 6 ms 7424 KB
subtask_03_03.txt AC 6 ms 7424 KB
subtask_03_04.txt WA 6 ms 7424 KB
subtask_03_05.txt AC 7 ms 7424 KB
subtask_03_ex2.txt AC 6 ms 7424 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