답안 #7584

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
7584	2014-08-11T13:18:16 Z	dohyun0324	경비원 (GA8_guard)	C++	8 / 100	60 ms	1096 KB

guard

#include<stdio.h>
int cnt,n,a[2510],m,ch[30],w;
int gcd(int x,int y)
{
    if(x%y==0) return y;
    return gcd(y,x%y);
}
void dfs(int x)
{
    int i;
    if(x==n)
    {
        if(w>=2)
        {
            cnt++;
        }
        return;
    }
    dfs(x+1);
    for(i=1;i<=w;i++)
    {
        if(gcd(ch[i],a[x+1])!=1) break;
    }
    if(i!=w+1) return;
    ch[++w]=a[x+1];
    dfs(x+1);
    ch[w--]=0;
}
int main()
{
    int i,j,s;
    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    scanf("%d",&n);
    for(i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        if(m<a[i]) m=a[i];
    }
    //subtask 1
    if(n<=20)
    {
        dfs(1);
        ch[++w]=a[1];
        dfs(1);
        printf("%d",cnt);
    }
    return 0;
}

Subtask #1

8.0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	1096 KB	Output is correct
2	Correct	0 ms	1096 KB	Output is correct
3	Correct	0 ms	1096 KB	Output is correct
4	Correct	0 ms	1096 KB	Output is correct
5	Correct	0 ms	1096 KB	Output is correct
6	Correct	0 ms	1096 KB	Output is correct
7	Correct	0 ms	1096 KB	Output is correct
8	Correct	0 ms	1096 KB	Output is correct
9	Correct	0 ms	1096 KB	Output is correct
10	Correct	0 ms	1096 KB	Output is correct
11	Correct	0 ms	1096 KB	Output is correct
12	Correct	0 ms	1096 KB	Output is correct
13	Correct	0 ms	1096 KB	Output is correct
14	Correct	0 ms	1096 KB	Output is correct
15	Correct	0 ms	1096 KB	Output is correct
16	Correct	0 ms	1096 KB	Output is correct
17	Correct	0 ms	1096 KB	Output is correct
18	Correct	0 ms	1096 KB	Output is correct
19	Correct	0 ms	1096 KB	Output is correct
20	Correct	0 ms	1096 KB	Output is correct
21	Correct	0 ms	1096 KB	Output is correct
22	Correct	0 ms	1096 KB	Output is correct
23	Correct	0 ms	1096 KB	Output is correct
24	Correct	0 ms	1096 KB	Output is correct
25	Correct	0 ms	1096 KB	Output is correct
26	Correct	0 ms	1096 KB	Output is correct
27	Correct	0 ms	1096 KB	Output is correct
28	Correct	0 ms	1096 KB	Output is correct
29	Correct	0 ms	1096 KB	Output is correct
30	Correct	60 ms	1096 KB	Output is correct
31	Correct	0 ms	1096 KB	Output is correct
32	Correct	0 ms	1096 KB	Output is correct
33	Correct	0 ms	1096 KB	Output is correct
34	Correct	0 ms	1096 KB	Output is correct
35	Correct	0 ms	1096 KB	Output is correct
36	Correct	0 ms	1096 KB	Output is correct
37	Correct	0 ms	1096 KB	Output is correct
38	Correct	0 ms	1096 KB	Output is correct
39	Correct	0 ms	1096 KB	Output is correct
40	Correct	0 ms	1096 KB	Output is correct
41	Correct	0 ms	1096 KB	Output is correct
42	Correct	24 ms	1096 KB	Output is correct

Subtask #2

0.0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	1096 KB	Output is correct
2	Correct	0 ms	1096 KB	Output is correct
3	Correct	0 ms	1096 KB	Output is correct
4	Correct	0 ms	1096 KB	Output is correct
5	Correct	0 ms	1096 KB	Output is correct
6	Correct	0 ms	1096 KB	Output is correct
7	Correct	0 ms	1096 KB	Output is correct
8	Correct	0 ms	1096 KB	Output is correct
9	Correct	0 ms	1096 KB	Output is correct
10	Correct	0 ms	1096 KB	Output is correct
11	Correct	0 ms	1096 KB	Output is correct
12	Correct	0 ms	1096 KB	Output is correct
13	Correct	0 ms	1096 KB	Output is correct
14	Correct	0 ms	1096 KB	Output is correct
15	Correct	0 ms	1096 KB	Output is correct
16	Correct	0 ms	1096 KB	Output is correct
17	Correct	0 ms	1096 KB	Output is correct
18	Correct	0 ms	1096 KB	Output is correct
19	Correct	0 ms	1096 KB	Output is correct
20	Incorrect	0 ms	1092 KB	Output isn't correct
21	Halted	0 ms	0 KB	-

Subtask #3

0.0 / 16.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	0 ms	1092 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #4

0.0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	0 ms	1092 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #5

0.0 / 36.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	0 ms	1092 KB	Output isn't correct
2	Halted	0 ms	0 KB	-