![]() |
Модераторы: Alx, Fixin |
![]() ![]() ![]() |
|
Strannik |
|
|||
Бывалый ![]() Профиль Группа: Участник Сообщений: 154 Регистрация: 25.1.2007 Репутация: нет Всего: 2 |
В лесу растёт N(до 2500) деревьев. Они заданы своими координатами (натуральные числа до 10^9). Вывести номера деревьев между которыми минимальные расстояния.
На примере будет понятнее. Ввод 5 {кол-во деревьев} 1 4 {координаты дерева №1} 3 4 3 2 6 4 7 2 {координаты дерева №5} Между деревьями 1 и 2 и деревьями 2 и 3 расстояние 1, оно минимально, тогда выводим: Вывод 3 {кол-во деревьев с минимальными расстояниями} 1 2 3 {деревья между которыми есть минимальные расстояния} Добавлено @ 18:21 П.С. Да, чуть не забыл, чтоб жизнь мёдом не казалась - ограничение по памяти 65535 байт. |
|||
|
||||
Sartorius |
|
|||
![]() Эксперт ![]() ![]() ![]() Профиль Группа: Завсегдатай Сообщений: 1568 Регистрация: 18.7.2006 Где: Ivory tower Репутация: нет Всего: 37 |
А при чем тут ограничение по памяти? Скорее по времени нужно ограничивать. За O(N^2) считаем все расстояния и находим минимальное, ничего при этом не сохраняя. потом пробегаемся по исходному массиву второй раз за O(N^2) и выводим все пары, расстояние между которыми равно минимальному. Где подвох то? Причем здесь память?
|
|||
|
||||
V.A.KeRneL |
|
|||
![]() Vadim A. Kazantsev ![]() ![]() Профиль Группа: Участник Сообщений: 291 Регистрация: 3.12.2006 Где: Moscow, Russia Репутация: нет Всего: 14 |
Sartorius, в формате выходных данных, наверно, как обычно... ![]() Тут же, смотри, не пары, а номера всех деревьев, которые в таковые пары входят. З.Ы. Strannik, а почему на сей раз на Си нельзя, а только на Паскале? Это сообщение отредактировал(а) V.A.KeRneL - 15.2.2007, 08:12 -------------------- «C'est un pense-creux d'ici. C'est le meilleur et le plus irascible homme du monde...» © Ф.М. Достоевский, «Бесы» ---/)/)---(\.../)---(\(\ --(':'=)---(=';'=)---(=':') (")(")..)-(").--.(")-(..(")(") |
|||
|
||||
Strannik |
|
||||||
Бывалый ![]() Профиль Группа: Участник Сообщений: 154 Регистрация: 25.1.2007 Репутация: нет Всего: 2 |
Да я вижу что любят тут значки логичеких операций в названиях тем... решил поизощрятся... да С++ код разбирать неохота..
Да если за два прохода - то ни причём...
А за один проход? |
||||||
|
|||||||
Alexeis |
|
|||
![]() Амеба ![]() Профиль Группа: Админ Сообщений: 11743 Регистрация: 12.10.2005 Где: Зеленоград Репутация: 3 Всего: 459 |
В принципе, тут язык вообще можно указывать в любом формате. Правил раздела нет, значит действуют только общие правила форума. -------------------- Vit вечная память. Обсуждение действий администрации форума производятся только в этом форуме гениальность идеи состоит в том, что ее невозможно придумать |
|||
|
||||
Strannik |
|
|||
Бывалый ![]() Профиль Группа: Участник Сообщений: 154 Регистрация: 25.1.2007 Репутация: нет Всего: 2 |
Хорошо... буду знать. |
|||
|
||||
Sartorius |
|
|||
![]() Эксперт ![]() ![]() ![]() Профиль Группа: Завсегдатай Сообщений: 1568 Регистрация: 18.7.2006 Где: Ivory tower Репутация: нет Всего: 37 |
И за один просто. Запоминаем все индексы деревьев пар с минимальным расстоянием. Нашли пару с меньшим расстояним - очищам этот список. Ясно. что потребуется не более 2500*2 *2 байт. |
|||
|
||||
Strannik |
|
|||
Бывалый ![]() Профиль Группа: Участник Сообщений: 154 Регистрация: 25.1.2007 Репутация: нет Всего: 2 |
Ну и так можно...
|
|||
|
||||
![]() ![]() ![]() |
0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей) | |
0 Пользователей: | |
« Предыдущая тема | Интересные и занимательные задачи по программированию | Следующая тема » |
|
По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности Powered by Invision Power Board(R) 1.3 © 2003 IPS, Inc. |