Submission #169800


Source Code Expand

Copy
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int N, num;
vector<int> data;
int state[100 + 5];


int factorial( int n ){
    int f = 1;
    
    for (int i=1; i<=n ; i++ ){
        f *= i;
    }
    return f;
}

void check(int pos){
    for(unsigned int i = pos; i < data.size()-1; ++i){
        //cout << data[i+1] << " % " << data[pos] << "=" << data[i+1] % data[pos] << endl;
        if(data[i+1] % data[pos] == 0){
            if(state[i+1] == 1){
                state[i+1] = 0;
//                cout << "0 in" << state[i+1] << endl;
            }else{
                state[i+1] = 1;
                //cout << "1 in" << endl;
            }
        }
    }
}

int main(){
    int sum = 0;

    cin >> N;
    for(int i=0; i < N; i++){
        cin >> num;
        data.push_back(num);
    }

    int fac = factorial(N);

    // 全ての順列を出力
    do{
        for(int i = 0; i < 105; i++){
            state[i] = 1;
        }
        for(unsigned int i=0; i < data.size()-1; ++i){
/*
            for(int j = 0; j < N; j++){
                cout << data[j] << ",";
            }
            cout << endl;
            */
            check(i);
/*            
            for(int j = 0; j < N; j++){
                cout << state[j] << ",";
//                sum += state[j];
            }
            cout << endl;            
            */
        }
        //cout << "--- ";
        for(int j = 0; j < N; j++){
            //cout << state[j] << ",";
            sum += state[j];
        }
        //cout << endl;

    }while(next_permutation(data.begin(), data.end()));

    float res = (float)sum / fac;

    //cout << sum << ", " << fac << endl;

    cout << res << endl;


}

Submission Info

Submission Time
Task C - コイン
User hlr0shl
Language C++ (G++ 4.6.4)
Score 0
Code Size 1814 Byte
Status WA
Exec Time 2038 ms
Memory 932 KB

Judge Result

Set Name Sample Subtask1 Subtask2
Score / Max Score 0 / 0 0 / 99 0 / 1
Status
WA × 3
AC × 6
WA × 14
AC × 7
WA × 15
TLE × 18
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt
Subtask1 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 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 WA 21 ms 924 KB
sample_02.txt WA 24 ms 800 KB
sample_03.txt WA 22 ms 800 KB
subtask1_01.txt AC 22 ms 804 KB
subtask1_02.txt AC 22 ms 732 KB
subtask1_03.txt WA 23 ms 916 KB
subtask1_04.txt AC 36 ms 736 KB
subtask1_05.txt WA 35 ms 704 KB
subtask1_06.txt AC 23 ms 924 KB
subtask1_07.txt AC 36 ms 804 KB
subtask1_08.txt WA 22 ms 920 KB
subtask1_09.txt WA 23 ms 928 KB
subtask1_10.txt AC 35 ms 804 KB
subtask1_11.txt WA 23 ms 840 KB
subtask1_12.txt WA 35 ms 804 KB
subtask1_13.txt WA 21 ms 924 KB
subtask1_14.txt WA 23 ms 736 KB
subtask1_15.txt WA 26 ms 928 KB
subtask1_16.txt WA 22 ms 736 KB
subtask1_17.txt WA 25 ms 800 KB
subtask1_18.txt WA 25 ms 736 KB
subtask1_19.txt WA 30 ms 800 KB
subtask1_20.txt WA 34 ms 800 KB
subtask2_01.txt AC 1560 ms 928 KB
subtask2_02.txt WA 21 ms 920 KB
subtask2_03.txt TLE 2030 ms 860 KB
subtask2_04.txt TLE 2030 ms 808 KB
subtask2_05.txt TLE 2030 ms 864 KB
subtask2_06.txt TLE 2038 ms 932 KB
subtask2_07.txt TLE 2030 ms 864 KB
subtask2_08.txt TLE 2031 ms 928 KB
subtask2_09.txt TLE 2029 ms 796 KB
subtask2_10.txt TLE 2033 ms 864 KB
subtask2_11.txt TLE 2032 ms 868 KB
subtask2_12.txt TLE 2030 ms 808 KB
subtask2_13.txt TLE 2038 ms 868 KB
subtask2_14.txt TLE 2029 ms 872 KB
subtask2_15.txt TLE 2031 ms 804 KB
subtask2_16.txt TLE 2036 ms 848 KB
subtask2_17.txt TLE 2030 ms 804 KB
subtask2_18.txt TLE 2030 ms 808 KB
subtask2_19.txt TLE 2034 ms 804 KB
subtask2_20.txt TLE 2031 ms 816 KB