Подсчет подмножеств, сумма элементов которых делится на 3

Подсчет подмножеств, сумма элементов которых делится на 3

 

Хотите готовиться со мной к ЕГЭ?
Пишите:  ydkras@mail.ru
Немного обо мне.

 

Рассмотрим задачу 27 для подготовки к ЕГЭ по информатике с сайта Полякова (вариант 20):

№ 3822) (А. Кабанов) В файле записана последовательность натуральных чисел. Гарантируется, что все числа различны. Рассматриваются всевозможные группы чисел, состоящие из любого количества элементов последовательности. Необходимо найти количество таких групп, для которых сумма элементов кратна 3.
Входные данные. Даны два входных файла (файл A и файл B), каждый из которых содержит в первой строке количество чисел N (1 ≤ N ≤ 100000). Каждая из следующих N строк содержит одно натуральное число, не превышающее 10⁸.
Пример входного файла:

4
5
7
12
23

Для указанных данных можно выбрать следующие группы: {12}; {7, 23}; {7, 12, 23}; {5, 7}; {5, 7, 12}. Программа должна вывести количество этих групп – 5.
В ответе укажите два числа: сначала искомое значение для файла А, затем для файла B.

Если мы скачаем файл B, то увидим, что в нём содержится 30 чисел. Нетрудно видеть,  что число непустых подмножеств этого множества чисел очень велико: 2**30 - 1, т.е. 1073741823 (знак ** означает возведение в степень). Поэтому прямой перебор всех возможных подмножеств, вычисление их сумм и подсчет подмножеств, сумма элементов которых кратна трём - это очень долго (скорее всего, экзамен закончится раньше). Необходимо придумать какой-то более быстрый способ.

Представим себе, что мы каким-то образом узнали, сколько подмножеств из части исходного файла дают сумму, которая делится на 3 без остатка, сколько подмножеств имеют сумму, которая при делении на 3 дает остаток 1 и сколько имеют сумму, которая дает остаток 2. Обозначим эти числа как g0, g1 и g2. Добавим к нашему множеству очередное число из входного массива. Как изменится количество соответствующих подмножеств?

Если наше число делится на 3 без остатка, то мы можем добавить его к любому подмножеству, которое делится на 3 без остатка, и получить новое подмножество, которое также будет делиться на 3 без остатка. Кроме того, данное число само образует подмножество, которое делится на 3 без остатка. Таким образом, g0' = 2*g0+1 (g0' - новое значение g0). Если добавить новое число в любое подмножество, сумма элементов которого дает при делении на 3 остаток 1, то мы получим новое подмножество опять-таки с суммой, дающей остаток 1. Иными словами, g1'=2*g1. Аналогично, g2'=2*g2.

Итак, если очередное число делится на 3 без остатка, то

g0'=2*g0+1
g1'=2*g1
g2'=2*g2

Если же наше новое число делится на 3 с остатком 1, то оно само образует подмножество, которое дает остаток 1. Кроме того, при добавлении его в любое подмножество с остатком 0 мы получаем подмножество с остатком 1. Таким образом, мы получаем, что g1'=g1+g0+1. При добавлении нашего числа в любое подмножество с остатком 1 мы получаем подмножество с остатком 2. Следовательно, g2'=g2+g1. Наконец, при добавлении нашего числа в любое подмножество с остатком 2 мы получаем подмножество, сумма которого делится на 3 без остатка. Отсюда g0'=g0+g2.

Итог: если новое число делится на три с остатком 1, то

g0'=g0+g2
g1'=g1+g0+1
g2'=g2+g1

И, наконец, если наше новое число при делении на 3 дает остаток 2, то

g0'=g0+g1
g1'=g1+g2
g2'=g2+g0+1

Теперь понятно, как можно построить очень быстрый алгоритм для решения данной задачи. Мы вначале полагаем, что g0=g1=g2=0. Затем читаем по очереди числа из входного массива и пересчитываем числа g0, g1 и g2 по приведенным выше формулам.

Составим программу на основе данных формул:

f=open("in.txt")
n=int(f.readline())
g0=0
g1=0
g2=0
for i in range(n):
    x=int(f.readline())%3
    if x==0:
        g0=2*g0+1
        g1=2*g1
        g2=2*g2
    if x==1:
        g0=g0+g2
        g1=g1+g0+1
        g2=g2+g1
    if x==2:
        g0=g0+g1
        g1=g1+g2
        g2=g2+g0+1
print(g0)

Запускаем нашу программу и... видим, что ответ совершенно неверный. Так, для файла A программа выдает ответ 1007, в то время как правильный ответ - 351. В чем дело?

А в том, что при выполнении последовательно записанных операторов, например, 

        g0=g0+g2
        g1=g1+g0+1
        g2=g2+g1

при вычислении g1 мы пользуемся уже "испорченным" (новым) значением g0. 

Самый простой выход - ввести новые переменные g0n, g1n, g2n, а потом переприсвоить их значения нашим переменным g0, g1 и g2:

f=open("in.txt")
n=int(f.readline())
g0=0
g1=0
g2=0
for i in range(n):
    x=int(f.readline())%3
    if x==0:
        g0n=2*g0+1
        g1n=2*g1
        g2n=2*g2
    if x==1:
        g0n=g0+g2
        g1n=g1+g0+1
        g2n=g2+g1
    if x==2:
        g0n=g0+g1
        g1n=g1+g2
        g2n=g2+g0+1
    g0=g0n
    g1=g1n
    g2=g2n
print(g0)

Теперь программа выдает правильный ответ.

Однако есть более короткое решение этой проблемы. Оператор присваивания в Питоне позволяет в девой части записать не одну переменную, а список переменных, разделенных запятыми. В правой части должен быть написан список значений (также через запятые). При этом сперва вычисляются значений выражений в правой части, а затем эти значения присваиваются переменным. Так, после выполнения оператора

a,b,c=3,5,8

переменная a получит значение 3, переменная b - 5 и переменная c - 8.

Новый код выглядит так:

f=open("in.txt")
n=int(f.readline())
g0=0
g1=0
g2=0
for i in range(n):
    x=int(f.readline())%3
    if x==0:
        g0,g1,g2=2*g0+1,2*g1,2*g2
    if x==1:
        g0,g1,g2=g0+g2,g1+g0+1,g2+g1
    if x==2:
        g0,g1,g2=g0+g1,g1+g2,g2+g0+1
print(g0)

Код стал существенно короче, и отпала надобность во временных переменных g0n,g1n,g2n.

Наконец, можно заметить, что формулы симметричны относительно переменных g1 и g2. Тогда, если не вводить отдельные переменные, а хранить значения в массиве, можно написать следующий код:

f=open("in.txt")
n=int(f.readline())
g=[0]*3
for i in range(n):
    x=int(f.readline())%3
    if x == 0: g[0], g[1], g[2] = 2*g[0]+1, 2*g[1], 2*g[2]
    else: g[0], g[x], g[3-x] = g[0] + g[3-x], g[x] + g[0]+1, g[3-x] + g[x]
print(g[0])

Очевидно, что если x=1, то 3-x=2 (и наоборот).

Оператор g=[0]*3 создает массив из трех элементов с начальными значениями, равными нулю.

Мы уложились в восемь строк.

Заметим также, что условие, что все числа во входном массиве различны, совершенно излишне. 

Подобным образом решается и задача 27 из варианта 19 на сайте Полякова:

(№ 3823) (А. Кабанов) В файле записана последовательность натуральных чисел. Гарантируется, что все числа различны. Рассматриваются всевозможные группы чисел, состоящие из любого количества элементов последовательности. Необходимо найти количество таких групп, для которых сумма элементов оканчивается на 5.
Входные данные. Даны два входных файла (файл A и файл B), каждый из которых содержит в первой строке количество чисел N (1 ≤ N ≤ 100000). Каждая из следующих N строк содержит одно натуральное число, не превышающее 10⁸.
Пример входного файла:

4
8
7
12
23

Для указанных данных можно выбрать следующие группы: {12, 23}; {8, 7}. Программа должна вывести количество этих групп – 2.
В ответе укажите два числа: сначала искомое значение для файла А, затем для файла B.

 

Очевидно, тут требуется рассматривать десять групп подмножеств: подмножества,  сумма элементов которых делится на 10 без остатка, подмножества, сумма элементов которых дает в остатке 1, 2, и т.д. до 9. Ответом будет число подмножеств, сумма элементов которых дает остаток 5. 

Прошу читателей не читать далее, а попробовать решить эту задачу самостоятельно.

Если же это не удалось, приведу решение:

f=open("in.txt")
n=int(f.readline())
k=10
g=[0]*k
dg=[0]*k
for i in range(n):
    x=int(f.readline())%k
    for j in range(k): dg[(j+x)%k] = g[j]
    dg[x] += 1
    for j in range(k): g[j] += dg[j]
print(g[5])

(c) Ю.Д.Красильников, 2021 г.