Простые гири

From

Egor Tsygvintsev (2:452/77.57)

To

Evgeniy Jirnov ()

Date

2003-01-21T22:53:30Z

Area

RU.ALGORITHMS

     Хай, Evgeniy

 Понедельник Январь 20 2003 21:28, Evgeniy Jirnov писал All:

 EJ> Имеются гири с массами 1,2,3,...,N(N<=500000). Написать программу,
 EJ> распределяющую эти гири на максимально возможное количество пар так,
 EJ> чтобы суммарный вес гирь в каждой паре выражался простым числом.

берешь N (если N нечетно) или N+1 (если четно), и начинаешь увеличивать на 2, пока оно не станет простым. причем все суммы чисел (N+i-k,k) будут простыми числами. затем берешь i вместо N и крутишь по кругу, пока не придешь к 1, попутно считая количество пар.

зыж можно писать проще (собственно, как я и писал в первый раз) но работает в ~600 раз дольше. этот алгоритм вкладывается в пять секунд на любом тесте.

                    Бай, Egor Tsygvintsev.
--- ... Линия отреза ...
 * Origin:  Стояли звери около двери... (с) Стругацкие  (2:452/77.57)