Пары/тройки чисел, выбрать из каждой пары/тройки число, кратность —Каталог задач по ЕГЭ - Информатика

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

#Для решения задачи будем искать макс. суммы с остатками по модулю 5
#и смотреть на их остатки по модулю 3 -
#чтобы сравнить с остатком суммы всех чисел.
#Если окажется, что эти остатки равны, то сумма нам не подходит
#(так как тогда (sum_all - current_sum) % 3 == 0, и надо смотреть на другую.
#Поэтому надо собрать суммы с разными парами остатков по модулю 5 и 3,
#а все такие суммы будут иметь разные остатки по модулю 3*5 = 15

modul = 15

def fun(a, a_new, x):
    for j in range(modul):
        k = (a[j] + x) % modul
        a_new[k] = max(a_new[k], a[j] + x)

a = [0] * modul
n = int(input())
sum_all = 0
for i in range(n):
    x, y = map(int, input().split())
    a_new = [-100000000] * modul
    fun(a, a_new, x)
    fun(a, a_new, y)
    sum_all += x + y
    a = a_new[:]
print(max([i for i in a if (i % 5 != 0 and i % 3 != sum_all % 3)]))

Ответ: 10676 32719168

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

Задача 5#40102

Имеется набор данных, состоящий из n пар натуральных чисел. Выбирается одно число из пары так, чтобы сумма всех таких чисел была максимальна и кратна 5 или 11, но не 5 и 11 одновременно. Определите, какую максимальную сумму, удовлетворяющую условиям задачи можно получить.

Формат входных данных

Набор данных состоит из пар натуральных чисел.

Первая строка входных данных содержит число n — количество строк, $1 ≤ n ≤ 106$ . Следующие n строк содержат пару натуральных чисел не превышающие 10000.

Формат выходных данных

Программа должна вывести целое число — максимальную сумму.

Пример:

$2$

$3$ $5$

$50$ $8$

Ответом для примера будет: $11$

Максимальная сумма, которую можно получить равна (5+50), но она кратна одновременно и 5, и 11, что недопустимо по условию задачи. Сумма 3+8 подходит по условиям задачи и является максимальной.

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

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

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

n = int(input())
ans = [0]*(5*11)

for i in range(n):
    a = [int(i) for i in input().split()]

    ans_new = [-1000000000]*55

    for k in range(len(a)):
        for j in range(55):
            ost = (ans[j] + a[k]) % 55
            if ans[j] + a[k] > ans_new[ost]:
                ans_new[ost] = ans[j] + a[k]

    ans = ans_new

print(max(max([i*(i % 5 == 0 and i % 11 != 0) for i in ans]), \
          max([i*(i % 5 != 0 and i % 11 == 0) for i in ans])
          ))

Ответ: 10650 32719148

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

Задача 6#40101

Имеется набор данных, состоящий из n пар натуральных чисел. Выбирается одно число из пары так, чтобы сумма всех таких чисел была максимальна и кратна 3 или 20. Определите, какую максимальную сумму, удовлетворяющую условиям задачи можно получить.

Формат входных данных

Набор данных состоит из пар натуральных чисел.

Первая строка входных данных содержит число n — количество строк, $1 ≤ n ≤ 106$ . Следующие n строк содержат пару натуральных чисел не превышающие 10000.

Формат выходных данных

Программа должна вывести целое число — максимальную сумму.

Пример:

$3$

$55$ $40$

$10$ $55$

$85$ $30$

Ответом для примера будет: $195$

Максимальная сумма, которую можно получить равна $(55+ 55+ 85)$ .

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

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

f = open(’27B.txt’)
n = int(f.readline())
ans = [0] * (3*20)

for i in range(n):
    a = [int(i) for i in f.readline().split()]

    ans_new = [-1000000000] * 60

    for k in range(len(a)):
        for j in range(60):
            ost = (ans[j] + a[k]) % 60
            if ans[j] + a[k] > ans_new[ost]:
                ans_new[ost] = ans[j] + a[k]

    ans = ans_new

print(max([i for i in ans if i % 3 == 0 or i % 20 == 0]))

Ответ: 10656 32719220

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

Задача 7#40100

Имеется набор данных, состоящий из n пар натуральных чисел. Выбирается одно число из пары так, чтобы сумма всех таких чисел была минимальна и кратна 7 или 10. Определите, какую минимальную сумму, удовлетворяющую условиям задачи можно получить.

Формат входных данных

Набор данных состоит из пар натуральных чисел.

Первая строка входных данных содержит число n — количество строк, $1 ≤ n ≤ 106$ . Следующие n строк содержат пару натуральных чисел не превышающие 10000.

Формат выходных данных

Программа должна вывести целое число — минимальную сумму.

Пример:

$3$

$55$ $40$

$10$ $55$

$85$ $30$

Ответом для примера будет: $80$

Минимальная сумма, которую можно получить равна $(40+ 10 +30)$ .

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

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

f = open(’27B.txt’)
n = int(f.readline())
ans = [0] * (7*10)

for i in range(n):
    a = [int(i) for i in f.readline().split()]

    ans_new = [1000000000000] * 70

    for k in range(len(a)):
        for j in range(70):
            ost = (ans[j] + a[k]) % 70
            if ans[j] + a[k] < ans_new[ost]:
                ans_new[ost] = ans[j] + a[k]

    ans = ans_new

print(min([i for i in ans if i % 10 == 0 or i % 7 == 0]))

Ответ: 5726 16765930

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

Задача 8#40099

Имеется набор данных, состоящий из n пар натуральных чисел. Выбирается одно число из пары так, чтобы сумма всех таких чисел была максимальна и кратна 3 или 6. Определите, какую максимальную сумму, удовлетворяющую условиям задачи можно получить.

Формат входных данных

Набор данных состоит из пар натуральных чисел.

Первая строка входных данных содержит число n — количество строк, $1 ≤ n ≤ 106$ . Следующие n строк содержат пару натуральных чисел не превышающие 10000.

Формат выходных данных

Программа должна вывести целое число — максимальную сумму.

Пример:

$3$

$55$ $40$

$10$ $55$

$85$ $30$

Ответом для примера будет: $195$

Максимальная сумма, которую можно получить равна $(55+ 55+ 85)$ .

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

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

f = open(’27B.txt’)
n = int(f.readline())
ans = [0] * 3

for i in range(n):
    a = [int(i) for i in f.readline().split()]

    ans_new = [-1000000000] * 3

    for k in range(len(a)):
        for j in range(3):
            ost = (ans[j] + a[k]) % 3
            if ans[j] + a[k] > ans_new[ost]:
                ans_new[ost] = ans[j] + a[k]

    ans = ans_new

print(ans[0])

Ответ: 10656 32719200

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

Задача 9#36735

Дано число n, затем n строк, в каждой по паре натуральных различных чисел. Из каждой пары берется одно число так, чтобы итоговая сумма всех таких чисел была максимальна и кратна 2.

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

3

17 20

21 11

1 2

Для таких входных данных значением искомое суммы будет число 42.

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

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

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

По сути, решение идентично любой подобной задаче на некратность (если кратность 2).

    f = open(’B5-8.txt’)
    n = int(f.readline())
    ans = 0
    diff = 10000000000
    for i in range(n):
        a = [int(i) for i in f.readline().split()]
        ans += max(a)
        if abs(a[0]-a[1]) % 2 == 1:
            diff = min(diff, abs(a[0]-a[1]))
    print(ans - diff * (ans % 2 == 1))

Ответ: 10756 32719168

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

Задача 10#36734

Дано число n, затем n строк, в каждой по паре натуральных различных чисел. Из каждой пары берется одно число так, чтобы итоговая сумма всех таких чисел была минимальна и кратна 3.

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

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

3

13 20

21 11

1 1

Для таких входных данных значением искомое суммы будет число 42.

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

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

Решение статикой.

Предположим, что после работы жадного алгоритма мы получили сумму, с остатком 2 при делении на 3.

Дифф — обозначение для какой-то разницы, от слова difference.

Итак, казалось бы все просто — можно добавить мин. дифф с остатком 1. Но на самом деле этого недостаточно. Ведь еще можно добавить к подобной сумме два мин. диффа с остатком 2. И ведь действительно: S(2) + diff(1) = (0) или S(2) + diff(2) + post_diff(2) = (0). (добавляем, так как уже посчитали минимальную сумму, теперь ее можно только увеличивать). Тоже самое и для суммы, с остатком 1.

Собственно, нужно хранить четыре разности: первые две с остатком 1, вторые с остатком 2.

    f = open(’A5-8.txt’)
    n = int(f.readline())
    ans = 0
    #индексы 0 и 1 отвечают за мин дифы с ост. 1
    #2 и 3 за мин дифы с ост. 2
    diff = [1000000]*4
    for i in range(n):
        a, b = map(int, f.readline().split())
        ans += min(a,b)
        tmp = abs(a-b)
        if tmp % 3 == 1:
            if tmp < diff[0]:
                diff[1], diff[0] = diff[0], tmp
            else:
                diff[1] = min(diff[1], tmp)
        if tmp % 3 == 2:
            if tmp < diff[2]:
                diff[3], diff[2] = diff[2], tmp
            else:
                diff[3] = min(diff[3], tmp)

    if ans % 3 == 0:
        print(ans)
    elif ans % 3 == 1:
        print(ans + min(diff[2], diff[0]+diff[1]))
    else:
        print(ans + min(diff[0], diff[2] + diff[3]))

Ответ: 5634 16765950

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

Задача 11#36732

Дано число $n$ , затем $n$ строк, в каждой по паре натуральных различных чисел. Из каждой пары берется одно число так, чтобы итоговая сумма всех таких чисел была минимальна и не кратна $10$ .

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

$3$

$10 20$

$21 9$

$1 1$

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

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

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

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

f = open(’A5-8.txt’)
n = int(f.readline())
ans = 0
diff = 10000000000
for i in range(n):
    a, b = map(int, f.readline().split())
    ans += min(a,b)
    if abs(a-b) % 10 != 0:
         diff = min(diff, abs(a-b))
print(ans + diff * (ans % 10 == 0))

Ответ: 5634 16766888

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

Задача 12#36731

Дано число n, затем n строк, в каждой по паре натуральных различных чисел. Из каждой пары берется одно число так, чтобы итоговая сумма всех таких чисел была максимальна и не кратна 7.

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

3

10 20

21 11

1 1

Для таких входных данных значением искомое суммы будет число 32.

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

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

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

    f = open(’B5-8.txt’)
    n = int(f.readline())
    ans = 0
    diff = 10000000000
    for i in range(n):
        a, b = map(int, f.readline().split())
        ans += max(a,b)
        if abs(a-b) % 7 != 0:
            diff = min(diff, abs(a-b))
    print(ans - diff * (ans % 7 == 0))

Ответ: 10756 32719168

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

Задача 13#36730

Набор данных состоит из троек натуральных чисел. Необходимо распределить все числа на три группы, при этом в каждую группу должно попасть ровно одно число из каждой исходной тройки. В первой группе должна быть максимальная сумма всех чисел, во второй –– сумма «средних» по значению в тройке чисел, в третьей — минимальная сумма всех чисел. Выведите все полученные три суммы на экран.

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

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

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

3

7 15 17

11 25 5

4 12 16

Для указанных данных искомые суммы равны 58 38 16, они соответствует такому распределению чисел по группам: (17, 25, 16), (7, 5, 4), (15, 11, 12).

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

A4.txt

B4.txt

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

        f = open(’A4.txt’)
        n = int(f.readline())
        maxim, average, minim = 0, 0, 0
        for i in range(n):
            a, b, c = [int(x) for x in f.readline().split()]
            maxim += max(a, b, c)
            minim += min(a, b, c)
            average += a + b + c - min(a, b, c) - max(a, b, c)
        print(maxim, average, minim)

Ответ: 16204 11412 5248 37317213 25001629 12700807

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

Задача 14#36729

Имеется набор данных, состоящий из пар натуральных чисел. Каждая пара чисел представляет собой средние баллы за ЕГЭ мальчиков (1 число) и девочек (2 число) из N-ой городской школы, соответственно 100 баллов максимум. Необходимо определить, в скольких школах количество баллов у мальчиков или у девочек больше, чем 60, и при этом есть хотя бы какая-то группа, балл которой не кратен 7.

Даны два входных файла (файл A и файл B), каждый из которых содержит в первой строке количество пар $N (1 ≤ N ≤ 100000).$ Каждая из следующих $N$ строк содержит два натуральных числа, не превышающих $100$ .

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

5

100 50

30 49

88 79

90 90

79 48

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

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

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

A1-3.txt

B1-3.txt

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

    f = open(’B1-3.txt’)
    n = int(f.readline())
    ans = 0
    for i in range(n):
        a, b = map(int, f.readline().split())
        if (a > 60 or b > 60) and (a % 7 !=0 or b % 7 != 0):
            ans += 1
    print(ans)

Ответ: 14 2772

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

Задача 15#36728

Имеется набор данных, состоящий из пар натуральных чисел. Каждая пара чисел представляет собой баллы за ЕГЭ по информатике (1 число) и математике (2 число), соответственно 100 баллов максимум. Необходимо составить рейтинг 3 лучших учеников исходя из их суммы баллов. Программа должна напечатать три числа — 3 суммы баллов учеников по убыванию, начиная с максимальной.

Даны два входных файла (файл A и файл B), каждый из которых содержит в первой строке количество пар $N (1 ≤ N ≤ 100000).$ Каждая из следующих $N$ строк содержит два натуральных числа, не превышающих $100$ .

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

5

100 50

30 49

88 79

90 90

79 48

Для указанных входных данных выходными значениями должны быть 180 167 150.

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

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

A1-3.txt

B1-3.txt

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

    f = open(’B1-3.txt’)
    n = int(f.readline())
    ans = []
    for i in range(n):
        a, b = map(int, f.readline().split())
        ans.append(a+b)
    ans.sort()
    print(ans[len(ans)-1],ans[len(ans)-2],ans[len(ans)-3])

Ответ: 196 196 160 198 198 198

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

Задача 16#36727

Имеется набор данных, состоящий из пар натуральных чисел. Каждая пара чисел представляет собой баллы за ЕГЭ по информатике (1 число) и физике (2 число), соответственно 100 баллов максимум. Необходимо выбрать из каждой пары число такое, что если баллы по физике меньше 60, то взять из пары баллы по информатике, иначе взять баллы по физике. Необходимо найти сумму этих баллов. Программа должна напечатать одно число — сумму, соответствующую условиям задачи.

Даны два входных файла (файл A и файл B), каждый из которых содержит в первой строке количество пар $N (1 ≤ N ≤ 100000).$ Каждая из следующих $N$ строк содержит два натуральных числа, не превышающих $100$ .

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

5

100 50

30 49

88 79

90 90

79 48

Для указанных входных данных значением искомой суммы должно быть число 378.

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

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

A1-3.txt

B1-3.txt

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

    f = open(’B1-3.txt’)
    n = int(f.readline())
    ans = 0
    for i in range(n):
        a, b = map(int, f.readline().split())
        if b < 60:
            ans += a
        else:
            ans += b
    print(ans)

Ответ: 1432 300032

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

Задача 17#32960

Максим Сергеевич любит большие числа. Сегодня ему дали задачу - из каждой группы чисел нужно выбрать ровно 2 и найти их НОК. После этого находится сумма всех таких НОК. Также известно, что МС любит числа 5 и 7, но не оба одновременно. МС с лёгкостью решил бы эту задачу, но после щелчка ему нужен отдых, и он отправился путешествовать по маршруту Москва-Ярославль-Питер-Ярославль-Москва-Сочи.
Помогите МС. Найдите максимальную сумму НОК из каждой группы чисел, чтобы она делилась либо на 7, либо на 5, но не на оба числа одновременно.
Входные данные:
Даны два входных файла, каждый из которых содержит в первой строке количество чисел $N$ ( $2 ≤ N ≤ 100000$ ). В каждой из следующих $N$ строк файлов записан сначала размер группы $K$ ( $K ≤ 10$ ), а затем $K$ натуральных чисел, не превышающих 500.
Пример входного файла:
4
2 8 6
3 2 7 8
2 6 5
4 7 3 8 6
Примечание:
Для указанных входных данных значения НОК для первой группы — 24; для второй группы — 14, 8, 56; для третьей группы — 30, для четвёртой группы — 6, 21, 24, 24, 42, 56. Значением искомой суммы должно быть число 110 (24+14+30+42). В ответе укажите два числа: сначала искомое значение для файла А, затем для файла B.

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

27-A.txt

27-B.txt

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

Решение №1.

def evklid(a, b): # поиск НОДа
    if b > a:
        a, b = b, a
    if a != 0 and b != 0:
        return evklid(a % b, b)
    return a + b # одно из чисел = 0

def nok(a, b): # НОК(a, b) = a * b // НОД(a, b)
    return a * b // evklid(a, b)

f = open(’test.txt’)
n = int(f.readline())
ans = [-10000000] * 35
ans[0] = 0
for i in range(n):
    a = [int(x) for x in f.readline().split()] # a[0] - количество элементов
    ans_new = [-10000000] * 35
    for q in range(1, len(a)):
        for k in range(q + 1, len(a)):
            NOK = nok(a[q], a[k])
            for j in range(35):
                ost = (ans[j] + NOK) % 35
                if ans[j] + NOK > ans_new[ost]:
                    ans_new[ost] = ans[j] + NOK
    ans = ans_new.copy()
maxim = -1
for i in ans:
    if (i % 5 == 0 or i % 7 == 0) and i % 35 != 0:
        maxim = max(i, maxim)
print(maxim)

Решение №2.

from math import gcd

def solve(file):
    f = open(file)
    n = int(f.readline())
    curr = [-1] * 35
    curr[0] = 0
    for q in range(n):
        a = list(map(int, f.readline().split()))
        cnt = a[0]
        del a[0]
        temp = [-1] * 35
        for i in range(cnt - 1):
            for j in range(i + 1, cnt):
                x, y = a[i], a[j]
                nod = gcd(x, y)
                nok = x * y // nod
                for k in range(35):
                    if curr[k] == -1:
                        continue
                    ost = (curr[k] + nok) % 35
                    temp[ost] = max(temp[ost], curr[k] + nok)
        curr = temp.copy()

    ans = -1

    for i in range(35):
        if (i % 7 == 0 or i % 5 == 0) and i % 35 != 0:
            ans = max(ans, curr[i])

    print(ans)
    f.close()

solve("27-A.txt")
solve("27-B.txt")

Ответ: 2257416 1254402115

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

Задача 18#30001

Имеется набор данных, состоящий из пар натуральных чисел. Необходимо выбрать из каждой пары ровно одно число так, чтобы шестнадцатеричная запись суммы всех выбранных чисел не оканчивалась на A, B и C и при этом была максимально возможной. Если искомую сумму получить нельзя, то напечатайте 0. Программа должна напечатать одно число – максимально возможную сумму, соответствующую условиям задачи, записанную в десятичной системе счисления.

Даны два входных файла (файл A и файл B), каждый из которых содержит в первой строке количество пар N (1 $≤ N ≤$ 100000). Каждая из следующих N строк содержит два натуральных числа, не превышающих 10 000.

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

5

3 8

35 29

13 31

4 4

44 44

Для таких входных данных значением искомой суммы будет число $117$

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

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

27PA.txt

27PB.txt

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

f = open(’27.txt’)
n = int(f.readline())
ans = [0] * 16
for i in range(n):
    a = [int(i) for i in f.readline().split()]
    ans_new = [-1000000000] * 16
    for k in range(len(a)):
        for j in range(16):
            ost = (ans[j] + a[k]) % 16
            if ans[j] + a[k] > ans_new[ost]:
                ans_new[ost] = ans[j] + a[k]
    ans = ans_new.copy()
maxim = 0
for i in range(16):
    if not(i in [10, 11, 12]):
        maxim = max(maxim, ans[i])
print(maxim)

Ответ: 10756 32719168

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

Задача 19#30000

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

Даны два входных файла (файл A и файл B), каждый из которых содержит в первой строке количество пар $N$ (1 $≤ N ≤$ 100000). Каждая из следующих N строк содержит два натуральных числа, не превышающих $10000$ .

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

6

1 3

5 12

6 9

5 4

3 3

5 1

Для таких входных данных значением искомой суммы будет число $37$ .

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

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