Форум программистов, компьютерный форум, киберфорум
Наши страницы
Алгоритмы
Войти
Регистрация
Восстановить пароль
 
Рейтинг 5.00/3: Рейтинг темы: голосов - 3, средняя оценка - 5.00
oobarbazanoo
5 / 28 / 8
Регистрация: 13.05.2015
Сообщений: 1,835
1

Задача про мороженное

06.11.2016, 14:30. Просмотров 560. Ответов 8
Метки нет (Все метки)

Может кто знает алгоритм решения данной задачи без использования полного перебора?
https://www.e-olymp.com/en/problems/4035
0
QA
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
06.11.2016, 14:30
Ответы с готовыми решениями:

Задача про Мурзика
Доброе утро форумчане! На e-olimp.com есть задача: Ссылка:...

Задача про хорды.
Подскажите пожалуйста, как можно использовать так называемое дерево отрезков для решения задачи: ...

Задача про массив
Дано натуральное число N и массив из N целых чисел a1, a2, ..., an. Над элементами массива можно...

задача про монеты
на столе лежат n-1 монет.двое игроков по очереди берут по 1,3 или 5 момент за раз.выигрывает тот...

Задача про инвестора
Здраствуйте! Подскажите пожалуйста. У меня был вопрос про задачу про инвестора: у одного...

8
Shamil1
Модератор
2444 / 1655 / 368
Регистрация: 26.03.2015
Сообщений: 6,053
06.11.2016, 19:52 2
Сразу приходит в голову самое простое решение: вычёркивать ларьки, которые ближе всего к своим соседям, пока не останется столько ларьков, сколько продавцов. Но как-то слишком просто для олимпиадной задачи. Возможно, на каких-то данных такой алгоритм находит не лучшее решение (хотя с ходу придумать опровергающий пример мне не удалось).

(сравниваем сначала по меньшему расстоянию, а если они равны, то потом по второму... у крайних ларьков второе расстояние бесконечно)
1
ProgJ
87 / 85 / 10
Регистрация: 20.11.2008
Сообщений: 724
06.11.2016, 21:54 3
Цитата Сообщение от Shamil1 Посмотреть сообщение
придумать опровергающий пример мне не удалось
например, 3 продавца, а координаты
0, 29, 30, 31, 60
2
oobarbazanoo
5 / 28 / 8
Регистрация: 13.05.2015
Сообщений: 1,835
07.11.2016, 10:12  [ТС] 4
Shamil1, не очень понятен Ваш алгоритм.
Имея ларьки {1, 2, 3, 20} и двух продавцов, то как мы можем узнать, что вычеркнуть нужно именно 2 и 3 ?

Добавлено через 58 секунд
Я сделал это задание немного другим способом.
Я подобрал ответ используя бинарный поиск.
Тогда выходит логарифмическое время.
Засчитали 100 процентов.
0
07.11.2016, 10:12
ProgJ
87 / 85 / 10
Регистрация: 20.11.2008
Сообщений: 724
07.11.2016, 10:21 5
Цитата Сообщение от oobarbazanoo Посмотреть сообщение
Я подобрал ответ используя бинарный поиск.
а по-подробнее не расскажите?
1
Shamil1
Модератор
2444 / 1655 / 368
Регистрация: 26.03.2015
Сообщений: 6,053
07.11.2016, 10:30 6
Цитата Сообщение от oobarbazanoo Посмотреть сообщение
Shamil1, не очень понятен Ваш алгоритм.
Зачем, если он выдаёт неверный ответ для примера, который привёл ProgJ?
1
Excalibur921
926 / 568 / 98
Регистрация: 12.10.2013
Сообщений: 3,817
07.11.2016, 10:42 7
Цитата Сообщение от oobarbazanoo Посмотреть сообщение
Засчитали 100
Проценты это наверно работоспособность программы вообще.
А время и память сколько? Гляньте там статистика есть.
1
oobarbazanoo
5 / 28 / 8
Регистрация: 13.05.2015
Сообщений: 1,835
07.11.2016, 16:53  [ТС] 8
Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def isFeasible(positions, dist, k):
    taken = 1
    last = positions[0]
    for i = 1 ... positions.size() - 1:
        if positions[i] - last >= dist:
            taken++
            last = positions[i]
    return taken >= k
 
def solve(positions, k):
    low = 0 // definitely small enough
    high = maxElement(positions) - minElement(positions) + 1 // definitely too big
    while high - low > 1:
        mid = (low + high) / 2
        if isFeasible(positions, mid, k):
            low = mid
        else:
            high = mid
    return low
2
Миниатюры
Задача про мороженное  
Excalibur921
926 / 568 / 98
Регистрация: 12.10.2013
Сообщений: 3,817
07.11.2016, 18:21 9
https://www.e-olymp.com/ru/problems/4035/statistics
278 ваше время а лидер 2.14?
1
07.11.2016, 18:21
Answers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
07.11.2016, 18:21

Задача про функцию
Вычислите функцию: f(n) = \begin{cases} & \text 1 {if}...

Задача про муравьев
У нас есть две колонии муравьев: красных и черных. Каждый муравей может быть голодным или сытым....

Задача про деки
Попалась такая вот задача на e-olimp: Мой код: #include <iostream> #include <deque>...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
9
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2019, vBulletin Solutions, Inc.