Минимизация опасностей

@Dmitry0-01 · Регистрация: 17.09.2021

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

Пожалуйста помогите решить 3 задачи, я вас умоляю морочусь не один день
В компании, где работает Иван, активно применяют различные средства для контроля качества кода.

Перед тем, как использовать написанную программу, ее код проверяют при помощи n проверок. В качестве результата каждой из проверок дается некоторое целое число — опасность кода. Назовем общей опасностью кода произведение опасностей для каждой из проверок.

Ваня только что дописал свою программу и запустил все проверки. В результате проверок, он получил массив опасностей a₁, a₂, ..., aₙ.

Иван хочет минимизировать общую опасность написанного кода, для этого он готов не более c раз внести изменения в свой код. За одно внесение изменений он может увеличить или уменьшить на d результат одной из проверок, результат остальных проверок при этом не поменяется.

Помогите Ивану и предложите значения результатов проверок, дающие минимальную общую опасность, которые он может получить, сделав не более c изменений. Формат входных данных

В первой строке ввода дано три целых числа n, c и d — количество проверок, максимальное количество изменений, которое готов внести Иван, и число (1≤n≤200000;1≤c≤200000;1≤d≤10⁹).

Во второй строке ввода дано n целых чисел a₁, a₂, ..., aₙ. — результаты проверок кода Ивана до всех изменений (10⁹≤aᵢ≤10⁹).

Формат выходных данных

В единственной строке выведите n значений результатов проверок кода после применения не более чем c исправлений. Произведение всех результатов проверок должно быть минимальным.
Если ответов несколько, вы можете вывести любой.
Пример 1
Ввод
5 3 1
5 4 3 5 2
Вывод
5 4 3 5 -1
Пример 2
Ввод
5 3 1
5 4 3 5 5
Вывод
5 4 0 5 5
Пример 3
Ввод
5 3 1
5 4 4 5 5
Вывод
5 1 0 5 5
Пример 4
Ввод
3 2 7
5 4 2
Вывод
5 11 -5

Добавлено через 3 часа 5 минут
Или сможете исправить код

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
def minimize_danger(n, c, d, a):
    # Находим два наименьших значения
    min1 = min(a)
    a.remove(min1)
    min2 = min(a)
 
    # Если c > 0, заменяем минимальные значения новым значением
    if c > 0:
        min1 += d
        min2 += d
        c -= 1
 
    # Выводим результаты
    for i in range(n):
        if a[i] == min1:
            a[i] = min1
        elif a[i] == min2 and c > 0:
            a[i] = min2
            c -= 1
 
    return a
 
# Вводим данные
n, c, d = map(int, input().split())
a = list(map(int, input().split()))
 
# Вызываем функцию и выводим результат
result = minimize_danger(n, c, d, a)
print(result)

@Dmitry0-01 · 31.08.2023, 17:04 **[ТС]**

idealist, Да оно неверное

@Movka · 11.09.2023, 20:38

Добрый вечер! Тоже столкнулся с этой задачкой. У Вас были мысли о том, хотя бы в каком направлении двигаться, чтобы решить ее?

@Red white socks · 12.09.2023, 05:31

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

хотя бы в каком направлении двигаться, чтобы решить ее?

Разбирать случаи, пытаться привести все в общую схему. Начните с 2 чисел.

@idealist · 12.09.2023, 06:58

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
47
import heapq
from math import ceil
 
def make_neg(c, d, zip_arr, arr):
    mi_val, mi_ind = heapq.heappop(zip_arr)
    c_min = int(mi_val/d) + 1
    c -= c_min
    mi_val -= d * c_min
    heapq.heappush(zip_arr, (mi_val, mi_ind))
    arr[mi_ind] = mi_val
    for _ in range(c):
        min_neg, min_neg_ind = heapq.heappop(zip_arr)
        min_pos, min_pos_ind = heapq.heappop(zip_arr)
        if abs(min_neg) < min_pos:
            heapq.heappush(zip_arr, (min_neg-d, min_neg_ind))
            arr[min_neg_ind] = min_neg-d
            heapq.heappush(zip_arr, (min_pos, min_pos_ind))
        else:
            heapq.heappush(zip_arr, (min_neg, min_neg_ind))
            heapq.heappush(zip_arr, (min_pos+d, min_pos_ind))
            arr[min_pos_ind] = min_pos+d
 
def make_null(c, d, zip_arr, arr):
    mi_val, mi_ind = heapq.heappop(zip_arr)
    heapq.heappush(zip_arr, (0, mi_ind))
    arr[mi_ind] = 0
 
def make_pos(c, d, zip_arr, arr):
    for _ in range(c):
        mi_val, mi_ind = heapq.heappop(zip_arr)
        heapq.heappush(zip_arr, (mi_val-d, mi_ind))
        arr[mi_ind] = mi_val-d
 
n, c, d = map(int, input('n, c, d->').split())
arr = list(map(int, input('->').split()))
zip_arr = list(zip(arr, list(range(len(arr)))))
heapq.heapify(zip_arr)
mi_val, mi_ind = heapq.heappop(zip_arr)
heapq.heappush(zip_arr, (mi_val, mi_ind))
res = mi_val - d * c
if res < 0:
    make_neg(c, d, zip_arr, arr)
elif res == 0:
    make_null(c, d, zip_arr, arr)
else:
    make_pos(c, d, zip_arr, arr)
print(*arr)

@Red white socks · 12.09.2023, 10:10

idealist, запутано всё у вас тут как-то.
Когда все числа неотрицательны, уменьшаем наименьший элемент. Как доуменьшались до отрицательного (можно эти шаги в один сгруппировать) - сваливаем модули в кучу и увеличиваем на каждом шаге наименьший. Кажется, что все это за меньшее число строк можно организовать.

@idealist · 12.09.2023, 10:17

Сообщение от Red white socks

Кажется, что все это за меньшее число строк можно организовать.

Может и можно, кто его знает. А как это в кучу, ведь модуль отрицательного увеличивается вычитанием, а положительного - сложением?

@Red white socks · 12.09.2023, 10:28

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

@idealist · 12.09.2023, 11:59

Сообщение от Red white socks

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

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

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
import heapq
from math import ceil
 
def make_neg(c, d, zip_arr, arr):
    min_neg, min_neg_ind = heapq.heappop(zip_arr)
    c_min = int(min_neg / d) + 1
    c -= c_min
    min_neg -= d * c_min
    arr[min_neg_ind] = min_neg
    for _ in range(c):
        min_pos, min_pos_ind = heapq.heappop(zip_arr)
        if abs(min_neg) < min_pos:
            min_neg -= d
            arr[min_neg_ind] = min_neg
        else:
            min_pos += d
            arr[min_pos_ind] = min_pos
        heapq.heappush(zip_arr, (min_pos, min_pos_ind))
        
def make_null(c, d, zip_arr, arr):
    mi_val, mi_ind = heapq.heappop(zip_arr)
    heapq.heappush(zip_arr, (0, mi_ind))
    arr[mi_ind] = 0
 
def make_pos(c, d, zip_arr, arr):
    for _ in range(c):
        mi_val, mi_ind = heapq.heappop(zip_arr)
        heapq.heappush(zip_arr, (mi_val - d, mi_ind))
        arr[mi_ind] = mi_val - d
 
n, c, d = map(int, input('n, c, d->').split())
arr = list(map(int, input('->').split()))
zip_arr = list(zip(arr, list(range(len(arr)))))
heapq.heapify(zip_arr)
mi_val, mi_ind = heapq.heappop(zip_arr)
heapq.heappush(zip_arr, (mi_val, mi_ind))
res = mi_val - d * c
if res < 0:
    make_neg(c, d, zip_arr, arr)
elif res == 0:
    make_null(c, d, zip_arr, arr)
else:
    make_pos(c, d, zip_arr, arr)
print(*arr)

А, и еще плюс моего подхода в том, что нулевой элемент до нулевого состояния и отрицательный элемент до отрицательного состояния доводятся аналитически, а не через кучу, что экономит время.

@Red white socks · 12.09.2023, 12:06

idealist, 3 функции излишни и два массива тоже, но дело вкуса

И вот этот кусок странный:

Python
1
2
mi_val, mi_ind = heapq.heappop(zip_arr)
heapq.heappush(zip_arr, (mi_val, mi_ind))

Минимум в куче - первый элемент списка

Python
1
mi_val, mi_ind = zip_arr[0]

@idealist · 12.09.2023, 12:11

Сообщение от Red white socks

Минимум в куче - первый элемент списка

Мерси, этот нюанс я еще не постиг.

@Red white socks · 12.09.2023, 12:12

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

А, и еще плюс моего подхода в том, что нулевой элемент до нулевого состояния и отрицательный элемент до отрицательного состояния доводятся аналитически

Тут я не спорю, но это при любом подходе можно сделать)

@idealist · 12.09.2023, 14:17

Сообщение от Red white socks

Минимум в куче - первый элемент списка

Тогда для отрицательного элемента кучу можно еще реже беспокоить:

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
import heapq
 
def make_neg(c, d, zip_arr, arr):
    min_neg, min_neg_ind = heapq.heappop(zip_arr)
    c_min = int(min_neg / d) + 1
    c -= c_min
    min_neg -= d * c_min
    arr[min_neg_ind] = min_neg
    for _ in range(c):
        if abs(min_neg) < zip_arr[0][0]:
            min_neg -= d
            arr[min_neg_ind] = min_neg
        else:
            min_pos, min_pos_ind = heapq.heappop(zip_arr)
            min_pos += d
            arr[min_pos_ind] = min_pos
            heapq.heappush(zip_arr, (min_pos, min_pos_ind))
 
def make_null(c, d, zip_arr, arr):
    mi_val, mi_ind = heapq.heappop(zip_arr)
    heapq.heappush(zip_arr, (0, mi_ind))
    arr[mi_ind] = 0
 
def make_pos(c, d, zip_arr, arr):
    for _ in range(c):
        mi_val, mi_ind = heapq.heappop(zip_arr)
        heapq.heappush(zip_arr, (mi_val - d, mi_ind))
        arr[mi_ind] = mi_val - d
 
n, c, d = map(int, input('n, c, d->').split())
arr = list(map(int, input('->').split()))
zip_arr = list(zip(arr, list(range(len(arr)))))
heapq.heapify(zip_arr)
mi_val, mi_ind = zip_arr[0]
res = mi_val - d * c
if res < 0:
    make_neg(c, d, zip_arr, arr)
elif res == 0:
    make_null(c, d, zip_arr, arr)
else:
    make_pos(c, d, zip_arr, arr)
print(*arr)

@Red white socks · 12.09.2023, 15:10

idealist, я все же не понимаю зачем вам процедуры make_pos и make_null

@idealist · 12.09.2023, 22:10

Сообщение от Red white socks

idealist, я все же не понимаю зачем вам процедуры make_pos и make_null

Да я уже сам пришел к выводу, что они лишние. Если мы не доходим до отрицательного элемента, то всё сводится к банальному многократному уменьшению одного и того же минимального элемента.
Вот так проще будет:

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
import heapq
 
def make_neg(c, d, zip_arr, arr):
    min_neg, min_neg_ind = heapq.heappop(zip_arr)
    c_min = int(min_neg / d) + 1
    c -= c_min
    min_neg -= d * c_min
    arr[min_neg_ind] = min_neg
    for _ in range(c):
        if abs(min_neg) <= zip_arr[0][0]:
            min_neg -= d
            arr[min_neg_ind] = min_neg
        else:
            min_pos, min_pos_ind = heapq.heappop(zip_arr)
            min_pos += d
            arr[min_pos_ind] = min_pos
            heapq.heappush(zip_arr, (min_pos, min_pos_ind))
 
n, c, d = map(int, input('n, c, d->').split())
arr = list(map(int, input('->').split()))
zip_arr = list(zip(arr, list(range(len(arr)))))
heapq.heapify(zip_arr)
mi_val, mi_ind = zip_arr[0]
res = mi_val - d * c
if res >= 0:
    arr[mi_ind] = res
else:
    make_neg(c, d, zip_arr, arr)
print(*arr)

@idealist · 13.09.2023, 05:46

Сообщение от Red white socks

излишни и два массива тоже

А как без второго массива? Вы его сортируете что ли в конце?

@Red white socks · 13.09.2023, 07:29

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

А как без второго массива? Вы его сортируете что ли в конце?

Тонкий момент. Вроде бы сортировка увеличивает время, но с другой стороны, асимптотика не увеличивается, зато в теле цикла убраны операции и код чуточку прозрачнее. Наверное, тоже дело вкуса

Новые блоги и статьи Все статьи Все блоги /
Запрет дублирования строк в табличной части Maks 13.09.2026 Реализация из решения ниже выполнена на нетиповом справочнике "Нормы ТО" с табличной часть "Виды ТО", разработанного в КА2, со следующими реквизитами: - ВидТО (СправочникСсылка. ВидыТО); - ВидГСМ. . .	Скрипты Tampermonkey для CyberForum, ChatGPT, Claude и пр. Jin X 06.09.2026 Скрипты Tampermonkey для CyberForum, ChatGPT, Claude и пр. Работая с форумом и нейросетями в браузере часто хочется что-то подкорректировать или добавить какого-то функционала. Ниже прикреплён. . .	Программа опроса у.з. расходомера SLS-720F Argus19 02.09.2026 Программа опроса у. з. расходомера SLS-720F Программа опрашивает один раз в минуту три ультразвуковых расходомера SLS-720F через интерфейс RS-485 по протоколу Modbus RTU. Опрашиваются регистры. . .	Hyper-V: Компьютер должен поддерживать доверенный платформенный модуль 2.0. Maks 31.08.2026 При установке Windows 11 на виртуальную машину Hyper-V 2-го поколения вылезла такая ошибка: Решение: в параметрах виртуальной машины, в разделе "Безопасность" (Security) активировать флаг. . .
Архитектура биовида Стива в Майнкрафте: Зачем бонобо кубический каннибализм anaschu 30.08.2026 Кубический Вагинокапитализм в Minecraft: Математический инвариант ОДУ и рок Стивов-бонобо Главная задача разработанной «Модели Всего» — наглядно продемонстрировать наличие системной «судьбы». . .	Оттачиваю умение писать js программы. russiannick 30.08.2026 Проектом выходного дня стало написание Книги шифров Виженера. Итогом стала версия 200, синий туман. Синий туман назван так, потому что замораживает текст под собой. Нажатие синих кнопок управляют. . .	мат медиц модель 30. презентация проекта anaschu 27.08.2026 хоп хоп хоп хидахоп, а я кладую))	Как у меня протекала болезнь zorxor 27.08.2026 Здравствуйте, друзья! Эта запись блога предназначена именно для вас - для моих дорогих друзей, которые знали меня лично. Чтобы ответить на вопрос - а что же со мной произошло на самом деле? Я учился. . .

@Dmitry0-01 4 / 5 / 2 Регистрация: 17.09.2021 Сообщений: 416
	31.08.2023, 17:04 [ТС]
	idealist, Да оно неверное 0

@Movka 0 / 0 / 0 Регистрация: 19.04.2020 Сообщений: 12
	11.09.2023, 20:38
	Добрый вечер! Тоже столкнулся с этой задачкой. У Вас были мысли о том, хотя бы в каком направлении двигаться, чтобы решить ее? 0

@Red white socks 4523 / 1899 / 336 Регистрация: 18.01.2021 Сообщений: 3,489
	12.09.2023, 10:10
	idealist, запутано всё у вас тут как-то. Когда все числа неотрицательны, уменьшаем наименьший элемент. Как доуменьшались до отрицательного (можно эти шаги в один сгруппировать) - сваливаем модули в кучу и увеличиваем на каждом шаге наименьший. Кажется, что все это за меньшее число строк можно организовать. 0

@Red white socks 4523 / 1899 / 336 Регистрация: 18.01.2021 Сообщений: 3,489
	12.09.2023, 10:28
	В кучу модули скидываем, а индекс отрицательного можно и запомнить 0

@Red white socks 4523 / 1899 / 336 Регистрация: 18.01.2021 Сообщений: 3,489
	12.09.2023, 15:10
	idealist, я все же не понимаю зачем вам процедуры make_pos и make_null 0

Минимизация опасностей

Решение