Вычислить сколько разговоров надо пропустить бизнесмену

@Cactoo · Регистрация: 23.03.2020

Студворк — интернет-сервис помощи студентам

Python
1
2
3
4
5
6
7
8
9
10
11
12
def qwer():
    n = int(input())
    P = list(map(int, input().split()))
    A = list(map(int, input().split()))
    maxv = 0
    maxc = 0
    for x in A:
        if maxv <= sum(P[x]: ]) and x < n and x != 0:
            maxv = sum(P[x:])
            maxc = x
        print(str(maxv) + ' ' + str(maxc))
        qwer()

Помогите исправить код, буду очень благодарен!

@unfindable_404 · 27.03.2020, 23:17

Python
1
2
3
4
5
6
7
8
9
10
11
12
def qwer():
    n = int(input())
    P = list(map(int, input().split()))
    A = list(map(int, input().split()))
    maxv = 0
    maxc = 0
    for x in A:
        if maxv <= sum(P[x:]) and x < n and x != 0:
            maxv = sum(P[x:])
            maxc = x
    print(str(maxv) + ' ' + str(maxc))
qwer()

А что он должен вообще делать?
Синтаксис поправил.

@Cactoo · 28.03.2020, 11:26 **[ТС]**

Спасибо большое! Этот код для задачи, приведённой ниже:

Телефон

У бизнесмена есть телефон, который он использует для связи с партнерами по бизнесу. Сегодня у предпринимателя запланированы n разговоров, про каждый из которых известно число Pi — сколько рублей прибыли получит бизнесмен, если i-й разговор состоится (Pi может быть равно 0 — в этом случае никакой выгоды от i-го разговора нет).

Телефон у бизнесмена сделан по новейшим технологиям, но иногда барахлит. Сегодня, например, телефон внезапно разрядился, поэтому он позволит бизнесмену провести только первые A0 разговоров, а затем выключится до конца дня. Однако телефон можно зарядить, пропустив несколько первых запланированных разговоров. Более формально, если предприниматель будет заряжать телефон вместо первых j разговоров (то есть разговоров с номерами от 1 до j), то он потом сможет провести ровно Aj разговоров (с номерами от j + 1 до min(n, j + Aj)), после чего телефон опять же перестанет работать до конца дня.

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

Входные данные На вход программе дается целое число n — количество запланированных звонков (1 ≤ n ≤ 2⋅105). На следующей строке вводятся через пробел n целых чисел Pi, обозначающие прибыли от звонков (0 ≤ Pi ≤ 1 000). Затем вводятся n+1 целых чисел Aj, обозначающие, сколько звонков можно будет провести после подзарядки (0 ≤ Aj ≤ 106).

Выходные данные Выведите два числа, первое — это максимальная выгода, которую может получить бизнесмен, второе — количество пропущенных первых звонков, при котором она получается (0, если выгоднее всего не заряжать телефон вовсе).

@unfindable_404 · 29.03.2020, 13:03

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
def qwer():
    input()
    P = list(map(int, input().split()))
    A = list(map(int, input().split()))
    maxv = 0
    maxc = 0
    for i, x in enumerate(A):
        if x != 0 and maxv <= sum(P[i:i + x]):
            maxv = sum(P[i:i + x])
            maxc = i
    print(maxv, maxc)
 
 
qwer()

Тогда уж так будет правильнее. Хотя и достаточно медленно при больших размерах списков.

@MrR0bot · 29.03.2020, 13:57

А вы не знаете, как решить задачу быстрее?

@eaa · 29.03.2020, 14:16

Интервальные суммы, так вроде называется.
Их можно вычислить один раз за O(n) в начале.
Тогда в цикле для того чтобы проверить сумму на интервале нам понадобится O(1) действий.
Итог весь алгоритм будет O(n) по времени.

@MrR0bot · 29.03.2020, 14:33

Не могли бы написать код? А то не очень понимаю о чём речь, ибо недавно начал изучать программирование.

@eaa · 29.03.2020, 16:19

суть
дан список a.
a = [51, 89, 78, 63, 77, 61, 54, 90, 72, 26, 45, 1, 58, 63, 21, 24, 6, 32, 56, 55]
строим список b
b = [0, 51, 140, 218, 281, 358, 419, 473, 563, 635, 661, 706, 707, 765, 828, 849, 873, 879, 911, 967, 1022]
если нужно найти сумму на отрезке [x,y].
то это будет b[y+1] - b[x].
найдем сумму на отрезке [5, 17]
[5, 17] - сумма =61 + 54 + 90 + 72 + 26 + 45 + 1 + 58 + 63 + 21 + 24 + 6 + 32 = 553
или b[18] - b[5] = 911 - 358 = 553

код самостоятельно.

@_qikert · 29.03.2020, 16:30

Для чего нужны интервальные суммы в данной задаче, а также по какому принципу вы строите список b?

@mathic · 30.03.2020, 08:28

eaa, очень интересно, но ничего не понятно

@Gdez · 30.03.2020, 17:33

К сожалению это тоже "медленно"

@eaa · 30.03.2020, 19:11

Сообщение от Gdez

К сожалению это тоже "медленно"

Удачи в реализации. Ни кода ни примеров, зато "медленно"

@Gdez · 30.03.2020, 19:32

Python
1
2
3
4
5
6
7
n = int(input())
c = ' ' + input()
s = tuple(int(elem) for elem in c.split())
d = tuple(int(elem) for elem in input().split())
dd = [sum(s[x:(x+d[x])]) for x in range(len(d))]
dd.reverse()
print(max(dd), n - dd.index(max(dd)))

@eaa · 30.03.2020, 19:37

я сдал решение unfindable_404.
применив то что описал в посте 6 и 8.
0.3 сек на максимальных ограничениях.

Добавлено через 2 минуты
Можете дерево отрезков или Фенвика написать. Как нравится.

@Gdez · 30.03.2020, 20:22

Нашел причину: у меня при нахождении dd по времени О(n**2) получалось. Переделал по вашему - прошло

@IvanNov1 · 30.03.2020, 20:47

И как ты переделал "по нашему"? Я не сильно понял...

@LuKy_RoMiK · 30.03.2020, 21:26

Даже информацию не могу найти про эту вашу интервальную сумму

Добавлено через 6 минут
Gdez объясни

@Gdez · 30.03.2020, 21:32

Дано а(0), а(1), а(2) ... а(n)
Получаем в(0), в(1), в(2) ... в(n), где:
в(0)=0
в(1)=а(0)
в(2)=а(0)+а(1)
......
в(n)= а(0)+в(1)+в(2)+ ... +а(n-1)
Чтобы найти сумму от а(7) до а(9) нужно найти в(9)-в(7)=а(7)+а(8)+а(9)
Полученный результат и есть интервальная сумма

@eaa · 30.03.2020, 21:36

leetcode 303-ая задача "Range Sum Query - Immutable". Разбирайся.

как писать тут было:
Частичные суммы

Добавлено через 2 минуты
Gdez,
в(10)-в(7) = а(7)+а(8)+а(9)

@Gdez · 30.03.2020, 21:37

Верно)))

Новые блоги и статьи Все статьи Все блоги /
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 Результат:	Установка CMake и MinGW 13.1 для сборки С и C++ приложений из консоли и из Qt Creator в EXE 8Observer8 10.03.2026 Содержание блога MinGW - это коллекция инструментов для сборки приложений в EXE. CMake - это система сборки приложений. Здесь описаны базовые шаги для старта программирования с помощью CMake и. . .	Как дизайн сайта влияет на конверсию: 7 решений, которые реально повышают заявки Neotwalker 08.03.2026 Многие до сих пор воспринимают дизайн сайта как “красивую оболочку”. На практике всё иначе: дизайн напрямую влияет на то, оставит человек заявку или уйдёт через несколько секунд. Даже если у вас. . .	Модульная разработка через nuget packages DevAlt 07.03.2026 Сложившийся в . Net-среде способ разработки чаще всего предполагает монорепозиторий в котором находятся все исходники. При создании нового решения, мы просто добавляем нужные проекты и имеем. . .

Вычислить сколько разговоров надо пропустить бизнесмену

Решение

Решение

@Cactoo 0 / 0 / 0 Регистрация: 23.03.2020 Сообщений: 14
	28.03.2020, 11:26 [ТС]
	Спасибо большое! Этот код для задачи, приведённой ниже: Телефон У бизнесмена есть телефон, который он использует для связи с партнерами по бизнесу. Сегодня у предпринимателя запланированы n разговоров, про каждый из которых известно число Pi — сколько рублей прибыли получит бизнесмен, если i-й разговор состоится (Pi может быть равно 0 — в этом случае никакой выгоды от i-го разговора нет). Телефон у бизнесмена сделан по новейшим технологиям, но иногда барахлит. Сегодня, например, телефон внезапно разрядился, поэтому он позволит бизнесмену провести только первые A0 разговоров, а затем выключится до конца дня. Однако телефон можно зарядить, пропустив несколько первых запланированных разговоров. Более формально, если предприниматель будет заряжать телефон вместо первых j разговоров (то есть разговоров с номерами от 1 до j), то он потом сможет провести ровно Aj разговоров (с номерами от j + 1 до min(n, j + Aj)), после чего телефон опять же перестанет работать до конца дня. Напишите программу, которая вычислит, сколько разговоров надо пропустить бизнесмену, чтобы заработать как можно больше. Если существует несколько ответов, то выведите тот, который требует большего времени зарядки, так как бизнесмену хочется отдохнуть подольше перед звонками. Входные данные На вход программе дается целое число n — количество запланированных звонков (1 ≤ n ≤ 2⋅105). На следующей строке вводятся через пробел n целых чисел Pi, обозначающие прибыли от звонков (0 ≤ Pi ≤ 1 000). Затем вводятся n+1 целых чисел Aj, обозначающие, сколько звонков можно будет провести после подзарядки (0 ≤ Aj ≤ 106). Выходные данные Выведите два числа, первое — это максимальная выгода, которую может получить бизнесмен, второе — количество пропущенных первых звонков, при котором она получается (0, если выгоднее всего не заряжать телефон вовсе). 0

@MrR0bot 0 / 0 / 0 Регистрация: 25.03.2020 Сообщений: 3
	29.03.2020, 13:57
	А вы не знаете, как решить задачу быстрее? 0

@eaa Status 418 4584 / 2350 / 601 Регистрация: 26.11.2017 Сообщений: 5,262 Записей в блоге: 3
	29.03.2020, 14:16
	Интервальные суммы, так вроде называется. Их можно вычислить один раз за O(n) в начале. Тогда в цикле для того чтобы проверить сумму на интервале нам понадобится O(1) действий. Итог весь алгоритм будет O(n) по времени. 2

@MrR0bot 0 / 0 / 0 Регистрация: 25.03.2020 Сообщений: 3
	29.03.2020, 14:33
	Не могли бы написать код? А то не очень понимаю о чём речь, ибо недавно начал изучать программирование. 0

@eaa Status 418 4584 / 2350 / 601 Регистрация: 26.11.2017 Сообщений: 5,262 Записей в блоге: 3
	29.03.2020, 16:19
	суть дан список a. a = [51, 89, 78, 63, 77, 61, 54, 90, 72, 26, 45, 1, 58, 63, 21, 24, 6, 32, 56, 55] строим список b b = [0, 51, 140, 218, 281, 358, 419, 473, 563, 635, 661, 706, 707, 765, 828, 849, 873, 879, 911, 967, 1022] если нужно найти сумму на отрезке [x,y]. то это будет b[y+1] - b[x]. найдем сумму на отрезке [5, 17] [5, 17] - сумма =61 + 54 + 90 + 72 + 26 + 45 + 1 + 58 + 63 + 21 + 24 + 6 + 32 = 553 или b[18] - b[5] = 911 - 358 = 553 код самостоятельно. 1

@_qikert 34 / 25 / 8 Регистрация: 16.11.2019 Сообщений: 179
	29.03.2020, 16:30
	Для чего нужны интервальные суммы в данной задаче, а также по какому принципу вы строите список b? 0

@mathic 0 / 0 / 0 Регистрация: 16.03.2020 Сообщений: 18 Записей в блоге: 1
	30.03.2020, 08:28
	eaa, очень интересно, но ничего не понятно 0

@Gdez 8851 / 4502 / 1864 Регистрация: 27.03.2020 Сообщений: 7,317
	30.03.2020, 17:33
	К сожалению это тоже "медленно" 0

@eaa Status 418 4584 / 2350 / 601 Регистрация: 26.11.2017 Сообщений: 5,262 Записей в блоге: 3
	30.03.2020, 19:37
	я сдал решение unfindable_404. применив то что описал в посте 6 и 8. 0.3 сек на максимальных ограничениях. Добавлено через 2 минуты Можете дерево отрезков или Фенвика написать. Как нравится. 0

@Gdez 8851 / 4502 / 1864 Регистрация: 27.03.2020 Сообщений: 7,317
	30.03.2020, 20:22
	Нашел причину: у меня при нахождении dd по времени О(n**2) получалось. Переделал по вашему - прошло 0

@IvanNov1 1 / 1 / 0 Регистрация: 16.03.2020 Сообщений: 2
	30.03.2020, 20:47
	И как ты переделал "по нашему"? Я не сильно понял... 0

@LuKy_RoMiK 8 / 6 / 2 Регистрация: 24.10.2019 Сообщений: 51
	30.03.2020, 21:26
	Даже информацию не могу найти про эту вашу интервальную сумму Добавлено через 6 минут Gdez объясни 0

@Gdez 8851 / 4502 / 1864 Регистрация: 27.03.2020 Сообщений: 7,317
	30.03.2020, 21:32
	Дано а(0), а(1), а(2) ... а(n) Получаем в(0), в(1), в(2) ... в(n), где: в(0)=0 в(1)=а(0) в(2)=а(0)+а(1) ...... в(n)= а(0)+в(1)+в(2)+ ... +а(n-1) Чтобы найти сумму от а(7) до а(9) нужно найти в(9)-в(7)=а(7)+а(8)+а(9) Полученный результат и есть интервальная сумма 1

@eaa Status 418 4584 / 2350 / 601 Регистрация: 26.11.2017 Сообщений: 5,262 Записей в блоге: 3
	30.03.2020, 21:36
	leetcode 303-ая задача "Range Sum Query - Immutable". Разбирайся. как писать тут было: Частичные суммы Добавлено через 2 минуты Gdez, в(10)-в(7) = а(7)+а(8)+а(9) 1

@Gdez 8851 / 4502 / 1864 Регистрация: 27.03.2020 Сообщений: 7,317
	30.03.2020, 21:37
	Верно))) 0