Contest Duration: - (local time) (120 minutes) Back to Home

Submission #169376

Source Code Expand

Copy
```//
//  main.cpp
//  ARCH
//
//  Created by 鹿島 悠 on 2014/04/20.
//

#include <iostream>
#include <queue>
#include <set>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <stack>
#include <math.h>

typedef long long ll;
using namespace std;

bool used[8];
int coin[8];
ll sum_omote = 0;
ll sum_pattern = 0;
int N;

int cur_coin[8];

void reverse(int n, bool omote[])
{
for (int i = n+1; i < N; i++) {
if (cur_coin[i] % cur_coin[n] == 0) {
omote[i] = !omote[i];
}
}
}

void dfs(int n) {
if (n == N) {
sum_pattern++;
bool omote[N];
for (int j = 0; j < N; j++) {
omote[j] = true;
}
for (int j = 0; j < N; j++) {
//cout << cur_coin[j] << ' ';
reverse(j, omote);
}
//cout << endl;
for (int j = 0; j < N; j++) {
//cout << (omote[j] ? 'T' : 'F');
if (omote[j]) sum_omote++;
}
//cout << endl;
}

for (int i = 0; i < N; i++) {
if (!used[i]) {
used[i] = true;
cur_coin[n] = coin[i];
dfs(n+1);
used[i] = false;
}
}
}

int main(int argc, const char * argv[])
{
cin >> N;

if (N > 8) {
return 0;
}

sum_omote = 0;

for (int i = 0; i < N; i++) {
cin >> coin[i];
}

dfs(0);

//cout << sum_omote << endl;
//cout << sum_pattern << endl;
cout << (sum_omote / (double)sum_pattern) << endl;
}

```

#### Submission Info

Submission Time 2014-05-10 21:47:02+0900 C - コイン nida_001 C++11 (GCC 4.8.1) 99 1702 Byte WA 45 ms 928 KB

#### Judge Result

Score / Max Score 0 / 0 99 / 99 0 / 1
Status
 AC × 2 WA × 1
 AC × 20
 AC × 20 WA × 20
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt
Case Name Status Exec Time Memory
sample_01.txt WA 22 ms 800 KB
sample_02.txt AC 22 ms 800 KB
sample_03.txt AC 28 ms 744 KB
subtask1_01.txt AC 20 ms 924 KB
subtask1_02.txt AC 23 ms 804 KB
subtask1_03.txt AC 22 ms 928 KB
subtask1_04.txt AC 43 ms 732 KB
subtask1_05.txt AC 38 ms 796 KB
subtask1_06.txt AC 28 ms 672 KB
subtask1_07.txt AC 32 ms 676 KB
subtask1_08.txt AC 23 ms 796 KB
subtask1_09.txt AC 21 ms 672 KB
subtask1_10.txt AC 40 ms 796 KB
subtask1_11.txt AC 22 ms 916 KB
subtask1_12.txt AC 32 ms 792 KB
subtask1_13.txt AC 22 ms 796 KB
subtask1_14.txt AC 23 ms 796 KB
subtask1_15.txt AC 41 ms 796 KB
subtask1_16.txt AC 34 ms 796 KB
subtask1_17.txt AC 45 ms 736 KB
subtask1_18.txt AC 39 ms 672 KB
subtask1_19.txt AC 42 ms 672 KB
subtask1_20.txt AC 40 ms 796 KB
subtask2_01.txt WA 23 ms 716 KB
subtask2_02.txt WA 21 ms 736 KB
subtask2_03.txt WA 22 ms 788 KB
subtask2_04.txt WA 22 ms 796 KB
subtask2_05.txt WA 22 ms 800 KB
subtask2_06.txt WA 21 ms 676 KB
subtask2_07.txt WA 21 ms 800 KB
subtask2_08.txt WA 23 ms 796 KB
subtask2_09.txt WA 22 ms 800 KB
subtask2_10.txt WA 20 ms 672 KB
subtask2_11.txt WA 20 ms 796 KB
subtask2_12.txt WA 21 ms 676 KB
subtask2_13.txt WA 21 ms 736 KB
subtask2_14.txt WA 21 ms 764 KB
subtask2_15.txt WA 21 ms 800 KB
subtask2_16.txt WA 22 ms 764 KB
subtask2_17.txt WA 20 ms 672 KB
subtask2_18.txt WA 20 ms 672 KB
subtask2_19.txt WA 21 ms 800 KB
subtask2_20.txt WA 21 ms 672 KB