Как решить задачу на олимпиаде по программированию?
Имеется решение на языке Python, но оно использует слишком много памяти.
Наследники
Король Т-Царства Олег в 2024 году празднует свое шестидесятилетие. В связи с этим его заинтересовал вопрос наследства. На данный момент Т-Царство представляет из себя прямоугольник w*h, разделенный на графства параллельно своим сторонам. По вертикали разрезы проходят в координатах x1,x2,x3, по горизонтали в y1, y2, y3....
В первой строке вводятся два числа размеры Т-Царства.
Во второй строке вводятся два числа количество вертикальных и горизонтальных делений на графства.
В третьей строке вводится одно число количество сыновей.
В четвертой строке вводятся чисел координаты делений на графства по вертикали.
В пятой строке вводятся чисел координаты делений на графства по горизонтали.
Вот пример решения
import heapq
import gc
def f(x):
return (x[i + 1] - x[i] for i in range(len(x) - 1))
def Solution(w, h, n, m, k, x, y):
# Освобождаем память от ненужных переменных
del w, h, n, m
gc.collect()
widths = f(x)
heights = f(y)
# Очистка памяти от ненужных переменных
del x, y
gc.collect()
# Поддерживаем кучу размера k
heap = []
for width in widths:
for height in heights:
area = width * height
if len(heap) < k:
heapq.heappush(heap, area)
else:
break
mi = min(heap)
# Освобождаем память от ненужных переменных
del widths, heights
gc.collect()
return heap, mi
if __name__ == "__main__":
w, h = map(int, input().split())
n, m = map(int, input().split())
k = int(input())
if n > 0:
x = list(map(int, input().split()))
else:
x = []
if m > 0:
y = list(map(int, input().split()))
else:
y = []
x = [0] + x + [w]
y = [0] + y + [h]
mi, ma = Solution(w, h, n, m, k, x, y)
print(mi, ma)
Можете переписать его на C++
ДополненЗабыл добавить что найти - площадь, которую получит младший сын и старший
Входные данные
10 8
3 2
6
1 5 7
4 6
Результат работы
6 16
Входные данные
5 5
0 1
2
3
Результат работы
10 15
У Олега k сыновей, и каждому из них он хочет оставить в наследство по одному графству, остальные участки отойдут в управление элите. Конечно, как и любой отец, Олег очень любит своих сыновей, поэтому он хочет отдать им
самых больших по размеру графств, при этом чем старше сын, тем большего размера ему должно достаться графство.
Теперь Олега интересует, а какая же разница в площади получится между графством самого младшего сына и графством самого старшего. Помогите Олегу посчитать площадь графства, которое получит самый младший из сыновей, и графства, которое получит самый старший из сыновей.
А задача-то где? Ты дал только описание исходных данных. Без описания того, что с этими данными нужно делать и что должно получиться в результате.
N.B. Спасибо, добавил, что должно получиться. Но где описание правил, по которым графства распределяются между сыновьями? Может быть, старший сын получит вообще всё и младшему ничего не достанется?
В заведомо не укладывающемся в лимиты Python-коде бессмысленно разбираться: раз "слишком много памяти", значит надо не "переписать на C++" (опять будет "слишком много памяти"), а найти другой способ решения.
Да поможет вам Бог🙏🏿🙏🏿🙏🏿🙏🏿🙏🏿
Решил?
в итоге решил ли ты эту задачу?
Количество "графств" не должно быть меньше количества сыновей. С оставшимися-то что делать? Надо упорядочить "графства" по убыванию значения площади и отобрать по количеству сыновей. То есть ответом будет разница нулевого и последнего. До этого вычислить эти площади по координатам и составить список (как-нибудь "графства" идентифицировав, например, перенумеровав). Для сокращения занятой памяти надо упорядочить список длин (отрезков) на каждой стороне по убыванию и, составляя список площадей, сразу создавать его убывающим и равным по длине количеству сыновей.