06 Макс/мин, кол-во пар, произведение кратно/не кратно - Каталог заданий по ЕГЭ

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

Задача 41#63849Максимум баллов за задание: 2

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

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

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

27A_3.txt

27B_3.txt

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

Примечание. Для файла B необходимо заменить первую строку кода.

f = open("27A_3.txt")
s = f.readlines()
n = int(s[0])
k = 0
k_0 = 0
k_74 = 0
k_2 = 0
k_37 = 0
for i in range(1, n + 1):
    s[i] = int(s[i])
    if s[i] % 74 == 0:
        k_74 += 1
    elif s[i] % 37 == 0:
        k_37 += 1
    elif s[i] % 2 == 0:
        k_2 += 1
    else:
        k_0 += 1
k = k_74 * k_0 + k_37 * k_2 + k_74 * k_37 + k_74 * k_2 + (k_74 * (k_74 - 1)) // 2
print(k)

Ответ: 19 1930471

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

Задача 42#63854Максимум баллов за задание: 2

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

В ответе укажите два числа: значение для файла А, затем, через пробел, для файла Б. Так же можно указать ответ ТОЛЬКО для файла А.

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

27A_8.txt

27B_8.txt

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

Примечание. Для файла B необходимо заменить первую строку кода.

f = open("27A_8.txt")
n = int(f.readline())
k=0
k19=0
for i in range(n):
    x=int(f.readline())
    if x%19==0:
        k19+=1
    else:
        k+=1
print(k19*(k19-1)//2+k19*k)

Варианты правильных ответов:

390
390 5235009

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

Задача 43#73021Максимум баллов за задание: 2

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

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

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

7

9

5

6

12

5

13

3

Для указанных чисел максимальное произведение двух элементов, кратное 6, 156.

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

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

2_A.txt

2_B.txt

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

#переборный алгоритм:
f = open(’2_A.txt’)
n = int(f.readline())
a = []
for i in range(n):
    a.append(int(f.readline()))

maxi = 0
for i in range(0,len(a)-1):
    for j in range(i+1,len(a)):
        if (a[i]*a[j]) % 6 == 0:
            maxi = max(maxi, a[i]*a[j])
print(maxi)

#эффективный алгоритм:
f = open(’2_B.txt’)
n = int(f.readline())

kr6 = 0
kr2 = 0
kr3 = 0
nkr = 0
ans = 0
for i in range(n):
    a = int(f.readline())
    if a % 6 == 0:
        ans = max(a*kr6, a*kr3, a*kr2, a*nkr, ans)
        kr6 = max(kr6, a)
    elif a % 3 == 0:
        ans = max(a*kr2, ans)
        kr3 = max(kr3, a)
    elif a % 2 == 0:
        ans = max(a*kr3, ans)
        kr2 = max(kr2, a)
    else:
        ans = max(a*kr6, ans)
        nkr = max(nkr, a)
print(ans)

Ответ: 776136 999000

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

Задача 44#73023Максимум баллов за задание: 2

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

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

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

7

9

5

6

13

5

15

3

Для указанных чисел максимальное произведение двух элементов, не кратное 15, равно 117.

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

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

4_A.txt

4_B.txt

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

#переборный алгоритм:
f = open(’4_A.txt’)
n = int(f.readline())
a = []
for i in range(n):
    a.append(int(f.readline()))

maxi = 0
for i in range(0,len(a)-1):
    for j in range(i+1,len(a)):
        if (a[i]*a[j]) % 15 != 0:
            maxi = max(maxi, a[i]*a[j])
print(maxi

#эффективный алгоритм:
f = open(’4_B.txt’)
n = int(f.readline())

del3 = [0, 0]
del5 = [0, 0]
notdel35 = [0, 0]
maxi = []
for i in range(n):
    a = int(f.readline())
    if a % 15 != 0:
        if a % 3 == 0 and a % 5 != 0:
            if a >= del3[1]:
                del3[0] = del3[1]
                del3[1] = a
            elif a >= del3[0]:
                del3[0] = a
        elif a % 3 != 0 and a % 5 == 0:
            if a >= del5[1]:
                del5[0] = del5[1]
                del5[1] = a
            elif a >= del5[0]:
                del5[0] = a
        else:
            if a >= notdel35[1]:
                notdel35[0] = notdel35[1]
                notdel35[1] = a
            elif a >= notdel35[0]:
                notdel35[0] = a

maxi.append(notdel35[0]*notdel35[1])
maxi.append(del3[0]*del3[1])
maxi.append(del5[0]*del5[1])
maxi.append(notdel35[1]*del3[1])
maxi.append(notdel35[1]*del5[1])
print(max(maxi))

Ответ: 9900091000000

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

Задача 45#73354Максимум баллов за задание: 2

Имеется набор данных, состоящий из положительных целых чисел. Необходимо определить количество пар элементов ( $ai$ , $aj$ ) этого набора, в которых 1 $≤$ i < j $≤$ N и произведение элементов кратно 14.

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

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

7

5

6

12

5

14

2

Для указанных входных данных количество подходящих пар должно быть равно 9.

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

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

1_A.txt

1_B.txt

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

#переборный алгоритм:
f = open(’1_A.txt’)
n = int(f.readline())

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

for i in range(0,len(a) - 1):
    for j in range(i+1,len(a)):
        if (a[i]*a[j]) % 14 == 0:
            counter += 1
print(counter)

#эффективный алгоритм:
f = open(’1_B.txt’)
n = int(f.readline())

counter = 0
prop = [0] * 4
a = int(f.readline())
for i in range(n - 1):

    prop[0] += 1
    prop[1] += int(a % 2 == 0)
    prop[2] += int(a % 7 == 0)
    prop[3] += int(a % 14 == 0)

    y = int(f.readline())
    a = y
    if y % 14 == 0:
        counter += prop[0]
    elif y % 7 == 0:
        counter += prop[1]
    elif y % 2 == 0:
        counter += prop[2]
    else:
        counter += prop[3]
print(counter)

Ответ: 28 357961420

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

Задача 46#73355Максимум баллов за задание: 2

Имеется набор данных, состоящий из положительных целых чисел. Необходимо определить количество пар элементов ( $ai$ , $aj$ ) этого набора, в которых 1 $≤$ i < j $≤$ N и произведение элементов кратно 16.

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

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

7

4

5

6

16

8

3

2

Для указанных входных данных количество подходящих пар должно быть равно 9.

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

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

2_A.txt

2_B.txt

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

#переборный алгоритм:
f = open(’2_A.txt’)
n = int(f.readline())

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

for i in range(0,len(a) - 1):
    for j in range(i+1,len(a)):
        if (a[i]*a[j]) % 16 == 0:
            counter += 1
print(counter)

#эффективный алгоритм:
f = open(’2_B.txt’)
n = int(f.readline())

counter = 0
prop = [0] * 5
a = int(f.readline())
for i in range(n - 1):

    prop[0] += 1
    prop[1] += int(a % 2 == 0)
    prop[2] += int(a % 4 == 0)
    prop[3] += int(a % 8 == 0)
    prop[4] += int(a % 16 == 0)

    y = int(f.readline())
    a = y
    if y % 16 == 0:
        counter += prop[0]
    elif y % 8 == 0:
        counter += prop[1]
    elif y % 4 == 0:
        counter += prop[2]
    elif y % 2 == 0:
        counter += prop[3]
    else:
        counter += prop[4]

print(counter)

Ответ: 57 336501432

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

Задача 47#73360Максимум баллов за задание: 2

Имеется набор данных, состоящий из положительных целых чисел. Необходимо определить количество пар элементов ( $ai$ , $aj$ ) этого набора, в которых 1 $≤$ i < j $≤$ N и произведение элементов не кратно 6.

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

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

6

9

7

4

2

8

3

Для указанных входных данных количество подходящих пар должно быть равно 9.

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

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

7_A.txt

7_B.txt

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

#переборный алгоритм:
f = open(’7_A.txt’)
n = int(f.readline())

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

for i in range(0,len(a) - 1):
    for j in range(i+1,len(a)):
        if (a[i]*a[j]) % 6 != 0:
            counter += 1
print(counter)

#эффективный алгоритм:
f = open(’7_B.txt’)
n = int(f.readline())

counter = 0
prop = [0] * 3
a = int(f.readline())
for i in range(n - 1):

    prop[0] += int(a % 2 != 0 and a % 3 != 0)
    prop[1] += int(a % 2 == 0 and a % 3 != 0)
    prop[2] += int(a % 2 != 0 and a % 3 == 0)

    y = int(f.readline())
    a = y
    if y % 2 != 0 and y % 3 != 0:
        counter += prop[0]
        counter += prop[1]
        counter += prop[2]
    elif y % 2 != 0 and y % 3 == 0:
        counter += prop[2]
        counter += prop[0]
    elif y % 2 == 0 and y % 3 != 0:
        counter += prop[1]
        counter += prop[0]

print(counter)

Ответ: 861053513084

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

Задача 48#73361Максимум баллов за задание: 2

Имеется набор данных, состоящий из положительных целых чисел. Необходимо определить количество пар элементов ( $ai$ , $aj$ ) этого набора, в которых 1 $≤$ i < j $≤$ N и произведение элементов не кратно 22.

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

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

6

9

11

4

2

8

3

Для указанных входных данных количество подходящих пар должно быть равно 12.

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

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

8_A.txt

8_B.txt

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

#переборный алгоритм:
f = open(’8_A.txt’)
n = int(f.readline())

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

for i in range(0,len(a) - 1):
    for j in range(i+1,len(a)):
        if (a[i]*a[j]) % 22 != 0:
            counter += 1
print(counter)

#эффективный алгоритм:
f = open(’8_B.txt’)
n = int(f.readline())

counter = 0
prop = [0] * 3
a = int(f.readline())
for i in range(n - 1):

    prop[0] += int(a % 2 != 0 and a % 11 != 0)
    prop[1] += int(a % 2 == 0 and a % 11 != 0)
    prop[2] += int(a % 2 != 0 and a % 11 == 0)

    y = int(f.readline())
    a = y
    if y % 2 != 0 and y % 11 != 0:
        counter += prop[0]
        counter += prop[1]
        counter += prop[2]
    elif y % 2 != 0 and y % 11 == 0:
        counter += prop[2]
        counter += prop[0]
    elif y % 2 == 0 and y % 11 != 0:
        counter += prop[1]
        counter += prop[0]

print(counter)

Ответ: 15343569328

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

Задача 49#73363Максимум баллов за задание: 2

Имеется набор данных, состоящий из положительных целых чисел. Необходимо определить количество пар элементов ( $ai$ , $aj$ ) этого набора, в которых 1 $≤$ i < j $≤$ N и произведение элементов кратно 32.

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

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

7

19

20

11

10

9

22

12

Для указанных входных данных количество подходящих пар должно быть равно 0.

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

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

10_A.txt

10_B.txt

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

#переборный алгоритм:
f = open(’10_A.txt’)
n = int(f.readline())

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

for i in range(0,len(a) - 1):
    for j in range(i+4,len(a)):
        if (a[i]*a[j]) % 32 == 0:
            counter += 1
print(counter)

#эффективный алгоритм:
f = open(’10_B.txt’)
n = int(f.readline())
counter = 0
prop = [0] * 6
a = int(f.readline())
for i in range(n - 1):

    prop[0] += 1
    prop[1] += int(a % 2 == 0)
    prop[2] += int(a % 4 == 0)
    prop[3] += int(a % 8 == 0)
    prop[4] += int(a % 16 == 0)
    prop[5] += int(a % 32 == 0)

    y = int(f.readline())
    a = y

    if y % 32 == 0:
        counter += prop[0]
    elif y % 16 == 0:
        counter += prop[1]
    elif y % 8 == 0:
        counter += prop[2]
    elif y % 4 == 0:
        counter += prop[3]
    elif y % 2 == 0:
        counter += prop[4]
    else:
        counter += prop[5]

print(counter)

Ответ: 35 136778776

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

Задача 50#74968Максимум баллов за задание: 2

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

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

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

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

1B.txt

1A.txt

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

Идея статического решения:

Произведение пары кратна 2 в том случае, когда произведение остатков пары чисел кратна 2. Идея заключается в том, что мы сначала совершим проход по файлу, в котором определим максимальные числа под каждым остатком. Затем, записав выражение мы определим максимальное произведение кратное 2.

Идея динамического решения:

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

#Переборный алгоритм
f = open(’1_A.txt’) # открытие файла
n = int(f.readline()) #считывание первого числа - количество чисел в файле
a = [] # список, в котором будут записаны все числа файла
for i in range(n): # проход по файлу
    a.append(int(f.readline())) # добавление в список числа

maxi = 0 # максимальное произведение пары
for i in range(0,len(a)-1): # проход для первого числа пары
    for j in range(i+1,len(a)): # проход для первого числа пары
        if (a[i]*a[j]) % 2 == 0: # проверка по условию
            maxi = max(maxi, a[i]*a[j]) # обновление максимального произведения
print(maxi) # вывод ответа

#Статическое решение
file = open(’1B__2rcsr.txt’) #открытие файла
n = int(file.readline()) #считывание первого числа - количество чисел в файле
div = 2 # наш делитель
#четное произведение можно получить помножив два чётных числа или одно чётное числа на нечётное
mx_0 = [0,0] #список, в котором будут храниться два максимальных чётных числа, где mx_0[0] - максимальное чётное, а mx_0[1] - предмаксимальное
mx_1 = 0 # максимальное нечётное число
mx_prod = 0 # максимальное произведение пары
for i in range(n): # проход по файлу
    x = int(file.readline()) # cчитываем текущее число
    if x % 2 == 0: # если текущее число - чётное
        if x > mx_0[0]: # если текущее число больше максимального
            mx_0[1] = mx_0[0] #в ячейку предмаксимального записываем максимальное
            mx_0[0] = x #вместо максимального записываем текущее число
        elif x > mx_0[1]: # если текущее число больше только предмаксимального
            mx_0[1] = x #вместо предмаксимального записываем текущее число
    else: # если текущее число - нечётное
        mx_1 = max(mx_1,x) #обновляем максимальное нечётное число
mx_prod = max(mx_1*mx_0[0],mx_0[0]*mx_0[1]) #записываем максимальное произведение из произведений двух чётных чисел или одного чётного и одного нечётного
print(mx_prod) # вывод ответа

#Динамическое решение
file = open(’1B__2rcsr.txt’) #открытие файла
n = int(file.readline()) #считывание первого числа - количество чисел в файле
div = 2 # наш делитель
mx = [0]*div  #список, в котором будет храниться максимальное число под каждым остатком при делении на 2
mx_prod = 0 #максимальное произведение пары
for i in range(n): # проход по всему файлу
    x = int(file.readline()) # считываем текущее число
    for d in range(div): # проход по всевозможным остаткам при делении на 2
        if x * d % div == 0: #если текущее число кратно 2 с определенным остатком
            mx_prod = max(mx_prod,x*mx[d]) # то обновляем максимальное произведение
    mx[x % div] = max(mx[x % div],x) # обновляем максимальное число под определенным остатком, сравнивая текущее число с тем, что было записано в ячейке ранее.
print(mx_prod) # вывод ответа.

Ответ: 886788 997002

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

Задача 51#74969Максимум баллов за задание: 2

Имеется набор данных, состоящий из положительных целых чисел. Необходимо определить количество пар элементов ( $ai$ , $aj$ ) этого набора, в которых 1 $≤$ i < j $≤$ N и произведение элементов кратно 10.

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

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

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

2B.txt

2A.txt

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

#переборный алгоритм:
f = open(’2_A.txt’)
n = int(f.readline())

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

for i in range(0,len(a) - 1):
    for j in range(i+1,len(a)):
        if (a[i]*a[j]) % 10 == 0:
            counter += 1
print(counter)

#эффективный алгоритм:
f = open(’2_B.txt’)
n = int(f.readline())

counter = 0
prop = [0] * 4
a = int(f.readline())
for i in range(n - 1):

    prop[0] += 1
    prop[1] += int(a % 2 == 0)
    prop[2] += int(a % 5 == 0)
    prop[3] += int(a % 10 == 0)

    y = int(f.readline())
    a = y
    if y % 10 == 0:
        counter += prop[0]
    elif y % 5 == 0:
        counter += prop[1]
    elif y % 2 == 0:
        counter += prop[2]
    else:
        counter += prop[3]
print(counter)

Ответ: 49 13372430