eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Антипростые последовательности

Антипростые последовательности

Для заданной последовательности последовательных целых чисел \textbf{n}, \textbf{n+1}, \textbf{n+2}, ..., \textbf{m}, \textit{антипростой последовательностью} назовём такую перестановку этих чисел, что сумма каждой пары соседних чисел не является простым числом. Например, если \textbf{n} = \textbf{1} и \textbf{m} = \textbf{10}, одной из таких антипростых последовательностей является последовательность \textbf{1}, \textbf{3}, \textbf{5}, \textbf{4}, \textbf{2}, \textbf{6}, \textbf{9}, \textbf{7}, \textbf{8}, \textbf{10}. Эта последовательность также является лексикографически первой такою последовательностью для заданной последовательности. Мы можем расширить определение, определив степень \textbf{d} антипростой последовательности, т.е. все последовательные подпоследовательности длины \textbf{2}, \textbf{3}, ..., \textbf{d} будут в сумме давать составные числа. Последовательность, приведённая выше, имеет степень \textbf{2} антипростой последовательности, но не является последовательностью степени \textbf{3}, так как имеющаяся в ней последовательность \textbf{5}, \textbf{4}, \textbf{2} даёт сумму равную \textbf{11}. Лексикографически первой антипростой последовательностью степени \textbf{3} для этих чисел будет последовательность \textbf{1}, \textbf{3}, \textbf{5}, \textbf{4}, \textbf{6}, \textbf{2}, \textbf{10}, \textbf{8}, \textbf{7}, \textbf{9}. \InputFile Входные данные будут состоять из нескольких наборов входных данных. Каждый набор входных данных будет состоять из трех целых чисел \textbf{n}, \textbf{m} и \textbf{d} в одной строке. Значения \textbf{n}, \textbf{m} и \textbf{d} удовлетворяют неравенствам \textbf{1} ≤ \textbf{n} < \textbf{m} ≤ \textbf{1000}, \textbf{2} ≤ \textbf{d} ≤ \textbf{10}. Строка, содержащая \textbf{0 0 0}, будет означать конец ввода и не должна быть обработана. \OutputFile Для каждого набора входных данных вывести в отдельной строке состоящую из разделенных запятыми чисел антипростую последовательность степени \textbf{d} (не вставляйте между числами пробелы и не разделяйте вывод на несколько строк). В случае, если существует более одной антипростой последовательности, выведите лексикографически первую. В случае, если не существует антипростой последовательность заданной степени, выведите сообщение "\textbf{No anti-prime sequence exists.}".
Лимит времени 3 секунды
Лимит использования памяти 64 MiB
Входные данные #1
1 10 2
1 10 3
1 10 5
40 60 7
0 0 0
Выходные данные #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