test/aoj/2294.test.cpp

View this file on GitHub
Last update: 2020-10-27 12:29:50+09:00
Problem: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2294

Depends on

Code

// verification-helper: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2294
// verification-helper: ERROR 1e-6

#include<bits/stdc++.h>
using namespace std;

#define call_from_test
#include "../../io/precision.cpp"
#include "../../vector/multi.cpp"
#undef call_from_test

signed main(){
  cin.tie(0);
  ios::sync_with_stdio(0);

  using D = long double;
  int h,n,p,m,k;
  cin>>h>>n>>p>>m>>k;
  p--;

  vector<int> bs(h,-1);
  for(int i=0;i<m;i++){
    int x,y;
    cin>>x>>y;
    bs[h-x]=y-1;
  }

  auto dp=make_v<D>(h+1,k+1,n+1);
  fill_v<D>(dp,0);

  dp[0][0][p]=1;
  for(int i=0;i<h;i++){
    for(int j=0;j<=k;j++){
      if(~bs[i]){
        swap(dp[i][j][bs[i]],dp[i][j][bs[i]+1]);
        for(int l=0;l<n;l++) dp[i+1][j][l]+=dp[i][j][l];
        continue;
      }
      for(int l=0;l<n;l++) dp[i+1][j][l]+=dp[i][j][l];
      if(j+1>k) continue;
      for(int l=0;l<n;l++){
        D x=0.0;
        if(l+1<n)  dp[i+1][j+1][l+1]+=dp[i][j][l]/(n-1.0),x+=1.0;
        if(l-1>=0) dp[i+1][j+1][l-1]+=dp[i][j][l]/(n-1.0),x+=1.0;
        dp[i+1][j+1][l]+=dp[i][j][l]*(n-1.0-x)/(n-1.0);
      }
    }
  }

  D ans=*max_element(dp[h][k].begin(),dp[h][k].end());
  for(int i=0;i<k;i++){
    ans/=(h-m-i);
    ans*=(i+1);
  }
  cout<<ans<<endl;
  return 0;
}

#line 1 "test/aoj/2294.test.cpp"
// verification-helper: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2294
// verification-helper: ERROR 1e-6

#include<bits/stdc++.h>
using namespace std;

#define call_from_test
#line 1 "io/precision.cpp"

#line 3 "io/precision.cpp"
using namespace std;
#endif
//BEGIN CUT HERE
struct Precision{
  Precision(){
    cout<<fixed<<setprecision(12);
  }
}precision_beet;
//END CUT HERE
#ifndef call_from_test
signed main(){
  return 0;
}
#endif
#line 1 "vector/multi.cpp"

#line 3 "vector/multi.cpp"
using namespace std;
#endif
//BEGIN CUT HERE
template<typename T>
vector<T> make_v(size_t a){return vector<T>(a);}

template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts){
  return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}

template<typename T,typename U,typename... V>
typename enable_if<is_same<T, U>::value!=0>::type
fill_v(U &u,const V... v){u=U(v...);}

template<typename T,typename U,typename... V>
typename enable_if<is_same<T, U>::value==0>::type
fill_v(U &u,const V... v){
  for(auto &e:u) fill_v<T>(e,v...);
}
//END CUT HERE
#ifndef call_from_test
//INSERT ABOVE HERE
signed main(){
  return 0;
}
#endif
#line 10 "test/aoj/2294.test.cpp"
#undef call_from_test

signed main(){
  cin.tie(0);
  ios::sync_with_stdio(0);

  using D = long double;
  int h,n,p,m,k;
  cin>>h>>n>>p>>m>>k;
  p--;

  vector<int> bs(h,-1);
  for(int i=0;i<m;i++){
    int x,y;
    cin>>x>>y;
    bs[h-x]=y-1;
  }

  auto dp=make_v<D>(h+1,k+1,n+1);
  fill_v<D>(dp,0);

  dp[0][0][p]=1;
  for(int i=0;i<h;i++){
    for(int j=0;j<=k;j++){
      if(~bs[i]){
        swap(dp[i][j][bs[i]],dp[i][j][bs[i]+1]);
        for(int l=0;l<n;l++) dp[i+1][j][l]+=dp[i][j][l];
        continue;
      }
      for(int l=0;l<n;l++) dp[i+1][j][l]+=dp[i][j][l];
      if(j+1>k) continue;
      for(int l=0;l<n;l++){
        D x=0.0;
        if(l+1<n)  dp[i+1][j+1][l+1]+=dp[i][j][l]/(n-1.0),x+=1.0;
        if(l-1>=0) dp[i+1][j+1][l-1]+=dp[i][j][l]/(n-1.0),x+=1.0;
        dp[i+1][j+1][l]+=dp[i][j][l]*(n-1.0-x)/(n-1.0);
      }
    }
  }

  D ans=*max_element(dp[h][k].begin(),dp[h][k].end());
  for(int i=0;i<k;i++){
    ans/=(h-m-i);
    ans*=(i+1);
  }
  cout<<ans<<endl;
  return 0;
}