|
4 / 3 / 3
Регистрация: 21.03.2020
Сообщений: 19
|
||||||
Проблема с оптимизацией кода26.03.2020, 19:54. Показов 7866. Ответов 39
Метки нет (Все метки)
Решаю олимпиадную задачу:
Клиппи и Мерлин решили грабить банк, который представляет собой N расположенных в ряд банковских ячеек, пронумерованных последовательно числами от 1 до N. С помощью своего друга Ровера, который работал в банке сторожевым псом, они добыли ключи от всех ячеек, а так же узнали, как много ценностей хранится в каждой ячейке. Чтобы не вызывать лишних подозрений, Клиппи и Мерлин решили ограбить всего две ячейки — по одной на каждого. Также, чтобы охрана банка не почуяла неладного, они решили работать далеко друг от друга — между ними должно быть не меньше K банковских ячеек. Входные данные: В первой строке вводятся два числа — N ( 2 ≤N≤ 105) и K (0 ≤K<N− 1) соответственно. В второй строке вводятся N чисел ai(0 ≤ai≤ 109) — стоимости хранимых ценностей в ячейках от 1 до N соответственно. Выходные данные: Выведите два числа в возрастающем порядке — номера ячеек, которые нужно ограбить, чтобы суммарно украсть как можно более дорогие ценности, не вызвав при этом лишних подозрений. Если вариантов несколько выберите тот, в котором меньший номер вскрываемой ячейки был как можно ближе к единице, чтобы в экстренном случае покинуть банк как можно скорее. Если и таких вариантов несколько, выберите тот, в котором и больший номер вскрываемой ячейки был как можно меньше. Примеры: Ввод: 6 2 2 4 3 1 4 4 Вывод: 2 5 Код я написал:
0
|
||||||
| 26.03.2020, 19:54 | |
|
Ответы с готовыми решениями:
39
Проблемы с оптимизацией кода
|
|
5516 / 2869 / 571
Регистрация: 07.11.2019
Сообщений: 4,760
|
||||||
| 26.03.2020, 20:09 | ||||||
|
У вас код вообще неправильно работает.
Пусть K=3, i, j=10,11, тогда 9-я строка выдаст true, хотя должна false, т.к. расстояние меньше 3. Лучше делать как-то так:
1
|
||||||
|
4 / 3 / 3
Регистрация: 21.03.2020
Сообщений: 19
|
|||||||
| 27.03.2020, 06:46 [ТС] | |||||||
|
Добавлено через 24 минуты u235, условие в 9 строке изменил.
0
|
|||||||
|
Модератор
|
||||||
| 27.03.2020, 08:57 | ||||||
0
|
||||||
|
4 / 3 / 3
Регистрация: 21.03.2020
Сообщений: 19
|
|
| 27.03.2020, 09:27 [ТС] | |
|
DmFat, спасибо, проверил, но, к сожалению, выдаёт "программа выполнялась слишком долго"
видимо, нужно задачу писать на С++, ибо ему скорости не занимать... Но интересно, существует ли некая программа-пендаль, чтобы ускорить весь цикл?
0
|
|
|
5516 / 2869 / 571
Регистрация: 07.11.2019
Сообщений: 4,760
|
|
| 27.03.2020, 09:57 | |
|
eaa, намекает, что может существовать алгоритм, решающий задачу не за квадратичное время, а за какое-то меньшее (лог-линейное, линейное м.б.)
Попробуйте, например, отсортировать список начиная от большего к меньшему и работать уже с этим списком. Задача олимпиадная - решать вам.
0
|
|
|
4 / 3 / 3
Регистрация: 21.03.2020
Сообщений: 19
|
|
| 27.03.2020, 10:04 [ТС] | |
|
u235, большое спасибо, приму к сведенью
0
|
|
|
4 / 3 / 3
Регистрация: 21.03.2020
Сообщений: 19
|
|
| 27.03.2020, 14:08 [ТС] | |
|
eaa, не знаю, не знаю...
0
|
|
|
Status 418
|
||||||
| 27.03.2020, 16:13 | ||||||
0
|
||||||
|
4 / 3 / 3
Регистрация: 21.03.2020
Сообщений: 19
|
|
| 27.03.2020, 16:40 [ТС] | |
|
eaa, протестил, вроде всё отлично, но теперь ругается на неправильный ответ
0
|
|
|
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 28.03.2020, 00:47 | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Я потестил функцию eaa, ответы верные вроде выдает. Сравнил со своей и с вариантом DmFat - один в один ответы. Только у DmFat, квадратичная сложность и поэтому долго работает. У eaa, сложность O(N) - самый оптимальный вариант. Вот мой вариант. Он чутка медленее чем O(N) потому что сортировка...
Добавлено через 10 минут Хотя нет. На некоторых списках функция eaa, выдает одинаковые индексы для двух ячеек (оба совпадают с индексом максимально ценной ячейки). (+1 к индексам в своих тестах я убрал, чтобы найденные индексы соответствовали реальным индексам списка )
(261, 99785), (262, 64290), (263, 47934), (264, 961), (265, 58627), (266, 11875), (267, 95306), (268, 32627), (269, 89116), (270, 92486), (271, 6351), (272, 1413), (273, 72029), (274, 68714), (275, 76361), (276, 1826), (277, 7619), (278, 77658), (279, 8743), (280, 99836)] Смотрим два первых максимума:
1
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
4 / 3 / 3
Регистрация: 21.03.2020
Сообщений: 19
|
|
| 28.03.2020, 08:41 [ТС] | |
|
Garry Galler, прогнал код в стандартном официальном компиляторе (3.8) - всё замечательно, работает. Прогнал в онлайн компиляторе - пишет "local variable 'second' referenced before assignment" в 20 строке. Поставил обработку исключения перед условием - заработало, но сайт не принял. WTF?
0
|
|
|
|
|||||||||||||
| 28.03.2020, 13:48 | |||||||||||||
Возьми тогда вот этот страшный код (переделанный с С++ Его оригинал вроде как все тесты прошел.
0
|
|||||||||||||
|
|
||||||||||||||||
| 29.03.2020, 22:47 | ||||||||||||||||
Сообщение было отмечено Garry Galler как решение
Решение
MaxGlock,
Ну дак что у тебя там проверками? Я потестил код который выше приводил (калька с С++) в чуть более питоничном виде.
1
|
||||||||||||||||
|
4 / 3 / 3
Регистрация: 21.03.2020
Сообщений: 19
|
|
| 31.03.2020, 10:51 [ТС] | |
|
Garry Galler, спасибо огромное, всё прошло!
0
|
|
|
2 / 1 / 1
Регистрация: 09.03.2020
Сообщений: 16
|
||
| 31.03.2020, 19:47 | ||
|
Во первых в чём смысл функции, во вторых что значит в 24 строке r = k+1? Это же строка.
0
|
||
|
4 / 3 / 3
Регистрация: 21.03.2020
Сообщений: 19
|
|
| 31.03.2020, 19:50 [ТС] | |
|
nns1, нет, r это число
0
|
|
| 31.03.2020, 19:50 | |
|
Помогаю со студенческими работами здесь
20
Проблема с оптимизацией запроса Проблема с оптимизацией сайта Нужна подсказка с оптимизацией кода Проблема с оптимизацией ролика (ActionScript3.0) Проблема с оптимизацией игры. Выдает 5 - 10 фпс. Unity3D Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |
|
Новые блоги и статьи
|
|||
|
Программный отбор значения справочника
Maks 21.03.2026
Процедура ВодителиНачалоВыбора(Элемент, ДанныеВыбора, ВыборДобавлением, СтандартнаяОбработка)
/ / Отключаем стандартную обработку (стандартное открытие формы выбора без фильтров)
. . .
|
Переходник USB-CAN-GPIO
Eddy_Em 20.03.2026
Достаточно давно на работе возникла необходимость в переходнике CAN-USB с гальваноразвязкой, оный и был разработан. Однако, все меня терзала совесть, что аж 48-ногий МК используется так тупо: просто. . .
|
Оттенки серого
Argus19 18.03.2026
Оттенки серого
Нашёл в интернете 3 прекрасных модуля:
Модуль класса открытия диалога открытия/ сохранения файла на Win32 API;
Модуль класса быстрого перекодирования цветного изображения в оттенки. . .
|
SDL3 для Desktop (MinGW): Рисуем цветные прямоугольники с помощью рисовальщика SDL3 на Си и C++
8Observer8 17.03.2026
Содержание блога
Финальные проекты на Си и на C++:
finish-rectangles-sdl3-c. zip
finish-rectangles-sdl3-cpp. zip
|
|
Символические и жёсткие ссылки в Linux.
algri14 15.03.2026
Существует два типа ссылок — символические и жёсткие.
Ссылка в Linux — это запись в каталоге, которая может указывать либо на inode «файла-ИСТОЧНИКА», тогда это будет «жёсткая ссылка» (hard link),. . .
|
[Owen Logic] Поддержание уровня воды в резервуаре количеством включённых насосов: моделирование и выбор регулятора
ФедосеевПавел 14.03.2026
Поддержание уровня воды в резервуаре количеством включённых насосов: моделирование и выбор регулятора
ВВЕДЕНИЕ
Выполняя задание на управление насосной группой заполнения резервуара,. . .
|
делаю науч статью по влиянию грибов на сукцессию
anaschu 13.03.2026
прикрепляю статью
|
SDL3 для Desktop (MinGW): Создаём пустое окно с нуля для 2D-графики на SDL3, Си и C++
8Observer8 10.03.2026
Содержание блога
Финальные проекты на Си и на C++:
hello-sdl3-c. zip
hello-sdl3-cpp. zip
Результат:
|