結果
問題 | No.574 正多面体サイコロ |
ユーザー |
![]() |
提出日時 | 2018-05-11 18:50:32 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 41 ms / 2,000 ms |
コード長 | 4,243 bytes |
コンパイル時間 | 1,573 ms |
コンパイル使用メモリ | 172,680 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-06-28 03:57:25 |
合計ジャッジ時間 | 2,627 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 20 |
ソースコード
#ifdef LOCAL111#define _GLIBCXX_DEBUG#else#define NDEBUG#endif#define _USE_MATH_DEFINES#ifndef _GLIBCXX_NO_ASSERT#include <cassert>#endif#include <cctype>#include <cerrno>#include <cfloat>#include <ciso646>#include <climits>#include <clocale>#include <cmath>#include <csetjmp>#include <csignal>#include <cstdarg>#include <cstddef>#include <cstdio>#include <cstdlib>#include <cstring>#include <ctime>#if __cplusplus >= 201103L#include <ccomplex>#include <cfenv>#include <cinttypes>#include <cstdbool>#include <cstdint>#include <ctgmath>#include <cwchar>#include <cwctype>#endif// C++#include <algorithm>#include <bitset>#include <complex>#include <deque>#include <exception>#include <fstream>#include <functional>#include <iomanip>#include <ios>#include <iosfwd>#include <iostream>#include <istream>#include <iterator>#include <limits>#include <list>#include <locale>#include <map>#include <memory>#include <new>#include <numeric>#include <ostream>#include <queue>#include <set>#include <sstream>#include <stack>#include <stdexcept>#include <streambuf>#include <string>#include <typeinfo>#include <utility>#include <valarray>#include <vector>#if __cplusplus >= 201103L#include <array>#include <atomic>#include <chrono>#include <condition_variable>#include <forward_list>#include <future>#include <initializer_list>#include <mutex>#include <random>#include <ratio>#include <regex>#include <scoped_allocator>#include <system_error>#include <thread>#include <tuple>#include <type_traits>#include <typeindex>#include <unordered_map>#include <unordered_set>#endifconst int INF = 1e9;using namespace std;template<typename T, typename U> ostream& operator<< (ostream& os, const pair<T,U>& p) { os << '(' << p.first << ' ' << p.second << ')'; return os; }#define endl '\n'#define ALL(a) (a).begin(),(a).end()#define SZ(a) int((a).size())#define FOR(i,a,b) for(int i=(a);i<(b);++i)#define RFOR(i,a,b) for (int i=(b)-1;i>=(a);i--)#define REP(i,n) FOR(i,0,n)#define RREP(i,n) for (int i=(n)-1;i>=0;i--)#ifdef LOCAL111#define DEBUG(x) cout<<#x<<": "<<(x)<<endltemplate<typename T> void dpite(T a, T b){ for(T ite = a; ite != b; ite++) cout << (ite == a ? "" : " ") << *ite; cout << endl;}#else#define DEBUG(x) truetemplate<typename T> void dpite(T a, T b){ return; }#endif#define F first#define S second#define SNP string::npos#define WRC(hoge) cout << "Case #" << (hoge)+1 << ": "template<typename T> void pite(T a, T b){ for(T ite = a; ite != b; ite++) cout << (ite == a ? "" : " ") << *ite; cout << endl;}template<typename T> bool chmax(T& a, T b){if(a < b){a = b; return true;} return false;}template<typename T> bool chmin(T& a, T b){if(a > b){a = b; return true;} return false;}typedef long long int LL;typedef unsigned long long ULL;typedef pair<int,int> P;void ios_init(){cout.setf(ios::fixed);cout.precision(12);#ifdef LOCAL111return;#endifios::sync_with_stdio(false); cin.tie(0);}int main(){ios_init();int f, n, k;while(cin >> f >> n >> k) {k = n-k+1;auto solve = [&](int x) -> double {vector<vector<double>> dp(n+1, vector<double>(n+1));dp[0][0] = 1.;double p1 = (x-1.) / f;double p2 = double(f-x) / f;DEBUG(x); DEBUG(p1); DEBUG(p2);REP(_, n) {DEBUG(_);RREP(i, n+1) {RREP(j, n+1) {dp[i][j] *= 1./f;if(i > 0) {dp[i][j] += dp[i-1][j] * p1;}if(j > 0) {dp[i][j] += dp[i][j-1] * p2;}}}REP(i, n+1) dpite(ALL(dp[i]));}double ans = 0;REP(x, k) REP(y, n-k+1) {DEBUG(x); DEBUG(y);DEBUG(dp[x][y]);ans += dp[x][y];}DEBUG(ans);return ans;};double ans = 0;FOR(x, 1, f+1) {ans += x * solve(x);}cout << ans << endl;}return 0;}