Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Печать | Помощь |
Задачи
2381. Букет из простых чисел
Динамическое программирование и запоминающие функцииОлимпиадные задачи на русском языке
| 07/04/2018 | Открытые командные соревнования по спортивному программированию "PRIME TIME" ( 1) |
Ограничения: время – 4s/4s, память – 512MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Финн нашёл в Цифровом мире полянку, на которой росло множество простых чисел и среди них
не было одинаковых. Финн решил собрать букет из простых чисел для Принцессы Бубльгум,
которой нравятся всякие научные штуки. Так как букет будет подарком на день рождения, то сумма
чисел в букете должна быть равна возрасту Принцессы. Кроме того, чтобы букет выглядел внушительно,
количество чисел в нём должно быть как можно больше.
Напишите программу, которая поможет Финну выбрать простые числа для букета.
Формат ввода
Первая строка ввода содержит одно целое число `T` (`1\ ≤\ T\ ≤\ 1000`) — количество тестовых случаев.
Далее следует `T` строк, каждая строка содержит одно целое число `N_i` (`7\ ≤\ N_i\ ≤\ 200000`).
Формат вывода
Для каждого тестового случая вывести строку, содержащую сначала целое число `K_i` — максимальное
количество простых чисел, которое нужно взять для составления букета, а затем `K_i` простых чисел в
порядке возрастания, сумма которых равна `N_i`. Если существует несколько вариантов для букета, то
можно вывести любой из них.
Пример ввода
2 828 11
Пример вывода
21 2 5 7 11 13 17 19 23 29 31 37 41 47 53 59 61 67 71 73 79 83 1 11
