Submission #169376


Source Code Expand

Copy
//
//  main.cpp
//  ARCH
//
//  Created by 鹿島 悠 on 2014/04/20.
//  Copyright (c) 2014年 鹿島 悠. All rights reserved.
//

#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
Task C - コイン
User nida_001
Language C++11 (GCC 4.8.1)
Score 99
Code Size 1702 Byte
Status
Exec Time 45 ms
Memory 928 KB

Test Cases

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