Submission #169655

---

Source Code Expand

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <sstream>
#include <functional>
#include <numeric>
#include <cmath>
#include <cstring>
#include <queue>
#include <stdio.h>

using namespace std;

const int INF = 1 << 29;
typedef pair<int, int> P;

int n = 0;
double ans = 0;
bool visited[100];
int coinRaw[100];
vector<int> coins;
void saiki(int count)
{
	if (count != n)
	{
		for (int i = 0; i < n; i++)
		{
			if (!visited[i])
			{
				visited[i] = true;
				coinRaw[i] = coins[count];
				saiki(count + 1);
				visited[i] = false;
			}
		}
	}
	else if (count == n)
	{
		vector<bool> reverse(n);
		for (int i = 0; i < n; i++)
		{
			reverse[i] = false;
		}
		for (int i = 0; i < n; i++)
		{
			for (int j = 1; j < n - i; j++)
			{
				if (coinRaw[i + j] % coinRaw[i] == 0)
				{
					reverse[i + j] = !reverse[i + j];
				}
			}
		}
		for (int i = 0; i < n; i++)
		{
			if (!reverse[i])
			{
				ans++;
			}
		}
	}
}
int main()
{
	while (cin >> n && n)
	{
		ans = 0;
		for (int i = 0; i < n; i++)
		{
			visited[i] = false;
			coinRaw[i] = 0;
		}
		coins.resize(n);
		for (int i = 0; i < n; i++)
		{
			cin >> coins[i];
		}
		double balance = 1;
		for (int i = 1; i <= n; i++)
		{
			balance *= i;
		}
		saiki(0);
		double ansInt = 0;
		ansInt = ans / balance;
		printf("%.10lf/n", ansInt);
	}
	return 0;
}

Submission Info

Judge Result