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

← →
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 тур, завтра второй. Вот на нем уже будут задачки с рекурсией, я это люблю :) Ну ладно, спасибо всем за попытки помощи.

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

VAD*Anti Gopn!k © (30.01.08 19:51) [28]
приМерно 50... конечно

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

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

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

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

← →
Kerk © (2008-01-30 21:13) [31]

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

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

← →
korneley © (2008-01-30 21:27) [32]

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

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

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

> такой умный

спасибо! :)

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

Спасибо :)

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

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

← →
Kerk © (2008-01-30 21:34) [34]

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

← →
korneley © (2008-01-30 21:43) [35]

> Lip (30.01.08 21:32) [33]

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

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

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

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

← →
Kerk © (2008-01-30 21:48) [37]

> Lip (30.01.08 21:46) [36]

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

← →
Рамиль © (2008-01-30 21:49) [38]

> Lip (30.01.08 21:46) [36]

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

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

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

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

← →
ketmar © (2008-01-30 21:56) [40]

>[22] clickmaker ©(30.01.08 16:05)
это ж где такой идиотизм спрашивают-то? O_o

← →
ketmar © (2008-01-30 21:56) [41]

>[39] Lip (30.01.08 21:51)
шо, нет времени читать, декомпилятор никак не запускается?

← →
Lip (2008-01-30 22:02) [42]

> шо, нет времени читать, декомпилятор никак не запускается?

Времени нет. Да и зачем его собственно тратить на чтение здесь постов?
Что-то новое узнаю?? =)

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

> Lip (30.01.08 21:51) [39]
> !!Честно говоря не обратил внимания на эти пункты =)

Ну, дык, тщательнЕе надо читать, о, поклонник Abstract Community of Machines

> Lip (30.01.08 22:02) [42]
>Ну и тут рекламу своего декомпилятора суете.

:))) ketmar = ZoldBerger!!! Ржунимагу (простите за албанцкий). Действительно, постов не читаем, но с выводами не церемонимся...

← →
Lip (2008-01-30 22:15) [46]

прикольно вы умеете слова подбирать для трех букв. Талант!

> Lip (30.01.08 22:15) [46]

При чем здесь кто-то другой, кроме тебя? [30] - твоё произведение, вот и предположения, что бы это могло значить. Продолжай исследовать Analog Compiler Means

> При чем здесь кто-то другой, кроме тебя? [30] - твоё произведение,
> вот и предположения, что бы это могло значить. Продолжай
> исследовать Analog Compiler Means

емоее... да вы действильно в танке.
Вы гуглом пользуетесь или только посылаете всех туда?

ACM - Association for Computing Machinery =)

откройте браузер и введите www.google.ru, только без ошибок и введите "ACM" и нажмите "найти". Потом кликните по 2 ссылке

>[42] Lip (30.01.08 22:02)
тебя вообще желательно изолировать от интернета. интернет разрушает неокрепший детский разум.

← →
ferr (2008-01-30 22:57) [50]

Лично смотрел как решения этих оболдуев тестировались. =)

Компьютер был этак мегагерц 600, что огаваривается в условии.

Ну и комплект задач спускается с мин образования, раньше старались своими силами, щас вот взяли дефолтный. Комплект возмутительно лёгкий был.

Напомню [30]:

> ...Тут такое понятие как ACM малоизвестно...

Вот я занялсЯ исследованием неизвестных мне тайных смыслов аббревиатуры. В контексте поста.

Мои и (Керка), смыслы, нравятся больше. Опять же в контексте... :)

> разрушает неокрепший детский разум.

У вас какие-то комплексы по поводу возраста.
Может вы стареете?

> Вот я занялсЯ исследованием неизвестных мне тайных смыслов
> аббревиатуры.

Я же вроде объяснил про гугль =) Какой шаг не понятен?

>[53] Lip ©(30.01.08 23:07)
да всего лишь детей жалко. а ещё жальче уборщиц: у дитя моск взорвётся — и всё. а уборщицам потом стены и пол отдраивать…

> да всего лишь детей жалко. а ещё жальче уборщиц: у дитя
> моск взорвётся — и всё. а уборщицам потом стены и пол отдраивать…

Поразили...
Я был лучшего мнения о вашем уровне интеллекта...

>[56] Lip ©(30.01.08 23:16)
ужас. вот теперь опять буду спать плохо, всё думать: что бы такого сделать, чтобы вернуть себе уважение Lip"а. а то без этого мне девушки не улыбаются и пиво в магазинах продают втридорога.

> Lip © (30.01.08 23:10) [54]
> Я же вроде объяснил про гугль =) Какой шаг не понятен?

Непонятно зачем Google, если умеем буквы складывать в слова, а не читать.

> ужас. вот теперь опять буду спать плохо, всё думать: что
> бы такого сделать, чтобы вернуть себе уважение Lip"а. а
> то без этого мне девушки не улыбаются и пиво в магазинах
> продают втридорога.

Тебе девушки на эране монитора улыбаются??? :)

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