Submission #1025801
Source Code Expand
#include <bits/stdc++.h> using namespace std; #define FOR(i,k,n) for(int i = (int)(k); i < (int)(n); i++) #define REP(i,n) FOR(i,0,n) #define ALL(a) a.begin(), a.end() #define MS(m,v) memset(m,v,sizeof(m)) typedef long long ll; typedef long double ld; typedef vector<int> vi; typedef vector<string> vs; typedef pair<int, int> pii; const int MOD = 1000000007; const int INF = MOD + 1; const ld EPS = 1e-12; template<class T> T &chmin(T &a, const T &b) { return a = min(a, b); } template<class T> T &chmax(T &a, const T &b) { return a = max(a, b); } /*--------------------template--------------------*/ typedef ld Data; typedef vector<Data> Array; typedef vector<Array> Matrix; bool is_zero(Data dat) { return (abs(dat) < EPS); } Matrix operator-(Matrix mat) { REP(i, mat.size()) REP(j, mat[0].size()) mat[i][j] = -mat[i][j]; return mat; } Matrix operator+(Matrix lhs, const Matrix &rhs) { REP(i, lhs.size()) REP(j, lhs[0].size()) lhs[i][j] = lhs[i][j] + rhs[i][j]; return lhs; } Matrix operator-(Matrix lhs, const Matrix &rhs) { REP(i, lhs.size()) REP(j, lhs[0].size()) lhs[i][j] = lhs[i][j] - rhs[i][j]; return lhs; } Matrix operator*(const Matrix &lhs, const Matrix &rhs) { Matrix res(lhs.size(), Array(rhs[0].size(), 0)); REP(i, lhs.size()) REP(j, rhs[0].size()) REP(k, rhs.size()) res[i][j] = fma(lhs[i][k], rhs[k][j], res[i][j]); return res; } Array operator+(const Array &lhs, const Array &rhs) { Array res = lhs; REP(i, rhs.size()) res[i] = res[i] + rhs[i]; return res; } Array operator*(const Matrix &lhs, const Array &rhs) { Array res(lhs.size()); REP(i, lhs.size()) res[i] = inner_product(begin(lhs[i]), end(lhs[i]), begin(rhs), Data(0)); return res; } Array operator*(Data scalar, const Array &rhs) { Array res(rhs.size()); REP(i, rhs.size()) res[i] = scalar * rhs[i]; return res; } Matrix transpose(const Matrix &A) { const int n = A[0].size(), m = A.size(); Matrix res(n, Array(m, 0)); REP(i, n)REP(j, m) res[i][j] = A[j][i]; return res; } Data inner_product_ex(const Array& a, const Array& b, const Matrix& m) { Array b_prime = m*b; return inner_product(begin(a), end(a), begin(b_prime), Data(0)); } Data norm(const Array &a) { return inner_product(begin(a), end(a), begin(a), Data(0)); } Data norm(const Array &a, const Matrix &M) { return inner_product_ex(a, a, M); } int rankMat(Matrix A) { const int n = A.size(), m = A[0].size(); int r = 0; for (int i = 0; r < n && i < m; ++i) { int pivot = r; for (int j = r + 1; j < n; ++j) if (abs(A[j][i]) > abs(A[pivot][i])) pivot = j; swap(A[pivot], A[r]); if (is_zero(A[r][i])) continue; for (int k = m - 1; k >= i; --k) A[r][k] = A[r][k] / A[r][i]; for (int j = r + 1; j < n; ++j) for (int k = m - 1; k >= i; --k) A[j][k] = fma(-A[r][k], A[j][i], A[j][k]); ++r; } return r; } Data det(Matrix A) { const int n = A.size(); Data D = Data(1); for (int i = 0; i < n; ++i) { int pivot = i; for (int j = i + 1; j < n; ++j) if (abs(A[j][i]) > abs(A[pivot][i])) pivot = j; swap(A[pivot], A[i]); D = D * A[i][i] * Data(i != pivot ? -1 : 1); if (is_zero(A[i][i])) break; for (int j = i + 1; j < n; ++j) for (int k = n - 1; k >= i; --k) A[j][k] = A[j][k] - A[i][k] * A[j][i] / A[i][i]; } return D; } Array gauss_jordan(const Matrix& A, const Array& b) { int n = A.size(); Matrix B(n, Array(n + 1)); REP(i, n)REP(j, n) B[i][j] = A[i][j]; REP(i, n) B[i][n] = b[i]; REP(i, n) { int pivot = i; FOR(j, i, n) { if (abs(B[j][i]) > abs(B[pivot][i])) pivot = j; } swap(B[i], B[pivot]); if (abs(B[i][i]) < EPS) return Array(); FOR(j, i + 1, n + 1) B[i][j] /= B[i][i]; REP(j, n) { if (i != j) { FOR(k, i + 1, n + 1) B[j][k] -= B[j][i] * B[i][k]; } } } Array x(n); REP(i, n) x[i] = B[i][n]; return x; } ld fact[111]; ld comb(int a, int b) { return fact[a] / fact[a - b] / fact[b]; } int n; Array calc(int a) { Array res(n); res[a - 1] = 1.0; ld exp = pow(1.0 / 3.0, a); REP(i, a + 1)REP(j, a + 1) { ld t = exp * comb(a, i) * comb(a - i, j); if (i + j > a) continue; int k = a - i - j; if (i == a || j == a || k == a || (i == j && j == k)) { res[a - 1] -= t; } else { int mn = INF; if (i != 0) chmin(mn, i); if (j != 0) chmin(mn, j); if (k != 0) chmin(mn, k); res[mn - 1] -= t; } } return res; } int main() { cin.sync_with_stdio(false); cout << fixed << setprecision(10); fact[0] = 1; REP(i, 110) fact[i + 1] = fact[i] * (i + 1); cin >> n; Matrix A(n, Array(n)); Array b(n); A[0][0] = 1.0; FOR(i, 1, n) b[i] = 1.0; FOR(i, 1, n) { Array t = calc(i + 1); A[i] = t; } Array x = gauss_jordan(A, b); cout << x[n - 1] << endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | C - ゲーマーじゃんけん |
User | amano |
Language | C++11 (GCC 4.8.1) |
Score | 100 |
Code Size | 4899 Byte |
Status | AC |
Exec Time | 29 ms |
Memory | 1312 KB |
Judge Result
Set Name | All | ||
---|---|---|---|
Score / Max Score | 100 / 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 | 19 ms | 928 KB |
input-003.txt | AC | 19 ms | 928 KB |
input-004.txt | AC | 19 ms | 928 KB |
input-005.txt | AC | 18 ms | 924 KB |
input-006.txt | AC | 20 ms | 924 KB |
input-007.txt | AC | 20 ms | 928 KB |
input-008.txt | AC | 18 ms | 924 KB |
input-009.txt | AC | 20 ms | 928 KB |
input-010.txt | AC | 20 ms | 924 KB |
input-011.txt | AC | 20 ms | 924 KB |
input-012.txt | AC | 20 ms | 924 KB |
input-013.txt | AC | 19 ms | 928 KB |
input-014.txt | AC | 20 ms | 928 KB |
input-015.txt | AC | 20 ms | 1056 KB |
input-016.txt | AC | 20 ms | 924 KB |
input-017.txt | AC | 20 ms | 924 KB |
input-018.txt | AC | 19 ms | 928 KB |
input-019.txt | AC | 18 ms | 928 KB |
input-020.txt | AC | 19 ms | 1052 KB |
input-021.txt | AC | 18 ms | 928 KB |
input-022.txt | AC | 19 ms | 924 KB |
input-023.txt | AC | 18 ms | 928 KB |
input-024.txt | AC | 19 ms | 1048 KB |
input-025.txt | AC | 20 ms | 928 KB |
input-026.txt | AC | 20 ms | 928 KB |
input-027.txt | AC | 20 ms | 928 KB |
input-028.txt | AC | 20 ms | 928 KB |
input-029.txt | AC | 19 ms | 924 KB |
input-030.txt | AC | 18 ms | 924 KB |
input-031.txt | AC | 18 ms | 928 KB |
input-032.txt | AC | 20 ms | 928 KB |
input-033.txt | AC | 20 ms | 924 KB |
input-034.txt | AC | 18 ms | 920 KB |
input-035.txt | AC | 21 ms | 932 KB |
input-036.txt | AC | 19 ms | 924 KB |
input-037.txt | AC | 21 ms | 1044 KB |
input-038.txt | AC | 18 ms | 1052 KB |
input-039.txt | AC | 20 ms | 924 KB |
input-040.txt | AC | 20 ms | 928 KB |
input-041.txt | AC | 20 ms | 924 KB |
input-042.txt | AC | 20 ms | 928 KB |
input-043.txt | AC | 20 ms | 1048 KB |
input-044.txt | AC | 20 ms | 928 KB |
input-045.txt | AC | 20 ms | 1052 KB |
input-046.txt | AC | 19 ms | 1052 KB |
input-047.txt | AC | 20 ms | 1052 KB |
input-048.txt | AC | 21 ms | 1056 KB |
input-049.txt | AC | 21 ms | 1060 KB |
input-050.txt | AC | 21 ms | 1056 KB |
input-051.txt | AC | 21 ms | 1056 KB |
input-052.txt | AC | 20 ms | 1052 KB |
input-053.txt | AC | 21 ms | 1052 KB |
input-054.txt | AC | 19 ms | 1056 KB |
input-055.txt | AC | 21 ms | 1052 KB |
input-056.txt | AC | 20 ms | 1052 KB |
input-057.txt | AC | 20 ms | 1044 KB |
input-058.txt | AC | 21 ms | 1096 KB |
input-059.txt | AC | 21 ms | 1052 KB |
input-060.txt | AC | 21 ms | 1056 KB |
input-061.txt | AC | 21 ms | 1056 KB |
input-062.txt | AC | 22 ms | 1048 KB |
input-063.txt | AC | 21 ms | 1184 KB |
input-064.txt | AC | 21 ms | 1172 KB |
input-065.txt | AC | 21 ms | 1056 KB |
input-066.txt | AC | 22 ms | 1056 KB |
input-067.txt | AC | 22 ms | 1048 KB |
input-068.txt | AC | 20 ms | 1056 KB |
input-069.txt | AC | 22 ms | 1104 KB |
input-070.txt | AC | 21 ms | 1184 KB |
input-071.txt | AC | 23 ms | 1048 KB |
input-072.txt | AC | 22 ms | 1176 KB |
input-073.txt | AC | 22 ms | 1056 KB |
input-074.txt | AC | 22 ms | 1180 KB |
input-075.txt | AC | 22 ms | 1172 KB |
input-076.txt | AC | 21 ms | 1180 KB |
input-077.txt | AC | 24 ms | 1052 KB |
input-078.txt | AC | 22 ms | 1184 KB |
input-079.txt | AC | 22 ms | 1184 KB |
input-080.txt | AC | 25 ms | 1184 KB |
input-081.txt | AC | 22 ms | 1180 KB |
input-082.txt | AC | 23 ms | 1064 KB |
input-083.txt | AC | 24 ms | 1184 KB |
input-084.txt | AC | 23 ms | 1176 KB |
input-085.txt | AC | 24 ms | 1176 KB |
input-086.txt | AC | 25 ms | 1140 KB |
input-087.txt | AC | 29 ms | 1184 KB |
input-088.txt | AC | 25 ms | 1308 KB |
input-089.txt | AC | 25 ms | 1184 KB |
input-090.txt | AC | 25 ms | 1176 KB |
input-091.txt | AC | 25 ms | 1180 KB |
input-092.txt | AC | 25 ms | 1184 KB |
input-093.txt | AC | 24 ms | 1180 KB |
input-094.txt | AC | 26 ms | 1184 KB |
input-095.txt | AC | 26 ms | 1172 KB |
input-096.txt | AC | 26 ms | 1184 KB |
input-097.txt | AC | 25 ms | 1180 KB |
input-098.txt | AC | 27 ms | 1184 KB |
input-099.txt | AC | 27 ms | 1312 KB |
input-100.txt | AC | 27 ms | 1276 KB |