Re: Простые гири

From

Oleg Khovayko ()

To

Evgeniy Jirnov ()

Date

2003-01-21T07:22:57Z

Area

RU.ALGORITHMS

From: Oleg Khovayko <olegh@hotpop.com>

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

А что программу писать? И так все понятно, без всякой программы!
Таких пар будет N/2.

Как распределять? Ну например так:

Первая пара: 1 + 2 = 3

Далее: 3 + 8 =
        4 + 7 =
        5 + 6 =
        11

Ну а все остальные:
9  + 500000 =
10 + 499999 =
11 + 499998 = ....
250004 + 250005 = 500009

Вот и все. Количество пар максимально и равно N/2.
Сумма каждой пары - простое число, что и требовалось
по условию - либо 3, либо 11, либо 500009.

--- ifmail v.2.15dev5
 * Origin: Demos online service (2:5020/400)