Задача на динамическое программирование на Python

Question

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

Условие: Задача денег. Ярослав и Мирослава имеют общую коллекцию из ? монет. Как символ своей дружбы они хотят отдельно хранить такую пару монет, что в сумме нарицательная стоимость этих двух монет дает особое число ?. Подсчитайте количество разных способов выбрать нужную пару.

Технические условия: Программа Money читает с устройства стандартного ввода натуральные числа ? и ? не менее 2. Во второй строке ? натуральных чисел — номинальные стоимости монет из коллекции. Все числа (включая числа ? и ?) не превышают 200000. Программа выводит на устройство стандартного вывода единственное число — количество способов выбрать две монеты с суммарной номинальной стоимостью ?. Известно, что искомое количество не превышает 10^9.

пробовал написать код, получилась огромная нерабочая писанина, сам понимаю, что пошёл я не тем путём, ещё и запутался, пока писал. идея у меня была такая, что нужно отсортировать массив, и после выбирать первую и последнюю монету, но только в случаях, когда s - номинал первой монеты = номиналу последней, а для монет с одинаковым номиналом написал целый генератор, правда потом сломал его..) в своём коде я пытался ещё много нюансов учесть, но 100% там есть другое, удобное решение.

если интересно, то вот мой код (он не работает, но можно было бы доделать, но у меня уже нет сил):

s, n = map(int, input().split())
m = list(map(int, input().split()))
m.sort()
count = 0
sser = s - 1


while True:
    if count > sser:
        break

    minner = min(m)
    maxxer = max(m)

    if count != sser:

        minner = min(m)
        maxxer = max(m)

        if s - maxxer < minner:
            starter = minner

            reverser = s - starter
            poiskovik = len(m)
            mega_zapper = m[0]
            count += 1
            sser -= 1

            for i in reversed(m):
                if i > reverser:
                    poiskovik -= 1

                    if mega_zapper != i:
                        mega_zapper = i
                        count += 1
                        sser -= 1
                else:
                    break

            m = m[:poiskovik:]

            if count > sser:
                break

        elif s - maxxer > minner:
            starter = maxxer

            reverser = s - starter
            mega_zapper = m[-1]
            count += 1
            sser -= 1
            poiskovik = 0

            for i in m:
                if i < reverser:
                    poiskovik += 1

                    if mega_zapper != i:
                        mega_zapper = i
                        count += 1
                        sser -= 1
                else:
                    break

            m = m[poiskovik::]

            if count > sser:
                break

        else:
            if s % 2 == 0:
                if s / 2 == m[0]:
                    counter2 = 0
                    twos_count = 0

                    for num in m:
                        twos_count += 1
                        counter2 += twos_count - 1

                    count += counter2
                else:
                    counter_ch_1 = 0
                    counter_ch_2 = 0

                    zapper_1 = m[0]
                    zapper_2 = m[-1]

                    while True:
                        if m[0] == zapper_1:
                            counter_ch_1 += 1
                            m = m[1::]
                           if not m:
                                break
                        else:
                            break
                    while True:
                        if m[-1] == zapper_2:
                            counter_ch_2 += 1
                            m = m[:1:]
                            if not m:
                                break
                        else:
                            break

                    count += (counter_ch_1 * counter_ch_2)
            else:
                counter_ch_1 = 0
                counter_ch_2 = 0

                zapper_1 = m[0]
                zapper_2 = m[-1]

                while True:
                    if m[0] == zapper_1:
                        counter_ch_1 += 1
                        m = m[1::]
                        if not m:
                            break
                    else:
                        break
                while True:
                    if m[-1] == zapper_2:
                        counter_ch_2 += 1
                        m = m[:1:]
                        if not m:
                            break
                    else:
                        break

                count += (counter_ch_1 * counter_ch_2)

            count += 1
            sser -= 1

print(count)

Answer 1

Способ с сортировкой:

Левый индекс в начало, правый в конец
Считаете, сколько одинаковых элементов стоит слева (nl)
Правым идёте влево, пока не найдёте парное значение к левому элементу или не дойдёте до меньшего, чем нужно, значения В случае успешного нахождения пары считаете количество одинаковых элементов (nr), добавляете nl*nr к количеству пар. Сдвигаете левый индекс, и всё повторяете, пока индексы не сойдутся.

Способ со словарём:

Заполняете Counter значениями монет.
Для каждого key проверяете наличие парного s-key, добавляете к количеству пар произведение счётчиков.

import random, collections

n = 15
s = 8
a = [random.randint(1,7) for _ in range(n)]
print(a)
Cnt = collections.Counter(a)
print(Cnt)
res = 0
for k, v in Cnt.items():
    t = s - k
    u = v * Cnt[t] if t!=k else v*(v-1)
    res += u
    print(k, t, u)

print(res//2)

[6, 6, 5, 7, 4, 6, 5, 2, 5, 5, 6, 1, 3, 4, 2]
Counter({6: 4, 5: 4, 4: 2, 2: 2, 7: 1, 1: 1, 3: 1})
6 2 8
5 3 4
7 1 1
4 4 2
2 6 8
1 7 1
3 5 4
14

БЛОГ НА HUSL

Задача на динамическое программирование на Python

Ответы (1 шт):