Задания 27. Программирование . Универсальный код

Question

Есть такое задание:

На вход программы поступает последовательность из N целых положительных чисел, все числа в последовательности различны. Рассматриваются все пары различных элементов последовательности (элементы пары не обязаны стоять в последовательности рядом, порядок элементов в паре неважен). Необходимо определить количество пар, для которых произведение элементов кратно 26.

В первой строке входных данных задаётся количество чисел N (1 ≤ N ≤ 60 000). В каждой из последующих N строк записано одно натуральное число, не превышающее 10 000. В качестве результата программа должна вывести одно число: количество пар, в которых произведение элементов кратно 26.

Пример организации исходных данных во входном файле:

5

2

6

13

31

93

Пример выходных данных для приведённого выше примера входных данных:

4

В ответе укажите два числа: сначала значение искомой суммы для файла А, затем для файла B.

Можно ли написать код, и решить данное задание без составления пар для числа 26 ? Составить универсальный код , который сможет обрабатывать все подобные числа, не тратя большое количество ресурсов по памяти ? Прошу помочь мне с этим заданием )

Как выглядит мой код с составлением пар:

f = open("pairs.txt" , 'r')
a = f.readlines()
k = []
for i in range(1, len(a)):
    q1 = int(a[i])
    k.append(q1)
k13 = 0
k0 = 0
k1 = 0
k26 = 0
count = 0
if k[0] % 13 == 0 and k[0] % 2 == 1:
    k13 += 1
elif k[0] % 26 == 0:
    k26 += 1
elif k[0] % 2 == 1:
    k1 += 1
elif k[0] % 2 == 0:
    k0 += 1
for j in range(1, len(k)):
    if k[j] % 13 == 0 and k[j] % 2 == 1:
        count += k0 + k26
        k13 += 1
    elif k[j] % 26 ==0:
        count += j
        k26 += 1
    elif k[j] % 2 ==1:
        count += k26
        k1 + =1
    elif k[j] % 2 == 0:
        count += k13
        k0 += 1
print(count)

Ваш код: ? ? ? ? ? введите сюда код

Универсальный код в моем понимании:

f = open("Файл")


def get():
    return list(map(int, f.readline().split()))

n = int(f.readline())
s = get()
m = float('-inf')
div = 3
for _ in range(n - 1):
    pair = get()
    temp = [i + j for i in s for j in pair]
    fake_s = [m] * div
    for x in temp:
        fake_s[x % div] = max(fake_s[x % div], x)
    s = [x for x in fake_s if x != m]
print(s)

Answer 1

Для получения результата вообще-то составлять пары совсем не нужно. Нужно иметь всего 3 счётчика - подсчитать числа которые делятся на 26, 13 и 2. А дальше просто вычислить количество комбинаций основываясь на этих счётчиках.

Если за эталон принять этот алгоритм, который проверяет все комбинации и вычисляет результат "в лоб":

def count_pairs_golden(iterable):
    count = 0
    for i, a in enumerate(iterable):
        for j, b in enumerate(iterable):
            if i != j and a * b % 26 == 0:
                count += 1

    return count

То алгоритм, который посчитает всё за один проход, будет выглядеть так:

def count_pairs(iterable):
    n = len(iterable)
    count2, count13, count26 = 0, 0, 0
    for value in iterable:
        mod2  = (value % 2  == 0)
        mod13 = (value % 13 == 0)
        if mod2 and mod13:
            count26 += 1
        elif mod2:
            count2  += 1
        elif mod13:
            count13 += 1
    
    # result = count2*count13*2       << количество комбинаций произведение
    #                                    которых делится на 26
    #        + count26*(n-1)          << количество чисел делящихся на 26 
    #                                    помножим  на остальные
    #        + count26*(n-count26)    << остальные (но не делящиеся на 26)
    #                                    помножим на количество чисел делящихся на 26
    return count2*count13*2 + count26*(n*2-count26-1)

Что всё считается правильно, можно проверить на рандомных тестах, сравнив с результатом, полученным при помощи "эталонного" алгоритма.

import random

#inp = [5,2,6,13,31, 39, 52, 65, 93, 26, 52, 78]
#inp = [1, 3, 26, 52, 78, 104]
inp = [2,6,13,31,93]
print(count_pairs_golden(inp), count_pairs(inp))

# random tests
numbers = range(1, 10001)
for _ in range(300):
    size = random.randint(500, 1500)
    inp = random.sample(numbers, size)
    count_golden = count_pairs_golden(inp)
    count = count_pairs(inp)
    if count_golden != count:
        print("ERROR!!!", count_golden, count)
        break
    #print("OK", size, count_golden, count)

Про "универсальный код" - я не понял. Если просто хочется записать компактно без кучи переменных, но чтобы ничего не понятно было, то можно так:

from itertools import product
def count_pairs(iterable):
    counts =  dict.fromkeys(product(range(2), repeat=2), 0)
    for value in iterable:
        counts[value%2==0,value%13==0] += 1
    return counts[1,0]*counts[0,1]*2 + counts[1,1]*(len(iterable)*2-counts[1,1]-1)

БЛОГ НА HUSL

Задания 27. Программирование . Универсальный код

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