Top.Mail.Ru
Ответы

Как решить задачу на олимпиаде по программированию?

Имеется решение на языке Python, но оно использует слишком много памяти.
Наследники
Король Т-Царства Олег в 2024 году празднует свое шестидесятилетие. В связи с этим его заинтересовал вопрос наследства. На данный момент Т-Царство представляет из себя прямоугольник w*h, разделенный на графства параллельно своим сторонам. По вертикали разрезы проходят в координатах x1,x2,x3, по горизонтали в y1, y2, y3....

В первой строке вводятся два числа размеры Т-Царства.

Во второй строке вводятся два числа количество вертикальных и горизонтальных делений на графства.

В третьей строке вводится одно число количество сыновей.

В четвертой строке вводятся чисел координаты делений на графства по вертикали.

В пятой строке вводятся чисел координаты делений на графства по горизонтали.


Вот пример решения


12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758
 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 сыновей, и каждому из них он хочет оставить в наследство по одному графству, остальные участки отойдут в управление элите. Конечно, как и любой отец, Олег очень любит своих сыновей, поэтому он хочет отдать им
самых больших по размеру графств, при этом чем старше сын, тем большего размера ему должно достаться графство.

Теперь Олега интересует, а какая же разница в площади получится между графством самого младшего сына и графством самого старшего. Помогите Олегу посчитать площадь графства, которое получит самый младший из сыновей, и графства, которое получит самый старший из сыновей.

По дате
По рейтингу
Аватар пользователя
Новичок
9мес

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

N.B. Спасибо, добавил, что должно получиться. Но где описание правил, по которым графства распределяются между сыновьями? Может быть, старший сын получит вообще всё и младшему ничего не достанется?

В заведомо не укладывающемся в лимиты Python-коде бессмысленно разбираться: раз "слишком много памяти", значит надо не "переписать на C++" (опять будет "слишком много памяти"), а найти другой способ решения.

Аватар пользователя
Мастер
9мес

Да поможет вам Бог🙏🏿🙏🏿🙏🏿🙏🏿🙏🏿

Аватар пользователя
Ученик
9мес

Решил?

Аватар пользователя
Ученик
9мес

в итоге решил ли ты эту задачу?

Аватар пользователя
Искусственный Интеллект
9мес

Количество "графств" не должно быть меньше количества сыновей. С оставшимися-то что делать? Надо упорядочить "графства" по убыванию значения площади и отобрать по количеству сыновей. То есть ответом будет разница нулевого и последнего. До этого вычислить эти площади по координатам и составить список (как-нибудь "графства" идентифицировав, например, перенумеровав). Для сокращения занятой памяти надо упорядочить список длин (отрезков) на каждой стороне по убыванию и, составляя список площадей, сразу создавать его убывающим и равным по длине количеству сыновей.