Главное меню
Мы солидарны с Украиной. Узнайте здесь, как можно поддержать Украину.

Задачки

Автор arseniiv, октября 2, 2015, 02:08

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

arseniiv

Попробуйте решить такую задачу, которую решил мой знакомый школьник за дня полтора (но он был сильно занят):

Несколько циклопов стоят на плоском поле, на котором также по прямой S посажены каким-то образом очень тонкие, практически точечные в сечении кипарисы. За этой прямой идёт параллельная ей дорога Y, по которой ночью катается машина с одной точечной фарой, светящей во все стороны ярко, но кипарис её загородит, если попадётся на пути. Циклопы путём долгих размышлений встали так, что или каждому из них одновременно видна фара машины, где бы та ни находилась, или одновременно всем им она загорожена. Циклопы вас любят и послали вам своё расположение относительно друг друга и тех прямых. Они предлагают определить, какое подмножество S может быть занято кипарисами, и непременно требуют указать все возможные варианты.

Для определённости можно ввести на плоскости прямоугольные координаты и поставить S = { y = 0 }, Y = { y = 1 }, а циклопы находятся в каких-то точках полуплоскости { y < 0 }.

Hellerick

Кипарисы — где-угодно, все циклопы — в одной точке.

Разве может быть какое-то другое решение?  :donno:

Тайльнемер

Цитата: Hellerick от октября  2, 2015, 06:07
Разве может быть какое-то другое решение?  :donno:
Да. Например, если координаты циклопов — {(сi ∈ 2Z , −1) | iI (произвольное множество)}, то подойдёт расположение кипарисов {(z, 1) | z ∈ Z}.

Hellerick

Я ничего не понимаю в этих обозначениях.

Волод

Цитата: Hellerick от октября  2, 2015, 06:07
Кипарисы — где-угодно, все циклопы — в одной точке.

Разве может быть какое-то другое решение?  :donno:
На всех циклопов один глаз. :green:

Тайльнемер

Цитата: Hellerick от октября  2, 2015, 08:09
Я ничего не понимаю в этих обозначениях.
Я имел в виду: кипарисы — на всех целых координатах, циклопы — на чётных по иксу и −1 по игреку.

Hellerick

Цитата: Тайльнемер от октября  2, 2015, 08:02
Цитата: Hellerick от октября  2, 2015, 06:07
Разве может быть какое-то другое решение?  :donno:
Да. Например, если координаты циклопов — {(сi ∈ 2Z , −1) | iI (произвольное множество)}, то подойдёт расположение кипарисов {(z, 1) | z ∈ Z}.

Попытался расшифровать. Я так понимаю, у Арсениива кипарисы росли по линии y=0, тогда как у вас они оказались на линии y=1.

Тайльнемер

Ой, это я просто ошибся! Ноль, конечно же.

arseniiv

Да, по сути не важно, какой там игрек — главное, чтобы циклопы были отгорожены от фары линией кипарисов.

Цитата: Hellerick от октября  2, 2015, 06:07
все циклопы — в одной точке
Стоп-стоп, циклопы заданы, их находить не надо. Хотя можно найти все пары (положения циклопов, положения кипарисов) — это, собственно, и есть общее решение: функция из первого во второе.

_Swetlana

1. Если хотя бы два циклопа находятся на прямой, параллельной S, 0 кипарисов.
2. Если все циклопы находятся на одной прямой, не параллельной S, находим пересечение этой прямой с S, сажаем там 1 кипарис.
3. Циклопы не на одной прямой, любые два циклопа расположены на прямой, пересекающей S.
Пусть хотя бы в одном положении фара не видна всем циклопам. Проводим по двум точкам (фара-циклоп) прямые, прямых будет не менее двух, т.к. циклопы не на одной прямой. В точках пересечения сажаем по кипарису (их не менее двух). Теперь проводим прямые через циклопа и "чужой" кипарис, получаем положение фары, когда она не видна ровно одному циклопу. Тут получаем бесконечный процесс "сажания" кипарисов, каждый раз соединяя кипарис с "чужим" циклопом.
0 кипарисов.
🐇

_Swetlana

Так, кипарисов не обязательно конечное множество.
Для первого случая, когда два циклопа расположены на параллельной S прямой, нужно счётное множество кипарисов, координаты кипарисов можно вычислить. А если их не два, то их можно брать попарно разными способами... чего-то я в этой задаче не понимаю.
🐇

Тайльнемер

А циклоп циклопу загораживает свет фары?

_Swetlana

Загораживает кипарис. Если фара, кипарис и все циклопы находятся на одной прямой, то один кипарис загораживает свет всем циклопам.
Следующий случай: n-1 циклоп находятся на одной прямой, и один отдельно. Здесь тоже нужно проводить прямые через отдельного циклопа и ещё какого-нибудь. В условии сказано, что циклопы хотят знать все варианты, потому что они нас любят. Все варианты - значит все.
🐇

_Swetlana

Если циклопы расположены на параллельной прямой, тогда с ними всё ясно. Расмотрим двух циклопов A и B.
а) Если кипарисов нет, они всегда одновременно видят фару.
б) Предположим, что хотя бы в одной точке фара им не видна (обоим). Ставим точку O произвольно, соединяем с циклопами, сажаем два красных кипариса. Соединяем циклопов с чужими кипарисами и получаем точки, где фара видна ровно одному. Чтобы закрыть фару и другому, сажаем зелёные кипарисы.
По построению видно, что у нас получаются трапеции, у которых через пересечение диагоналей проведена прямая, параллельная основаниям. Отрезок этой прямой делится пополам. То есть кипарисы сажаем на равных расстояниях. Можно, конечно, координаты кипарисов посчитать через координаты точки O. Двум циклопам нужно счётное множество кипарисов.

Если циклопов несколько, то ставим т. O, сажаем исходные красные кипарисы, затем каждый отрезок откладываем бесконечное число раз в обе стороны, в концах этих отрезков сажаем зелёные кипарисы.

🐇

_Swetlana

С двумя циклопами на прямой, не параллельной дороге. Параллельная дорога будет частным случаем.
Пусть циклопы называются A и B, O - произвольная точка на дороге, пересечение прямой AO с дорогой (кипарис) A1, пересечение прямой ΒO с дорогой (кипарис) Β1.
Обозначим [tex]k_1=\frac{\left | AO \right |}{\left | A_1O \right |} [/tex]и [tex]k_2=\frac{\left | BO \right |}{\left | B_1O \right |}.[/tex]
Также обозначим расстояние между кипарисами [tex]a_0=\left | A_1B_1 \right | [/tex]. Тогда расстояния между кипарисами - геометрическая прогрессия с начальным членом [tex]a_0[/tex] и коэффициентом [tex]\frac{k_1}{k_2}[/tex].
В одну сторону отрезки будут уменьшаться, пока не выродятся до точки на прямой, проходящей через обоих циклопов, в другую - увеличиваться.
Когда циклопы на одной прямой, то [tex]k_1=k_2[/tex] и отрезки (между соседними кипарисами) равны.
🐇

_Swetlana

Нарисовала в сторону уменьшения расстояния между кипарисами. Кипарисов тоже счётно, но они ограничены прямой, проходящей через циклопов.
🐇

_Swetlana

Но как рассмотреть все случаи, не знаю. Циклопы! я вас люблю, но на сегодня всё  ;D
🐇

_Swetlana

...любовь еще, быть может,
В душе моей угасла не совсем;
Но пусть она вас больше не тревожит;
Я не хочу печалить вас ничем.
:-[
🐇

Тайльнемер

Цитата: Тайльнемер от декабря 21, 2015, 05:33
А циклоп циклопу загораживает свет фары?
На этот вопрос — ответ «нет»?
То есть, пустое множество кипарисов всегда попадёт в ответ?

_Swetlana

У меня циклопы просто точки на плоскости. Пустое множество кипарисов является решением только в случае, если все циклопы расположены на прямой, параллельной дороге.

🐇

_Swetlana

Опасная задача - в воскресенье вечером взялась за неё, а в понедельник узнала, что мне сильно некогда даже в те дни, когда ничто не предвещало. Вечером ещё порешаю  :)
🐇

Тайльнемер

Цитата: _Swetlana от декабря 22, 2015, 09:09
Пустое множество кипарисов является решением только в случае, если все циклопы расположены на прямой, параллельной дороге.
То есть таки загораживают они друг другу свет?

Цитата: _Swetlana от декабря 22, 2015, 09:09
У меня циклопы просто точки на плоскости.
Вот как? Они вас любят, а для вас они — просто точки... ;D

_Swetlana

Белоснежка и N циклопов, сказка для взрослых  :-[

Чтобы указать все решения хотя бы для двух циклопов, нужно перебрать все варианты множеств точек на дороге, которые циклопы не хотят видеть. А если циклопы не хотят видеть на прямой несчётное множество меры нуль? Что из себя будет представлять множество кипарисов? Кстати, какая там мера прямой по условиям задачи?
🐇

_Swetlana

Цитата: _Swetlana от декабря 21, 2015, 22:11
С двумя циклопами на прямой, не параллельной дороге. Параллельная дорога будет частным случаем.
Пусть циклопы называются A и B, O - произвольная точка на дороге, пересечение прямой AO с дорогой (кипарис) A1, пересечение прямой ΒO с дорогой (кипарис) Β1.
Обозначим [tex]k_1=\frac{\left | AO \right |}{\left | A_1O \right |} [/tex]и [tex]k_2=\frac{\left | BO \right |}{\left | B_1O \right |}.[/tex]
Также обозначим расстояние между кипарисами [tex]a_0=\left | A_1B_1 \right | [/tex]. Тогда расстояния между кипарисами - геометрическая прогрессия с начальным членом [tex]a_0[/tex] и коэффициентом [tex]\frac{k_1}{k_2}[/tex].
В одну сторону отрезки будут уменьшаться, пока не выродятся до точки на прямой, проходящей через обоих циклопов, в другую - увеличиваться.
Когда циклопы на одной прямой, то [tex]k_1=k_2[/tex] и отрезки (между соседними кипарисами) равны.
Очепятка  :-[ Не те отрезки для к-тов [tex]k_1[/tex] и [tex]k_2[/tex] написала.
[tex]k_1=\frac{\left | AO \right |}{\left | A_1A \right |} [/tex]и [tex]k_2=\frac{\left | BO \right |}{\left | B_1B \right |}.[/tex]

Окончательно, считаем, что два циклопа выбирают точку на прямой, которую они не хотят видеть. По этой точке и расположению циклопов сажаем два кипариса, расстояние между ними [tex]a_0[/tex], вычисляем к-ты [tex]k_1[/tex] и [tex]k_2[/tex]. Если [tex]k_1\neq k_2[/tex], то в одну сторону расстояние между кипарисами изменяется как геометрическая прогрессия с начальным членом [tex]a_0[/tex] и к-том [tex] \frac{k_1}{k_2}[/tex], в другую - с к-том [tex] \frac{k_2}{k_1}[/tex].
Если [tex]k_1=k_2[/tex], то циклопы находятся на прямой, параллельной дороге (обратная т-ма Фалеса), и кипарисы сажаем равномерно с шагом [tex]a_0[/tex] в обе стороны.

Для двух циклопов задача решена, я щетаю  :)
🐇


Быстрый ответ

Обратите внимание: данное сообщение не будет отображаться, пока модератор не одобрит его.

Имя:
Имейл:
Проверка:
Оставьте это поле пустым:
Наберите символы, которые изображены на картинке
Прослушать / Запросить другое изображение

Наберите символы, которые изображены на картинке:

√36:
ALT+S — отправить
ALT+P — предварительный просмотр