ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Sergey Politov                       2:5015/176.18  20 Jan 2002  07:16:33
 To : Kartohin Ruslan
 Subject : Re: ... Пpодолжение. Еще задачи.
 -------------------------------------------------------------------------------- 
 

 
 До меня дошли слухи, что *08.12.01* *20:50:11* пролетало сообщение
 от Kartohin к *All* про *"... Пpодолжение. Еще задачи."*. И я решил вмешаться.
 
  KR>     1. ---- (пpопущено за пpостотой задачи :)))     2. Дано игpовое поле
 
 [...]
 
  KR> кооpдината - стpока, втоpая столбец.
 
   Почему эта задача не пропущена из-за своей простоты? 
 
  KR> 3. Hа некой оцепленной теppитоpии (pазмеpа MxN (0<=M,N<=1000)) находится
 
 [...] 
 
  KR>     Пpимеp входного файла:     10 10     A:1,1     X:6,3     D:1,5
  KR> B:6,5     C:6,1     X:4,4
  KR>     Ответ: 6 3
 
 Вообще как и на большинстве областных задача поставлена мега не точно,
 что значит агент смотрит на север? Он видит тех у кого координати Y 
 больше, или надо что бы еще X совпадали, ну это еще можно понять из 
 примера. А вот такой вопрос, если тут все же второй вариант, то 
 закрывают подозреваемые друг друга, или нет? Я решал задачу при условии, что
 не закрывают, если же закрывают, то решение будет выглядеть несколько иначе.
 
 Все очень сильно зависит от огарничений. Пусть G - кол-во агентов, H - кол-во 
 подозреваемых. Так вот если G*H не больше 1e+6, то можно делать тупо. За первый
 проход по файлу запоминаем где какой агент стоит, за второй проход считаем 
 сколько агентов на кого смотрит. Сложность O(G*H).
 Можно предварительно отсортировать агентов по их координате, при чем агентов 
 A и B, по X, а при равенстве X по Y, а агентов C и D наоборот. Все группы
 агентов сортируются отдельно. Тогда можно значительно быстрее опрделять какие 
 агенты на кого смотрят, используя двоичный поиск. 
 Сложность O(G*logG+H*(logG+logG)), или O((G+H)*logG), что значительно быстрее.
 Особенно если подозреваемых будет значительно больше.
 
 np: Quorthon "Rain"
 
 Искренне Ваш
                Sergey Politov
 --- WP/95 Rus 1.78 Релиз 1  Reg.
  * Origin: Человек - побочный продукт любви. (2:5015/176.18)
 
 

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

Тема:    Автор:    Дата:    ... Пpодолжение. Еще задачи.   Kartohin Ruslan   08 Dec 2001 21:50:11   Re: ... Пpодолжение. Еще задачи.   Vadim Goncharov   12 Jan 2002 00:21:29   Re: ... Пpодолжение. Еще задачи.   Sergey Politov   20 Jan 2002 07:16:33