| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Интересные и занимательные задачи по программированию > [PASCAL & !C++] Задача деревья... |
| Автор: Strannik 14.2.2007, 18:20 |
| В лесу растёт 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 14.2.2007, 18:44 |
| А при чем тут ограничение по памяти? Скорее по времени нужно ограничивать. За O(N^2) считаем все расстояния и находим минимальное, ничего при этом не сохраняя. потом пробегаемся по исходному массиву второй раз за O(N^2) и выводим все пары, расстояние между которыми равно минимальному. Где подвох то? Причем здесь память? |
| Автор: V.A.KeRneL 15.2.2007, 08:11 | ||
Sartorius, в формате выходных данных, наверно, как обычно...  Тут же, смотри, не пары, а номера всех деревьев, которые в таковые пары входят. З.Ы. Strannik, а почему на сей раз на Си нельзя, а только на Паскале? |
| Автор: Strannik 15.2.2007, 13:44 | ||||||
Да я вижу что любят тут значки логичеких операций в названиях тем... решил поизощрятся... да С++ код разбирать неохота..
Да если за два прохода - то ни причём...
А за один проход? |
| Автор: Alexeis 15.2.2007, 15:02 | ||
В принципе, тут язык вообще можно указывать в любом формате. Правил раздела нет, значит действуют только общие правила форума. |
| Автор: Strannik 15.2.2007, 18:01 | ||
Хорошо... буду знать. |
| Автор: Sartorius 15.2.2007, 18:09 | ||
И за один просто. Запоминаем все индексы деревьев пар с минимальным расстоянием. Нашли пару с меньшим расстояним - очищам этот список. Ясно. что потребуется не более 2500*2 *2 байт. |
| Автор: Strannik 17.2.2007, 19:37 |
| Ну и так можно... |
