"Проще простого"
Имеется натуральное число N. Выяснить, на какое наименьшее количество непересекающихся групп можно разбить числа от 1 до N так, чтобы сумма чисел в каждой из групп была простым числом.
Вход:файл input.txt, в котором записано единственное число N
Ограничения: 1<N≤30000
Выход: файл output.txt, содержащий единственное число (минимальное количество групп)
Пример:
input.txt 18
output.txt 3
Примечание к примеру: числа от 1 до 18 можно разбить на три группы с нужным свойством
(например, 1+3+4+5+6+18, 2+7+8+9+10+11+12+13+14+17 и 15+16 с суммами 103, 37 и 31), на меньшее число групп, как легко показать, нельзя.
Добавлено через 6 мин.
"Острова"
В океане расположен архипелаг из N островов, каждый из которых имеет форму выпуклого многоугольника. Острова не соприкасаются и не пересекаются. Эти острова необходимо соединить между собой мостами так, чтобы от любого острова архипелага можно было добраться до любого другого. Каждый мост должен соединять пару островов, при этом суммарная длина мостов должна быть минимальной.
Вход: файл input.txt, имеющий следующую структуру: в первой строке входного файла записано число N – количество островов в архипелаге. Далее идет N строк с описанием островов. В каждой строке описывается один остров, который задаётся числом вершин (первое число строки) и далее их координатами в порядке обхода по часовой стрелке (у каждой вершины первой идет абсцисса, а второй - ордината). Координаты внутри строки разделяются пробелами.
Ограничения: число N – натуральное от 2 до 50 (включительно), для каждого острова число вершин не превосходит 20, все координаты – целые числа, не превосходящие по модулю 30000.
Выход: файл output.txt, содержащий два числа (по одному в строке), первая строка ¬- число: количество мостов; второе строка - число: суммарная длина мостов с точностью до 0.001
Пример 1:
Входной файл input.txt содержит:
2
4 –2 –2 –2 2 2 2 2 –2
3 3 –2 3 2 6 0
Результат (файл output.txt):
1
1
Пример 2:
Входной файл input.txt содержит:
3
4 –2 –2 –2 2 2 2 2 –2
3 -3 0 –5 –1 –5 1
3 6 –5 8 –4 8 -5
Результат (файл output.txt):
2
6