亚洲免费在线-亚洲免费在线播放-亚洲免费在线观看-亚洲免费在线观看视频-亚洲免费在线看-亚洲免费在线视频

poj Anti-prime Sequences

系統 1852 0
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.?

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.?

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
      
      
        ;

}
      
    

poj Anti-prime Sequences


更多文章、技術交流、商務合作、聯系博主

微信掃碼或搜索:z360901061

微信掃一掃加我為好友

QQ號聯系: 360901061

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

【本文對您有幫助就好】

您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描上面二維碼支持博主2元、5元、10元、自定義金額等您想捐的金額吧,站長會非常 感謝您的哦!!!

發表我的評論
最新評論 總共0條評論
主站蜘蛛池模板: 久草视频免费 | 青草小视频 | 国产精品免费视频一区一 | 色综合欧美亚洲另类久久 | 亚洲视频91| 精品热99| 天天干夜夜添 | 亚洲国产精品成人综合色在线婷婷 | 在线观看精品视频一区二区三区 | a级在线观看视频 | 尤物久久99热国产综合 | 伊人精品综合 | 欧美色视频日本片免费高清 | 欧美一级毛片在线观看 | ww欧美 | 97午夜理伦片在线影院 | 久久精品久久精品久久精品 | 成人精品视频 成人影院 | 色婷婷综合久久久中文字幕 | 亚洲麻豆国产精品 | 福利一区视频 | 神马影院在线观看我不卡 | 日本精品夜色视频一区二区 | 99久久亚洲精品影院 | 久久久久久九 | 亚洲精品欧美精品国产精品 | 美女国产在线 | 国产成人免费视频精品一区二区 | 中文字幕一区二区三区四区 | 精品久久在线 | 永久黄网站色视频免费观看99 | 91视频网页版 | 亚洲国产综合专区在线播一一 | 国产成人综合网亚洲欧美在线 | 色综久久 | 国产人成激情视频在线观看 | 亚洲视频一区在线播放 | 久免费视频 | 免费观看黄色 | 99久久免费精品国产免费高清 | xxx色视频|