eolymp
bolt
Try our new interface for solving problems
Problems

Anti-prime Sequences

Anti-prime Sequences

Given a sequence of consecutive integers \textbf{n}, \textbf{n+1}, \textbf{n+2}, ..., \textbf{m}, an \textit{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 \textbf{n = 1} and \textbf{m = 10}, one such anti-prime sequence is \textbf{1}, \textbf{3}, \textbf{5}, \textbf{4}, \textbf{2}, \textbf{6}, \textbf{9}, \textbf{7}, \textbf{8}, \textbf{10}. This is also the lexicographically first such sequence. We can extend the definition by defining a degree \textbf{d}-\textit{anti-prime sequence} as one where all consecutive subsequences of length \textbf{2},\textbf{3},...,\textbf{d} sum to a composite number. The sequence above is a degree \textbf{2} anti-prime sequence, but not a degree \textbf{3}, since the subsequence \textbf{5},\textbf{4},\textbf{2} sums to \textbf{11}. The lexicographically .rst degree \textbf{3} anti-prime sequence for these numbers is \textbf{1}, \textbf{3}, \textbf{5}, \textbf{4}, \textbf{6}, \textbf{2}, \textbf{10}, \textbf{8}, \textbf{7}, \textbf{9}. \InputFile Input will consist of multiple input sets. Each set will consist of three integers, \textbf{n}, \textbf{m}, and \textbf{d} on a single line. The values of \textbf{n}, \textbf{m} and \textbf{d} will satisfy \textbf{1} ≤ \textbf{n} < \textbf{m} ≤ \textbf{1000}, and \textbf{2} ≤ \textbf{d} ≤ \textbf{10}. The line \textbf{0 0 0} will indicate end of input and should not be processed. \OutputFile 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 "\textbf{No anti-prime sequence exists}.".
Time limit 3 seconds
Memory limit 64 MiB
Input example #1
1 10 2
1 10 3
1 10 5
40 60 7
0 0 0
Output example #1
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