Anti-prime Sequences
Time Limit: ?3000MS | ? | Memory Limit: ?30000K |
Total Submissions: ?2175 | ? | Accepted: ?1022 |
Description
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.?
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
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.
Output
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.?
No anti-prime sequence exists.?
Sample Input
1 10 2 1 10 3 1 10 5 40 60 7 0 0 0
Sample Output
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
題意:求n到m的數中任意連續2到d的數的和是合數
DFS
#include<stdio.h> #include < string .h> #include <math.h> const int MAXN= 10001 ; int n,m,d; int vis[MAXN]; int num[MAXN]; int pri[MAXN]; int ans; int flag; void init () { memset(pri, 0 , sizeof (pri)); pri[ 0 ] = pri[ 1 ] = 1 ; for ( int i = 2 ; i <= 100 ; i++ ) { if ( pri[i] ) continue ; for ( int j = 2 ; i * j < 10001 ; j++ )//這里錯了 pri[i *j] = 1 ; } } bool judge( int t, int step) { num[step] = t; if (step> 0 ) { ans = 0 ; int judge= 0 ; for ( int j=step; j>=step-d+ 1 ; j-- ) { ans += num[j]; if (judge== 1 && pri[ans]== 0 ) { return false ; } judge = 1 ; if (j== 0 ) break ; } } return true ; } void DFS( int step) { int ans,i,t; if (flag) return ; if (step==m-n+ 1 ) // 已經找到了 { flag = 1 ; return ; } for (i=n; i<=m; i++ ) { t = 0 ; if (flag) return ; if (!vis[i] && judge(i,step)) { vis[i] = 1 ; DFS(step + 1 ); vis[i] = 0 ; } } } int main() { int i,j; init(); while (scanf( " %d%d%d " ,&n,&m,& d)) { flag = 0 ; if (n== 0 && m== 0 && d== 0 ) break ; memset(vis, 0 , sizeof (vis)); DFS( 0 ); if (!flag) printf( " No anti-prime sequence exists. " ); else { for (i= 0 ; i<=m-n; i++ ) if (i== 0 ) printf( " %d " ,num[i]); else printf( " ,%d " ,num[i]); } printf( " \n " ); } return 0 ; }
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索:z360901061

微信掃一掃加我為好友
QQ號聯系: 360901061
您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧,狠狠點擊下面給點支持吧,站長非常感激您!手機微信長按不能支付解決辦法:請將微信支付二維碼保存到相冊,切換到微信,然后點擊微信右上角掃一掃功能,選擇支付二維碼完成支付。
【本文對您有幫助就好】元
