Меню сайта

Категории раздела
Готовимся к олимпиаде по программированию (задачи взяты с сайта http://olimpiada.com.ru) [36]
Решение олимпиадных задач по программированию
Готовимся к олимпиаде по математике [3]
Решение олимпиадных задач по математике

Мини-чат

Наш опрос
Уважаемый посетитель сайта, к какой категории вы себя относите?
Всего ответов: 5525

Статистика

Онлайн всего: 1
Гостей: 1
Пользователей: 0


Главная

Регистрация

Вход
Вы вошли как Гость | Группа "Гости" | RSS


Личный сайт учителя математики и информатики

Фоновой Натальи Леонидовны



Четверг, 28.03.2024, 23:33
Главная » Файлы » Внеурочная деятельность » Готовимся к олимпиаде по программированию (задачи взяты с сайта http://olimpiada.com.ru)

Простые гири
14.02.2012, 08:24

Условие:
Имеются гири с массами: 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.
Категория: Готовимся к олимпиаде по программированию (задачи взяты с сайта http://olimpiada.com.ru) | Добавил: admin
Просмотров: 1346 | Загрузок: 0 | Рейтинг: 0.0/0
Всего комментариев: 0
Добавлять комментарии могут только зарегистрированные пользователи.
[ Регистрация | Вход ]
Форма входа

Поиск

Кнопка сайта

Одна кнопка

время жизни сайта

Сайт участвует
конкурс сайтов 

Новости образовани

Фраза дня

Web-мастеру

OperaFirefoxGoogle ChromeDownload Master
QIPSkypeµTorrentTeamViewer
Dr.Web CureITAvira AntiVirTotal CommanderCDBurnerXP
PicasaIrfanViewCheMaxDAEMON Tools
AIMPKMPlayerBSplayerK-Lite Codec Pack

Установить себе такой Блок
Скрипты и HTML для uCOz

Раскрутка сайта
Graffiti Decorations(R) Studio (TM) Site Promoter

Copyright MyCorp © 2024
/td>