27 - Обработка потока данных
Источники:
сайт Полякова (https://kpolyakov.spb.ru/)
демонстрационная версия станции КЕГЭ (https://kompege.ru/)
Embedded Files
1) (№ 2681) Имеется набор данных, состоящий из пар положительных целых чисел. Необходимо выбрать из каждой пары ровно одно число так, чтобы сумма всех выбранных чисел оканчивалась на 8 и при этом была максимально возможной. Гарантируется, что искомую сумму получить можно. Программа должна напечатать одно число – максимально возможную сумму, соответствующую условиям задачи.
Входные данные. Даны два входных файла (файл A и файл B), каждый из которых содержит в первой строке количество пар N (1 ≤ N ≤ 100000). Каждая из следующих N строк содержит два натуральных числа, не превышающих 10 000.
Пример входного файла:
6
1 3
5 12
6 9
5 4
3 3
5 1
Для указанных входных данных значением искомой суммы должно быть число 28.
В ответе укажите два числа: сначала значение искомой суммы для файла А, затем для файла B.
Решение
Вариант 1
f=open('a.txt','r')
n=int(f.readline())
a=[0]*10
x,y=map(int, f.readline().split())
a[x%10]=x
a[y%10]=max(a[y%10],y)
for i in range(n-1):
x,y=map(int, f.readline().split())
b=[0]*10
for p in range(2):
for k in range(10):
if a[k]>0:
b[(a[k]+x)%10]=max(b[(a[k]+x)%10],a[k]+x)
x=y
a=b[:]
print(a[8])
Вариант 2
f=open('B.txt')
n=int(f.readline())
a=[0]*10
x,y=map(int,f.readline().split())
a[x%10]=x
a[y%10]=max(a[y%10],y)
for i in range(1,n):
b=[0]*10
x,y=map(int,f.readline().split())
for p in range(10):
if a[p]>0:
b[(a[p]+x)%10]=max(b[(a[p]+x)%10],a[p]+x)
b[(a[p]+y)%10]=max(b[(a[p]+y)%10],a[p]+y)
a=b[:]
print(a[8])
Ответы:
A - 13608
B - 40724928
2) (№ 2627) Имеется набор данных, состоящий из троек положительных целых чисел. Необходимо выбрать из каждой тройки ровно одно число так, чтобы сумма всех выбранных чисел делилась на 8 и при этом была максимально возможной. Гарантируется, что искомую сумму получить можно. Программа должна напечатать одно число – максимально возможную сумму, соответствующую условиям задачи.
Входные данные. Даны два входных файла (файл A и файл B), каждый из которых содержит в первой строке количество троек N (1 ≤ N ≤ 100000). Каждая из следующих N строк содержит три натуральных числа, не превышающих 10 000.
Пример входного файла:
6
8 3 4
4 8 12
9 5 6
2 8 3
12 3 5
1 4 12
Для указанных входных данных значением искомой суммы должно быть число 56.
В ответе укажите два числа: сначала искомое значение для файла А, затем для файла B.
Решение
f=open('a.txt','r')
s=0
a=[0]*8
n=int(f.readline())
for i in range(n):
b=[0]*8
x,y,z=map(int, f.readline().split())
for k in range(3):
for l in range(8):
r=a[l]+x
if r>b[r%8]: b[r%8]=r
if k==0: x=y
else: x=z
a=b[:]
print(a[0])
Ответы:
A - 14432
B - 45978688
3) (№ 2693 Д.Ф. Муфаззалов) Имеется набор данных, состоящий из троек положительных целых чисел. Необходимо выбрать из каждой тройки два числа так, чтобы сумма всех выбранных чисел делилась на 4 и при этом была максимально возможной. Гарантируется, что искомую сумму получить можно. Программа должна напечатать одно число – максимально возможную сумму, соответствующую условиям задачи.
Входные данные: Даны два входных файла: файл A (a1.txt) и файл B (b1.txt), каждый из которых содержит в первой строке количество троек N (1 ≤ N ≤ 100000). Каждая из следующих N строк содержит три натуральных числа, не превышающих 10 000.
Пример входного файла:
6
8 3 4
4 8 12
9 5 6
2 8 3
12 3 5
1 4 12
Для указанных входных данных значением искомой суммы должно быть число 88.
В ответе укажите два числа: сначала значение искомой суммы для файла А, затем для файла B.
Предупреждение: для обработки файла B не следует использовать переборный алгоритм, вычисляющий сумму для всех возможных вариантов, поскольку написанная по такому алгоритму программа будет выполняться слишком долго.
Решение
f=open('a1.txt','r')
n=int(f.readline())
a=[0]*4
x,y,z=map(int,f.readline().split())
a[(x+y)%4]=x+y
a[(y+z)%4]=max(a[(y+z)%4],y+z)
a[(x+z)%4]=max(a[(x+z)%4],x+z)
for i in range(1,n):
x,y,z=map(int,f.readline().split())
b=[0]*4
for k in range(4):
if a[k]>0:
b[(a[k]+x+y)%4]=max(b[(a[k]+x+y)%4],a[k]+x+y)
b[(a[k]+y+z)%4]=max(b[(a[k]+y+z)%4],a[k]+y+z)
b[(a[k]+x+z)%4]=max(b[(a[k]+x+z)%4],a[k]+x+z)
a=b[:]
print(a[0])
Ответ:
27-A - 18380
27-B - 58701760
4) (№ 3825 А. Кабанов) В файле записана последовательность натуральных чисел. Гарантируется, что все числа различны. Рассматриваются всевозможные группы чисел, состоящие из любого количества элементов последовательности. Необходимо найти наибольшую сумму такой группы, заканчивающуюся на 50. Программа должна вывести эту сумму.
Входные данные. Даны два входных файла (файл A2 и файл B2), каждый из которых содержит в первой строке количество чисел N (1 ≤ N ≤ 100000). Каждая из следующих N строк содержит одно натуральное число, не превышающее 108.
Пример входного файла:
6
21
29
12
72
14
28
Для указанных данных можно выбрать следующие группы: {21, 29}; {21, 29, 72, 28}. Суммы элементов данных групп равны 50 и 150. Программа должна вывести наибольшую из этих сумм – 150.
В ответе укажите два числа: сначала искомое значение для файла А, затем для файла B.
Решение
f=open('a2.txt','r')
n=int(f.readline())
a=[0]*100
b=[0]*100
for i in range(n):
x=int(f.readline())
b[x%100]=x
for p in range(100):
if a[p]>0:
pb=(a[p]+x)%100
b[pb]=max(b[pb],a[p]+x)
a=b[:]
print(b[50])
Ответ:
A - 850
B - 5036250
5) (№ 2664) Имеется набор данных, состоящий из пар положительных целых чисел. Необходимо выбрать из каждой пары ровно одно число так, чтобы сумма всех выбранных чисел делилась на 5 и при этом была максимально возможной. Гарантируется, что искомую сумму получить можно. Программа должна напечатать одно число – максимально возможную сумму, соответствующую условиям задачи.
Входные данные: Даны два входных файла: файл A (27-4a.txt) и файл B (27-4b.txt), каждый из которых содержит в первой строке количество пар N (1 ≤ N ≤ 100000). Каждая из следующих N строк содержит два натуральных числа, не превышающих 10 000.
Пример входного файла:
6
1 3
5 11
6 9
5 4
3 3
1 1
Для указанных входных данных значением искомой суммы должно быть число 30.
В ответе укажите два числа: сначала значение искомой суммы для файла А, затем для файла B.
Решение
Вариант 1
f=open('27-4a.txt','r')
n=int(f.readline())
a=[0]*5
x,y=map(int, f.readline().split())
a[x%5]=x
a[y%5]=max(a[y%5],y)
for i in range(n-1):
b=[0]*5
x,y=map(int, f.readline().split())
for k in range(2):
for l in range(5):
if a[l]>0:
r=a[l]+x
b[r%5]=max(b[r%5],r)
x=y
a=b[:]
print(a[0])
Вариант 2
Решение с использованием электронных таблиц 5_A_B.xlsx
Ответ: 123720 402332230
6) (№2665) Имеется набор данных, состоящий из пар положительных целых чисел. Необходимо выбрать из каждой пары ровно одно число так, чтобы сумма всех выбранных чисел делилась на 5 и при этом была минимально возможной. Гарантируется, что искомую сумму получить можно. Программа должна напечатать одно число – минимально возможную сумму, соответствующую условиям задачи.
Входные данные: Даны два входных файла: файл A (27-5a.txt) и файл B (27-5b.txt), каждый из которых содержит в первой строке количество пар N (1 ≤ N ≤ 100000). Каждая из следующих N строк содержит два натуральных числа, не превышающих 10 000.
Пример входного файла:
6
1 3
5 11
6 9
5 4
3 3
1 1
Для указанных данных искомая сумма равна 20.
В ответе укажите два числа: сначала значение искомой суммы для файла А, затем для файла B.
Решение
Вариант 1
f=open('27-5a.txt','r')
n=int(f.readline())
a=[0]*5
x,y=map(int, f.readline().split())
a[x%5]=x
if a[y%5]>y or a[y%5]==0:a[y%5]=y
for i in range(n-1):
b=[0]*5
x,y=map(int, f.readline().split())
for k in range(2):
for l in range(5):
if a[l]>0:
r=a[l]+x
if b[r%5]>r or b[r%5]==0:b[r%5]=r
x=y
a=b[:]
print(a[0])
Вариант 2
Решение с помощью электронных таблиц - 6_A_B.xlsx
Ответ: 75960 203343860
7)(№ 3699) Набор данных состоит из нечётного количества пар натуральных чисел.Необходимо выбрать из каждой пары ровно одно число так, чтобы сумма выбранных чисел была максимальной при условии, что чётность этой суммы совпадает с чётностью большинства выбранных чисел. Определите максимальную сумму, которую можно получить при таком условии. Гарантируется, что удовлетворяющий условиям выбор возможен.
Входные данные: Даны два входных файла: файл A (27-48a.txt) и файл B (27-48b.txt), каждый из которых содержит в первой строке количество чисел N (1 ≤ N ≤ 100000). Каждая из следующих N строк содержит два натуральных числа, не превышающих 10000.
Пример входного файла:
5
13 8
5 11
6 9
7 2
9 14
Для указанных данных надо выбрать числа 13, 11, 6, 7 и 14. Большинство из них нечётны, их сумма 51 тоже нечётна. В ответе укажите два числа: сначала искомое значение для файла А, затем для файла B
Решение (Обратите внимание на блок анализа максимальной суммы. Проверяются 5 исходов - чётности совпадают, сумма четная_нечетных много, сумма нечетная_четных много и два исхода, когда количество различается на 1)
Вариант 1
f=open('27-48a.txt','r')
n=int(f.readline())
s=0
knch=0
nch=[10**9,10**9]
ch=[10**9,10**9]
for i in range(n):
x,y=map(int, f.readline().split())
if x<y: x,y=y,x
s+=x; knch+=x%2
if (x+y)%2==1:
if y%2==0:
ch.append(x-y)
ch=sorted(ch)[:2]
else:
nch.append(x-y)
nch=sorted(nch)[:2]
if (s%2==1 and knch*2>n) or (s%2==0 and knch*2<n): #Все получилось сразу
maxs=s
elif s%2==0 and knch*2-n>1:# Если сумма четная - нечетных много
maxs=s-nch[0]
elif s%2==1 and knch*2-n<-1:# Если сумма нечетная - четных много
maxs=s-ch[0]
elif s%2==0 and knch*2-n==1:# Если сумма четная - различие в 1
maxs=max(s-sum(ch),s-nch[0])
else:maxs=max(s-sum(nch),s-ch[0])# Если сумма нечетная - различие в 1
print(maxs)
Вариант 2
Решение в электронной таблице 27-48b.xlsx
Ответ: 117046 411037387
8) (№2671) Имеется набор данных, состоящий из троек положительных целых чисел. Необходимо выбрать из каждой тройки ровно одно число так, чтобы сумма всех выбранных чисел делилась на 8 и при этом была максимально возможной. Гарантируется, что искомую сумму получить можно. Программа должна напечатать одно число – максимально возможную сумму, соответствующую условиям задачи.
Входные данные: Даны два входных файла: файл A (27-11a.txt) и файл B (27-11b.txt), каждый из которых содержит в первой строке количество троек N (1 ≤ N ≤ 100000). Каждая из следующих N строк содержит три натуральных числа, не превышающих 10 000.
Пример входного файла:
6
8 3 4
4 8 12
9 5 6
2 8 3
12 3 5
1 4 12
Для указанных входных данных значением искомой суммы должно быть число 56.
В ответе укажите два числа: сначала значение искомой суммы для файла А, затем для файла B.
Решение
Вариант 1
f=open('27-11a.txt','r')
n=int(f.readline())
a=[0]*8
x,y,z=map(int, f.readline().split())
a[x%8]=x
a[y%8]=max(a[y%8],y)
a[z%8]=max(a[z%8],z)
for i in range(n-1):
b=[0]*8
x,y,z=map(int, f.readline().split())
for k in range(3):
for l in range(8):
if a[l]>0:
r=a[l]+x
b[r%8]=max(b[r%8],r)
if k==0:x=y
else:x=z
a=b[:]
print(a[0])
Вариант 2
Решение с помощью электронной таблицы - 27-11a.xlsx
Ответ: 14432 45978688
9) Дана последовательность N целых положительных чисел. Рассматриваются все пары элементов последовательности, разность которых чётна и, по крайней мере, один из элементов делится на р = 25. Порядок элементов в паре неважен. Среди всех таких пар нужно найти и вывести пару с максимальной суммой элементов. Если одинаковую максимальную сумму имеет несколько пар, можно вывести любую из них. Если подходящих пар в последовательности нет, нужно вывести два нуля.
Описание входных и выходных данных
В первой строке входных данных задаётся количество чисел N (2 < N< 10 000). В каждой из последующих N строк записано одно натуральное число, не превышающее 10 000.
Пример входных данных:
5
50
12
75
82
75
Пример выходных данных для приведённого выше примера входных данных:
75 75
Пояснение. Из данных пяти чисел можно составить три различные пары, удовлетворяющие условию: (50,12), (50,82), (75,75). Наибольшая сумма получается в паре (75,75). Эта пара допустима, так как число 81 встречается в исходной последовательности дважды.
Ответом на задание является указание максимальной пары чисел.
Файл для решения A.txt
Решение
Вариант 1
f=open('a.txt','r')
n=int(f.readline())
print(n)
ma=[0]*2
ma25=[0]*2
for i in range(n):
x=int(f.readline())
c=x%2
if x%25==0:
if ma25[c]<x:
ma[c]=max(ma[c],ma25[c])
ma25[c]=x
else:
ma[c]=max(ma[c],x)
else:
ma[c]=max(ma[c],x)
if ma[0]*ma25[0]+ ma[1]*ma25[1]==0: a=0;b=0
elif ma[0]+ma25[0]>ma[1]+ma25[1] and ma[0]*ma25[0]>0 : a=ma[0];b=ma25[0]
else:a=ma[1];b=ma25[1]
print(min(a,b),max(a,b))
Вариант 2
Решение с помощью электронной таблицы - zad27_Решение.xlsx
Ответ: 4525 8935
10) Для заданной последовательности неотрицательных целых чисел необходимо найти максимальное произведение двух её элементов, номера которых различаются не менее чем на 8. Значение каждого элемента последовательности не превышает 1000. Количество элементов последовательности не превышает 60000.
Задача А. Напишите программу для решения поставленной задачи, в которой входные данные будут запоминаться в массиве, после чего будут проверены все возможные пары элементов. Максимальная оценка за выполнение задания А – 2 балла.
Задача Б. Напишите программу для решения задачи, которая будет эффективна как по времени, так и по памяти (или хотя бы по одной из этих характеристик).
Входные данные представлены следующим образом. В первой строке задаётся число N – общее количество элементов последовательности. Гарантируется, что N > 8. В каждой из следующих N строк задаётся одно неотрицательное целое число – очередной элемент последовательности.
Пример входных данных:
10
100
45
55
245
35
25
10
10
10
26
Пример выходных данных для приведённого выше примера входных данных:
2600
Даны два входных файла: файл A (10-a.txt) и файл B (10-b.txt), каждый из которых содержит в первой строке количество чисел N (1 ≤ N ≤ 60000). Каждая из следующих N строк содержит одно целое число, не превышающее 1000.
Решение
Вариант 1 (Полный перебор)
f=open('10-a.txt','r')
n=int(f.readline())
m=[]
for i in range(n):
m.append(int(f.readline()))
pma=0
for i in range(n-8):
for j in range(i+8,n):
pma=max(pma,m[i]*m[j])
print(pma)
Вариант 2 (Очередь)
f=open('10-b.txt','r')
n=int(f.readline())
m=[]
for i in range(8):
m.append(int(f.readline()))
pma=0
ma=0
for i in range(8,n):
ma=max(ma,m[0])
m=m[1:]+[int(f.readline())]
pma=max(pma,ma*m[-1])
print(pma)
Ответ:
A - 39400
B - 998001
11) На вход программы поступает последовательность из N целых положительных чисел, все числа в последовательности различны. Рассматриваются все пары различных элементов последовательности. Необходимо определить количество таких пар, для которых произведение элементов делится на 31.
Описание входных и выходных данных
В первой строке входных данных задаётся количество чисел N (2 ≤ N ≤ 60 000).
В каждой из последующих N строк записано одно целое положительное число, не превышающее 1000.
В качестве результата программа должна вывести одно число: количество пар элементов в которых произведение элементов кратно 31.
Пример входных данных:
6
62
2
3
5
4
3
Пример выходных данных для приведённого выше примера входных данных:
5
Даны два входных файла: файл A (10-a.txt) и файл B (10-b.txt), каждый из которых содержит в первой строке количество чисел N (1 ≤ N ≤ 60000). Каждая из следующих N строк содержит одно целое число, не превышающее 1000.
Решение
Вариант 1 (Полный перебор)
f=open('10-a.txt','r')
n=int(f.readline())
m=[]
for i in range(n):
m.append(int(f.readline()))
k=0
for i in range(n-1):
for j in range(i+1,n):
if m[i]*m[j]%31==0:
k+=1
print(k)
Вариант 2 (Очередь)
f=open('10-b.txt','r')
n=int(f.readline())
k,k31=0,0
for i in range(n):
if int(f.readline())%31==0: k+=i;k31+=1
else: k+=k31
print(k)
Ответ:
A - 590
B - 111554895
12) На вход программы поступает последовательность из N целых положительных чисел, все числа в последовательности различны. Рассматриваются все пары различных элементов последовательности, находящихся на расстоянии не меньше чем 3 (разница в индексах элементов пары должна быть 3 или более, порядок элементов в паре неважен).
Необходимо определить количество таких пар, для которых произведение элементов делится на 31.
Описание входных и выходных данных
В первой строке входных данных задаётся количество чисел N (3 ≤ N ≤ 60 000).
В каждой из последующих N строк записано одно целое положительное число, не превышающее 1000.
В качестве результата программа должна вывести одно число: количество пар элементов, находящихся в последовательности на расстоянии не меньше чем 3, в которых произведение элементов кратно 31.
Пример входных данных:
6
62
2
3
5
4
31
Пример выходных данных для приведённого выше примера входных данных:
5
Пояснение. Из шести заданных элементов с учётом допустимых расстояний между ними можно составить 6 произведений: 62·5, 62·4, 62·31, 2·4, 2·31, 3·31. Из них на 31 делятся 5 произведений.
Даны два входных файла: файл A (10-a.txt) и файл B (10-b.txt), каждый из которых содержит в первой строке количество чисел N (1 ≤ N ≤ 60000). Каждая из следующих N строк содержит одно целое число, не превышающее 1000.
Решение
Вариант 1 (Полный перебор)
f=open('10-a.txt','r')
n=int(f.readline())
m=[]
for i in range(n):
m.append(int(f.readline()))
k=0
for i in range(n-1):
for j in range(i+1,n):
if m[i]*m[j]%31==0:
k+=1
print(k)
Вариант 2 (Очередь)
f=open('10-a.txt','r')
n=int(f.readline())
m=[]
for i in range(3):
m.append(int(f.readline()))
k31,k=0,0
for i in range(3,n):
if m[0]%31==0: k31+=1
m=m[1:]+[int(f.readline())]
if m[-1]%31==0: k+=i-2
else:k+=k31
print(k)
Ответ:
A - 574
B - 111547462
13) На вход программы поступает последовательность из N целых положительных чисел, все числа в последовательности различны. Рассматриваются все пары различных элементов последовательности, находящихся на расстоянии не меньше чем 3 (разница в индексах элементов пары должна быть 3 или более, порядок элементов в паре неважен).
Необходимо определить количество таких пар, для которых сумма элементов делится на 4.
Описание входных и выходных данных
В первой строке входных данных задаётся количество чисел N (3 ≤ N ≤ 60000).
В каждой из последующих N строк записано одно целое положительное число, не превышающее 1000.
В качестве результата программа должна вывести одно число: количество пар элементов, находящихся в последовательности на расстоянии не меньше чем 3, в которых сумма элементов кратно 4.
Пример входных данных:
6
62
2
4
5
4
6
Пример выходных данных для приведённого выше примера входных данных:
2
Даны два входных файла: файл A (10-a.txt) и файл B (10-b.txt), каждый из которых содержит в первой строке количество чисел N (1 ≤ N ≤ 60000). Каждая из следующих N строк содержит одно целое число, не превышающее 1000.
Решение
Вариант 1 (Полный перебор)
f=open('10-a.txt','r')
n=int(f.readline())
m=[]
for i in range(n):
m.append(int(f.readline()))
k=0
for i in range(n-3):
for j in range(i+3,n):
if (m[i]+m[j])%4==0:
k+=1
print(k)
Вариант 2 (Очередь)
f=open('10-b.txt','r')
n=int(f.readline())
m=[]
mo=[0]*4
for i in range(3):
m.append(int(f.readline()))
k31=0
k=0
for i in range(3,n):
mo[m[0]%4]+=1
m=m[1:]
m.append(int(f.readline()))
k+=mo[(4-m[2]%4)%4]
print(k)
Ответ:
A - 2717
B - 449989909
14) Имеется набор данных, состоящий из пар положительных целых чисел. Необходимо выбрать из каждой пары ровно одно число так, чтобы сумма всех выбранных чисел в семеричной системе счисления оканчивалась на четную цифру и при этом была максимально возможной. Гарантируется, что искомую сумму получить можно. Программа должна напечатать одно число – максимально возможную сумму, соответствующую условиям задачи.
Входные данные. Даны два входных файла (файл A-1 и файл B-1), каждый из которых содержит в первой строке количество пар N (1 ≤ N ≤ 100000). Каждая из следующих N строк содержит два натуральных числа, не превышающих 10 000.
Пример входного файла:
6
1 3
5 12
6 9
5 4
3 3
5 1
Для указанных входных данных значением искомой суммы должно быть число 37.
В ответе укажите два числа: сначала значение искомой суммы для файла А, затем для файла B.
Решение
f=open('a-1.txt','r')
a=[0]*7
n=int(f.readline())
x,y=map(int, f.readline().split())
a[x%7]=x
a[y%7]=max(a[y%7],y)
for i in range(1,n):
b=[0]*7
x,y=map(int, f.readline().split())
for p in range(7):
b[(a[p]+x)%7]=max(b[(a[p]+x)%7],a[p]+x)
b[(a[p]+y)%7]=max(b[(a[p]+y)%7],a[p]+y)
a=b[:]
print(max(a[0],a[2],a[4],a[6]))
Ответ:
A - 13682
B - 40724966
15) Имеется набор данных, состоящий из троек положительных целых чисел. Необходимо выбрать из каждой тройки ровно одно число так, чтобы сумма всех выбранных чисел в шестнадцатеричной системе счисления оканчивалось на «С» и при этом была максимально возможной. Гарантируется, что искомую сумму получить можно. Программа должна напечатать одно число – максимально возможную сумму, соответствующую условиям задачи.
Входные данные. Даны два входных файла (файл A-2 и файл B-2), каждый из которых содержит в первой строке количество троек N (1 ≤ N ≤ 100000). Каждая из следующих N строк содержит три натуральных числа, не превышающих 10 000.
Пример входного файла:
6
8 3 4
4 8 12
9 5 6
2 8 3
12 3 5
1 4 12
Для указанных входных данных значением искомой суммы должно быть число 44.
В ответе укажите два числа: сначала искомое значение для файла А, затем для файла B.
Решение
f=open('a-2.txt','r')
a=[0]*16
n=int(f.readline())
x,y,z=map(int, f.readline().split())
a[x%16]=x
a[y%16]=max(a[y%16],y)
a[z%16]=max(a[z%16],z)
for i in range(1,n):
b=[0]*16
x,y,z=map(int, f.readline().split())
for p in range(16):
b[(a[p]+x)%16]=max(b[(a[p]+x)%16],a[p]+x)
b[(a[p]+y)%16]=max(b[(a[p]+y)%16],a[p]+y)
b[(a[p]+z)%16]=max(b[(a[p]+z)%16],a[p]+z)
a=b[:]
print(a[12])
Ответ:
A - 14428
B - 45978684
16)(№ 2660 Демовариант 2021г.) Имеется набор данных, состоящий из пар положительных целых чисел. Необходимо выбрать из каждой пары ровно одно число так, чтобы сумма всех выбранных чисел не делилась на 3 и при этом была максимально возможной. Гарантируется, что искомую сумму получить можно. Программа должна напечатать одно число – максимально возможную сумму, соответствующую условиям задачи.
Входные данные. Даны два входных файла (файл A-3 и файл B-4), каждый из которых содержит в первой строке количество пар N (1 ≤ N ≤ 100000). Каждая из следующих N строк содержит два натуральных числа, не превышающих 10 000.
Пример входного файла:
6
1 3
5 12
6 9
5 4
3 3
1 1
Для указанных входных данных значением искомой суммы должно быть число 32.
В ответе укажите два числа: сначала значение искомой суммы для файла А, затем для файла B.
Решение
f=open('a-3.txt','r')
a=[0]*3
n=int(f.readline())
x,y=map(int, f.readline().split())
a[x%3]=x
a[y%3]=max(a[y%3],y)
for i in range(1,n):
b=[0]*3
x,y=map(int, f.readline().split())
for p in range(3):
b[(a[p]+x)%3]=max(b[(a[p]+x)%3],a[p]+x)
b[(a[p]+y)%3]=max(b[(a[p]+y)%3],a[p]+y)
a=b[:]
print(max(a[1],a[2]))
Ответ:
A - 127127
B - 399762080
17)(№ 2667) Имеется набор данных, состоящий из положительных целых чисел, каждое из которых не превышает 1000. Требуется найти для этой последовательности контрольное значение – наибольшее число R, удовлетворяющее следующим условиям:
– R – произведение двух различных переданных элементов последовательности («различные» означает, что не рассматриваются квадраты переданных чисел, произведения различных, но равных по величине элементов допускаются);
– R делится на 7 и не делится на 49.
Если такое произведение получить невозможно, считается, что контрольное значение R = 1.
Входные данные. Даны два входных файла (файл A-4 и файл B-4), каждый из которых содержит в первой строке количество чисел N (1 ≤ N ≤ 100000). Каждая из следующих N строк содержит одно натуральное число, не превышающее 10 000.
Пример входного файла:
6
60
17
3
7
9
60
Для указанных входных данных искомое контрольное значение равно 420.
В ответе укажите два числа: сначала контрольное значение для файла А, затем для файла B.
Решение
f=open('a-4.txt','r')
max7,maxc=0,0
for i in range(int(f.readline())):
x=int(f.readline())
if x%7: maxc=max(maxc,x)
elif x%49: max7=max(max7,x)
print(maxc*max7)
Ответ:
A - 692286
B - 952567
18)(№ 2713 Д.Ф. Муфаззалов) Дан набор данных, состоящий из неотрицательных целых чисел. Из данного набора выбрали некоторые (или все) числа и записали их подряд без пробелов в произвольном порядке. Определите наибольшее значение с симметричной записью (читается справа налево и слева направо одинаково), кратное числу 5, которое может быть получено таким образом. Гарантируется, что искомое значение получить можно. Программа должна напечатать одно число – сумму цифр искомого значения.
Входные данные. Даны два входных файла (файл A-5 и файл B-5), каждый из которых содержит в первой строке количество чисел N (1 ≤ N ≤ 100000). Каждая из следующих N строк содержит одно целое неотрицательное число, каждое из которых меньше числа 10.
Пример входного файла:
10
8
3
2
3
5
9
5
3
9
9
Для указанных входных данных значением искомой суммы должно быть число 43. Соответствующее ей симметричное число – 5939395.
В ответе укажите два числа: сначала значение искомой суммы для файла А, затем для файла B.
Решение
f=open('A-5.txt','r')
n=int(f.readline())
m=[0]*10
s=5
sr=''
for i in range(n):
m[int(f.readline())]+=1
m[5]-=2
for i in range(9,-1,-1):
s+=i*(m[i]//2)
if m[i]%2 and sr=='': sr=i
print(s*2+sr)
Ответ:
A - 71
B - 254363
19) (№ 4279 А. Кабанов) Набор данных представляет собой последовательность натуральных чисел. Необходимо выбрать такую подпоследовательность подряд идущих чисел, чтобы их сумма была максимальной, делилась на 93 и была нечётной. Гарантируется, что такая подпоследовательность существует. В качестве ответа укажите сумму чисел данной подпоследовательности.
Входные данные. Даны два входных файла (файл A-6 и файл B-6), каждый из которых содержит в первой строке количество чисел N (2 ≤ N ≤ 108). Каждая из следующих N строк содержит натуральное число, не превышающее 10000.
Пример входного файла:
6
31
44
18
11
186
93
В этом наборе можно выбрать последовательности 31+44+18 (сумма 93), 186+93 (сумма 279) и 93. Ответ: 279.
В ответе укажите два числа: сначала искомое значение для файла А, затем для файла B.
Решение
f=open('A-6.txt','r')
n=int(f.readline())
a=[0]*93
max93=0
for i in range(n):
b=[0]*93
x=int(f.readline())
b[x%93]=x
for p in range(93):
b[(a[p]+x)%93]=max(b[(a[p]+x)%93],a[p]+x)
if b[0]%2!=0: max93=max(max93,b[0])
a=b[:]
print(max93)
Ответ:
A - 19437
B - 50211537
20) (№ 2680 Е.А.Мирончик) На столе выложили цепочку из N костяшек по принципу домино. Под костяшкой понимается пара любых неотрицательных чисел, каждое не превышает 100. В наборе могут быть одинаковые костяшки. Переставлять местами костяшки нельзя, но можно поворачивать любое количество костяшек, получая, например, из костяшки 1-2 костяшку 2-1. Определите максимальную длину цепочки костяшек домино, которую можно получить с помощью переворачиваний. Под цепочкой понимается последовательность костяшек, в которой второе число первой костяшки равно первому числу второй.
Входные данные. Даны два входных файла (файл A и файл B), каждый из которых содержит в первой строке количество пар N (1 ≤ N ≤ 100000). Каждая из следующих N строк содержит два натуральных числа, не превышающих 100.
Пример входного файла:
5
1 2
2 3
5 4
5 5
5 1
Для указанных входных данных искомая длина должна быть число 3: если перевернуть третью костяшку, то образуется цепочка: 4-5 5-5 5-1.
В ответе укажите два числа: сначала искомое значение для файла А, затем для файла B.
Решение
f=open('27_01b.txt')
n=int(f.readline())
a=[0]*101
maxl=0
for i in range(n):
b=[0]*101
x,y=map(int,f.readline().split())
b[y]=a[x]+1
b[x]=a[y]+1
maxl=max(maxl,max(b))
a=b[:]
print(maxl)
Ответ:
A - 19
B - 235
21) (№ 2666) Имеется набор данных, состоящий из положительных целых чисел, каждое из которых не превышает 1000. Требуется найти для этой последовательности контрольное значение – наибольшее число R, удовлетворяющее следующим условиям:
– R – произведение двух различных переданных элементов последовательности («различные» означает, что не рассматриваются квадраты переданных чисел, произведения различных, но равных по величине элементов допускаются);
– R делится на 6.
Входные данные. Даны два входных файла (файл A и файл B), каждый из которых содержит в первой строке количество чисел N (1 ≤ N ≤ 100000). Каждая из следующих N строк содержит одно натуральное число, не превышающее 10 000.
Пример входного файла:
6
60
17
3
7
9
60
Для указанных входных данных искомое контрольное значение равно 3600.
В ответе укажите два числа: сначала контрольное значение для файла А, затем для файла B.
Решение
f=open('27_02a.txt')
n=int(f.readline())
m6,m3,m2,m=0,0,0,0
maxp=0
for i in range(n):
x=int(f.readline())
if x%6==0:
maxp=max(maxp,m*x)
m6=max(m6,x)
elif x%3==0:
maxp=max(maxp,m2*x,m6*x)
m3=max(m3,x)
elif x%2==0:
maxp=max(maxp,m3*x,m6*x)
m2=max(m2,x)
else:
maxp=max(maxp,m6*x)
m=max(m,x)
print(maxp)
Ответ:
A - 782040
B - 997002
22) (№ 4848) На вход программе подается последовательность целых чисел и натуральное число K. Особым числом называется отрицательное число, заканчивающееся на 3. Рассматриваются все непрерывные подпоследовательности исходной последовательности, содержащие ровно K особых чисел. Программа должна вывести одно число – максимальную сумму элементов такой подпоследовательности. Гарантируется, что в последовательности существует хотя бы K особых чисел.
Входные данные. Даны два входных файла (файл A и файл B), каждый из которых содержит в первой строке количество чисел N (100 ≤ N ≤ 5000000) и натуральное число K. Каждая из следующих N строк файлов содержит одно целое число, не превышающее по модулю 10000. Гарантируется, что сумма любой подпоследовательности исходной последовательности не превышает 109.
Пример входного файла:
14 1
-1
-1
2
-3
3
-13
1
-1
6
-23
8
23
8
1
В этом наборе три особых числа: –3, –13 и –23. Можно выбрать подпоследовательность (6, –23, 8, 23, 8, 1), которая имеет сумму 23 и содержит одно особое число. Ответ для приведенного примера: 23.
В ответе укажите два числа: сначала искомое значение для файла А, затем для файла B.
Решение
f=open('27_01а.txt')
n,k=map(int,f.readline().split())
m=[0]*(k+1)
maxs=-10000
kt=0
for i in range(n):
x=int(f.readline())
for p in range(k+1):
m[p]+=x
if x<0 and str(x)[-1]=='3':
m=[0]+m[:-1]
kt+=1
if m[0]<0: m[0]=0
if kt>=k:
maxs=max(maxs,m[-1])
print(maxs)
Ответ:
A - 20139
B - 38739
23) (№ 4847 Д.Муфаззалов) На вход программе подается последовательность целых чисел. Особым называется положительное четное число. Рассматриваются все непрерывные подпоследовательности исходной последовательности, содержащих ровно одно особое число. Программа должна вывести одно число – максимальную сумму такой подпоследовательности. Гарантируется, что в последовательность существует хотя бы одно особое число.
Входные данные. Даны два входных файла (файл A и файл B), каждый из которых содержит в первой строке количество чисел N (100 ≤ N ≤ 5000000). Каждая из следующих N строк файлов содержит одно целое число, не превышающее по модулю 10000. Гарантируется, что сумма любой подпоследовательности, содержащей особое число, не превышает 109.
Пример входного файла:
14
-1
-1
2
-3
3
20
1
-1
6
-7
8
23
8
1
В этом наборе пять особых чисел: 2, 20, 6, 8, 8. Можно выбрать подпоследовательность (23, 8, 1), которая имеет сумму 32 и содержит одно особое число. Ответ для приведенного примера: 32.
В ответе укажите два числа: сначала искомое значение для файла А, затем для файла B.
Решение
f=open('27_02b.txt')
n=int(f.readline())
m=[0]*2
mc=-100000
kt=0
for i in range(n):
x=int(f.readline())
for j in range(2):
m[j]+=x
if x>0 and x%2==0:
m=[0]+m[:-1]
kt+=1
if m[0]<0: m[0]=0
if kt>=1:
mc=max(mc,m[-1])
print(mc)
Ответ:
A - 4710
B - 7368
24) (№ 3823 А.Кабанов) В файле записана последовательность натуральных чисел. Рассматриваются всевозможные группы чисел, состоящие из любого количества элементов последовательности. Необходимо найти количество таких групп, для которых сумма элементов оканчивается на 5.
Входные данные. Даны два входных файла (файл A и файл B), каждый из которых содержит в первой строке количество чисел N (1 ≤ N ≤ 100000). Каждая из следующих N строк содержит одно натуральное число, не превышающее 108.
Пример входного файла:
4
8
7
12
23
Для указанных данных можно выбрать следующие группы: {12, 23}; {8, 7}. Программа должна вывести количество этих групп – 2.
В ответе укажите два числа: сначала искомое значение для файла А, затем для файла B.
Решение
Вариант 1(перебор)
f=open('27_05a.txt')
n=int(f.readline())
m=[]
for i in range(n):m.append(int(f.readline()))
k=0
for i in range(2**n):
a=bin(i)[2:]
a='0'*(n-len(a))+a
s=0
for i in range(n):
s+=m[i]*int(a[i])
if s%10==5: k+=1
print(k)
Вариант 2 (комбинаторика)
import itertools
f=open('27_05а.txt')
n=int(f.readline())
m=[]
for i in range(n):m.append(int(f.readline()))
k=0
for i in range(1,n+1):
for p in itertools.combinations(m,i):
if sum(p)%10==5:k+=1
print(k)
Вариант 3 (решает всё)
f=open('27_05b.txt')
n=int(f.readline())
a=[0]*10
b=[0]*10
for i in range(n):
x=int(f.readline())
b[x%10]+=1
for p in range(10):
if a[p]!=0: b[(x+p)%10]+=a[p]
a=b[:]
print(b[5])
Ответ:
A - 115
B - 107374272
25) (№ 4193 А.Богданов ) Набор данных состоит из групп натуральных чисел, каждая группа записана в отдельной строке. В любой группе содержится не менее двух чисел. Из каждой группы нужно выбрать одно или несколько чисел так чтобы их сумма была чётной. Какую максимальную сумму выбранных чисел, не кратную 5, можно получить?
Входные данные. Даны два входных файла (файл A и файл B), каждый из которых содержит в первой строке количество групп чисел N (N ≤ 100000). В каждой из следующих N строк файлов записан сначала размер группы K (N ≤ 20), а затем – K натуральных чисел, не превышающих 1000.
Пример входного файла:
4
4 1 3 5 6
2 3 6
2 5 8
2 7 12
Из каждой строки выбираем числа с четной суммой (3+5+6)+(6)+(8)+(12)=40. Чтобы сумма не делилась на 5, можно уменьшить её на 2, заменив в первой группе 3 на 1. Ответ: 40-2=38.
В ответе укажите два числа: сначала искомое значение для файла А, затем для файла B.
Решение
import itertools
f=open('27_06a.txt')
n=int(f.readline())
a=[0]*10
for i in range(n):
mt=list(map(int,f.readline().split()))[1:]
maxs=[0]*10
for dl in range(1,len(mt)+1):
for p in itertools.combinations(mt,dl):
st=sum(p)
if st%2==0: maxs[st%10]=max(maxs[st%10],st)
b=[0]*10
for p in range(0,10,2):
if a[p]>0 or i==0:
for x in maxs:
b[(a[p]+x)%10]=max(b[(a[p]+x)%10],a[p]+x)
a=b[:]
print(max(b[1:]))
Ответ:
A - 4908
B - 134271196
26) (№ 4281 демо-2022) Дана последовательность из N натуральных чисел. Рассматриваются все её непрерывные подпоследовательности, такие что сумма элементов каждой из них кратна k = 43. Найдите среди них подпоследовательность с максимальной суммой, определите её длину. Если таких подпоследовательностей найдено несколько, в ответе укажите количество элементов самой короткой из них.
Входные данные. Даны два входных файла (файл A и файл B), каждый из которых содержит в первой строке количество чисел N (2 ≤ N ≤ 108). Каждая из следующих N строк содержит натуральное число, не превышающее 10000.
Пример входного файла:
7
21
13
9
19
17
26
95
В этом наборе можно выбрать последовательности 21+13+9 (сумма 43) и 17+26 (сумма 43). Самая короткая из них, 17 + 26, имеет длину 2. Ответ: 2.
В ответе укажите два числа: сначала искомое значение для файла А, затем для файла B.
Решение
Вариант 1 (перебор) (время работы программы a - 0.23 c.)
f=open('27-a.txt')
n=int(f.readline())
m=[]
for i in range(n): m.append(int(f.readline()))
maxs=0
for i in range(n):
s=0
for p in range(i,n):
s+=m[p]
if s%43==0:
if s>maxs:
maxs,minl=s,p-i+1
elif s==maxs:
minl=min(minl,p-i+1)
print(minl)
Вариант 2 (время работы программы a - 0.0299c. b - 59.4152c.)
f=open('27-b.txt')
n=int(f.readline())
a=[0]*43
maxsa=[0]*43
max0=0
k=0
for i in range(n):
b=[0]*43
maxsb=[0]*43
x=int(f.readline())
b[x%43]=1
maxsb[x%43]=x
for p in range(43):
if a[p]>0:
b[(maxsa[p]+x)%43]=a[p]+1
maxsb[(maxsa[p]+x)%43]=maxsa[p]+x
if max0<maxsb[0]:
max0=maxsb[0]
k=b[0]
elif max0==maxsb[0]:
k=min(k,b[0])
a=b[:]
maxsa=maxsb[:]
print(k)
Вариант 3 (время работы программы a - 0.0170c. b - 7.0160c.)
f=open('27-a.txt')
n=int(f.readline())
a=[10**20]*43
ka=[0]*43
s,sk=0,0
maxs,mink=0,n+1
for i in range(n):
x=int(f.readline())
s+=x
if a[s%43]>s:
a[s%43]=s
ka[s%43]=i
if s%43==0:
if s>maxs: maxs=s;sk=i
elif a[s%43]!=10**20:
if maxs<s-a[s%43]:
maxs=s-a[s%43]
sk=i-ka[s%43]
elif maxs==s-a[s%43]:sk=min(sk,i-ka[s%43])
print(sk,maxs)
Ответ:
A - 185
B - 329329
27) (№2945 Апробация 19 февраля 2022 года, Москва ) Дана последовательность из N натуральных чисел. Рассматриваются все её непрерывные подпоследовательности, такие что сумма элементов каждой из них кратна k = 67. Найдите среди них подпоследовательность с максимальной суммой. Укажите в ответе найденную максимальную сумму.
Входные данные
Даны два входных файла (Z_27_A.TXT и Z_27_A.TXT), каждый из которых содержит в первой строке количество чисел N (1 < N< 10 000 000). Каждая из следующих N строк содержит одно натуральное число, не превышающее 10 000.
Пример организации исходных данных во входном файле:
7
1
3
4
93
8
5
95
В ответе укажите два числа: сначала значение искомой суммы для файла А, затем — для файла В.
Решение
Вариант 1 (перебор)
f=open('z_27_a.txt')
n=int(f.readline())
m=[]
for i in f.readlines(): m.append(int(i))
max67=0
for i in range(n):
s=0
for j in range(i,n):
s+=m[j]
if s%67==0: max67=max(max67,s)
print(max67)
Вариант 2
f=open('z_27_b.txt')
n=int(f.readline())
a=[0]*67
max67=0
for i in range(n):
x=int(f.readline())
b=[0]*67
b[x%67]=x
for p in range(67):
if a[p]!=0:b[(a[p]+x)%67]=max(b[(a[p]+x)%67],a[p]+x)
max67=max(max67,b[0])
a=b[:]
print(max67)
Вариант 3
f=open('z_27_b.txt')
n=int(f.readline())
m=[10**20]*67
max67,s=0,0
for i in range(n):
x=int(f.readline())
s+=x
if s%67==0:max67=max(max67,s)
else:
max67=max(max67,s-m[s%67])
m[s%67]=min (m[s%67],s)
print(max67)
Ответ:
A - 649565
B - 208957389
28) (№4124 В.Якшигулов) Набор данных состоит из пар натуральных чисел. Необходимо выбрать из каждой пары одно число так, чтобы сумма выбранных чисел была максимально возможной и не делилась на 5, при этом сумма невыбранных чисел не делилась на 3. Какую наибольшую сумму выбранных чисел можно при этом получить?
Входные данные. Даны два входных файла (файл 27-a.txt и файл 27-b.txt), каждый из которых содержит в первой строке количество чисел N (1 ≤ N ≤ 12000). Каждая из следующих N строк содержит два натуральных числа, не превышающих 500.
Пример входного файла:
5
13 18
18 10
15 8
19 11
7 15
Для указанных входных данных значением искомой суммы должно быть число 18+18+8+19+15=78 (сумма остальных элементов 13+10+15+11+7=56).
В ответе укажите два числа: сначала искомое значение для файла А, затем для файла B.
Решение
Вариант 1 (перебор)
В процессе написания
Вариант 2
f=open('27-66a.txt')
n=int(f.readline())
a=[0]*5
s=0
for i in range(n):
x,y=map(int,f.readline().split())
b=[0]*5
s+=x+y
if i==0:
b[x%5]=x
b[y%5]=max(b[y%5],y)
else:
for p in range(5):
if a[p]!=0:
b[(a[p]+x)%5]=max(b[(a[p]+x)%5],a[p]+x)
b[(a[p]+y)%5]=max(b[(a[p]+y)%5],a[p]+y)
a=b[:]
maxs=0
for i in range(1,5):
if (s-a[i])%3!=0: maxs=max(maxs,a[i])
print(maxs)
Ответ:
A - 453
B - 3695118
29) (№3587) На каждом километре кольцевой автодороги с двусторонним движением установлены контейнеры для мусора. Длина кольцевой автодороги равна N километров. Нулевой километр и N-й километр автодороги находятся в одной точке. Известно количество мусора, которое накапливается ежедневно в каждом из контейнеров. Из каждого пункта мусор вывозит отдельный мусоровоз. Стоимость доставки мусора вычисляется как произведение количества мусора на расстояние от пункта до центра переработки. Определите километровую отметку автодороги с наименьшим номером, на который требуется открыть центр переработки отходов, чтобы обеспечить минимальную стоимость перевозки мусора из всех пунктов в этот центр. Входные данные
Дано два входных файла (файл 27-a.txt и файл 27-b.txt), каждый из которых в первой строке содержит число N (1<=N<=10 000 000) - количество пунктов сбора мусора на кольцевой автодороге. В каждой из следующих N строк находится число - количество мусора в контейнере (все числа натуральные, количество мусора в каждом пункте не превышает 1000). Числа указаны в порядке расположения контейнеров на автомагистрали, начиная с первого километра. В ответе укажите два числа: сначала значение искомой величины для файла А, зачем - для файла В. Типовой пример организации данных на входном файле
6
8
20
5
13
7
19
При таких входных данных, если контейнеры установлены на каждом километре автодороги, необходимо открыть центр переработки в пункте 6. В этом случае сумма транспортных затрат составит: 1*7+0*19+1*8+2*20+3*5+2*13
Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов. Предупреждение: для обработки файла В не следует использовать переборный алгоритм, вычисляющих сумму для всех возможных вариантов, поскольку написанную по такому алгоритму программа будет выполняться слишком долго.
Решение
Вариант 1 (перебор)(время работы программы a - 0.0156 c.)
f=open('27-a.txt')
n=int(f.readline())
m=[]
for i in range(n):m.append(int(f.readline()))
m=m*3
mins=10**20
for i in range(n,n*2):
s=0
for l in range(1,n//2):
s+=m[i-l]*l+m[i+l]*l
s+=m[i+n//2]*n//2
if s<mins:
mins=s
p=i-n+1
print(p)
Вариант 2 (перебор)(время работы программы a - 0.0312c.)
f=open('27-a.txt')
n=int(f.readline())
m=[]
for i in range(n):m.append(int(f.readline()))
m=m[-n//2:]+m+m[:n//2+1]
for i in range(1,len(m)): m[i]+=m[i-1]
dn=pt=n//2
mins=10**20
for pt in range(pt,pt+n):
s1,s2=0,0
for i in range(1,n//2):
s1+=m[pt-i]-m[pt-dn]
s2+=m[pt+dn-1]-m[pt+i-1]
s=s1+s2+(m[pt+dn]-m[pt+dn-1])*dn
if s<mins:
mins=s
p=pt-dn+1
print(p)
Вариант 3 (время работы программы a - 0.0156c. b - 10.2572c.)
f=open('27-b.txt')
n=int(f.readline())
m=[]
for i in range(n):m.append(int(f.readline()))
m=[0]+m[-n//2:]+m+m[:n//2+1]
for i in range(1,len(m)): m[i]+=m[i-1]
dn=n//2
pt=n//2+1
s1,s2=0,0
for i in range(1,n//2):
s1+=m[pt-i]-m[pt-dn]
s2+=m[pt+dn-1]-m[pt+i-1]
mins=s1+s2+(m[pt+dn]-m[pt+dn-1])*dn
for pt in range(pt+1,pt+n):
s1-=(m[pt-dn]-m[pt-dn-1])*dn
s2+=(m[pt+dn-1]-m[pt+dn-2])*dn
s1+=m[pt-1]-m[pt-dn-1]
s2-=m[pt+dn-1]-m[pt-1]
s=s1+s2+(m[pt+dn]-m[pt+dn-1])*dn
if s<mins:
mins=s
p=pt-dn
print(p)
Ответ:
A - 152
B - 524909
30) (№23 Демоверсия 2021) Имеется набор данных, состоящий из пар положительных целых чисел. Необходимо выбрать из каждой пары ровно одно число так, чтобы сумма всех выбранных чисел не делилась на 3 и при этом была максимально возможной. Гарантируется, что искомую сумму получить можно. Программа должна напечатать одно число – максимально возможную сумму, соответствующую условиям задачи.
Входные данные. Даны два входных файла (файл 27-a.txt и файл 27-b.txt), каждый из которых содержит в первой строке количество пар N (1 ≤ N ≤ 100000). Каждая из следующих N строк содержит два натуральных числа, не превышающих 10 000.
Пример организации исходных данных во входном файле:
6
1 3
5 12
6 9
5 4
3 3
1 1
Для указанных входных данных значением искомой суммы должно быть число 32. В ответе укажите два числа: сначала значение искомой суммы для файла А, затем для файла B.
Предупреждение: для обработки файла B не следует использовать переборный алгоритм, вычисляющий сумму для всех возможных вариантов, поскольку написанная по такому алгоритму программа будет выполняться слишком долго.
Решение
Вариант 1
f=open('27-a.txt')
n=int(f.readline())
maxs=0
d=[10**20]*3
for i in range(n):
x,y=map(int,f.readline().split())
maxs+=max(x,y)
r=abs(x-y)
d[r%3]=min(d[r%3],r)
if maxs%3==0:maxs-=min(d[1:])
print(maxs)
Вариант 2
f=open('27-a.txt')
n=int(f.readline())
a=[0]*3
x,y=map(int,f.readline().split())
a[x%3]=x
a[y%3]=max(a[y%3],y)
for i in range(1,n):
x,y=map(int,f.readline().split())
b=[0]*3
for p in range(3):
if a[p]!=0:
b[(a[p]+x)%3]=max(b[(a[p]+x)%3],a[p]+x)
b[(a[p]+y)%3]=max(b[(a[p]+y)%3],a[p]+y)
a=b[:]
print(max(a[1:]))
Ответ:
A - 127127
B - 399762080
31) (№69 Джобс 31.08.2020) На вход программы поступает последовательность из N целых положительных чисел. Рассматриваются все пары различных элементов последовательности. Необходимо определить количество пар чисел, разность которых кратна 13, а произведение чётно.
Входные данные.
Даны два входных файла (файл 27-a.txt и файл 27-b.txt), каждый из которых содержит в первой строке количество чисел N (2 ≤ N ≤ 12000). В каждой из последующих N строк записано одно целое положительное число, не превышающее 10 000.
Программа должна вывести в первой строке одно число: количество пар чисел, разность которых кратна 13, а произведение чётно. Если подходящих пар нет, нужно вывести “NO”.
Пример организации исходных данных во входном файле:
7
55
28
15
2
42
27
16
Для указанных входных данных значением искомой суммы должно быть число 6.
В ответе укажите два числа: сначала значение искомой суммы для файла А, затем для файла B.
Предупреждение: для обработки файла B не следует использовать переборный алгоритм, вычисляющий сумму для всех возможных вариантов, поскольку написанная по такому алгоритму программа будет выполняться слишком долго.
Решение
Вариант 1 (переборный)
f=open('27-a.txt')
n=int(f.readline())
m=[]
for i in f.readlines(): m.append(int(i))
k=0
for i in range(n-1):
for j in range(i+1,n):
if (m[i]-m[j])%13==0 and m[i]*m[j]%2==0:k+=1
print(k)
Вариант 2
f=open('27-a.txt')
n=int(f.readline())
kd,knd=[0]*13,[0]*13
k=0
for i in range(n):
x=int(f.readline())
if x%2==0:
k+=kd[x%13]+knd[x%13]
kd[x%13]+=1
else:
k+=kd[x%13]
knd[x%13]+=1
print(k)
Ответ:
A - 18
B - 1821568
32) (№108 Джобс 07.09.2020) На вход программы поступает последовательность из N пар целых положительных чисел. Необходимо выбрать из каждой пары число таким образом, чтобы сумма выбранных чисел не делилась на 5, при этом была максимальной возможной.
Входные данные.
Даны два входных файла (файл A и файл B), каждый из которых содержит в первой строке количество чисел N (2 ≤ N ≤ 120000). В каждой из последующих N строк записана пара целых положительных чисел, не превышающих 100.
Программа должна вывести в первой строке одно число: полученную сумму.
Если искомую сумму получить невозможно, нужно вывести “NO”.
Пример организации исходных данных во входном файле:
7
10 9
13 17
20 24
15 30
17 18
22 19
10 14
Для указанных входных данных значением искомой суммы должно быть число 134.
В ответе укажите два числа: сначала значение искомой суммы для файла А, затем для файла B.
Предупреждение: для обработки файла B не следует использовать переборный алгоритм, вычисляющий сумму для всех возможных вариантов, поскольку написанная по такому алгоритму программа будет выполняться слишком долго.
Решение
Вариант 1
f=open('27-b.txt')
n=int(f.readline())
maxs=0
d=[10**20]*5
for i in range(n):
x,y=map(int,f.readline().split())
maxs+=max(x,y)
r=abs(x-y)
d[r%5]=min(d[r%5],r)
if maxs%5==0:maxs-=min(d[1:])
if maxs%5==0: print('No')
else: print(maxs)
Вариант 2
f=open('27-a.txt')
n=int(f.readline())
a=[0]*5
x,y=map(int,f.readline().split())
a[x%5]=x
a[y%5]=max(a[y%5],y)
for i in range(1,n):
x,y=map(int,f.readline().split())
b=[0]*5
for p in range(5):
if a[p]!=0:
b[(a[p]+x)%5]=max(b[(a[p]+x)%5],a[p]+x)
b[(a[p]+y)%5]=max(b[(a[p]+y)%5],a[p]+y)
a=b[:]
print(max(a[1:]))
Ответ:
A - 107
B - 7989169
33) (Вариант 25028412) Менеджер по работе с персоналом присваивает рейтинговый балл каждому из N кандидатов, резюме которых он изучает. Он хочет нанять двух специалистов с суммарным рейтингом не менее К баллов.
Требуется по имеющимся данным о баллах N кандидатов определить, сколько различных пар кандидатов можно выбрать так, чтобы их суммарный рейтинговый балл составлял не менее К. Две пары кандидатов считаются различными, если хотя бы один из членов пары не присутствует в другой паре. Запишите в ответе найденное количество пар.
Входные данные
Даны два входных файла (файл А и файл В), каждый из которых в первой строке содержит натуральное число К – ограничение на суммарный рейтинг двух кандидатов в баллах, а во второй - количество кандидатов N (1 < К< 10 000 000,1 < N < 10 000 000).
В каждой из следующих N строк находится одно число: рейтинговый балл соответствующего кандидата. Данные кандидатов отсортированы в порядке неубывания.
В ответе укажите два числа: сначала значение искомой величины
В ответе укажите два числа: сначала значение искомой величины
для файла А, затем — для файла В.
Типовой пример организации данных во входном файле
100
5
20
50
50
100
200
При таких исходных данных искомая величина равна 8. Первый кандидат может составлять пары с двумя последними; второй кандидат с рейтингом 50 может быть в паре с третьим, четвёртым или пятым; третий имеет такой же рейтинг, как второй, и может составлять пару с четвёртым или пятым кандидатом, которые, в свою очередь, образуют допустимую пару друг с другом.
Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов.
Предупреждение: для обработки файла В не следует использовать переборный алгоритм, вычисляющий искомую величину для всех возможных вариантов, поскольку написанная по такому алгоритму программа будет выполняться слишком долго.
Решение
f=open('27_a.txt')
k=int(f.readline())
n=int(f.readline())
s=0
m=list(map(int,f.readlines()))
maxx=max(m)
m1=[0]*(maxx+1)
for x in m: m1[x]+=1
for i in range(len(m1)-1):m1[i+1]+=m1[i]
s1=k-maxx
if s1==0:s1=1
for i in range(s1,maxx):
t=k-i
if i>=t: t=i+1
if i*2>=k:s+=sum(range(m1[i]-m1[i-1]))
s+=(m1[maxx]-m1[t-1])*(m1[i]-m1[i-1])
if maxx*2>=k:s+=sum(range(m1[maxx]-m1[maxx-1]))
print(s)
Ответ:
A - 43666
B - 1303810249487
34) (№ 13102 ) Дана последовательность целых чисел. Расстояние между элементами последовательности – это разность их порядковых номеров. Например, если два элемента стоят в последовательности рядом, то расстояние между ними равно 1, если два элемента стоят через один – расстояние равно 2 и т. д.
Необходимо выбрать из последовательности три числа так, чтобы расстояние между какими-то двумя из них было равно 2K, а сумма всех трёх чисел была максимально возможной.
Запишите в ответе найденную сумму.
Входные данные
Первая строка входного файла содержит целое число K – параметр для определения расстояния, вторая строка содержит число N – общее количество чисел в наборе (1 < 2K < N). Каждая из следующих N строк содержит одно число, не превышающее по модулю 107
Вам даны два входных файла (A и B), каждый из которых имеет описанную выше структуру. В ответе укажите два числа: сначала требуемую сумму для файла A, затем – для файла B.
Решение
f=open('27-a_13102.txt')
k=int(f.readline())*2
n=int(f.readline())
m=list(map(int,f.readlines()))
maxs=m1=m2=m3=-10**20
for i in range(n-k):
if maxs<m[i]+m[i+k]:
maxs=m[i]+m[i+k];maxp=i
if maxp>0:m1=max(m[:maxp])
m2=max(m[maxp+1:maxp+k])
if maxp<n-k-1:m3=max(m[maxp+k+1:])
maxs=maxs+max(m1,m2,m3)
print(maxs)
Ответ:
A - 205706
B - 23894
35) (№ 4203 В.Ярцев) Имеется набор данных, состоящий из троек положительных целых чисел. Необходимо выбрать из каждой тройки ровно два числа так, чтобы сумма всех выбранных чисел оканчивалась либо на 3 в семеричной записи, либо на 5 в десятичной записи, но не оканчивалась на 3 в семеричной записи и на 5 в десятичной записи одновременно, и при этом была максимально возможной. Гарантируется, что искомую сумму получить можно.
Входные данные. Даны два входных файла (файл A и файл B), каждый из которых содержит в первой строке количество троек N (N ≤ 250000). Каждая из следующих N строк содержит три натуральных числа, не превышающих 10 000.
Пример входного файла:
5
3 40 33
22 28 38
25 17 3
35 9 14
10 33 1
Для указанных входных данных значением искомой суммы должно быть число 262.
В ответе укажите два числа: сначала искомое значение для файла А, затем для файла B.
Решение
Вариант 1 (t = 57.21c.)
f=open('a1.txt')
n=int(f.readline())
a=[0]*100
xx,yy,zz=map(int,f.readline().split())
x=xx+yy;y=xx+zz;z=yy+zz
a[x%100]=x
a[y%100]=max(a[y%100],y)
a[z%100]=max(a[z%100],z)
for i in range(n-1):
b=[0]*100
xx,yy,zz=map(int,f.readline().split())
x=xx+yy;y=xx+zz;z=yy+zz
for p in range(100):
if a[p]>0:
b[(a[p]+x)%100]=max( b[(a[p]+x)%100],a[p]+x)
b[(a[p]+y)%100]=max( b[(a[p]+y)%100],a[p]+y)
b[(a[p]+z)%100]=max( b[(a[p]+z)%100],a[p]+z)
a=b[:]
max5=max3=0
for i in a:
if i%10==5 and i%7!=3: max5=max(max5,i)
for i in a:
if i%10!=5 and i%7==3: max3=max(max3,i)
print(max(max5,max3))
Вариант 2 (t = 34.82 c.)
def s7(x):
return x//7%7*10+x%7
f=open('a1.txt')
n=int(f.readline())
a=[0]*70
xx,yy,zz=map(int,f.readline().split())
x=xx+yy;y=xx+zz;z=yy+zz
a[s7(x)]=x
p=s7(y)
a[p]=max(a[p],y)
p=s7(z)
a[p]=max(a[p],z)
for i in range(n-1):
b=[0]*70
xx,yy,zz=map(int,f.readline().split())
x=xx+yy;y=xx+zz;z=yy+zz
for p in range(70):
if a[p]>0:
p1=s7(a[p]+x)
b[p1]=max( b[p1],a[p]+x)
p1=s7(a[p]+y)
b[p1]=max( b[p1],a[p]+y)
p1=s7(a[p]+z)
b[p1]=max( b[p1],a[p]+z)
a=b[:]
max5=max3=0
for i in a:
if i%10==5 and i%7!=3: max5=max(max5,i)
for i in a:
if i%10!=5 and i%7==3: max3=max(max3,i)
print(max(max5,max3))
Ответ:
A - 412891
B - 1249650958
36) (№ 2662) Имеется набор данных, состоящий из пар положительных целых чисел. Необходимо выбрать из каждой пары ровно одно число так, чтобы сумма всех выбранных чисел делилась на 3 и при этом была максимально возможной. Гарантируется, что искомую сумму получить можно. Программа должна напечатать одно число – максимально возможную сумму, соответствующую условиям задачи.
Входные данные. Даны два входных файла (файл A и файл B), каждый из которых содержит в первой строке количество пар N (1 ≤ N ≤ 100000). Каждая из следующих N строк содержит два натуральных числа, не превышающих 10 000.
Пример входного файла:
6
1 3
5 11
6 9
5 4
3 3
1 1
Для указанных входных данных значением искомой суммы должно быть число 30.
В ответе укажите два числа: сначала значение искомой суммы для файла А, затем для файла B.
Решение
f=open('a2.txt')
n=int(f.readline())
a=[0]*3
x,y=map(int,f.readline().split())
a[x%3]=x
a[y%3]=max(a[y%3],y)
for i in range(n-1):
b=[0]*3
x,y=map(int,f.readline().split())
for p in range(3):
if a[p]>0:
b[(a[p]+x)%3]=max(b[(a[p]+x)%3],a[p]+x)
b[(a[p]+y)%3]=max(b[(a[p]+y)%3],a[p]+y)
a=b[:]
print(a[0])
Ответ:
A - 109737
B - 401536407
37) (№ 4278 А.Кабанов) Набор данных представляет собой последовательность натуральных чисел. Необходимо найти количество подпоследовательностей подряд идущих чисел, сумма которых делится на 71. Гарантируется, что такие подпоследовательности существуют.
Входные данные. Даны два входных файла (файл A и файл B), каждый из которых содержит в первой строке количество чисел N (2 ≤ N ≤ 108). Каждая из следующих N строк содержит натуральное число, не превышающее 10000.
Пример входного файла:
6
12
59
45
13
31
27
В этом наборе можно выбрать последовательности 12+59 (сумма 71), 13+31+27 (сумма 71). Ответ: 2.
В ответе укажите два числа: сначала искомое значение для файла А, затем для файла B.
Решение
Вариант 1 (перебор)
f=open('a3.txt')
n=int(f.readline())
m=list(map(int,f.readlines()))
k=0
for i in range(n):
for j in range(i+1,n+1):
if sum(m[i:j])%71==0: k+=1
print(k)
Вариант 2
f=open('a3.txt')
n=int(f.readline())
m=list(map(int,f.readlines()))
a=[-1]*71
for i in range(n):
b=[-1]*71
x=m[i]
if x%71==0:b[0]=1
else:b[x%71]=0
for p in range(71):
if a[p]>-1:
if (p+x)%71==0:
b[0]=a[p]+1
else:
b[(p+x)%71]=a[p]
a=b[:]
s=0
for i in range(71):
if a[i]>0:
for i in range(a[i]+1):
s+=i
print(s)
Ответ:
A - 17
B - 70416562
38) (№ 2733) Дана последовательность N целых положительных чисел. Необходимо определить количество пар элементов этой последовательности, сумма которых делится на m = 80 и при этом хотя бы один элемент из пары больше b = 50000
Описание входных и выходных данных
Даны два входных файла (файл A и файл B), каждый из которых содержит в первой строке входных данных количество чисел N (2 ≤ N ≤ 10 000). В каждой из последующих N строк записано одно натуральное число, не превышающее 100 000.
Пример входных данных:
6
60
40
72040
30
40
120
Пример выходных данных для приведённого выше примера входных данных: 3
В ответе укажите два числа: сначала значение искомой суммы для файла А, затем для файла B.
Предупреждение: для обработки файла B не следует использовать переборный алгоритм, вычисляющий сумму для всех возможных вариантов, поскольку написанная по такому алгоритму программа будет выполняться слишком долго.
Файлы к заданию: 27a_2733.txt 27b_2733.txt
Решение
Вариант 1 (перебор)
Вариант 2
f=open('27b_2733.txt')
n=int(f.readline())
b=[0]*80;b5=[0]*80
m=list(map(int,f.readlines()))
k=0
for x in m:
if x>50000:
k+=b[(80-x%80)%80]+b5[(80-x%80)%80]
b5[x%80]+=1
else:
k+=b5[(80-x%80)%80]
b[x%80]+=1
print(k)
Ответ:
A - 48
B - 465486
39) (№ 8281 М.Шагитов) Добро пожаловать в мир удивительных числовых артефактов! Ваша миссия состоит в том, чтобы стать храбрым исследователем и отыскать магические артефакты с числовыми характеристиками. Вам необходимо найти все пары артефактов, обладающих особыми свойствами.
Согласно древним легендам, вам предстоит найти пары артефактов, сумма значений которых делится нацело на 8. Также существует еще одно условие: разница между индексами артефактов в вашем файле не должна превышать K.
Входные данные: вы получаете два файла артефактов - файл A и файл B. Каждый файл начинается с двух чисел: N - количество артефактов, и K - максимальное разрешенное расстояние между индексами артефактов (оба числа натуральные, не превышающее 107). Далее следуют N строк, каждая содержит значение числового артефакта (натуральное число, не превышающее 107).Вам требуется определить количество пар артефактов, соответствующих условиям, для файла A и файла B. В ответе укажите два числа: сначала искомое значение для файла A, затем для файла B.
Пример файла артефактов:
10
4
62
77
87
40
43
94
30
32
63
24
В данном примере условиям удовлетворяют 3 пары артефактов: (77,43), (32,24) и (40,32).
Обратите внимание, что представленный пример носит иллюстративный характер. Для выполнения задачи используйте данные из прилагаемых файлов.
Файлы к заданию: 27_A.txt 27_8281.txt
Решение
Вариант 1 (перебор)
f=open('27_a_8281.txt')
n=int(f.readline())
k=int(f.readline())
m=list(map(int,f.readlines()))
kl=0
for i in range(n-1):
if i+k+1>=n:k=n-i-1
for j in range(i+1,i+k+1):
if (m[i]+m[j])%8==0:kl+=1
print(kl)
Вариант 2
f=open('27_b_8281.txt')
n=int(f.readline())
k=int(f.readline())
m=list(map(int,f.readlines()))
b=[0]*8
kl=0
for i in range(k+1):
kl+=b[(8-m[i]%8)%8]
b[m[i]%8]+=1
for i in range(k+1,n):
b[m[i-k-1]%8]-=1
kl+=b[(8-m[i]%8)%8]
b[m[i]%8]+=1
print(kl)
Ответ:
A - 59817
B - 6236107
40) (№ 8281 М.Шагитов) Добро пожаловать в мир удивительных числовых артефактов! Ваша миссия состоит в том, чтобы стать храбрым исследователем и отыскать магические артефакты с числовыми характеристиками. Вам необходимо найти все пары артефактов, обладающих особыми свойствами.
Согласно древним легендам, вам предстоит найти пары артефактов, сумма значений которых делится нацело на 8. Также существует еще одно условие: разница между индексами артефактов в вашем файле не должна превышать K.
Входные данные: вы получаете два файла артефактов - файл A и файл B. Каждый файл начинается с двух чисел: N - количество артефактов, и K - максимальное разрешенное расстояние между индексами артефактов (оба числа натуральные, не превышающее 107). Далее следуют N строк, каждая содержит значение числового артефакта (натуральное число, не превышающее 107).Вам требуется определить количество пар артефактов, соответствующих условиям, для файла A и файла B. В ответе укажите два числа: сначала искомое значение для файла A, затем для файла B.
Пример файла артефактов:
10
4
62
77
87
40
43
94
30
32
63
24
В данном примере условиям удовлетворяют 3 пары артефактов: (77,43), (32,24) и (40,32).
Обратите внимание, что представленный пример носит иллюстративный характер. Для выполнения задачи используйте данные из прилагаемых файлов.
Файлы к заданию: 27_A.txt 27_8281.txt
Решение
Вариант 1 (перебор)
f=open('27_a_8281.txt')
n=int(f.readline())
k=int(f.readline())
m=list(map(int,f.readlines()))
kl=0
for i in range(n-1):
if i+k+1>=n:k=n-i-1
for j in range(i+1,i+k+1):
if (m[i]+m[j])%8==0:kl+=1
print(kl)
Вариант 2
f=open('27_b_8281.txt')
n=int(f.readline())
k=int(f.readline())
m=list(map(int,f.readlines()))
b=[0]*8
kl=0
for i in range(k+1):
kl+=b[(8-m[i]%8)%8]
b[m[i]%8]+=1
for i in range(k+1,n):
b[m[i-k-1]%8]-=1
kl+=b[(8-m[i]%8)%8]
b[m[i]%8]+=1
print(kl)
Ответ:
A - 59817
B - 6236107
41) (№ 6891 Г.Шапошников) Заявки на прием у начальника поступают в виде времени начала и конца планируемого приема. Будем считать, что приемы начинаются и заканчиваются в начале заданной минуты. Прием может быть проведен в том случае, если нет ни одного другого приема, который бы занимал хотя бы единицу времени, находящуюся в диапазоне времени проведения данного приема. По заданному списку заявок определите, сколько приемов удастся провести, при условии, что все заявки поступают в том порядке, в котором они представлены во входных файлах.
Входные данные. Даны два входных файла (файл A и файл B), каждый из которых в первой строке содержит натуральное число N (N ≤ 1000000) – количество заявок. Каждая из следующих N строк содержит два числа, X и Y (1 ≤ X < Y ≤ 100000000 и Y-X ≥ 10000), разделенные пробелом – время начала и время окончания планируемого приёма.
Пример входного файла:
7
100000 500000
490000 700000
500000 700000
10000 50000
60000 80000
50000 90000
710000 900000
При таких исходных данных будет проведено пять приёмов: первый, третий, четвертый, пятый и седьмой. Ответ: 5.
В ответе укажите два числа: сначала искомое значение для файла А, затем для файла B.
Решение
f=open('27_b.txt')
n=int(f.readline())
m=[[0,0]]
k=0
for i in range(n):
x,y=map(int,f.readline().split())
fl=1
for j in range(len(m)):
if m[j][0]<=x<m[j][1] or m[j][0]<=y<m[j][1] or x<=m[j][0]<=y: fl=0;break
if fl: m.append([x,y]);k+=1
print(k)
Ответ:
A - 2
B - 65
Page updated
Google Sites
Report abuse