Статистика решения: 7,32% участников полностью решили задачу, 26,83% набрали 0 баллов.

Решение задачи:

Очень важно осознать условие задачи и ограничения. Переформулировав условие, можно сказать, что требуется определить правильность расстановки станций по зонам. Если они расставлены правильно, то можно определить возможные границы первой зоны, если нет, то надо просто вывести -1. В условии явно не сказано, что г.Киров лежит в центре первой зоны, хотя это и отображено на рисунке. Существенно и то, что г.Киров не может быть одной из станций. Ограничения на расстояние и время работы отсекают попытку перебрать все возможные точки между станциями, где может лежать г.Киров (их можно получить, отсортировав станции по зонам, далее идя слева наткнувшись на возрастание номера зоны, определить правую границу, а левая граница будет первая отличающаяся по номеру зоны станция, находящаяся левее) и сопоставлением расстановки зон на имеющиеся станции. Рассмотрим способы решения задачи на первом входном примере:

1 способ. Относительно каждой станции можно выдвинуть первое утверждение: первая зона лежит либо слева – отрезок , либо справа – отрезок , где d – расстояние от Москвы до текущей станции, а k – номер зоны текущей станции. Сделав такие утверждения относительно всех станций, можно их совместить, то есть пересечь отрезки. Очевидно, что после пересечения всех отрезков по первому утверждению может получиться не более двух результирующих отрезков. Вот, кажется и все решение задачи, но нельзя торопиться. Если станция находиться в 1-ой зоне, то воспользовавшись первым утверждением мы не учтем того, что г.Киров не может быть станцией, поэтому утверждение измениться на: и соответственно (так как числа целые, то уменьшив правую границу первого выражения на 1 и увеличив левую границу второго выражения на один можно снова получить вид как в первом утверждении). Итак, если все станции находятся в первой зоне, то может получиться n+1 отрезок. Для реализации потребуется набор отрезков в текущий момент времени, отражающий возможное положение первой зоны, с которым для каждой зоны будем производить пересечение с парой гипотез о нахождении первой зоны. В частности для первого примера этим способом можно показать, что только одна точка может быть ответом:

 

 

 

Рассмотрим случай, когда несколько городов лежит в 1-ой зоне и образуются более двух отрезков:

 

 

 

Слева на рисунке отображены исходные отрезки, справа отображен процесс пересечения. Это худший случай – получилось n+1 отрезков. Такое решение будет работать со сложностью от O(n) до O(n²), что в принципе не много.

2 способ. Является улучшением первого и позволяет решать задачу почти за линейное время, но, к сожалению, вывод результата в этом случае иногда становится квадратичным. Что будет происходить, если не учитывать ситуацию со станциями в 1-ой зоне? А ничего, кроме возможного попадания г.Кирова в уже существующие станции. Это можно легко поправить, сохранив расстояние до станций в 1-ой зоне, и при выводе результата их учесть. Тогда будет только 3 возможных случая: на текущий момент либо 2 отрезка, либо 1, либо пустое множество, причем если уже был 1 отрезок, то 2 далее не получится, также и с пустым множеством.

Хоть уже и говорилось о недостатках этого метода, он все же работает быстрее первого, так как сущность выполняемых операций в квадратичной части намного проще, чем у первого способа (цикл и условие против получения пересечений 2-х и в плоть до n отрезков).

3 способ. Он кардинально отличается от первых двух. Он действительно дает линейный алгоритм работы, если не считать, что надо предварительно отсортировать станции по расстоянию от Москвы. Итак, станции расположены по порядку от Москвы. Так как первая станция самая левая, то можно предположить, что Киров лежит справа, то есть в . Аналогично для следующих станций. Будем хранить в массиве lsec[i] пересечение i-ого предположения и предположений для всех лежащих левее станций, это можно сделать с помощь пересечения этого промежутка с предыдущим, то есть lsec[i-1]. Сделаем аналогичное предположение и с правой стороны и сохраним эти пересечения в rsec, но в отличие от заполнения lsec, rsec[i] не будет включать предположение об i-ой станции. Это делается за 2N операций пересечения. Далее самое интересное. Зададимся вопросом, как можно определить, находится ли Киров между двумя соседними станциями? С помощью введенных нами структур это делается очень легко. Для i от 0 до N:

• есть обобщенное предположение, что г.Киров лежит правее i-ой станции в отрезке lsec[i] (отрезок включает предположение относительно i-ой станции);

• есть обобщенное предположение, что г.Киров лежит левее (i+1)-ой станции в отрезке rsec[i] (отрезок не включает предположение относительно i-ой станции, а только относительно станций правее i);

Тогда для определения истинности высказывания «Киров находится между i и i+1 станциями» надо пересечь lsec[i] и rsec[i]. Если получен не пустой отрезок, то в нем наверняка будет лежать Киров. Для того, чтобы быть уверенным, что Киров не является станцией, надо пересечь его еще с отрезком между i и i+1 станциями, не включая самих станций. И если этот отрезок не пуст, то ответ найден!

 

Примечание:

Были неудачные попытки решить задачу дихотомией, то есть определив между какими городами может лежать г.Киров, последовательно деля расстояние пополам найти точное расположение за log(x) операций, где x – максимальное расстояние между парой городов. Но, похоже, не смогли решить проблему до конца с определением направления, в которое нужно двигаться на каждом шаге.

 

 

 

Заданы точки (станции). Для каждой станции известно расстояние от начала координат (Москва) и зона. Зоны имеют одинаковую длину. Требуется определить координаты г. Кирова, от которого расходятся зоны.

1 10
910 1

0

2 10
910 1
800 15

-1