27. 07 Прочие прототипы

Показать ответ и решение

Решение 1

f = open(’27A.txt’)
n = int(f.readline())

nums = []
for i in range(n):
    nums.append(int(f.readline()))

ans = []
for i in range(2**n):
    t = i
    mn = []
    for j in range(n):
        if t % 2 == 1:
            mn.append(nums[j])
        t //= 2

    if len(mn) > 0:
        ans.append(mn)

print(len(ans))

Решение 2

from itertools import combinations

f = open(’27A.txt’)
n = int(f.readline())

nums = []
for i in range(n):
    nums.append(int(f.readline()))

ans = []
for j in range(1, 21):
    for i in combinations(nums, j):
        ans.append(i)

print(len(ans))

Ответ: 1048575

Ошибка.
Попробуйте повторить позже

Задача 4#40716

На вход программы поступает последовательность из $N$ натуральных чисел, все числа в последовательности различны.

Рассматриваются всевозможные непустые уникальные подмножества, состоящие из элементов последовательности. Необходимо определить количество различных множеств, длины 5.

Уникальным множеством считается то, что встречается один раз (то есть перестановки элементов внутри множества не делают его уникальным).

Пример входных данных:

Первая строка входного файла содержит число $N$ — общее количество чисел. Каждая из следующих $N$ строк содержит натуральные числа, не превышающих 10 000.

Пример входного файла

5

10

15

91

33

Для указанных данных ответом будут являться {5, 10, 15, 91, 33}, то есть 1.

Вложения к задаче

Показать ответ и решение

Решение 1

f = open(’27A.txt’)
n = int(f.readline())

nums = []
for i in range(n):
    nums.append(int(f.readline()))

ans = []
for i in range(2**n):
    t = i
    mn = []
    for j in range(n):
        if t % 2 == 1:
            mn.append(nums[j])
        t //= 2
        if len(mn) > 5:
            break

    if len(mn) == 5:
        ans.append(mn)

print(len(ans))

Решение 2

from itertools import combinations

f = open(’27A.txt’)
n = int(f.readline())

nums = []
for i in range(n):
    nums.append(int(f.readline()))

ans = []
for i in combinations(nums, 5):
    ans.append(i)

print(len(ans))

Решение 3

f = open(’27A.txt’)
n = int(f.readline())


def factorial(m):
    c = 1
    for j in range(1, m + 1):
        c *= j
    return c


ans = 0
for i in range(1, n + 1):
    ans += (factorial(20 - i) // ((factorial(4) * factorial(20 - i - 4))))

print(ans)

Ответ: 15504

Ошибка.
Попробуйте повторить позже

Задача 5#40717

На вход программы поступает последовательность из $N$ натуральных чисел, все числа в последовательности различны.

Рассматриваются всевозможные непустые уникальные подмножества, состоящие из элементов последовательности. Необходимо определить количество различных множеств, длины 5.

Уникальным множеством считается то, что встречается один раз (то есть перестановки элементов внутри множества не делают его уникальным).

Пример входных данных:

Первая строка входного файла содержит число $N$ — общее количество чисел. Каждая из следующих $N$ строк содержит натуральные числа, не превышающих 10 000.

Пример входного файла

5

10

15

91

33

Для указанных данных ответом будут являться {5, 10, 15, 91, 33}, то есть 1.

Вложения к задаче

Показать ответ и решение

Решение 1

f = open(’27A.txt’)
n = int(f.readline())

nums = []
for i in range(n):
    nums.append(int(f.readline()))

ans = []
for i in range(2**n):
    t = i
    mn = []
    for j in range(n):
        if t % 2 == 1:
            mn.append(nums[j])
        t //= 2
        if len(mn) > 5:
            break

    if len(mn) == 5:
        ans.append(mn)

print(len(ans))

Решение 2

from itertools import combinations

f = open(’27A.txt’)
n = int(f.readline())

nums = []
for i in range(n):
    nums.append(int(f.readline()))

ans = []
for i in combinations(nums, 5):
    ans.append(i)

print(len(ans))

Решение 3

f = open(’27A.txt’)
n = int(f.readline())


def factorial(m):
    c = 1
    for j in range(1, m + 1):
        c *= j
    return c


ans = 0
for i in range(1, n + 1):
    ans += (factorial(20 - i) // ((factorial(4) * factorial(20 - i - 4))))

print(ans)

Ответ: 524287

Ошибка.
Попробуйте повторить позже

Задача 6#40718

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

Пример входных данных:

Первая строка входного файла содержит число N – общее количество чисел. Каждая из следующих N строк содержит натуральные числа, не превышающих 10 000.

Пример входного файла

3

2

10

5

Для указанных данных ответом будут являться {2}, {10}, {2, 10}, то есть 3.

Вложения к задаче

Показать ответ и решение

Решение 1

f = open(’27A.txt’)
n = int(f.readline())

nums = []
for i in range(n):
    nums.append(int(f.readline()))

ans = 0
for i in range(2**n):
    t = i
    mn = []
    for j in range(n):
        if t % 2 == 1:
            mn.append(nums[j])
        t //= 2
    if len(mn) > 0:
        if sum(mn) % 2 == 0:
            ans += 1

print(ans)

Решение 2

f = open(’27A.txt’)
n = int(f.readline())
k = 2
ans = [0] * k

for i in range(n):
    x = int(f.readline())
    ans_new = ans[:]  # Аналог ans.copy()
    for j in range(k):
        ans_new[(j + x) % k] += ans[j]
    ans_new[x % k] += 1
    ans = ans_new[:]

print(ans[0])

Ответ: 524287

Ошибка.
Попробуйте повторить позже

Задача 7#40719

На вход программы поступает последовательность из $N$ натуральных чисел, все числа в последовательности различны. Рассматриваются всевозможные непустые подмножества, состоящие из элементов последовательности. Необходимо найти количество подмножеств длины 3, в которых сумма элементов кратна 3.

Пример входных данных:

Первая строка входного файла содержит число $N$ – общее количество чисел. Каждая из следующих $N$ строк содержит натуральные числа, не превышающих 10 000.

Пример входного файла

3

1

2

3

Для указанных данных ответом будет являться, {1, 2, 3}, то есть 1.

Вложения к задаче

Показать ответ и решение

Решение 1

f = open(’27A.txt’)
n = int(f.readline())

nums = []
for i in range(n):
    nums.append(int(f.readline()))

ans = 0
for i in range(2**n):
    t = i
    mn = []
    for j in range(n):
        if t % 2 == 1:
            mn.append(nums[j])
        t //= 2
    if len(mn) == 3:
        if sum(mn) % 3 == 0:
            ans += 1

print(ans)

Решение 2

from itertools import combinations

f = open(’27A.txt’)
n = int(f.readline())

nums = []
for i in range(n):
    nums.append(int(f.readline()))

ans = 0
for i in combinations(nums, 3):
    if sum(i) % 3 == 0:
        ans += 1

print(ans)

Ответ: 357

Ошибка.
Попробуйте повторить позже

Задача 8#40720

На вход программы поступает последовательность из $N$ натуральных чисел, все числа в последовательности различны. Рассматриваются всевозможные непустые подмножества, состоящие из элементов последовательности. Необходимо найти количество подмножеств, в которых есть хотя бы одно простое число. Простым числом является то, которое делится только на себя и на 1. Также 1 не является простым числом.

Пример входных данных:

Первая строка входного файла содержит число $N$ – общее количество чисел. Каждая из следующих $N$ строк содержит натуральные числа, не превышающих 10 000.

Пример входного файла

3

2

4

6

Для указанных данных ответом будет являться, {2}, {2, 4}, {2, 6}, {2, 4, 6}, то есть 4.

Вложения к задаче

Показать ответ и решение

Решение 1

def prime(x):
    if x == 1:
        return False
    for i in range(2, int(x**0.5)+1):
        if x % i == 0:
            return False
    return True

f = open(’27A.txt’)
n = int(f.readline())

nums = []
for i in range(n):
    nums.append(int(f.readline()))

ans = 0
for i in range(2**n):
    t = i
    mn = []
    for j in range(n):
        if t % 2 == 1:
            mn.append(nums[j])
        t //= 2

    for x in mn:
        if prime(x):
            ans += 1
            break

print(ans)

Решение 2

from itertools import combinations

def prime(x):
    if x == 1:
        return False
    for i in range(2, int(x**0.5)+1):
        if x % i == 0:
            return False
    return True

f = open(’27A.txt’)
n = int(f.readline())

nums = []
for i in range(n):
    nums.append(int(f.readline()))

ans = 0
for j in range(1, n+1):
    for i in combinations(nums, j):
        for x in i:
            if prime(x):
                ans += 1
                break

print(ans)

Ответ: 786432

Ошибка.
Попробуйте повторить позже

Задача 9#42400

На вход программы поступает последовательность из $N$ натуральных чисел, все числа в последовательности различны.

Рассматриваются все возможные непустые уникальные подмножества, состоящие из элементов последовательности. Необходимо определить количество различных множеств, в которых присутствует число $233$ .

Уникальным множеством считается то, что встречается один раз (то есть перестановки элементов внутри множества не делают его уникальным).

Пример входных данных:

Первая строка входного файла содержит число $N$ — общее количество чисел. Каждая из следующих N строк содержит натуральные числа, не превышающих $10$ $000$ .

Пример входного файла

Если требуется посчитать кол-во множеств, где присутствует $5$ .

3

5

10

15

Для указанных данных ответом будут являться ${5},{5,10},{5,15},{5,10,15}$ , то есть $4$ .

Вложения к задаче

Показать ответ и решение

f = open(’27.txt’)
n = int(f.readline())

nums = []
for i in range(n):
    nums.append(int(f.readline()))

count = 0
subsets = set()
for i in range(1, 2**n): # i = 0 нам не подходит, так как задает пустое подмножество
    t = i
    mn = []
    for j in range(n):
        if t % 2 == 1:
            mn.append(nums[j])
        t //= 2
    if 233 in mn and tuple(sorted(mn)) not in subsets:
        count += 1
    subsets.add(tuple(sorted(mn)))

print(count)

Ответ: 524288

Ошибка.
Попробуйте повторить позже

Задача 10#42401

На вход программы поступает последовательность из $N$ натуральных чисел, все числа в последовательности различны.

Рассматриваются все возможные непустые уникальные подмножества, состоящие из элементов последовательности. Необходимо определить количество различных множеств, в которых не присутствуют числа $2005$ и $1081$ .

Уникальным множеством считается то, что встречается один раз (то есть перестановки элементов внутри множества не делают его уникальным).

Пример входных данных:

Первая строка входного файла содержит число $N$ — общее количество чисел. Каждая из следующих N строк содержит натуральные числа, не превышающих $10$ $000$ .

Вложения к задаче

Показать ответ и решение

f = open(’27.txt’)
n = int(f.readline())

nums = []
for i in range(n):
    nums.append(int(f.readline()))

ans = 0
for i in range(1, 2**n): # i = 0 нам не подходит, так как задает пустое подмножество
    t = i
    mn = []
    for j in range(n):
        if t % 2 == 1:
            mn.append(nums[j])
        t //= 2

    if not 2005 in mn and not 1081 in mn:
        ans += 1

print(ans)

Ответ: 262143

Ошибка.
Попробуйте повторить позже

Задача 11#42402

На вход программы поступает последовательность из $N$ натуральных чисел, все числа в последовательности различны.

Рассматриваются все возможные непустые уникальные подмножества, состоящие из элементов последовательности. Необходимо определить количество различных множеств, длины $5$ , содержащих число $2337$ .

Уникальным множеством считается то, что встречается один раз (то есть перестановки элементов внутри множества не делают его уникальным).

Пример входных данных:

Первая строка входного файла содержит число $N$ — общее количество чисел. Каждая из следующих $N$ строк содержит натуральные числа, не превышающих $10$ $000$ .

Вложения к задаче

Показать ответ и решение

f = open(’27.txt’)
n = int(f.readline())

nums = []
for i in range(n):
    nums.append(int(f.readline()))

ans = 0
for i in range(1, 2**n): # i = 0 нам не подходит, так как задает пустое подмножество
    t = i
    mn = []
    for j in range(n):
        if t % 2 == 1:
            mn.append(nums[j])
        t //= 2

        if len(mn) > 5:
            break

    if len(mn) == 5:
        if 2337 in mn:
            ans += 1

print(ans)

Ответ: 3876

Ошибка.
Попробуйте повторить позже

Задача 12#42403

На вход программы поступает последовательность из $N$ натуральных чисел, все числа в последовательности различны. Гарантируется, что все числа различны. Рассматриваются все возможные непустые подмножества, состоящие из элементов последовательности. Необходимо найти количество подмножеств, в которых сумма элементов кратна $5$ , а произведение элементов кратно $10$ .

Пример входных данных:

Первая строка входного файла содержит число $N$ – общее количество троек в наборе. Каждая из следующих $N$ строк содержит натуральные числа, не превышающих $10$ $000$ .

Вложения к задаче

Показать ответ и решение

f = open(’27.txt’)
n = int(f.readline())

nums = []
for i in range(n):
    nums.append(int(f.readline()))

ans = 0
for i in range(1, 2**n): # i = 0 нам не подходит, так как задает пустое подмножество
    t = i
    mn = []
    for j in range(n):
        if t % 2 == 1:
            mn.append(nums[j])
        t //= 2
    s, p = 0, 1
    for x in mn:
        s += x
        p *= x
    if s % 5 == 0 and p % 10 == 0:
        ans += 1

print(ans)

Ответ: 202865

Ошибка.
Попробуйте повторить позже

Задача 13#42405

На вход программы поступает последовательность из $N$ натуральных чисел, все числа в последовательности различны.

Рассматриваются все возможные непустые уникальные подмножества, состоящие из элементов последовательности. Необходимо найти количество подмножеств, в которых количество четных чисел больше, чем количество нечетных.

Уникальным множеством считается то, что встречается один раз (то есть перестановки элементов внутри множества не делают его уникальным).

Пример входных данных:

Первая строка входного файла содержит число $N$ — общее количество чисел. Каждая из следующих $N$ строк содержит натуральные числа, не превышающих $10$ $000$ .

Вложения к задаче

Показать ответ и решение

f = open(’27.txt’)
n = int(f.readline())

nums = []
for i in range(n):
    nums.append(int(f.readline()))

ans = 0
for i in range(1, 2**n): # i = 0 нам не подходит, так как задает пустое подмножество
    t = i
    mn = []
    for j in range(n):
        if t % 2 == 1:
            mn.append(nums[j])
        t //= 2

    ch = len([x for x in mn if x % 2 == 0])
    if ch > len(mn) - ch:
        ans += 1

print(ans)

Ответ: 263950

Ошибка.
Попробуйте повторить позже

Задача 14#43241

На вход программы поступает последовательность из $N$ натуральных чисел, все числа в последовательности различны. Рассматриваются всевозможные непустые подмножества, состоящие из элементов последовательности. Необходимо найти количество подмножеств, в которых сумма элементов кратна $2$ .

Пример входных данных:

Первая строка входного файла содержит число $N$ – общее количество чисел в наборе. Каждая из следующих $N$ строк содержит натуральное число, не превышающее $10000$ .

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

$5$

$10$

$15$

$91$

$33$

Для указанных данных ответом будет являться $15$ .

Вложения к задаче

Показать ответ и решение

f = open(’27A.txt’)
n = int(f.readline())
k = 2
ans = [0]*k
for i in range(n):
    x = int(f.readline())
    ans_new = ans[:] #Аналог ans.copy()

    #Подсчет ответа для уже существующих подмножеств
    for j in range(k):
        ans_new[(j+x) % k] += ans[j]
    #Составление нового множества из одного числа x
    ans_new[x % k] += 1

    #Сохранение нового количества множеств
    ans = ans_new[:]

print(ans[0])

Ответ: 524287 633825300114114700748351602687

Ошибка.
Попробуйте повторить позже

Задача 15#43242

На вход программы поступает последовательность из $N$ натуральных чисел, все числа в последовательности различны. Рассматриваются всевозможные непустые подмножества, состоящие из элементов последовательности. Необходимо найти количество подмножеств, в которых сумма элементов кратна $5$ .

Пример входных данных:

Первая строка входного файла содержит число $N$ – общее количество чисел в наборе. Каждая из следующих $N$ строк содержит натуральное число, не превышающее $10000$ .

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

$5$

$10$

$15$

$91$

$33$

Для указанных данных ответом будет являться $7$ .

Вложения к задаче

Показать ответ и решение

f = open(’27A.txt’)
n = int(f.readline())
k = 5
ans = [0]*k
for i in range(n):
    x = int(f.readline())
    ans_new = ans[:] #Аналог ans.copy()

    #Подсчет ответа для уже существующих подмножеств
    for j in range(k):
        ans_new[(j+x) % k] += ans[j]
    #Составление нового множества из одного числа x
    ans_new[x % k] += 1

    #Сохранение нового количества множеств
    ans = ans_new[:]

print(ans[0])

Ответ: 209727 253530120045645880299340640255

Ошибка.
Попробуйте повторить позже

Задача 16#43243

На вход программы поступает последовательность из $N$ натуральных чисел, все числа в последовательности различны. Рассматриваются всевозможные непустые подмножества, состоящие из элементов последовательности. Необходимо найти количество подмножеств, сумма элементов которых кратна $9$ и кратна $2$ .

Пример входных данных:

Первая строка входного файла содержит число $N$ – общее количество чисел в наборе. Каждая из следующих $N$ строк содержит натуральное число, не превышающее $10000$ .

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

$5$

$18$

$1$

$2$

$3$

$36$

Для указанных данных ответом будет являться $3$ .

Вложения к задаче

Показать ответ и решение

f = open(’27A.txt’)
n = int(f.readline())
k = 9*2
ans = [0]*k
for i in range(n):
    x = int(f.readline())
    ans_new = ans[:] #Аналог ans.copy()

    #Подсчет ответа для уже существующих подмножеств
    for j in range(k):
        ans_new[(j+x) % k] += ans[j]
    #Составление нового множества из одного числа x
    ans_new[x % k] += 1

    #Сохранение нового количества множеств
    ans = ans_new[:]

print(ans[0])

Ответ: 58283 70425033346012744527579710463

Ошибка.
Попробуйте повторить позже

Задача 17#43244

На вход программы поступает последовательность из $N$ натуральных чисел, все числа в последовательности различны. Рассматриваются всевозможные непустые подмножества, состоящие из элементов последовательности. Необходимо найти количество подмножеств, в которых сумма элементов кратна $2$ и некратна $3$ .

Пример входных данных:

Первая строка входного файла содержит число $N$ – общее количество чисел в наборе. Каждая из следующих $N$ строк содержит натуральное число, не превышающее $10000$ .

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

$5$

$2$

$4$

$8$

$1$

$3$

Для указанных данных ответом будет являться $10$ .

Вложения к задаче

Показать ответ и решение

def sol(k, data):
    ans = [0] * k
    for i in range(len(data)):
        x = data[i]
        ans_new = ans[:]  # Аналог ans.copy()

        # Подсчет ответа для уже существующих подмножеств
        for i in range(k):
            ans_new[(i + x) % k] += ans[i]
        # Составление нового множества из одного числа x
        ans_new[x % k] += 1

        # Сохранение нового количества множеств
        ans = ans_new[:]

    return ans

f = open(’27A.txt’)
n = int(f.readline())
data = [int(f.readline()) for i in range(n)]
ans2 = sol(2, data)
ans6 = sol(6, data)
# Эквивалентные выводы
print(ans2[0] - ans6[0])
print(ans6[2] + ans6[4])

Ответ: 349440 422550200076076467165612474368

Ошибка.
Попробуйте повторить позже

Задача 18#43245

На вход программы поступает последовательность из $N$ натуральных чисел, все числа в последовательности различны. Рассматриваются всевозможные непустые подмножества, состоящие из элементов последовательности. Необходимо найти количество подмножеств, в которых произведение элементов кратно $4$ и некратно $8$ .

Пример входных данных:

Первая строка входного файла содержит число $N$ – общее количество чисел в наборе. Каждая из следующих $N$ строк содержит натуральные числа, не превышающих $10000$ .

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

$5$

$2$

$4$

$8$

$1$

$3$

Для указанных данных ответом будет являться $4$ .

Вложения к задаче

Показать ответ и решение

Решение 1

f = open(’27.txt’)
n = int(f.readline())
k = 8
ans = [0]*k
for i in range(n):
    x = int(f.readline())
    ans_new = ans[:] #Аналог ans.copy()

    #Подсчет ответа для уже существующих подмножеств
    for j in range(k):
        ans_new[(j*x) % k] += ans[j]
    #Составление нового множества из одного числа x
    ans_new[x % k] += 1

    #Сохранение нового количества множеств
    ans = ans_new[:]

print(ans[4])

Решение 2

def dels(k):
    a = []
    for i in range(1, int(k**0.5)+1):
        if k % i == 0:
            a.append(i)
            if i != k // i:
                a.append(k // i)

    return sorted(a)[::-1]

def sol(k, data):
    ans = [0] * (k + 1)
    dels_of_k = dels(k)

    for i in range(n):
        x = data[i]
        ans_new = ans[:]  # Аналог ans.copy()

        # Подсчет ответа для уже существующих подмножеств
        for j in dels_of_k:
            for q in dels_of_k:
                if j * x % q == 0:
                    ans_new[q] += ans[j]
                    break

        # Составление нового множества из одного числа x
        for j in dels_of_k:
            if x % j == 0:
                ans_new[j] += 1
                break

        # Сохранение нового количества множеств
        ans = ans_new[:]

    return ans[k]

f = open(’1.txt’)
n = int(f.readline())
                                                                                                     
                                                                                                     
data = [int(f.readline()) for i in range(n)]

print(sol(4, data) - sol(8, data))

Решение 3

def dels(k):
    a = []
    for i in range(1, int(k**0.5)+1):
        if k % i == 0:
            a.append(i)
            if i != k // i:
                a.append(k // i)

    return sorted(a)[::-1]

def sol(k, data):
    ans = [0] * (k + 1)
    dels_of_k = dels(k)

    for i in range(n):
        x = data[i]
        ans_new = ans[:]  # Аналог ans.copy()

        # Подсчет ответа для уже существующих подмножеств
        for j in dels_of_k:
            for q in dels_of_k:
                if j * x % q == 0:
                    ans_new[q] += ans[j]
                    break

        # Составление нового множества из одного числа x
        for j in dels_of_k:
            if x % j == 0:
                ans_new[j] += 1
                break

        # Сохранение нового количества множеств
        ans = ans_new[:]

    return ans[4]

f = open(’27A.txt’)
n = int(f.readline())
                                                                                                     
                                                                                                     
data = [int(f.readline()) for i in range(n)]

print(sol(8, data))

Ответ: 34816 2765210171205484544

Ошибка.
Попробуйте повторить позже

Задача 19#43482

В финал конкурса на получение грантов прошло три предприятия (назовем их $g1,g2,g3$ ). Заранее было посчитано и отображено в сводной таблице, сколько каждое предприятие сможет производить единиц товара за определенное количество единиц денежных средств.

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

Также фонд может выдать средства каждому предприятию лишь единожды. Например, для примера входных данных, он может выдать предприятию $g1$ $10$ денежных средств, но не $10$ и $20$ денежных средств одновременно, несмотря на то, что фонду хватит на это денег.

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

Имеется следующий набор данных:

В первой строке указано натуральное $N$ , $1 < N < 10000$ — количество строк сводной таблицы. Во второй строке указано натуральное число $S$ — общий размер денежных средств фонда для распределения грантов. В третьей строке указано натуральное число $k$ — дискретизация распределения средств грантом. Т.е. фонд может выдать количество денежных средств одному предприятию $0,k,2⋅k,...$ , но не большее, чем число $S$ . В последующих $N$ строках подается 4 числа — шаг дискретизации, единицы товара для $g1$ , единицы товара для $g2,$ единицы товара для $g3$ .

В ответе укажите два числа через пробел: искомое значение для файла A и для файла B.

Пример входных данных:

4

30

10

0 0 0 0

10 34 21 33

20 47 23 40

30 67 55 90

Эти данные можно представить в виде таблицы для большей наглядности:

|---|---|---|---| |-k-|g1-|g2-|g3-| |-0-|-0-|-0-|-0-| |10 |34 |21 |33 | |---|---|---|---| |20-|47-|23-|40-| -30--67--55--90-|

Например, если фонд выдаст $g1$ 10 ед. денежных средств, то $g1$ сможет произвести 34 единицы товара.

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

Выгоднее всего оказалось выдать $30$ ед. денежных средств предприятию $g3$ (а остальным не выдать ничего), т.к. в таком случае будет произведено наибольшее количество товара.

Вложения к задаче

Показать ответ и решение

Неэффективное решение

f = open(’27A.txt’)
n = int(f.readline())
s = int(f.readline())
k = int(f.readline())
g1, g2, g3 = [], [], []

for i in range(n):
    a = list(map(int, f.readline().split()))
    g1.append(a[1])
    g2.append(a[2])
    g3.append(a[3])

ans = 0
for i in range(n):
    for j in range(n):
        for w in range(n):
            if (i * k) + (j * k) + (w * k) <= s:
                if g1[i] + g2[j] + g3[w] > ans:
                    ans = g1[i] + g2[j] + g3[w]
print(ans)

Эффективное решение

f = open(’27B.txt’)
n = int(f.readline())
s = int(f.readline())
k = int(f.readline())
g1, g2, g3 = [], [], []

for i in range(n):
    a = list(map(int, f.readline().split()))
    g1.append(a[1])
    g2.append(a[2])
    g3.append(a[3])

g = [g1, g2, g3]
ans = [[0] * n for i in range(n)]
F = [[0] * n for i in range(len(g))]
F[0] = g[0].copy()

for k in range(1, 3):
    for i in range(n):
        for j in range(n):
            if i - j >= 0:
                ans[i][j] = g[k][j] + F[k - 1][i - j]

    for i in range(n):
        F[k][i] = max(ans[i])

print(max(F[2]))

Ответ: 101 555322

Ошибка.
Попробуйте повторить позже

Задача 20#45289

Дано число $N$ , зачем $N$ чисел. Нужно найти количество подмножеств, сумма элементов которых делится на $3$ .

Вложения к задаче