27. Программирование

Задание 27. Программирование

ВАРИАНТ 1

Дана последовательность из N натуральных чисел. Рассматриваются все непрерывные подпоследовательности, такие что сумма элементов каждой из них кратна k = 123. Найдите среди них подпоследовательность с минимальной суммой, определите ее длину. Если таких подпоследовательностей найдено несколько, в ответе укажите количество элементов самой длинной из них.

Входные данные:

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

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

7
1
3
4
193
8
5
195

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

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

Решение и ответ

f=open('27v1234_A.txt')
p = [int(x) for x in f] #читаем файл в целочисленный массив
N = p[0] #количество элементов в массиве
k=123
del(p[0])# удаляем первый элемент массива
f.close()
s_min=10000000 # минимальной сумме присваиваем верхнее значение
l=0 # длина подпоследовательности
s=0 # переменная содержащая суммы непрерывных последовательностей
a=[0]*k # массив, содержащий суммы с одинаковыми остатками
b=[0]*k # массив, содержащий длины подпоследовательностей с одинаковыми остатками

for i in range(N):
s += p[i] # накапливаем сумму
ost = s % k # находим остаток от деления данной суммы на k
if a[ost] != 0:
d = s - a[ost] #находим разницу между текущим s и суммой с таким же остатком
if d < s_min:
l = i - b[ost] # запоминаем длину d в переменную l
if d == s_min:
l = max (l, i - b[ost]) #если последовательности имеют равные длины, находим наибольшей длины
s_min = min(s_min, d) # ищем минимальную сумму
elif ost == 0 and s < s_min: # случай, когда последовательность начинается с нулевого элемента
l = i + 1 # длина на 1 больше
s_min = s
a[ost] = s # запоминаем текущее значение суммы с таким остатком
b[ost] = i # запоминаем номер элемента с таким остатком

print(l)

Ответ:

ВАРИАНТ 2

Дана последовательность из N натуральных чисел. Рассматриваются все непрерывные подпоследовательности, такие что сумма элементов каждой из них кратна k = 321. Найдите среди них подпоследовательность с минимальной суммой, определите ее длину. Если таких подпоследовательностей найдено несколько, в ответе укажите количество элементов самой короткой из них.

Входные данные:

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

7
1
3
4
193
8
5
195

Решение и ответ

f=open('27v1234_A.txt')
p = [int(x) for x in f] #читаем файл в целочисленный массив
N = p[0] #количество элементов в массиве
k=321
del(p[0])# удаляем первый элемент массива
f.close()
s_min=10000000 # минимальной сумме присваиваем верхнее значение
l=0 # длина подпоследовательности
s=0 # переменная содержащая суммы непрерывных последовательностей
a=[0]*k # массив, содержащий суммы с одинаковыми остатками
b=[0]*k # массив, содержащий длины подпоследовательностей с одинаковыми остатками

for i in range(N):
s += p[i] # накапливаем сумму
ost = s % k # находим остаток от деления данной суммы на k
if a[ost] != 0:
d = s - a[ost] #находим разницу между текущим s и суммой с таким же остатком
if d < s_min:
l = i - b[ost] # запоминаем ее длину в переменную l
if d == s_min:
l = min (l, i - b[ost]) #если последовательности имеют равные длины, находим наименьшей длины
elif ost == 0 and s < s_min: # случай, когда последовательность начинается с нулевого элемента
l = i + 1 # длина на 1 больше
s_min = s
a[ost] = s # запоминаем текущее значение суммы с таким остатком
b[ost] = i # запоминаем номер элемента с таким остатком

print(l)

Ответ:

ВАРИАНТ 3

Дана последовательность из N натуральных чисел. Рассматриваются все непрерывные подпоследовательности, такие что сумма элементов каждой из них кратна k = 145. Найдите среди них подпоследовательность с максимальной суммой, определите ее длину. Если таких подпоследовательностей найдено несколько, в ответе укажите количество элементов самой длинной из них.

Входные данные:

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

7
1
3
4
193
8
5
195

Решение и ответ

f=open('27v1234_A.txt')
p = [int(x) for x in f] #читаем файл в целочисленный массив
N = p[0] #количество элементов в массиве
k=145
del(p[0])# удаляем первый
f.close()

s_max=0 # максимальной сумме присваиваем нижнее значение
l=0 # длина подпоследовательности
s=0 # переменная содержащая суммы непрерывных последовательностей
a=[0]*k # массив, содержащий суммы с остатками от 0 до k
b=[0]*k # массив, содержащий длины подпоследовательностей

for i in range(N):
s += p[i] # накапливаем сумму
ost = s % k # находим остаток от деления данной суммы на k
if a[ost] != 0:
d = s - a[ost] #находим разницу, которая кратна k
if d > s_max:
l = i - b[ost] # запоминаем длину d
if d == s_max:
l = max (l, i - b[ost]) #если последовательности имеют равные длины, находим наибольшей длины
s_max = max(d, s_max)
else:
a[ost] = s # сумма запоминается только если она не равна 0, чтобы последовательность была максимальной
b[ost] = i # запоминаем номер элемента с таким остатком
if ost==0 and s > s_max:
l = i + 1
s_max = s

print(l)

Ответ:

612

1497992

ВАРИАНТ 4

Дана последовательность из N натуральных чисел. Рассматриваются все непрерывные подпоследовательности, такие что сумма элементов каждой из них кратна k = 157. Найдите среди них подпоследовательность с максимальной суммой, определите ее длину. Если таких подпоследовательностей найдено несколько, в ответе укажите количество элементов самой короткой из них.

Входные данные:

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

7
1
3
4
193
8
5
195

Решение и ответ

f=open('27v1234_A.txt')

p = [int(x) for x in f] #читаем файл в целочисленный массив
N = p[0] #количество элементов в массиве
k=157
del(p[0])# удаляем первый
f.close()

for i in range(N):
s += p[i] # накапливаем сумму
ost = s % k # находим остаток от деления данной суммы на k
if a[ost] != 0:
d = s - a[ost] #находим разницу, которая кратна k
if d > s_max:
l = i - b[ost] # запоминаем длину d
if d == s_max:
l = min (l, i - b[ost]) #если последовательности имеют равные длины, находим наименьшей длины
s_max = max(d, s_max)
else:
a[ost] = s # сумма запоминается только если она не равна 0, чтобы последовательность была максимальной
b[ost] = i # запоминаем номер элемента с таким остатком
if ost == 0 and s > s_max:
l = i + 1
s_max = s

print(l)

Ответ:

601

1497991

ВАРИАНТ 5

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

Программа должна напечатать одно число - максимально возможную сумму, соответствующую условиям задачи.

Входные данные:

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

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

6
1 3
5 12
6 9
5 4
3 3
1 1
Для указанных входных данных значением искомой суммы должно быть число 33. В ответе укажите два числа: сначала значение искомой суммы для файла А, затем для файла В.

Решение и ответ

f=open('27v05_A.txt','r')
st = f.readlines() # создаем массив из строк файла
f.close()
N = int(st[0]) # записываем количество строк в переменную N
del (st[0]) # удаляем первую строку
s = 0 # создаем переменную для суммы
min_r = 10000

for i in range(N):
a, b = map(int, st[i].split()) #разделяем строку на две переменные
s += max(a,b) # накапливаем сумму из максимальных значений
m = abs (a-b) #находим разницу между значениями одной строки
if m % k !=0:
min_r=min (m, min_r) #мин. разница, которая не делится на k

if s % k!=0:
print (s)
else:
print (s - min_r)

Ответ:

639688

664195557

ВАРИАНТ 6

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

Программа должна напечатать одно число - максимально возможную сумму, соответствующую условиям задачи.

Входные данные:

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

Решение и ответ

f=open('27v06_A.txt','r')

st = f.readlines() # создаем массив из строк файла
f.close()
N = int(st[0]) # записываем количество строк в переменную N
del (st[0]) # удаляем первую строку
s = 0 # создаем переменную для суммы
min_r = 10000

for i in range(N):
a, b =map(int, st[i].split()) #разделяем строку на две переменные
s += max (a,b) # накапливаем сумму из максимальных значений
m = abs (a-b) #находим разницу между значениями одной строки
if m % k !=0:
min_r=min (m, min_r) #мин. разница, которая не делится на k

if s % k != 0:
print (s)
else:
print (s - min_r)

Ответ:

650905

666120736

ВАРИАНТ 7

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

Программа должна напечатать одно число - максимально возможную сумму, соответствующую условиям задачи.

Входные данные:

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

Решение и ответ

f=open('27v07_A.txt','r')
st = f.readlines() # создаем массив из строк файла
f.close()
N = int (st[0]) # записываем количество строк в переменную N
del (st[0]) # удаляем первую строку
s = 0 # создаем переменную для суммы
min_r = 10000
k = 35

for i in range(N):
a, b =map (int, st[i].split()) #разделяем строку на две переменные
s += max (a,b) # накапливаем сумму из максимальных значений
m = abs (a-b) #находим разницу между значениями одной строки
if m % k !=0:
min_r = min (m, min_r) #мин. разница, которая не делится на k

if s % k!=0:
print (s)
else:
print (s - min_r)

Ответ:

665848

665534337

ВАРИАНТ 8

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

Программа должна напечатать одно число - максимально возможную сумму, соответствующую условиям задачи.

Входные данные:

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

Решение и ответ

f=open('27v08_A.txt','r')
st = f.readlines() # создаем массив из строк файла
f.close()
N = int (st[0]) # записываем количество строк в переменную N
del (st[0]) # удаляем первую строку
s=0 # создаем переменную для суммы
min_r = 10000
k = 37

for i in range(N):
a, b =map(int, st[i].split()) #разделяем строку на две переменные
s+= max (a, b) # накапливаем сумму из максимальных значений
m = abs (a - b) #находим разницу между значениями одной строки
if m % k !=0:
min_r=min (m, min_r) #мин. разница, которая не делится на k

if s % k!=0:
print (s)
else:
print (s-min_r)

Ответ:

639036

664014548

ВАРИАНТ 9

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

Программа должна напечатать одно число - максимально возможную сумму, соответствующую условиям задачи.

Входные данные:

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

Решение и ответ

f=open('27v09_A.txt','r')
st = f.readlines() # создаем массив из строк файла
f.close()
N = int(st[0]) # записываем количество строк в переменную N
del (st[0]) # удаляем первую строку
s = 0 # создаем переменную для суммы
min_r = 10000
k = 39

for i in range(N):
a, b =map (int, st[i].split()) #разделяем строку на две переменные
s += max (a, b) # накапливаем сумму из максимальных значений
m = abs (a - b) #находим разницу между значениями одной строки
if m % k !=0:
min_r = min (m, min_r) #мин. разница, которая не делится на k

if s % k != 0:
print (s)
else:
print (s - min_r)

Ответ:

639036

664014548

ВАРИАНТ 10

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

Программа должна напечатать одно число - максимально возможную сумму, соответствующую условиям задачи.

Входные данные:

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

Решение и ответ

f=open('27v10_A.txt','r')
st = f.readlines() # создаем массив из строк файла
f.close()
N = int(st[0]) # записываем количество строк в переменную N
del (st[0]) # удаляем первую строку
s = 0 # создаем переменную для суммы
min_r = 10000
k = 41

for i in range(N):
a, b =map (int, st[i].split()) #разделяем строку на две переменные
s += max (a, b) # накапливаем сумму из максимальных значений
m = abs (a - b) #находим разницу между значениями одной строки
if m % k !=0:
min_r = min (m, min_r) #мин. разница, которая не делится на k

if s % k != 0:
print (s)
else:
print (s - min_r)

Ответ:

637397

664908620

ВАРИАНТ 11

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

Программа должна напечатать одно число - максимально возможную сумму, соответствующую условиям задачи.

Входные данные:

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

Решение и ответ

f=open('27v11_A.txt','r')
st = f.readlines() # создаем массив из строк файла
f.close()
N = int(st[0]) # записываем количество строк в переменную N
del (st[0]) # удаляем первую строку
s = 0 # создаем переменную для суммы
min_r = 10000
k = 43

for i in range(N):
a, b =map (int, st[i].split()) #разделяем строку на две переменные
s += max (a, b) # накапливаем сумму из максимальных значений
m = abs (a - b) #находим разницу между значениями одной строки
if m % k !=0:
min_r = min (m, min_r) #мин. разница, которая не делится на k

if s % k != 0:
print (s)
else:
print (s - min_r)

Ответ:

707992

664360575

ВАРИАНТ 12

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

Программа должна напечатать одно число - максимально возможную сумму, соответствующую условиям задачи.

Входные данные:

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

Решение и ответ

f=open('27v12_A.txt','r')
st = f.readlines() # создаем массив из строк файла
f.close()
N = int(st[0]) # записываем количество строк в переменную N
del (st[0]) # удаляем первую строку
s = 0 # создаем переменную для суммы
min_r = 10000
k = 45

for i in range(N):
a, b =map (int, st[i].split()) #разделяем строку на две переменные
s += max (a, b) # накапливаем сумму из максимальных значений
m = abs (a - b) #находим разницу между значениями одной строки
if m % k !=0:
min_r = min (m, min_r) #мин. разница, которая не делится на k

if s % k != 0:
print (s)
else:
print (s - min_r)

Ответ:

694741

664750894

ВАРИАНТ 13

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

Программа должна напечатать одно число - максимально возможную сумму, соответствующую условиям задачи.

Входные данные:

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

Решение и ответ

f=open('27v13_A.txt','r')
st = f.readlines() # создаем массив из строк файла
f.close()
N = int(st[0]) # записываем количество строк в переменную N
del (st[0]) # удаляем первую строку
s = 0 # создаем переменную для суммы
min_r = 10000
k = 47

for i in range(N):
a, b =map (int, st[i].split()) #разделяем строку на две переменные
s += max (a, b) # накапливаем сумму из максимальных значений
m = abs (a - b) #находим разницу между значениями одной строки
if m % k !=0:
min_r = min (m, min_r) #мин. разница, которая не делится на k

if s % k != 0:
print (s)
else:
print (s - min_r)

Ответ:

668506

663821071

ВАРИАНТ 14

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

Программа должна напечатать одно число - максимально возможную сумму, соответствующую условиям задачи.

Входные данные:

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

Решение и ответ

f=open('27v14_A.txt','r')
st = f.readlines() # создаем массив из строк файла
f.close()
N = int(st[0]) # записываем количество строк в переменную N
del (st[0]) # удаляем первую строку
s = 0 # создаем переменную для суммы
min_r = 10000
k = 49

for i in range(N):
a, b =map (int, st[i].split()) #разделяем строку на две переменные
s += max (a, b) # накапливаем сумму из максимальных значений
m = abs (a - b) #находим разницу между значениями одной строки
if m % k !=0:
min_r = min (m, min_r) #мин. разница, которая не делится на k

if s % k != 0:
print (s)
else:
print (s - min_r)

Ответ:

670680

661782863

ВАРИАНТ 15

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

Программа должна напечатать одно число - максимально возможную сумму, соответствующую условиям задачи.

Входные данные:

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

Решение и ответ

f = open('27v15_A.txt','r')
st = f.readlines()
f.close()

N = int(st[0])
s = 0
min_r = 1000
del(st[0])
k = 51

for i in range(N):
a, b = map (int, st[i].split())
s += min (a, b) # накапливаем сумму из минимальных значений
m = abs (a - b)
if m % k != 0:
min_r = min (m, min_r)
if s % k!=0:
print (s)
else:
print (s + min_r) #добавляем разницу

Ответ:

347392

332620649

ВАРИАНТ 16

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

Программа должна напечатать одно число - максимально возможную сумму, соответствующую условиям задачи.

Входные данные:

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

Решение и ответ

f = open('27v16_B.txt','r')
st = f.readlines()
f.close()

N = int(st[0])
s = 0
min_r = 10000
del(st[0])
k = 53

for i in range(N):
a, b = map(int, st[i].split())
s += min (a, b) # накапливаем сумму из минимальных значений
m = abs (a - b)
if m % k !=0:
min_r = min (m, min_r)

if s % k != 0:
print(s)
else:
print(s + min_r) #добавляем разницу

Ответ:

315699

334529749

ВАРИАНТ 17

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

Программа должна напечатать одно число - максимально возможную сумму, соответствующую условиям задачи.

Входные данные:

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

Решение и ответ

f = open('27v17_A.txt','r')
st = f.readlines()
f.close()

N = int(st[0])
s = 0
min_r = 1000
del(st[0])
k = 55

Ответ:

357333

333648796

ВАРИАНТ 18

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

Программа должна напечатать одно число - максимально возможную сумму, соответствующую условиям задачи.

Входные данные:

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

Решение и ответ

f = open('27v18_A.txt','r')
st = f.readlines()
f.close()

N = int(st[0])
s = 0
min_r = 1000
del(st[0])
k = 57

Ответ:

343941

333920555

ВАРИАНТ 19

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

Программа должна напечатать одно число - максимально возможную сумму, соответствующую условиям задачи.

Входные данные:

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

Решение и ответ

f = open('27v19_A.txt','r')
st = f.readlines()
f.close()

N = int(st[0])
s = 0
min_r = 1000
del(st[0])
k = 59

Ответ:

378516

333374254

ВАРИАНТ 20

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

Программа должна напечатать одно число - максимально возможную сумму, соответствующую условиям задачи.

Входные данные:

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

Решение и ответ

f = open('27v20_A.txt','r')
st = f.readlines()
f.close()

N = int(st[0])
s = 0
min_r = 1000
del(st[0])
k = 61

Ответ:

327550

334402029