Submission #7479988
Source Code Expand
// 3_drango2015pre_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>// 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> using namespace std; #define rep(i, n) for(int i = 0; i < (int)(n); i++) #define rep1(i, n) for(int i = 1; i <= (int)(n); i++) #define SZ(x) ((int)(x).size()) #define INF (1e16) #define MOD (1000000007) typedef long long ll; vector<double> dp; vector<vector<double>> ncr; void calc_ncr(int k){ for(int n = 1; n <= k; n++){ ncr[n][0] = 1; ncr[n][1] = n; for(int r = 2; r <= n; r++){ ncr[n][r] = ncr[n][r - 1] / r * (n - r + 1); } } } int hantei(int g, int c, int p){ char ch; if((g == 0 && c == 0) || (c == 0 && p == 0) || (p == 0 && g == 0)){ return g + c + p; } if(g == c && c == p){ // pattern 2-3 return g + c + p; } // g, c, pいずれも1人以上 if(g != 0 && c != 0 && p != 0){ if((g < c && g < p) || (c < g && c < p) || (p < g && p < c)){ // pattern2-1 if(g == min({g, c, p})) return g; else if(c == min({g, c, p})) return c; else return p; } if((g < p && c < p)){ return g; }else if((c < g && p < g)){ return c; }else{ return p; } } if(g == 0){ if(c <= p) return c; else return p; } if(c == 0){ if(p <= g) return p; else return g; } if(p == 0){ if(g <= c) return g; else return c; } } double dfs(int n){ if(dp[n] >= 0) return dp[n]; double expect = 0.0; double p_aiko = pow(1.0 / 3.0, n) * 3; if(n % 3 == 0){ double tmp = pow(1.0 / 3.0, n); tmp *= ncr[n][n / 3] * ncr[2 * n / 3][n / 3]; p_aiko += tmp; } for(int g = 0; g <= n; g++){ for(int c = 0; c <= n - g; c++){ int p = n - g - c; double p_gcp = pow(1.0 / 3.0, n) * ncr[n][g] * ncr[n - g][c]; int a = hantei(g, c, p); if(a == n) continue; expect += p_gcp * (dp[a] + 1); } } expect = (expect + p_aiko) / (1.0 - p_aiko); dp[n] = expect; return expect; } int main(){ cin.tie(0); ios::sync_with_stdio(false); int n; cin >> n; dp.resize(n + 1); ncr.resize(n + 1, vector<double> (n + 1)); rep(i, n + 1){ dp[i] = -1; } calc_ncr(n); dp[0] = 0; dp[1] = 0; cout << dfs(n) << endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | C - ゲーマーじゃんけん |
User | Yoko453 |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 3768 Byte |
Status | WA |
Exec Time | 3 ms |
Memory | 384 KB |
Judge Result
Set Name | All | ||||
---|---|---|---|---|---|
Score / Max Score | 0 / 100 | ||||
Status |
|
Set Name | Test Cases |
---|---|
All | input-002.txt, input-003.txt, input-004.txt, input-005.txt, input-006.txt, input-007.txt, input-008.txt, input-009.txt, input-010.txt, input-011.txt, input-012.txt, input-013.txt, input-014.txt, input-015.txt, input-016.txt, input-017.txt, input-018.txt, input-019.txt, input-020.txt, input-021.txt, input-022.txt, input-023.txt, input-024.txt, input-025.txt, input-026.txt, input-027.txt, input-028.txt, input-029.txt, input-030.txt, input-031.txt, input-032.txt, input-033.txt, input-034.txt, input-035.txt, input-036.txt, input-037.txt, input-038.txt, input-039.txt, input-040.txt, input-041.txt, input-042.txt, input-043.txt, input-044.txt, input-045.txt, input-046.txt, input-047.txt, input-048.txt, input-049.txt, input-050.txt, input-051.txt, input-052.txt, input-053.txt, input-054.txt, input-055.txt, input-056.txt, input-057.txt, input-058.txt, input-059.txt, input-060.txt, input-061.txt, input-062.txt, input-063.txt, input-064.txt, input-065.txt, input-066.txt, input-067.txt, input-068.txt, input-069.txt, input-070.txt, input-071.txt, input-072.txt, input-073.txt, input-074.txt, input-075.txt, input-076.txt, input-077.txt, input-078.txt, input-079.txt, input-080.txt, input-081.txt, input-082.txt, input-083.txt, input-084.txt, input-085.txt, input-086.txt, input-087.txt, input-088.txt, input-089.txt, input-090.txt, input-091.txt, input-092.txt, input-093.txt, input-094.txt, input-095.txt, input-096.txt, input-097.txt, input-098.txt, input-099.txt, input-100.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
input-002.txt | AC | 3 ms | 384 KB |
input-003.txt | AC | 1 ms | 256 KB |
input-004.txt | WA | 1 ms | 256 KB |
input-005.txt | WA | 1 ms | 256 KB |
input-006.txt | WA | 1 ms | 256 KB |
input-007.txt | WA | 1 ms | 256 KB |
input-008.txt | WA | 1 ms | 256 KB |
input-009.txt | WA | 1 ms | 256 KB |
input-010.txt | WA | 1 ms | 256 KB |
input-011.txt | WA | 1 ms | 256 KB |
input-012.txt | WA | 1 ms | 256 KB |
input-013.txt | WA | 1 ms | 256 KB |
input-014.txt | WA | 1 ms | 256 KB |
input-015.txt | WA | 1 ms | 256 KB |
input-016.txt | WA | 1 ms | 256 KB |
input-017.txt | WA | 1 ms | 256 KB |
input-018.txt | WA | 1 ms | 256 KB |
input-019.txt | WA | 1 ms | 256 KB |
input-020.txt | WA | 1 ms | 256 KB |
input-021.txt | WA | 1 ms | 256 KB |
input-022.txt | WA | 1 ms | 256 KB |
input-023.txt | WA | 1 ms | 256 KB |
input-024.txt | WA | 1 ms | 256 KB |
input-025.txt | WA | 1 ms | 256 KB |
input-026.txt | WA | 1 ms | 256 KB |
input-027.txt | WA | 1 ms | 256 KB |
input-028.txt | WA | 1 ms | 256 KB |
input-029.txt | WA | 1 ms | 256 KB |
input-030.txt | WA | 1 ms | 256 KB |
input-031.txt | WA | 1 ms | 256 KB |
input-032.txt | WA | 1 ms | 256 KB |
input-033.txt | WA | 1 ms | 256 KB |
input-034.txt | WA | 1 ms | 256 KB |
input-035.txt | WA | 1 ms | 256 KB |
input-036.txt | WA | 1 ms | 256 KB |
input-037.txt | WA | 1 ms | 256 KB |
input-038.txt | WA | 1 ms | 256 KB |
input-039.txt | WA | 1 ms | 256 KB |
input-040.txt | WA | 1 ms | 256 KB |
input-041.txt | WA | 1 ms | 256 KB |
input-042.txt | WA | 1 ms | 256 KB |
input-043.txt | WA | 1 ms | 256 KB |
input-044.txt | WA | 1 ms | 256 KB |
input-045.txt | WA | 1 ms | 256 KB |
input-046.txt | WA | 1 ms | 256 KB |
input-047.txt | WA | 1 ms | 256 KB |
input-048.txt | WA | 2 ms | 256 KB |
input-049.txt | WA | 1 ms | 256 KB |
input-050.txt | WA | 2 ms | 256 KB |
input-051.txt | WA | 2 ms | 256 KB |
input-052.txt | WA | 2 ms | 256 KB |
input-053.txt | WA | 2 ms | 256 KB |
input-054.txt | WA | 2 ms | 256 KB |
input-055.txt | WA | 2 ms | 256 KB |
input-056.txt | WA | 2 ms | 256 KB |
input-057.txt | WA | 2 ms | 256 KB |
input-058.txt | WA | 2 ms | 256 KB |
input-059.txt | WA | 2 ms | 256 KB |
input-060.txt | WA | 2 ms | 256 KB |
input-061.txt | WA | 2 ms | 256 KB |
input-062.txt | WA | 2 ms | 256 KB |
input-063.txt | WA | 2 ms | 256 KB |
input-064.txt | WA | 2 ms | 256 KB |
input-065.txt | WA | 2 ms | 256 KB |
input-066.txt | WA | 2 ms | 256 KB |
input-067.txt | WA | 2 ms | 256 KB |
input-068.txt | WA | 2 ms | 256 KB |
input-069.txt | WA | 2 ms | 256 KB |
input-070.txt | WA | 2 ms | 256 KB |
input-071.txt | WA | 2 ms | 256 KB |
input-072.txt | WA | 2 ms | 256 KB |
input-073.txt | WA | 2 ms | 256 KB |
input-074.txt | WA | 2 ms | 256 KB |
input-075.txt | WA | 2 ms | 256 KB |
input-076.txt | WA | 2 ms | 256 KB |
input-077.txt | WA | 2 ms | 256 KB |
input-078.txt | WA | 2 ms | 256 KB |
input-079.txt | WA | 2 ms | 256 KB |
input-080.txt | WA | 2 ms | 256 KB |
input-081.txt | WA | 2 ms | 384 KB |
input-082.txt | WA | 2 ms | 256 KB |
input-083.txt | WA | 2 ms | 384 KB |
input-084.txt | WA | 2 ms | 384 KB |
input-085.txt | WA | 2 ms | 384 KB |
input-086.txt | WA | 2 ms | 384 KB |
input-087.txt | WA | 2 ms | 384 KB |
input-088.txt | WA | 2 ms | 384 KB |
input-089.txt | WA | 2 ms | 384 KB |
input-090.txt | WA | 2 ms | 384 KB |
input-091.txt | WA | 2 ms | 384 KB |
input-092.txt | WA | 2 ms | 384 KB |
input-093.txt | WA | 2 ms | 384 KB |
input-094.txt | WA | 2 ms | 384 KB |
input-095.txt | WA | 2 ms | 384 KB |
input-096.txt | WA | 2 ms | 384 KB |
input-097.txt | WA | 2 ms | 384 KB |
input-098.txt | WA | 2 ms | 384 KB |
input-099.txt | WA | 2 ms | 384 KB |
input-100.txt | WA | 2 ms | 384 KB |