Можете пожалуйста помочь с решением задач?

Question

[YSSITJ]

ПЫТАЮСЬ(ключевое слово) решить задачи -> https://contest.yandex.ru/contest/50668/problems/D...
данного контеста, но возникают проблемы. Есть ли у кого нибудь ответы на этот контест?
И не могли бы вы проверить почему мой код проходит по тестам, кроме тайм лимита(примерно понимаю что уровень O(N^2), но не знаю как упростить). Задача D "Лей, лей, не жалей"

a = [list(map(int, input().split())) for _ in range(int(input()))]
for i in range(int(input())):
    s = 0
    rs, re, typ = map(int, input().split())
    for st, end, cost in a:
        if typ == 1 and re >= st >= rs:
            s += cost
        elif typ == 2 and rs <= end <= re:
            s += end - st
    print(s, end=' ')

Comments

[Wispik]

Условие задачи то какое?

[Алан Гибизов]

Код трудно читать из-за коротких невнятных имен переменных. Следуйте PEP8 при написании кода.

Задача не видна без регистрации.

Было бы неплохо показать пример входных данных и ожидаемый результат, а также ожидаемое время исполнения.

Answer 1

[Руслан .]

Если упопядочить данные в списке "а" по возрастанию диапазонов, то не нужно будет всякий раз бежать до конца списка.
Можно будет сразу сделать break как только st и end перестанут укладываться в диапазон rs-re.
Опять же при наличии сортировки можно попообовать использовать бинарный поиск.

Comments

[YSSITJ]

Перед сном как раз грезил о том как использовать бинарный поиск ) Спасибо большое

[NikitaStepin]

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

def main():
    result_list = []
    list_of_dict = []

    n = int(input())
    for _ in range(n):
        start, end, cost = input().split(' ')
        list_of_dict.append(
            {
                "start": int(start),
                "end": int(end),
                "cost": int(cost),
            }
        )

    sorted_data_for_one = sorted(list_of_dict, key=lambda d: (d["start"]))
    sorted_data_for_two = sorted(list_of_dict, key=lambda d: (d["end"]))

    edge = len(sorted_data_for_one) // 2
    q = int(input())
    for _ in range(q):
        start, end, t_type = map(int, input().split(' '))

        flag_l = True
        flag_r = False
        i = edge
        if edge + 1 <= len(sorted_data_for_one) - 1:
            k = edge + 1
            flag_r = True

        if t_type == 1:
            total_cost = 0

            while flag_l or flag_r:
                if flag_l:
                    if start <= sorted_data_for_one[i]["start"] <= end:
                        total_cost += sorted_data_for_one[i]["cost"]
                    if i >= 1:
                        i -= 1
                    else:
                        flag_l = False

                if flag_r:
                    if start <= sorted_data_for_one[k]["start"] <= end:
                        total_cost += sorted_data_for_one[k]["cost"]

                    if k <= len(sorted_data_for_one) - 2:
                        k +=1
                    else:
                        flag_r = False

            result_list.append(str(total_cost))
        else:
            total_time = 0

            while flag_l or flag_r:
                if flag_l:
                    if start <= sorted_data_for_two[i]["end"] <= end:
                        total_time += sorted_data_for_two[i]["end"] - sorted_data_for_two[i]["start"]
                    if i >= 1:
                        i -= 1
                    else:
                        flag_l = False

                if flag_r:
                    if start <= sorted_data_for_two[k]["end"] <= end:
                        total_time += sorted_data_for_two[k]["end"] - sorted_data_for_two[k]["start"]
                    if k <= len(sorted_data_for_two) - 2:
                        k += 1
                    else:
                        flag_r = False

            result_list.append(str(total_time))

    print(" ".join(result_list))


if __name__ == '__main__':
    main()

[Руслан .]

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

def coins_sets(list_of_coins, target_sum, cur_coin, cur_coins_set, result, remaining_sum):
    if sum(cur_coins_set) > target_sum or (remaining_sum + sum(cur_coins_set)) < target_sum:
        return

    if sum(cur_coins_set) == target_sum:
        result.add(tuple(cur_coins_set))
        return

    for i in range(cur_coin, len(list_of_coins)):
        coins_sets(list_of_coins, target_sum, i + 1, [*cur_coins_set, list_of_coins[cur_coin]], result, remaining_sum - list_of_coins[cur_coin])

list_of_coins = [1, 1, 1, 1, 2, 3, 3, 5, 5, 5, 10, 10, 15, 20, 20, 25, 50, 50, 100]
target_sum = 25

result = set()
coins_sets(list_of_coins, target_sum, 0, [], result, sum(list_of_coins))

for cs in result:
    print(cs)