Олимпиадная задача. 11 класс

@zhenianor · Регистрация: 19.05.2013

Студворк — интернет-сервис помощи студентам

Задача 1: Минимальное расстояние (10).

Заранее спасибо!

Комментарий администратора

тексты заданий перепечатываем на форум. читаем правила

@zhenianor · 24.11.2013, 13:44 **[ТС]**

Прикладываю задачу в виде картинки.

@кот Бегемот · 25.11.2013, 15:31

И чего в ней олимпиадного? Расстояние между двумя точками не можешь вычислить и найти его минимум? Зачем тогда на олимпиаду собрался?

@zhenianor · 25.11.2013, 20:28 **[ТС]**

Дак вычисли же, пожалуйста, раз настолько это примитивно. Я ее сделал, до некоторой степени, просто хочется посмотреть другие, возможно, более рациональные варианты решений.

@кот Бегемот · 26.11.2013, 00:43

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

@Ромаха · 26.11.2013, 07:25

Сообщение от кот Бегемот

В цикле по единственной формуле находим расстояние между каждыми двумя точками и сравниваем его с минимумом, первоначально заданным как самое большое число. Запоминаем точки, соответствующие минимуму. Всё. Другие варианты отсутствуют.

Неа..
Гляньте ограничения, N <= 10^5
Вы предлагаете полный перебор каждых двух вершин..
Что будет долго..

У кого-нибудь еще есть идеи по решению? (Вижу только вариант с деревом отрезков)

@bormant · 26.11.2013, 11:56

Сообщение от кот Бегемот

Расстояние между двумя точками

Функция y=sqrt(x) монотонно возрастающая, будет достаточно и квадрата расстояния между точками, сильно сэкономит время на извлечении корня.

Добавлено через 1 час 5 минут
В целях поиска минимального расстояния стоит подумать, можно ли для понижения вычислительной сложности использовать abs(x1-x2)+abs(y1-y2) вместо sqr(x1-x2)+sqr(y1-y2), избавившись от двух целочисленных умножений.

Добавлено через 1 час 39 минут
Ромаха, тестировал в виртуалке

Code
1
2
Intel(R) Core(TM) i3 CPU M350 @2.27GHz
smpboot: Total of 1 processors activated (4340.77 BogoMIPS)

Перебор по квадрату расстояния:

Code
1
2
3
4
5
6
Прочитано точек: 100000
982-985, (-9795;-2219) - (-9794;-2219), R2= 1, R= 1.00
 
real    0m31.220s
user    0m30.785s
sys 0m0.044s

Перебор по модулю:

Code
1
2
3
4
5
6
Прочитано точек: 100000
982-985, (-9795;-2219) - (-9794;-2219), R2= 1, R= 1.00
 
real    1m0.755s
user    0m59.678s
sys 0m0.134s

Обращаю внимание, что модуль (abs) оказался даже медленнее целочисленного возведения в квадрат (sqr).

Дополнительно можно прерывать перебор, если обнаружится расстояние 0 -- меньше уже не будет :-) В тестах выше этого нет.

@кот Бегемот · 26.11.2013, 12:35

Сообщение от bormant

В целях поиска минимального расстояния стоит подумать, можно ли для понижения вычислительной сложности использовать abs(x1-x2)+abs(y1-y2) вместо sqr(x1-x2)+sqr(y1-y2), избавившись от двух целочисленных умножений.

Это неверно. Например, разности получились (12 и 1) и (7 и 7) по формуле квадратов получается 145 и 98 а по формуле сумм модулей 13 и 14

PS уточнения о необязательности вычисления корня не отменяют принципа алгоритма, о котором я написал.

@bormant · 26.11.2013, 13:07

Сообщение от кот Бегемот

уточнения о необязательности вычисления корня не отменяют принципа алгоритма, о котором я написал

Естественно, с этим никто не спорил. Суть алгоритма -- полный перебор пар, отказ от извлечения корня -- это лишь способ понижения вычислительной сложности, в том числе сохранение только целочисленной арифметики.

Если кто-то предложит какие-либо эвристики по исключению из перебора заведомо проигрышных вариантов, могу сравнить затраты времени в сопоставимых с приведёнными выше цифрами условиях.

@zhenianor · 26.11.2013, 14:25 **[ТС]**

Сообщение от кот Бегемот

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

дак напиши же этот цикл, потом пиши. На словах и без тебя понятно, как решать.

@кот Бегемот · 26.11.2013, 14:34

А ложку тебе ко рту не поднести?

@zhenianor · 26.11.2013, 15:10 **[ТС]**

Сообщение от кот Бегемот

А ложку тебе ко рту не поднести?

ладно, с вами все ясно.

@Ромаха · 26.11.2013, 19:21

Сообщение от bormant

Ромаха, тестировал в виртуалке

Код?

Новичок · 26.11.2013, 19:28

Сообщение от Ромаха

Вы предлагаете полный перебор каждых двух вершин..

Смешно,зачем же каждых?

Pascal
1
2
for i:=1 to n-1 do
for j:=i+1 to n do

@Ромаха · 26.11.2013, 19:30

Сообщение от Новичок

Смешно,зачем же каждых?

Смешно^2, дык Вы и перебираете каждые..

Новичок · 26.11.2013, 19:31

А как по другому?Как?
P.S Каждые это

Pascal
1
2
for i:=1 to n do
for j:=1 to n do if i<>j then

@Ромаха · 26.11.2013, 19:54

Сообщение от Новичок

P.S Каждые это

Code
1
2
for i:=1 to n do
for j:=1 to n do if i<>j then

Это называется тупой полный перебор..

Добавлено через 20 минут
И даже "Ваш" вариант, который перебирает "не каждые 2", не укладывается даже в 15 сек.тыц

Новичок · 26.11.2013, 20:03

А вот это уже интересно.А там что 15 секунд ограничения?И как тогда быть?Я то и сам готовлюсь к олимпиаде.

@Ромаха · 26.11.2013, 20:17

Сообщение от Новичок

А там что 15 секунд ограничения?

Я никогда не видел ограничений больших 15 с.

И как тогда быть?

Замечательный вопрос..
Если бы мы искали MAX, можно было бы придумать что-то с поиском мин и макс точки (по каким-то критериям), а вот с Min - это проблема..

Я вот думаю, а что если отсортировать точки? За O (N log N) отсортировать, найти min разницу.. за O(N)
И того..
10^5*17 + 10^5 = 1800000
А такое кол-во операций мы сделаем за секунду (если не меньше)..
Осталось придумать по какому правилу сортировать..
Предлагаю так, как точки располагаются на плоскости, тоесть точка A (x1, y1) > B(x2, y2), тогда и только тогда, Abs(x1+y1) > Abs(x2+y2) // не уверен, а проверить нет времени..

Сообщение от Новичок

Я то и сам готовлюсь к олимпиаде.

Удачи, коллега

Новые блоги и статьи Все статьи Все блоги /
Old Classic Notepad for Windows 11 Jel 10.01.2026 Old Classic Notepad for Windows 11 Приложение для Windows 11, позволяющее пользователям вернуть классическую версию текстового редактора «Блокнот» из Windows 10. Программа предоставляет более. . .	Почему дизайн решает? Neotwalker 09.01.2026 В современном мире, где конкуренция за внимание потребителя достигла пика, дизайн становится мощным инструментом для успеха бренда. Это не просто красивый внешний вид продукта или сайта — это. . .	Модель микоризы: классовый агентный подход 3 anaschu 06.01.2026 aa0a7f55b50dd51c5ec569d2d10c54f6/ O1rJuneU_ls https:/ / vkvideo. ru/ video-115721503_456239114	Owen Logic: О недопустимости использования связки «аналоговый ПИД» + RegKZR ФедосеевПавел 06.01.2026 Owen Logic: О недопустимости использования связки «аналоговый ПИД» + RegKZR ВВЕДЕНИЕ Введу сокращения: аналоговый ПИД — ПИД регулятор с управляющим выходом в виде числа в диапазоне от 0% до. . .
Модель микоризы: классовый агентный подход 2 anaschu 06.01.2026 репозиторий https:/ / github. com/ shumilovas/ fungi ветка по-частям. коммит Create переделка под биомассу. txt вход sc, но sm считается внутри мицелия. кстати, обьем тоже должен там считаться. . . .	Расчёт токов в цепи постоянного тока igorrr37 05.01.2026 / * Дана цепь постоянного тока с сопротивлениями и напряжениями. Надо найти токи в ветвях. Программа составляет систему уравнений по 1 и 2 законам Кирхгофа и решает её. Последовательность действий:. . .	Новый CodeBlocs. Версия 25.03 palva 04.01.2026 Оказывается, недавно вышла новая версия CodeBlocks за номером 25. 03. Когда-то давно я возился с только что вышедшей тогда версией 20. 03. С тех пор я давно снёс всё с компьютера и забыл. Теперь. . .	Модель микоризы: классовый агентный подход anaschu 02.01.2026 Раньше это было два гриба и бактерия. Теперь три гриба, растение. И на уровне агентов добавится между грибами или бактериями взаимодействий. До того я пробовал подход через многомерные массивы,. . .

@zhenianor 0 / 0 / 0 Регистрация: 19.05.2013 Сообщений: 48
	24.11.2013, 13:44 [ТС]
	Прикладываю задачу в виде картинки. Миниатюры 0

@кот Бегемот Платежеспособный зверь 8964 / 4387 / 1654 Регистрация: 28.10.2009 Сообщений: 11,645
	25.11.2013, 15:31
	И чего в ней олимпиадного? Расстояние между двумя точками не можешь вычислить и найти его минимум? Зачем тогда на олимпиаду собрался? 0

@zhenianor 0 / 0 / 0 Регистрация: 19.05.2013 Сообщений: 48
	25.11.2013, 20:28 [ТС]
	Дак вычисли же, пожалуйста, раз настолько это примитивно. Я ее сделал, до некоторой степени, просто хочется посмотреть другие, возможно, более рациональные варианты решений. 0

@кот Бегемот Платежеспособный зверь 8964 / 4387 / 1654 Регистрация: 28.10.2009 Сообщений: 11,645
	26.11.2013, 00:43
	Чо ты врёшь, мальчик? Какие там могут быть варианты решения? В цикле по единственной формуле находим расстояние между каждыми двумя точками и сравниваем его с минимумом, первоначально заданным как самое большое число. Запоминаем точки, соответствующие минимуму. Всё. Другие варианты отсутствуют. 0

@кот Бегемот Платежеспособный зверь 8964 / 4387 / 1654 Регистрация: 28.10.2009 Сообщений: 11,645
	26.11.2013, 14:34
	А ложку тебе ко рту не поднести? 0

Новичок 1682 / 1098 / 489 Регистрация: 17.07.2012 Сообщений: 5,360
	26.11.2013, 20:03
	А вот это уже интересно.А там что 15 секунд ограничения?И как тогда быть?Я то и сам готовлюсь к олимпиаде. 0