Anti-prime Sequences

Time Limit: 3000MS		Memory Limit: 30000K
Total Submissions: 3355		Accepted: 1531

Given a sequence of consecutive integers n,n+1,n+2,...,m, an anti-prime sequence is a rearrangement of these integers so that each adjacent pair of integers sums to a composite (non-prime) number. For example, if n = 1 and m = 10, one such anti-prime sequence is 1,3,5,4,2,6,9,7,8,10. This is also the lexicographically first such sequence.


We can extend the definition by defining a degree danti-prime
sequence as one where all consecutive subsequences of length 2,3,...,d
sum to a composite number. The sequence above is a degree 2 anti-prime
sequence, but not a degree 3, since the subsequence 5, 4, 2 sums to 11.
The lexicographically .rst degree 3 anti-prime sequence for these
numbers is 1,3,5,4,6,2,10,8,7,9.

Input
will consist of multiple input sets. Each set will consist of three
integers, n, m, and d on a single line. The values of n, m and d will
satisfy 1 <= n < m <= 1000, and 2 <= d <= 10. The line 0 0
0 will indicate end of input and should not be processed.

For
each input set, output a single line consisting of a comma-separated
list of integers forming a degree danti-prime sequence (do not insert
any spaces and do not split the output over multiple lines). In the case
where more than one anti-prime sequence exists, print the
lexicographically first one (i.e., output the one with the lowest first
value; in case of a tie, the lowest second value, etc.). In the case
where no anti-prime sequence exists, output



No anti-prime sequence exists.

1 10 2

1 10 3

1 10 5

40 60 7

0 0 0

1,3,5,4,2,6,9,7,8,10

1,3,5,4,6,2,10,8,7,9

No anti-prime sequence exists.

40,41,43,42,44,46,45,47,48,50,55,53,52,60,56,49,51,59,58,57,54
题意：在【2，d】长度的连续序列的和都要为合数。
思路：DFS。

 1 #include<stdio.h>

 2 #include<algorithm>

 3 #include<iostream>

 4 #include<stdlib.h>

 5 #include<string.h>

 6 #include<queue>

 7 #include<stack>

 8 #include<math.h>

 9 using namespace std;

10 typedef long long LL;

11 bool prime[20000]= {0};

12 int tt[10000];

13 bool cm[1005];

14 int ts=0;

15 bool check(int n,int m);

16 int dfs(int n,int m,int d,int kk,int pp);

17 int main(void)

18 {

19     int i,j,k;

20     for(i=2; i<=1000; i++)

21     {

22         if(!prime[i])

23         {

24             for(j=i; (i*j)<=20000; j++)

25             {

26                 prime[i*j]=true;

27             }

28         }

29     }

30     int n,m;

31     while(scanf("%d %d %d",&n,&m,&k),n!=0&&m!=0&&k!=0)

32     {

33         memset(cm,0,sizeof(cm));

34         ts=0;

35         int uu=dfs(0,m-n+1,k,n,m);

36         if(uu)

37         {

38             printf("%d",tt[0]);

39             for(i=1; i<(m-n+1); i++)

40             {

41                 printf(",%d",tt[i]);

42             }

43             printf("\n");

44         }

45         else printf("No anti-prime sequence exists.\n");

46     }

47 }

48 bool check(int n,int m)

49 {

50     int i,j;

51

52

53         LL sum=tt[m];

54         for(i=m-1; i>=max(n,0); i--)

55         {

56             sum+=tt[i];

57             if(!prime[sum])

58                 return false;

59         }

60         return true;

61 }

62 int dfs(int n,int m,int d,int kk,int pp)

63 {

64     int i;

65     if(ts)return 1;

66     if(n==m)

67     {

68

69             bool cc=check(n-d,m-1);

70             if(!cc)

71             {

72                 return 0;

73             }

74         ts=1;

75         return 1;

76     }

77     else

78     {

79         bool cc=check(n-d,n-1);

80         if(cc)

81         {

82             for(i=kk; i<=pp; i++)

83             {

84                 if(ts)return 1;

85                 if(!cm[i])

86                 {

87                     tt[n]=i;

88                     cm[i]=true;

89                     int uu=dfs(n+1,m,d,kk,pp);

90                     cm[i]=false;

91                     if(uu)return 1;

92                 }

93             }

94         }

95         else return 0;

96     }

97     return 0;

98 }