Форум программистов, компьютерный форум, киберфорум
Python для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
 
Рейтинг 4.97/35: Рейтинг темы: голосов - 35, средняя оценка - 4.97
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


Код я написал:
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def qwer():
    Q=list(map(int, input().split()))
    A=list(map(int, input().split()))
    N=Q[0]
    K=Q[1]
    maxv=0
    for i in range(N):
        for j in range(N):
            if i+j>=K:
                if maxv<A[i]+A[j] and i>j:
                    maxv=A[i]+A[j]
                    q=i+1
                    w=j+1
    print(str(min(q,w))+' '+str(max(q,w)))
    
qwer()
Принимающий код ругается на время исполнения программы. Помогите оптимизировать и ускорить код, пожалуйста
0
Лучшие ответы (1)
Programming
Эксперт
39485 / 9562 / 3019
Регистрация: 12.04.2006
Сообщений: 41,671
Блог
26.03.2020, 19:54
Ответы с готовыми решениями:

Проблема с оптимизацией
Здравствуйте, проблема в следующем. Есть следующая задача: На шахматной доске стоит конь. Отметьте положение коня на доске и все...

Проблемы с оптимизацией кода
У бизнесмена есть телефон, который он использует для связи с партнерами по бизнесу. Сегодня у предпринимателя запланированы n разговоров,...

Помогите с оптимизацией кода
Всем доброго времени суток. Проблема заключается в том, что ноут препода почему-то не способен воспроизвести этот код, что выливается в то,...

39
5516 / 2869 / 571
Регистрация: 07.11.2019
Сообщений: 4,760
26.03.2020, 20:09
У вас код вообще неправильно работает.
Пусть K=3, i, j=10,11, тогда 9-я строка выдаст true, хотя должна false, т.к. расстояние меньше 3.
Лучше делать как-то так:
Python
1
2
  for i in range(N):
        for j in range(i+k+1,N):
тогда условие в 9 строке не нужно.
1
Status 418
Эксперт Python
4584 / 2350 / 601
Регистрация: 26.11.2017
Сообщений: 5,262
Записей в блоге: 3
26.03.2020, 22:03
от этого квадрат не перестанет быть квадратом
1
4 / 3 / 3
Регистрация: 21.03.2020
Сообщений: 19
27.03.2020, 06:46  [ТС]
Цитата Сообщение от u235 Посмотреть сообщение
for i in range(N):
        for j in range(i+k+1,N):
u235, немного не понял, покажите то, что у вас было в вводе, пожалуйста

Добавлено через 24 минуты
u235, условие в 9 строке изменил.
Python
1
if i-j>=K:
Но проблема во времени, проверка выдаёт ошибку, мол, слишком долго выполнялась. Как ускорить программу, вот в чём вопрос
0
Модератор
Эксперт Python
 Аватар для Fudthhh
2695 / 1601 / 513
Регистрация: 21.02.2017
Сообщений: 4,210
Записей в блоге: 1
27.03.2020, 08:57
Python
1
2
3
4
5
6
7
def task(n: int, k: int, cells: list) -> (int, int):
    result, price = [0, 0], 0
    for i in range(n):
        for j in range(i + k + 1, n):
            if cells[i] + cells[j] > price:
                result, price = [i + 1, j + 1], cells[i] + cells[j]
    return result
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
Status 418
Эксперт Python
4584 / 2350 / 601
Регистрация: 26.11.2017
Сообщений: 5,262
Записей в блоге: 3
27.03.2020, 14:04
так это вроде последняя задача из ЕГЭ на пары только более общая
0
4 / 3 / 3
Регистрация: 21.03.2020
Сообщений: 19
27.03.2020, 14:08  [ТС]
eaa, не знаю, не знаю...
0
Status 418
Эксперт Python
4584 / 2350 / 601
Регистрация: 26.11.2017
Сообщений: 5,262
Записей в блоге: 3
27.03.2020, 16:13
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
n, k = map(int, input().split())
*a, = map(int, input().split())
m1 = i1 = 0
m2 = i2 = 0
k += 1
for i in range(k, n):
    #m1 = max(m1 , a[i-k])
    if a[i-k] > m1:  # строго больше чтобы левее
        m1 = a[i-k]
        i1 = i-k
    #m2 = max(m2, m1 + a[i])
    if m1 + a[i] > m2:  # строго больше чтобы левее
        m2 = m1 + a[i]
        i2 = i
print(m2)
print(i1+1, i2+1)
не тестил, может есть ошибки.
0
4 / 3 / 3
Регистрация: 21.03.2020
Сообщений: 19
27.03.2020, 16:40  [ТС]
eaa, протестил, вроде всё отлично, но теперь ругается на неправильный ответ
0
Эксперт Python
5438 / 3859 / 1215
Регистрация: 28.10.2013
Сообщений: 9,552
Записей в блоге: 1
28.03.2020, 00:47
Цитата Сообщение от MaxGlock Посмотреть сообщение
но теперь ругается на неправильный ответ
А что именно?
Я потестил функцию eaa, ответы верные вроде выдает.
Сравнил со своей и с вариантом DmFat - один в один ответы.
Только у DmFat, квадратичная сложность и поэтому долго работает.
У eaa, сложность O(N) - самый оптимальный вариант.

Вот мой вариант. Он чутка медленее чем O(N) потому что сортировка...
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def argsort(seq, descending=False):
    return sorted(range(len(seq)), key=seq.__getitem__,reverse=descending)
 
 
def rob(arr:list, k:int) -> (int,int):
    len_a = len(arr)
    # список отсортированных индексов
    index = argsort(arr, descending=True)
   
    i,j = 0,1
    first = index[i] # очевидно, что здесь индекс самой дорогой ячейки
    while j < len_a-1:
        # смотрим направо пока не встретим ближайшую 
        # разрешенную ячейку; она и будет вторым нашим максимумом
        if abs(index[i] - index[j]) > k:
            second = index[j]
            break
        j += 1
            
    if first > second:
        first, second = second, first
    
    return  first + 1, second + 1
---------------------------------------------

Добавлено через 10 минут
Хотя нет. На некоторых списках функция eaa, выдает одинаковые индексы для двух ячеек (оба совпадают с индексом максимально ценной ячейки).

(+1 к индексам в своих тестах я убрал, чтобы найденные индексы соответствовали реальным индексам списка )

Python
1
arr = [random.randint(1,100000) for _ in range(1000)]
Python
1
2
3
idx = rob3(arr,2)
print(idx)
print(arr[idx[0]], arr[idx[1]])
Code
1
2
(280, 280)
99836 99836
А правильный ответ:
Python
1
2
3
idx = rob(arr,2)
print(idx)
print(arr[idx[0]], arr[idx[1]])
Code
1
2
(261, 280)
99785 99836
Проверяем:
Python
1
max(arr)
Code
1
99836
Python
1
list(enumerate(arr[260:281], 260))
[(260, 80104),
(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)]
Смотрим два первых максимума:
Python
1
2
a = sorted(arr,reverse=True)
a[0],a[1]
Code
1
(99836, 99785)
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
Status 418
Эксперт Python
4584 / 2350 / 601
Регистрация: 26.11.2017
Сообщений: 5,262
Записей в блоге: 3
28.03.2020, 13:24
Garry Galler, что то подсказывало что есть ошибка у меня.
0
Эксперт Python
5438 / 3859 / 1215
Регистрация: 28.10.2013
Сообщений: 9,552
Записей в блоге: 1
28.03.2020, 13:48
Цитата Сообщение от MaxGlock Посмотреть сообщение
local variable 'second' referenced before assignment
Надо просто инициализацию second поставить рядом с first.
Python
1
2
first = index[i] # индекс самой дорогой ячейки
second = index[j] # индекс второй по ценности ячейки

Цитата Сообщение от MaxGlock Посмотреть сообщение
но сайт не принял. WTF?
WTF.
Возьми тогда вот этот страшный код (переделанный с С++
Его оригинал вроде как все тесты прошел.
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
def rob(n,k):
    
    a = [0]  * n
    p = [0]  * n
    s = [0]  * n
    
    i, j = 0, 0
    # здесь у чувака происходит ввод списка ячеек и какая-то дополнительная магия
    for i in range(n):
        a[i] = int(input('>>'))
        if (a[i] > a[j]):
            p[i] = i
            j = i
        else: 
            p[i] = p[j]
        
    
    i = n-1
    j = n-1
    
    #print(a)
    #print(p)
    
    while i >= 0:
        if (a[i] >= a[j]):
            s[i] = i 
            j = i
        else:
            s[i] = s[j]
        i -= 1    
    
    m = 0 
    l = 0 
    r = k + 1
    i = l
    j = r
    while j < n:
        t = a[p[i]] + a[s[j]]
        
        if (t > m):
            l = p[i]
            r = s[j] 
            m = t
        i += 1
        j += 1
    return l+1, r+1
0
Эксперт Python
5438 / 3859 / 1215
Регистрация: 28.10.2013
Сообщений: 9,552
Записей в блоге: 1
29.03.2020, 22:47
Лучший ответ Сообщение было отмечено Garry Galler как решение

Решение

MaxGlock,
Ну дак что у тебя там проверками?
Я потестил код который выше приводил (калька с С++) в чуть более питоничном виде.
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
def rob_1(a, k):
    n = len(a)
    p = [0] * n
    s = [0] * n
    
    i, j = 0, 0
    
    for i in range(n):
        if (a[i] > a[j]):
            p[i] = i
            j = i
        else: 
            p[i] = p[j]
        
    
    j = n - 1
    for i in range(n - 1, -1, -1):
        if (a[i] >= a[j]):
                s[i] = i
                j = i
        else:
            s[i] = s[j]     
       
    m, l, r = 0, 0, k + 1
    i = l
    
    for j in range(r, n):
        t = a[p[i]] + a[s[j]]
        if t > m:
            l = p[i]
            r = s[j]
            m = t
        i += 1
 
    return l, r   # +1 к индексам добавьте сами если нужно
Работает идеально, но правда медленнее, чем мой вариант с сортировкой. Где-то в два с лишним раза.
Code
1
2
%timeit -n 10 -r 10 rob(arr,2)
46.7 ms ± 919 µs per loop (mean ± std. dev. of 10 runs, 10 loops each)
Code
1
2
%timeit -n 10 -r 10 rob_1(arr,2)
117 ms ± 444 µs per loop (mean ± std. dev. of 10 runs, 10 loops each)
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
Цитата Сообщение от MaxGlock Посмотреть сообщение
Garry Galler, спасибо огромное, всё прошло!
Всмысле прошло?
Во первых в чём смысл функции, во вторых что значит в 24 строке r = k+1? Это же строка.
0
4 / 3 / 3
Регистрация: 21.03.2020
Сообщений: 19
31.03.2020, 19:50  [ТС]
nns1, нет, r это число
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
inter-admin
Эксперт
29715 / 6470 / 2152
Регистрация: 06.03.2009
Сообщений: 28,500
Блог
31.03.2020, 19:50
Помогаю со студенческими работами здесь

Проблема с оптимизацией запроса
Всем привет, у меня возникла проблема, имеется запрос SELECT new FROM sbrh2_tabel_pers_log WHERE id = ANY(SELECT max(id) FROM...

Проблема с оптимизацией сайта
Оптимизировал картинку путём сжатия её размера перезалил на хост и появилась данная ошибки, я не понимаю почему. Уже столько с ней...

Нужна подсказка с оптимизацией кода
Штука такая: решил сделать таймер отсчёта времени, по окончании которого процедура идёт далее. Написал вот такой код в модуль: Public...

Проблема с оптимизацией ролика (ActionScript3.0)
Доброе время суток. У меня такая проблема. Написал рекламный модуль для сайта (использовал AdobeFlash CS5 ActionScript3.0). Модуль...

Проблема с оптимизацией игры. Выдает 5 - 10 фпс. Unity3D
Всей хай.. Делаю 3д игру под мобилки. Не закончив проект до конца, задумался об оптимизации. Решил воспользоваться удаленным...


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

Или воспользуйтесь поиском по форуму:
20
Ответ Создать тему
Новые блоги и статьи
Программный отбор значения справочника
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 Результат:
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru