Задача с областной олимпиады.

← →
VAD*Anti Gopn!k © (2008-01-30 14:31) [0]

Задача:
"на числовой прямой задано n точек. Необходимо найти среди них две ближайшие. Значения координат x[i] не превосходят 10^9 по абсолютной величине.

Ограничения: время работы 2 с, размер памяти 64 мб.

Задачу решил, но не уложился по времени на некоторых тестах.
Подскажите оптимальный алгоритм. Думал-думал не надумал. Может, есть какие эффективные методы сортировки.

← →
oldman © (2008-01-30 14:33) [1]

> на числовой прямой задано n точек

1. Вразброс или упорядочено?
2. Чем задано?

← →
VAD*Anti Gopn!k © (2008-01-30 14:40) [2]

1. разбросано.
2. числами. Например:
3 5 4 7 0 1 14

← →
Jeer © (2008-01-30 14:42) [3]

Если уже упорядочены, то:
Задача сводится к дискретному дифференцированию ( по простому - нахождение разностей между соседними двумя) и поиском максимума.
Как понимаю, линейная сложность.

← →
Jeer © (2008-01-30 14:43) [4]

Если не упорядочены - сортировка, затем, как описано.

← →
clickmaker © (2008-01-30 14:43) [5]

> Может, есть какие эффективные методы сортировки

а ты какой использовал?

← →
VAD*Anti Gopn!k © (2008-01-30 14:49) [6]

> Jeer © (30.01.08 14:43) [4]

Хе хе. В том то и фишка. Например, если сортировать методом пузырька то будет цикл до 10^9.l Пустой такой цикл работает 2.5 мин. а мне нужно 2 сек.

> clickmaker © (30.01.08 14:43) [5]

а я без сортировки обошелся. Тупо перебор. Фактически алгоритм цикла до 10^9, но нормально работает при не таких больших числах.

← →
Palladin © (2008-01-30 14:54) [7]

> а я без сортировки обошелся. Тупо перебор.

как же"ш ты на олимпиаду то областную попал...

← →
VAD*Anti Gopn!k © (2008-01-30 14:56) [8]

> Palladin © (30.01.08 14:54) [7]

Видать, и вы по другому не сможете решить. Сможете-буду очень благодарен. Она же не одна задача там...

← →
Jeer © (2008-01-30 15:03) [9]

> VAD*Anti Gopn!k © (30.01.08 14:49) [6]

Навскидку:
- пузырек
- Шелла
- Простые вставки
- Бинарные вставки
- Поиск минимума ( максимума)
- Пирамидальная
- Выбором
- Quick

В качестве домашнего задания - разобраться с каждой

← →
Riply © (2008-01-30 15:05) [10]

> Ограничения: время работы 2 с

Объясните пожалуйста, что это за ограничение ?

Или я чего-то не понимаю, или это бред сивой кобылы :)
Единственный случай, когда оно имеет смысл, если оно отведено на написание алгоритма. :)

← →
VAD*Anti Gopn!k © (2008-01-30 15:05) [11]

> Jeer © (30.01.08 15:03) [9]

Всех не знаю, НО

- пузырек
- Поиск минимума ( максимума)

отпадает ввиду вложенных циклов

← →
Jeer © (2008-01-30 15:10) [12]

> если оно отведено на написание алгоритма. :)

Именно:)

← →
atruhin © (2008-01-30 15:49) [13]

Может я чего не понимаю, но из условия задачи непонятно:
1. чему равно n, т.е. сколько точек.
2. время работы 2 с, на каком процессоре, Intel 386 или современный 4x ядерник.

← →
Denis__ © (2008-01-30 15:51) [14]

> Задача:
> "на числовой прямой задано n точек. Необходимо найти среди
> них две ближайшие. Значения координат x[i] не превосходят
> 10^9 по абсолютной величине.

> Задача с областной олимпиады.

Возникает вопрос : В какой стране? Не верю, что в России! НЕ ВЕРЮ что областная олимпиада! У нас(Казахстан) задачи на уровне города такие, что прежде чем решать мы сидим обычно минут по 40. А потом уже - кодить. А если посмотреть примеры в Инете, то вообще...

← →
atruhin © (2008-01-30 15:54) [15]

В догонку:
>>размер памяти 64 мб.
Размер какой памяти? Размер физической памяти компьютера, размер памяти занимаемой программой,
размер динамически запрашиваемой памяти.

← →
Kerk © (2008-01-30 15:59) [16]

> Denis__ © (30.01.08 15:51) [14]

Я когда на всероссийской был, там была пара задач, которые решит любой. Практически официально заявлялось, что оно надо, чтоб не травмировать психику аутсайдерам :)

← →
Denis__ © (2008-01-30 15:59) [17]

> размер памяти занимаемой программой,
> размер динамически запрашиваемой памяти.

по-моему вместе. Могу путать.

> > Ограничения: время работы 2 с
>
> Объясните пожалуйста, что это за ограничение ?

Да-да! Время раьоты программы!
for i:=0 to 1000000000 do begin for j:=0 to 1000000000 do ... end;
:D

← →
Denis__ © (2008-01-30 16:02) [18]

> Я когда на всероссийской был, там была пара задач, которые
> решит любой. Практически официально заявлялось, что оно
> надо, чтоб не травмировать психику аутсайдерам :)

Ну, на Всероссах я не был:) но задачи оттуда видел. Страшно, если честно.

← →
Anatoly Podgoretsky © (2008-01-30 16:03) [19]

> VAD*Anti Gopn!k (30.01.2008 14:31:00) [0]

Возьми компьютер по быстрее.

← →
Anatoly Podgoretsky © (2008-01-30 16:04) [20]

> Palladin (30.01.2008 14:54:07) [7]

Стреляли

← →
Denis__ © (2008-01-30 16:04) [21]

Автобусный диспетчер (XIV Всероссийская олимпиада по информатике)

На кольцевом маршруте №54 протяженностью S, проходящем мимо пансионата "Энергетик", работает N автобусов. Автобусы пронумерованы числами от 1 до N в порядке их следования по маршруту. Автобус с номером 1 движется за автобусом с номером N. Расписание составлено таким образом, что автобусы движутся с одинаковой скоростью V0 и с равными интервалами между ними. Движение автобусов контролирует диспетчер.
В 12 часов дня некоторые K автобусов одновременно снимаются с маршрута и отправляются на обед. Для восстановления равенства интервалов между автобусами, продолжающими движение по маршруту, потребуется некоторое время Т и, возможно, изменение скорости некоторых автобусов по команде диспетчера. В течение этого времени автобусы должны двигаться с постоянными скоростями из интервала [Vmin, Vmax], назначенными диспетчером. Изменение скорости движения автобуса происходит мгновенно. По истечении времени Т автобусы возобновляют движение по маршруту со скоростью V0.
Требуется написать программу для автоматического диспетчера, которая вычисляет минимальное время Tmin, за которое интервалы движения между оставшимися автобусами станут равными, и скорости движения каждого из них в течение этого времени.

Входные данные
Входной файл bus.in содержит две строки.
В первой строке находятся натуральные числа N, К, S, Vmin, Vmax и V0, где K < N <= 10000, S <= 10000, Vmin < Vmax <= 10000, Vmin <= V0 <= Vmax.
Во второй строке расположены в порядке возрастания K чисел - номера автобусов, снятых с маршрута. Все данные в строках разделены пробелами.

Выходные данные
В первой строке выходного файла bus.out должно находиться значение Tmin.
В каждой из последующих N - K строк должны быть по два разделенных пробелом числа - номер автобуса на маршруте и скорость его движения в течение времени Tmin. Номера автобусов упорядочить по возрастанию. Значения Tmin и скоростей выводить с точностью до 4-х значащих цифр после десятичной точки.

Пример 1
Входной файл bus.in
4 1 60 21 70 60
3
Выходной файл bus.out
0.2041
1 45.5
2 21
4 70

Пример 2
Входной файл bus.in
4 2 40 30 80 50
2 4
Выходной файл bus.out
0
1 50
3 50

← →
clickmaker © (2008-01-30 16:05) [22]

> Да-да! Время раьоты программы!
> for i:=0 to 1000000000 do
> begin
> for j:=0 to 1000000000 do
> ...
> end;

на собеседованиях-тестах такие дают иногда.
дано: проц 1 ГГц, считать, что он весь отдан одному процессу, подсчитать, сколько будет выполняться N сложений/умножений и пр.

← →
atruhin © (2008-01-30 16:52) [23]

> на собеседованиях-тестах такие дают иногда.
> дано: проц 1 ГГц,

Только у автора в вопросе процессор как раз не указан.

← →
Правильный_Вася (2008-01-30 16:56) [24]

> Необходимо найти среди них две ближайшие

ближайшие к чему?
к началу координат? к друг другу?

← →
clickmaker © (2008-01-30 16:59) [25]

> у автора в вопросе процессор как раз не указан

а там обратная задача: на каком процессоре данный цикл будет выполняться 2 сек? )

← →
имя (2008-01-30 19:01) [26]

Удалено модератором

← →
Lip (2008-01-30 19:21) [27]

> В догонку:>>размер памяти 64 мб.Размер какой памяти? Размер
> физической памяти компьютера, размер памяти занимаемой программой,
> размер динамически запрашиваемой памяти.

Вы видимо никогда не участвовали в школьных олимпиадах.
Естественно это размер памяти занимаемой программой в оперативной памяти.

> Denis__ © (30.01.08 16:04) [21]
> Автобусный диспетчер (XIV Всероссийская олимпиада по информатике)

Ну и какой смысл выкладывать сюда задачу с Всероссийской олимпиады? Ясно же что никто решать не будет да и не решит.

> Возникает вопрос : В какой стране? Не верю, что в России!
> НЕ ВЕРЮ что областная олимпиада! У нас(Казахстан) задачи
> на уровне города такие, что прежде чем решать мы сидим обычно
> минут по 40

Что это ты не веришь? Учитывай, что есть провинциальные городки, в которых задачи соответствующие и есть такой город как Москва,
где чтобы дойти до этапа городской олимпиады нужно пройти ещё несколько этапов.

> Riply © (30.01.08 15:05) [10]
> > Ограничения: время работы 2 сОбъясните пожалуйста, что
> это за ограничение ?

А это вы спросите у составителей задач.
И вообще, имхо, ориентироваться на 2 сек. особо не стоит. Просто нужно стараться решать задачу оптимальным алгоритмом.

ТАк что delphi это одно, а олимпиадные задачи совсем другое!

← →
VAD*Anti Gopn!k © (2008-01-30 19:51) [28]

2 all

Я так понял что никто не может найти решение. Как и я. Поэтому, я написал тупой алгоритм для того, чтобы получить несколько лишних балов. То есть присерно 50 из 100 возможных. И я думаю, что каждый и вас поступил бы также. Это лишь 1 тур, завтра второй. Вот на нем уже будут задачки с рекурсией, я это люблю :) Ну ладно, спасибо всем за попытки помощи.

← →
Lip (2008-01-30 21:05) [30]

> Я так понял что никто не может найти решение. Как и я. Поэтому,
> я написал тупой алгоритм для того, чтобы получить несколько
> лишних балов. То есть присерно 50 из 100 возможных. И я
> думаю, что каждый и вас поступил бы также. Это лишь 1 тур,
> завтра второй. Вот на нем уже будут задачки с рекурсией,
> я это люблю :) Ну ладно, спасибо всем за попытки помощи.
>

Чел, не советую тебе здесь задавать вопросы связанные с олимпиадным программированием. Тут такое понятие как ACM малоизвестно.

По поводу задачи.
Я бы сначала отсоритровал координаты сортировкой с логарифмической сложностью. А потом бы прошелся по массиву сравнивая 2 соседних элемента.
Получается n*log(n) + n, против N^2. Всяк лучше!

> Lip (30.01.08 21:05) [30]
> Чел, не советую тебе здесь задавать вопросы связанные с
> олимпиадным программированием. Тут такое понятие как ACM
> малоизвестно.

Ты откуда такой умный взялся? :)

> Lip (30.01.08 21:05) [30]
> не советую тебе здесь задавать вопросы связанные с олимпиадным
> программированием. Тут такое понятие как ACM малоизвестно

Забавный парень... :) Знает, как пользоваться "сортировкой с логарифмической сложностью" и, наверное, "AСM" (Anti Coding Method)

← →
Lip (2008-01-30 21:32) [33]

> такой умный

спасибо! :)

> Забавный парень...

Спасибо :)

> Знает, как пользоваться

Пользоваться и понимать разные вещи :)
Ещё я знаю про сортировку пузырьком, которую тут путают с сортировкой вставками :)

Ясно, очередной школьник. Сам таким был :)

> Lip (30.01.08 21:32) [33]

Вообще-то на вопрос Jeer ответил, еще в [3] и [4] (с учетом того, что сортировкой до этого и не пахло, см. [6])... И, да пребудет с тобой ACM (Absolute Checking Matrix)!!!

← →
Lip (2008-01-30 21:46) [36]

> Ясно, очередной школьник. Сам таким был :)

Нее.. надо было сказать что типа в детский сад интернет провели, как вы это любите :) А.. что хорошие шутки, с такими только в камеди клаб :)

> Lip (30.01.08 21:46) [36]

Ответ на вопрос автора в самом начале ветки. А вот ты ничего полезного ему не сообщил, зато умные слова знаешь ;)

> Lip (30.01.08 21:46) [36]

Пароль на Navity давай, потом буш тут учить, кто может, а кто не может.

← →
Lip (2008-01-30 21:51) [39]

> Вообще-то на вопрос Jeer ответил, еще в [3] и [4] (с учетом
> того, что сортировкой до этого и не пахло, см. [6])... И,
> да пребудет с тобой ACM (Absolute Checking Matrix)!!!

Честно говоря не обратил внимания на эти пункты =)

Задача с областной олимпиады. Найти похожие ветки