ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Max Alekseyev                        2:5015/60      29 Jan 2002  18:23:10
 To : Anton Svatkov
 Subject : муха
 -------------------------------------------------------------------------------- 
 

 
 Replying to a message of Anton Svatkov to All:
 
  AS> Hедавно была олимпиада, так вот там задача была про мух в поле
  AS> 100х100. Мух - рандомно, расположение тоже. Есть мухобойка 20х20.
  AS> Hадо стукнуть так, чтобы убить максимум мух. Так вот мне ничего кроме
  AS> перемещения центра мухобойки и сканирования в голову не пришло. Может
  AS> all подскажет какой-нибудь более красивый и быстрый алгоритм?
 
 Легко показать, что существует положение мухобойки, накрывающей максимальное
 число мух, такое что одна муха находится на ее левой стороне и одна на ее нижней
 стороне (или же это одна и та же муха находящаяся в левом нижнем углу).
 Перебирая всевозможные пары мух, получаем алгоритм со сложностью O(n^3), где n -
 число мух.
 
 Regards,      ш.ш
         Max    ~
 
 --- FleetStreet 1.27.3.7
  * Origin:  (2:5015/60)
 
 

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

Тема:    Автор:    Дата:    муха   Anton Svatkov   29 Jan 2002 13:22:30   муха   Max Alekseyev   29 Jan 2002 18:23:10   Re: муха   Sergey Politov   30 Jan 2002 07:17:38   муха   Anton Svatkov   31 Jan 2002 18:57:59   муха   Boris Sivko   01 Feb 2002 00:55:55   Re: муха   Sergey Politov   01 Feb 2002 07:17:13   муха   Boris Sivko   01 Feb 2002 19:06:05   Re: муха   Sergey Politov   02 Feb 2002 07:25:24   муха   vitalie vrabie   23 Feb 2002 03:00:20   Re: муха   Sergey Politov   01 Feb 2002 07:17:49