Участник:Tenzo(savok)/Intervals

Материал из DISCOPAL
< Участник:Tenzo(savok)
Версия от 20:54, 4 мая 2021; Tenzo(savok) (обсуждение | вклад) (Новая страница: «Суть проста. С каждым новым интервалом считаем количество вариантов для каждой суммы(с п…»)

(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

Суть проста. С каждым новым интервалом считаем количество вариантов для каждой суммы(с помощью словарей, что довольно просто). Формула сугубо математическая.

t = int(input())
intervals = []
Min = Max = 0
for i in range(t):
    s, e = map(int, input().split())
    if s <= e:
        intervals.append([s, e])
    else:
        intervals.append([e, s])
n, x = map(int, input().split())
 
 
def summarize(prev, now):
    Dict = dict()
    for first in prev:
        for second in now:
            Dict[first + second] = Dict.get(first + second, 0) + prev[first]
    return Dict
 
 
start = dict()
for i in range(t):
    if i == 0:
        for j in range(intervals[i][0], intervals[i][1] + 1):
            start[j] = 1
    else:
        new = dict()
        for j in range(intervals[i][0], intervals[i][1] + 1):
            new[j] = 1
        start = summarize(start, new)
for i in range(n, n + x + 1):
    if i not in start:
        print("NO")
    else:
        print(start[i])