Модераторы: Alx, Fixin
  

Поиск:

Ответ в темуСоздание новой темы Создание опроса
> [PASCAL & !C++] Задача деревья... 
:(
    Опции темы
Strannik
Дата 14.2.2007, 18:20 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Бывалый
*


Профиль
Группа: Участник
Сообщений: 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 байт.
PM MAIL   Вверх
Sartorius
Дата 14.2.2007, 18:44 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
***


Профиль
Группа: Завсегдатай
Сообщений: 1568
Регистрация: 18.7.2006
Где: Ivory tower

Репутация: нет
Всего: 37



 А при чем тут ограничение по памяти? Скорее по времени нужно ограничивать. За O(N^2) считаем все расстояния и находим минимальное, ничего при этом не сохраняя. потом пробегаемся по исходному массиву второй раз за O(N^2)  и выводим все пары, расстояние между которыми равно минимальному. Где подвох то? Причем здесь память?
PM MAIL ICQ   Вверх
V.A.KeRneL
  Дата 15.2.2007, 08:11 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Vadim A. Kazantsev
**


Профиль
Группа: Участник
Сообщений: 291
Регистрация: 3.12.2006
Где: Moscow, Russia

Репутация: нет
Всего: 14



Цитата(Sartorius @  14.2.2007, 18:44 Найти цитируемый пост)

... и выводим все пары, расстояние между которыми равно минимальному. Где подвох то? ...

Sartorius, в формате выходных данных, наверно, как обычно... smile
Тут же, смотри, не пары, а номера всех деревьев, которые в таковые пары входят.

З.Ы. 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...» © Ф.М. Достоевский, «Бесы»
---/)/)---(\.../)---(\(\
--(':'=)---(=';'=)---(=':')
(")(")..)-(").--.(")-(..(")(")

PM MAIL IM ICQ AOL YIM MSN   Вверх
Strannik
Дата 15.2.2007, 13:44 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Бывалый
*


Профиль
Группа: Участник
Сообщений: 154
Регистрация: 25.1.2007

Репутация: нет
Всего: 2



Цитата

З.Ы. Strannik, а почему на сей раз на Си нельзя, а только на Паскале?

Да я вижу что любят тут значки логичеких операций в названиях тем... решил поизощрятся... да С++ код разбирать неохота..

Цитата

Где подвох то? Причем здесь память?

Да если за два прохода - то ни причём...
Цитата

потом пробегаемся по исходному массиву второй раз за O(N^2)

А за один проход?
PM MAIL   Вверх
Alexeis
Дата 15.2.2007, 15:02 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Амеба
Group Icon


Профиль
Группа: Админ
Сообщений: 11743
Регистрация: 12.10.2005
Где: Зеленоград

Репутация: 3
Всего: 459



Цитата(Strannik @  15.2.2007,  13:44 Найти цитируемый пост)
Да я вижу что любят тут значки логичеких операций в названиях тем... решил поизощрятся... да С++ код разбирать неохота..

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


--------------------
Vit вечная память.

Обсуждение действий администрации форума производятся только в этом форуме

гениальность идеи состоит в том, что ее невозможно придумать
PM ICQ Skype   Вверх
Strannik
Дата 15.2.2007, 18:01 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Бывалый
*


Профиль
Группа: Участник
Сообщений: 154
Регистрация: 25.1.2007

Репутация: нет
Всего: 2



Цитата

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


Хорошо... буду знать.

PM MAIL   Вверх
Sartorius
Дата 15.2.2007, 18:09 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
***


Профиль
Группа: Завсегдатай
Сообщений: 1568
Регистрация: 18.7.2006
Где: Ivory tower

Репутация: нет
Всего: 37



Цитата

А за один проход? 

 И за один просто. Запоминаем все индексы деревьев  пар с минимальным расстоянием. Нашли пару с меньшим расстояним - очищам этот список. Ясно. что потребуется не более 2500*2 *2  байт.
PM MAIL ICQ   Вверх
Strannik
Дата 17.2.2007, 19:37 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Бывалый
*


Профиль
Группа: Участник
Сообщений: 154
Регистрация: 25.1.2007

Репутация: нет
Всего: 2



Ну и так можно...
PM MAIL   Вверх
  
Ответ в темуСоздание новой темы Создание опроса
0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема | Интересные и занимательные задачи по программированию | Следующая тема »


 




[ Время генерации скрипта: 0.0698 ]   [ Использовано запросов: 22 ]   [ GZIP включён ]


Реклама на сайте     Информационное спонсорство

 
По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности     Powered by Invision Power Board(R) 1.3 © 2003  IPS, Inc.