Условие: Имеются гири с массами: 1 г, 2 г, ..., N г (N<500000). Требуется написать программу, распределяющую эти гири на максимально возможное количество пар так, чтобы суммарный вес гирь в каждой паре выражался простым числом.
Технические условия: Ограничение по времени тестирования: по 3 секунды на один тест.
Формат входных данных: Входной файл INPUT.TXT содержит число N.
Формат выходных данных: В выходной файл OUTPUT.TXT выводится список найденных пар. Все числа в выходном файле разделяются пробелами и символами перевода строки. В каждой строке записывается одна найденная пара.
Примеры входных и выходных файлов: Input.txt 7
Output.txt 1 6 7 4 5 2
Решение: ---------- cut ---------- Для решения задачи найдем наименьшее простое число p, большее чем n. Тогда пары чисел (p-n, n), (p-n+1, n-1), ... будут удовлетворять условию задачи. А также легко заметить, что этими парами выбираются все числа интервала от p-n до n. Теперь повторяем эту процедуру для нового n равного p-n-1 до тех пор пока n>1. В результате получим максимальное количество пар n/2.
( , где [] - целая часть числа), удовлетворяющих условию задачи.
Изложенное выше и использовано в программе. ---------- cut ----------
var f, g : text; n, p, l, i : longint; function prost(n:longint) : boolean; var b : boolean; x : longint; begin b:=true; for x:=2 to round(sqrt(n)) do b:=b and (n mod x <> 0); prost:=b end;
begin assign(f,'input.txt'); reset(f); readln(f,n); assign(g,'output.txt'); rewrite(g); while n>1 do begin p:=n+1; while not prost(p) do p:=p+1; l:=p-n; for i:=0 to (n-l) div 2 do writeln(g,l+i,' ',n-i); n:=l-1 end; close(g) end.
