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

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條評論
主站蜘蛛池模板: 欧美金妇欧美乱妇xxxx | 国产一精品一aⅴ一免费 | 色偷偷亚洲女性天堂 | 国产亚洲一级精品久久 | 男人女人真曰批的视频动态 | 97dyy在线观看手机版 | 日韩欧国产精品一区综合无码 | 久青草中文字幕精品视频 | 九九99视频在线观看视频观看 | 久久综合九色综合97伊人麻豆 | 中文字幕在线不卡视频 | 5151四虎永久在线精品免费 | 欧美在线视频在线观看 | 免费看一级毛片 | 美国成人a免费毛片 | 999在线播放 | 真实子伦视频不卡 | 精品中文字幕一区二区三区四区 | 一级毛片在线免费观看 | 精品福利在线观看 | www.夜夜骑| 久久免费视频观看 | 国产伦一区二区三区免费 | 男人天堂免费 | 国产成人丝袜网站在线观看 | 精品外国呦系列在线观看 | 亚洲精品国产经典一区二区 | 一级毛片在线免费播放 | 国产精品亚洲国产三区 | 91亚洲最新精品 | 色综合精品久久久久久久 | 国产伦精品一区二区三区在线观看 | 免费看日韩欧美一级毛片 | 91国内精品线免费播放 | 久久国产精品国产精品 | 国产一区二区三区亚洲综合 | 亚洲高清在线观看播放 | 国内精品久久久久激情影院 | 国产免费一级高清淫曰本片 | 亚洲精品视频观看 | 国产片一区二区三区 |