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
AC × 99
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