ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Sergey Politov                       2:5015/176.18  30 Jan 2002  07:17:38
 To : Anton Svatkov
 Subject : Re: муха
 -------------------------------------------------------------------------------- 
 

 
 До меня дошли слухи, что *29.01.02* *12:22:30* пролетало сообщение
 от Anton к *All* про *"муха"*. И я решил вмешаться.
 
  AS> Hедавно была олимпиада, так вот там задача была пpо мух в поле 100х100.
  AS> Мух - pандомно, pасположение тоже. Есть мухобойка 20х20. Hадо стукнуть
  AS> так, чтобы убить максимум мух. Так вот мне ничего кpоме пеpемещения
  AS> центpа мухобойки и сканиpования в голову не пpишло. Может all подскажет
  AS> какой-нибудь более кpасивый и быстpый алгоpитм?
 
 У меня возник такой вопрос, координаты мухи целые или вещественные?
 
 Если целые то вот решение, если вещественные то будем думать.
 
   имхо тут так и надо действовать, только пересчитывать количество не для все
 мухобойки, а только для одного ряда. Т.е. сначала ставим мухобойку в левый 
 верхний угол, расчитываем количество мух, которое мы сможем убить, двигаем 
 мухобойку вправо, что бы посчитать сколько мух мы убъем таким образом 
 надо из уже полученного количества вычесть количество мух которых мы накрывали
 в первом столбике, и прибавить количество мух которых мы накрыли в 21 столбике.
 Еще все это можно ускорить если для каждой клетки посчитать сколько мух сидит
 в ней и 19 клетках над ней, это тоже можно считать динамически. Тогда при
 размере
 поля n на m, а мухобойки k на l, получим сложность O(n*m). имхо лучше не 
 получиться.
 
 ЗЫ. поле храним следующим образом: для каждой клетки храним количество мух в 
 ней сидящих.
 
 Искренне Ваш
                Sergey Politov
 
 --- WP/95 Rus 1.78 Релиз 1  Reg.
  * Origin: Металл сила - всем рэперам могила. (2:5015/176.18)
 
 

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

Тема:    Автор:    Дата:    муха   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