Автор Тема: Добрый день. Помогите решить... Вечеринка.  (Прочитано 808 раз)

0 Пользователей и 1 Гость просматривают эту тему.

Оффлайн maska11

  • Новичок
  • *
  • Сообщений: 27
    • Просмотр профиля
Деревня имеет форму квадрата со стороной 2 км. В ней n домов, в каждом живёт один человек. В 12.00   А. заскучал и решил устроить вечеринку в 19.00.  Сразу же начал обходить своих соседей с приглашением. Как только житель деревни узнавал о вечеринке, шёл приглашать остальных. Если все жители деревни ходят со скоростью 3 км/час решите, могли ли независимо от n и расположения домов,  распространить информацию так, чтобы все жители деревни собрались в 19.00 у А. дома на вечеринке.

Оффлайн Artem of 93

  • Эксперт
  • ******
  • Сообщений: 1117
    • Просмотр профиля
    • Mozgovarka
Re: Добрый день. Помогите решить... Вечеринка.
« Ответ #1 : 30 Сентябрь 2016, 23:04:35 »
Честно говоря, условия опять расплывчатые:

1) Что значит, что "А начал обходить соседей"? Кто его соседи? Дома справа и слева от него или вся деревня?
2) Что значит, что житель деревни "шёл приглашать остальных"? Тоже соседей или всю деревню?
3) Что значит, что деревня имеет форму квадрата? Жителям можно ходить только по сторонам квадрата или по диагоналям тоже?
Постоянный читатель "Смекалки" с 2013 года. Пишу комментарии на сайте под этим же ником. Мой сайт и блог.

Оффлайн maska11

  • Новичок
  • *
  • Сообщений: 27
    • Просмотр профиля
Re: Добрый день. Помогите решить... Вечеринка.
« Ответ #2 : 30 Сентябрь 2016, 23:28:46 »
Перевод практически дословный. Как я понимаю,  дома расположены по сторонам квадрата и внутри него произвольным образом, числом n. О направлении движения А вообще ничего не сказано, как и о том, сказал ли он только одному человеку или нескольким. О соседях сказано, что "как только человек получил информацию, шёл распространять её между остальными". Ходить можно как по сторонам, так и по диагонали.

Оффлайн Artem of 93

  • Эксперт
  • ******
  • Сообщений: 1117
    • Просмотр профиля
    • Mozgovarka
Re: Добрый день. Помогите решить... Вечеринка.
« Ответ #3 : 30 Сентябрь 2016, 23:47:32 »
Если предположить, что дома располагаются по периметру квадрата, то у меня такая версия.

Допустим, А пошёл к соседу справа, затем вернулся домой. Его сосед пошёл к своему соседу справа, после чего пошёл на вечеринку к А. И так далее. Либо они все вместе будут ходить по кругу. По сути, это ведь равносильно тому, что А сам будет обходить всю деревню. Периметр деревни равен 8 км, а так как скорость жителя равна 3 км/ч, понадобится 2 часа 40 минут, чтобы обойти всю деревню. Также возможен вариант, что А задаст цепную реакцию в обе стороны (сначала предупредит соседа справа, затем - соседа слева). Таким образом, к 19:00 вся деревня гарантированно соберётся на вечернику.

Правда, тогда сложно сказать, в чём смысл задачи.
Постоянный читатель "Смекалки" с 2013 года. Пишу комментарии на сайте под этим же ником. Мой сайт и блог.

Оффлайн StrannikPiter

  • Эксперт
  • ******
  • Сообщений: 1462
    • Просмотр профиля
Re: Добрый день. Помогите решить... Вечеринка.
« Ответ #4 : 30 Сентябрь 2016, 23:57:22 »
Тут как раз условия нормальные. Дома располагаются произвольно (по периметру это слишком просто), от дома к дому можно идти по прямой, как я понимаю. Чем больше домов, тем больше народу нужно оповещать, зато и среднее расстояние между домами меньше. Кроме того, число "оповещальщиков" растет в геометрической прогрессии. Интуитивно понятно, что 7 часов должно хватить и скорее всего с большим запасом. Но как строго доказать, пока не придумал.

Оффлайн StrannikPiter

  • Эксперт
  • ******
  • Сообщений: 1462
    • Просмотр профиля
Re: Добрый день. Помогите решить... Вечеринка.
« Ответ #5 : 01 Октябрь 2016, 00:06:46 »
А по поводу, кого считать соседями, то оповестить по условию нужно всех, но рациональней идти в первую очередь к ближайшим, чтобы не ходить много туда-сюда. И разумеется каждого достаточно оповестить один раз, не обязательно лично, можно и через цепочку других.
То есть как бы предполагается, что А. должен сразу выработать общую стратегию, кто к кому идет и в каком порядке оповещает, и передавать эту стратегию по цепочке, чтобы минимизировать время.

Оффлайн Artem of 93

  • Эксперт
  • ******
  • Сообщений: 1117
    • Просмотр профиля
    • Mozgovarka
Re: Добрый день. Помогите решить... Вечеринка.
« Ответ #6 : 01 Октябрь 2016, 00:10:43 »
Тут как раз условия нормальные.

Не согласен, что они нормальные. Условия задачи должны быть прописаны однозначно, должны быть обозначены все нюансы.
Постоянный читатель "Смекалки" с 2013 года. Пишу комментарии на сайте под этим же ником. Мой сайт и блог.

Оффлайн Головолом

  • Старожил
  • ****
  • Сообщений: 312
    • Просмотр профиля
    • E-mail
Re: Добрый день. Помогите решить... Вечеринка.
« Ответ #7 : 03 Октябрь 2016, 14:36:23 »
...решите, могли ли независимо от n и расположения домов,  распространить информацию так, чтобы все жители деревни собрались в 19.00 у А. дома на вечеринке.
Я решил, что могли  :rest:

Оффлайн StrannikPiter

  • Эксперт
  • ******
  • Сообщений: 1462
    • Просмотр профиля
Re: Добрый день. Помогите решить... Вечеринка.
« Ответ #8 : 03 Октябрь 2016, 17:34:28 »
Потребуется не больше 4 часов.
Можно предложить следующий алгоритм оповещения. А. выбирает дом, расположенный наиболее близко к одному из краев деревни (назовем его стартовый край) и идет туда. Теперь о вечеринке знают уже двое. Они делят деревню на две полосы, шириной в 1 км, которые узкой стороной начинаются на стартовом краю. Каждый выбирает неоповещенный дом на соей полосе, ближайший к стартовому краю. Каждый из них, дойдя до своего дома делит снова свою полосу на две, уже шириной 500 м.
Если идти всегда параллельно краям деревни (не срезать путь), то на то, чтобы прочесать всю деревню, от стартового края до финишного, А. потребуется максимум пройти 6 км, даже если он всегда будет выбирать из 2-х вариантов наиболее длинный.

6 км найдено так. Весь путь будет складываться из продольных и поперечных участков. Сумма всех продольных будет максимально равна 2 км от стартового края до финишного. Максимальная сумма поперечных участков будет представлять собой ряд вида
(1 + 1/2 + 1/4 + 1/8 + ... + 1/2m)*2 км. Этот ряд сходится при любых m, и его предельное значение будет равно 4 км.

Остается найти путь от дома А. до первого дома возле стартового края и от финишного края до дома А. Срезать тоже не будем, получим сумму продольных участков 2 км и 2 поперечных участка, каждый по 2 км. То есть еще 6 км.

Итого максимальный путь будет 12 км, на него потребуется 4 часа. Причем очевидно, что данный алгоритм не будет оптимальным. Во-первых можно срезать путь. Во-вторых можно делить на полосы не равной ширины (где плотность домов выше, там полоса уже). В-третьих наверняка выгодней не идти сразу на край, а зайти к ближайшему соседу, так как чем раньше увеличится число оповещальщиков, тем быстрее закончится весь процесс. Но это сложно решить в общем виде.