ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Egor Tsygvintsev                     2:452/77.57    21 Jan 2003  23:53:30
 To : Evgeniy Jirnov
 Subject : Простые гири
 -------------------------------------------------------------------------------- 
 

 
  Понедельник Январь 20 2003 21:28, Evgeniy Jirnov писал All:
 
  EJ> Имеются гири с массами 1,2,3,...,N(N<=500000). Hаписать программу,
  EJ> распределяющую эти гири на максимально возможное количество пар так,
  EJ> чтобы суммарный вес гирь в каждой паре выражался простым числом.
 
 берешь N (если N нечетно) или N+1 (если четно), и начинаешь увеличивать на 2,
 пока оно не станет простым. причем все суммы чисел (N+i-k,k) будут простыми
 числами. затем берешь i вместо N и крутишь по кругу, пока не придешь к 1,
 попутно считая количество пар.
 
 зыж можно писать проще (собственно, как я и писал в первый раз) но работает в
 ~600 раз дольше. этот алгоритм вкладывается в пять секунд на любом тесте.
 
                     Бай, Egor Tsygvintsev.
 --- ... Линия отреза ...
  * Origin:  Стояли звери около двери... (с) Стругацкие  (2:452/77.57)
 
 

Вернуться к списку тем, сортированных по: возрастание даты  уменьшение даты  тема  автор 

Тема:    Автор:    Дата:    Простые гири   Evgeniy Jirnov   20 Jan 2003 22:28:20   Re: Простые гири   Oleg Khovayko   21 Jan 2003 08:22:57   Простые гири   Sergey Politov   21 Jan 2003 07:46:56   Простые гири   Egor Tsygvintsev   21 Jan 2003 23:53:30