Submission #7525

#	Time	Username	Problem	Language	Result	Execution time	Memory
7525		tncks0121	경비원 (GA8_guard)	C++98	8 / 100	2000 ms	1128 KiB

guard

	
#include <cstdio>
using namespace std;
  
int gcd (int a, int b) { return b == 0 ? a : gcd(b, a%b); }
int n, a[100], g[100][100], x[100];
  
int main() {
    scanf("%d", &n);
    for(int i = 0; i < n; i++) scanf("%d", a+i);
    for(int i = 0; i < n; i++) {
        for(int j = i+1; j < n; j++) {
            g[i][j] = g[j][i] = gcd(a[i], a[j]);
        }
    }
  
  
        int res = 0;
    for(int state = 0; state < (1<<n); state++) {
        int c = 0;
        for(int i = 0; i < n; i++) if((state >> i) & 1) x[c++] = i;
        if(c <= 1) continue;
        bool s = true;
        for(int i = 0; i < c && s; i++) {
            for(int j = i+1; j < c && s; j++) {
                if(g[x[i]][x[j]] >= 2) s = false;
            }
        }
        if(s) {
            ++res;
        //for(int i = 0; i < c; i++) printf("%s%d%s", (i == 0) ? "{" : "", a[x[i]], ((i == c-1) ? "}\n": ", "));
        }
    }
  
    printf("%d\n", res);
    return 0;
}

• Subtask 1: 8 / 8
• Subtask 2: 0 / 13
• Subtask 3: 0 / 16
• Subtask 4: 0 / 27
• Subtask 5: 0 / 36