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

Печать
Звезда не активнаЗвезда не активнаЗвезда не активнаЗвезда не активнаЗвезда не активна
 

ВАРИАНТ 1

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

Концерн планирует открыть молокоперерабатывающий завод при одной из ферм. Перевозить молоко разрешается на расстояние не более M. Молоко перевозят в бидонах вместимостью 15 литров каждый. Каждая ферма имеет свой набор бидонов для перевозки молока, при этом с каждой фермы на завод может быть доставлено не более одного неполного бидона. Место для возведения завода выбрано так, чтобы количество доставляемых туда бидонов с молоком было максимальным. Определите необходимое общее количество бидонов для доставки молока на этот завод.

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

Даны два входных файла (файл А и файл В), каждый из которых в первой строке содержит два числа N и (1 ≤N≤ 10000000, 1 ≤M≤ 10000000) — количество ферм и максимальное расстояние, на которое разрешено перевозить молоко с соответствующей фермы. В каждой из следующих N строк находятся два числа: номер фермы и количество литров молока (в литрах), производимых на этой ферме за сутки (все числа натуральные, количество литров молока на каждой ферме не превышает 1000).
Фермы перечислены в порядке их расположения вдоль пути, считая от нулевой отметки.

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

Типовой пример организации данных во входном файле

6 5
1 112
5 204
10 50
11 20
12 20
13 33

При таких исходных данных и вместимости бидона, составляющей 10 литров, концерну выгодно открыть молокоперерабатывающий завод в пункте 5. В этом случае количество бидонов, привозимых на завод за сутки: 12 + 21 + 5

Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов.

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

Решение и ответ
Решение перебором для файла А (1 балл)
from math import ceil
f=open('27v01_A.txt')
st = f.readlines() # создаем массив из строк файла
f.close()

N, M = map (int, st[0].split())# записываем количество ферм в переменную N, максимальное расстояние в М
del (st[0]) # удаляем первую строку

a = {} # пустой словарь, для номеров ферм и количества бидонов
for i in range(N):
    x, y = map (int, st[i].split()) # считываем построчно, разделяем на две переменные  
    a[x] = ceil (y/15) # заполняем словарь (номер фермы: количество бидонов (округление сверху))

k = 0 #обнуляем количество бидонов
z = 0 # завод в нулевом пункте
for  x in a.keys(): 
    k = max(( sum(a[x]  for x in a if abs(x - z) <= M)) , k) #суммируем бидоны на фермах на расстоянии не более М
    z = x #меняем положение завода 

print(k)

Решение для файлов А и В (2 балла). В основе кода решение Александра Павлова

from math import ceil
f=open('27v01_B.txt')
st = f.readlines() # создаем массив из строк файла
f.close()
N, M = map (int, st[0].split()) # записываем количество ферм в переменную N, расстояние в переменную М
del (st[0]) # удаляем первую строку
A = [] #резервируем массив

for i in range(N):
    a, b = map (int, st[i].split()) # считываем построчно, разделяем на две переменные  
    A.append([a, ceil(b / 15)]) #в массив запишем номера ферм и количество бидонов (округляем сверху)

r = 0 #правая граница
l = 0 #левая граница
k_max = 0 #максимальное количество бидонов
k = 0 #количество бидонов молока доставляемых на завод на расстоянии не более М

for i in range(N):
    while r < N and A[r][0] - A[i][0] <= M: #доставляем бидоны в пределах правой границы
        k += A[r][1]
        r +=1 #сдвигаем правую границу вправо на 1

    while A[i][0] - A[l][0] > M: #доставляем бидоны в пределах левой границы
        k -= A[l][1]
        l +=1 #сдвигаем левую границу вправо на 1
    k_max = max(k_max, k) #находим максимальное количество

print (k_max)

Ответ:  

1531  6362

 

ВАРИАНТ 2

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

Концерн планирует открыть молокоперерабатывающий завод при одной из ферм. Перевозить молоко разрешается на расстояние не более M. Молоко перевозят в бидонах вместимостью 20 литров каждый. Каждая ферма имеет свой набор бидонов для перевозки молока, при этом с каждой фермы на завод может быть доставлено не более одного неполного бидона. Место для возведения завода выбрано так, чтобы количество доставляемых туда бидонов с молоком было максимальным. Определите необходимое общее количество бидонов для доставки молока на этот завод.

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

Даны два входных файла (файл А и файл В), каждый из которых в первой строке содержит два числа N и (1 ≤N≤ 10000000, 1 ≤ M≤ 10000000) — количество ферм и максимальное расстояние, на которое разрешено перевозить молоко с соответствующей фермы. В каждой из следующих N строк находятся два числа: номер фермы и количество литров молока (в литрах), производимых на этой ферме за сутки (все числа натуральные, количество литров молока на каждой ферме не превышает 1000).
Фермы перечислены в порядке их расположения вдоль пути, считая от нулевой отметки.

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

Типовой пример организации данных во входном файле

6 5
1 112
5 204
10 50
11 20
12 20
13 33

При таких исходных данных и вместимости бидона, составляющей 10 литров, концерну выгодно открыть молокоперерабатывающий завод в пункте 5. В этом случае количество бидонов, привозимых на завод за сутки: 12 + 21 + 5

Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов.

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

Решение и ответ
Решение перебором для файла А

from math import ceil
f=open('27v02_A.txt')
st = f.readlines() # создаем массив из строк файла
f.close()

N, M = map (int, st[0].split())# записываем количество ферм в переменную N, максимальное расстояние в М
del (st[0]) # удаляем первую строку

a = {} # пустой словарь, для номеров ферм и количества бидонов
for i in range(N):
    x, y = map (int, st[i].split()) # считываем построчно, разделяем на две переменные  
    a[x] = ceil (y/20) # заполняем словарь (номер фермы: количество бидонов (округление сверху))

k = 0 #обнуляем количество бидонов
z = 0 # завод в нулевом пункте
for  x in a.keys(): 
    k = max(( sum(a[x]  for x in a if abs(x - z) <= M)) , k) #суммируем бидоны на фермах на расстоянии не более М
    z = x #меняем положение завода 

print(k)

Решение для файлов А и В (2 балла). В основе кода решение Александра Павлова

from math import ceil
f=open('27v02_B.txt')
st = f.readlines() # создаем массив из строк файла
f.close()
N, M = map (int, st[0].split()) # записываем количество ферм в переменную N, расстояние в переменную М
del (st[0]) # удаляем первую строку
A = [] #резервируем массив

for i in range(N):
    a, b = map (int, st[i].split()) # считываем построчно, разделяем на две переменные  
    A.append([a, ceil(b / 20)]) #в массив запишем номера ферм и количество бидонов (округляем сверху)

r = 0 #правая граница
l = 0 #левая граница
k_max = 0 #максимальное количество бидонов
k = 0 #количество бидонов молока доставляемых на завод на расстоянии не более М

for i in range(N):
    while r < N and A[r][0] - A[i][0] <= M: #доставляем бидоны в пределах правой границы
        k += A[r][1]
        r +=1 #сдвигаем правую границу вправо на 1

    while A[i][0] - A[l][0] > M: #доставляем бидоны в пределах левой границы
        k -= A[l][1]
        l +=1 #сдвигаем правую границу вправо на 1
    k_max = max(k_max, k) #находим максимальное количество

print (k_max)

Ответ:  

1208  4291

 

ВАРИАНТ 3

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

Концерн планирует открыть молокоперерабатывающий завод при одной из ферм. Молоко перевозят в бидонах вместимостью 20 литров каждый.
Стоимость перевозки молока равна произведению расстояния от фермы до завода на количество перевозимых с данной фермы бидонов с молоком.
Общая стоимость перевозки за день равна сумме стоимостей перевозок с каждой фермы до завода. 
Место для возведения завода выбрано так, чтобы общая стоимость перевозки молока была минимальной.
Определите минимальную общую стоимость доставки молока со всех ферм на завод.

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

Даны два входных файла (файл А и файл В), каждый из которых в первой строке содержит число N и (1 ≤N ≤ 10000000) — количество ферм. В каждой из следующих N строк находятся два числа: номер фермы и количество литров молока (в литрах), производимых на этой ферме за сутки (все числа натуральные, количество литров молока на каждой ферме не превышает 1000). Фермы перечислены в порядке их расположения вдоль пути, считая от нулевой отметки.

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

Типовой пример организации данных во входном файле

6 5
1 112
5 204
10 50
11 20
12 20
13 33

При таких исходных данных и вместимости бидона, составляющей 10 литров, концерну выгодно открыть молокоперерабатывающий завод в пункте 5. В этом случае количество бидонов, привозимых на завод за сутки: 12 + 21 + 5

Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов.

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

Решение и ответ
Решение перебором для файла А (1 балл)
from math import ceil
f=open('27v03_A.txt')
st = f.readlines() # создаем массив из строк файла
f.close()
N = int( st[0])# записываем количество ферм в переменную N
del (st[0]) # удаляем первую строку

a = {} # пустой словарь, для номеров ферм и количества бидонов
for i in range(N):
    x, y = map (int, st[i].split()) # считываем построчно, разделяем на две переменные 
    a[x] = ceil (y/20) # заполняем словарь (номер фермы: количество бидонов (округление сверху))

s = float('inf') #верхняя граница минимума стоимости
z = 0 # завод в нулевом пункте
for  x in a.keys(): 
    s = min (( sum(abs(x - z) *a[x]  for x in a)) , s) #суммируем стоимость
    z = x #меняем положение завода 

print(s)

Решение перебором для файла А и В (2 балла)

from math import ceil
f=open('27v03_B.txt')
st = f.readlines() # создаем массив из строк файла
f.close()
N = int (st[0]) # записываем количество ферм в переменную N
del (st[0]) # удаляем первую строку

a = {} # пустой словарь, для номеров ферм и количества бидонов 
s = 0 #  стоимость перевозки для одной фермы
k_right = 0 # обнуляем количество всех бидонов справа от завода
k_left = 0 # обнуляем количество всех бидонов слева от завода
s_min = float('inf') # верхняя граница минимальной стоимости

for i in range(N):
    x, y = map (int, st[i].split()) # считываем построчно, разделяем на две переменные
    a[x] = ceil (y/20) # заполняем словарь (номер фермы: количество бидонов (округление сверху)) 
    s  += a[x] * x # найдем стоимость доставки молока для завода в нулевом пункте
    k_right += a[x] # найдем количество всех бидонов 

# в следующем цикле мы не считаем полную стоимость доставки, а изменяем нулевую при перемещении завода вправо

y = 0 # предыдущий пункт
for x in a:
    s += k_left * (x - y) # добавляем стоимость доставки слева от завода
    s -= k_right * (x - y)  # вычитаем стоимость доставки справа от завода
    s_min = min (s_min, s) # находим минимальную стоимость
    k_left += a[x] # прибавляем бидоны справа
    k_right -= a[x] # убавляем бидоны слева
    y = x # предыдущий пункт

print (s_min)

Ответ:  

47983179 189110287146352 

 

ВАРИАНТ 4

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

Концерн планирует открыть молокоперерабатывающий завод при одной из ферм.Молоко на завод с ферм перевозят в бидонах вместимостью 15 литров каждый.
Стоимость перевозки молока равна произведению расстояния от фермы до завода на количество перевозимых с данной фермы бидонов с молоком.
Общая стоимость перевозки за день равна сумме стоимостей перевозок с каждой из ферм до завода. 
Место для возведения завода выбрано так, чтобы общая стоимость доставки молока со всех ферм была минимальной.
Определите минимальную общую стоимость доставки молока со всех ферм на завод.

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

Даны два входных файла (файл А и файл В), каждый из которых в первой строке содержит число N и (1 ≤N ≤ 10000000) — количество ферм. В каждой из следующих N строк находятся два числа: номер фермы и количество литров молока (в литрах), производимых на этой ферме за сутки (все числа натуральные, количество литров молока на каждой ферме не превышает 1000). Фермы перечислены в порядке их расположения вдоль пути, считая от нулевой отметки.

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

Типовой пример организации данных во входном файле

6 5
1 112
5 204
10 50
11 20
12 20
13 33

При таких исходных данных и вместимости бидона, составляющей 10 литров, концерну выгодно открыть молокоперерабатывающий завод в пункте 5. В этом случае количество бидонов, привозимых на завод за сутки: 12 + 21 + 5

Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов.

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

Решение и ответ
Решение перебором для файла А
from math import ceil
f=open('27v04_A.txt')
st = f.readlines() # создаем массив из строк файла
f.close()
N = int( st[0])# записываем количество ферм в переменную N
del (st[0]) # удаляем первую строку

a = {} # пустой словарь, для номеров ферм и количества бидонов
for i in range(N):
    x, y = map (int, st[i].split()) # считываем построчно, разделяем на две переменные 
    a[x] = ceil (y/20) # заполняем словарь (номер фермы: количество бидонов (округление сверху))

s = float('inf') #верхняя граница минимума стоимости
z = 0 # завод в нулевом пункте
for  x in a.keys(): 
    s = min (( sum(abs(x - z) *a[x]  for x in a)) , s) #суммируем стоимость
    z = x #меняем положение завода 

print(s)

Решение перебором для файла А и В (2 балла)

from math import ceil
f=open('27v04_B.txt')
st = f.readlines() # создаем массив из строк файла
f.close()
N = int (st[0]) # записываем количество ферм в переменную N
del (st[0]) # удаляем первую строку

a = {} # пустой словарь, для номеров ферм и количества бидонов 
s = 0 #  стоимость перевозки для одной фермы
k_right = 0 # обнуляем количество всех бидонов справа от завода
k_left = 0 # обнуляем количество всех бидонов слева от завода
s_min = float('inf') # верхняя граница минимальной стоимости

for i in range(N):
    x, y = map (int, st[i].split()) # считываем построчно, разделяем на две переменные
    a[x] = ceil (y/15) # заполняем словарь (номер фермы: количество бидонов (округление сверху)) 
    s  += a[x] * x # найдем стоимость доставки молока для завода в нулевом пункте
    k_right += a[x] # найдем количество всех бидонов 

# в следующем цикле мы не считаем полную стоимость доставки, а изменяем нулевую при перемещении завода вправо

y = 0 # предыдущий пункт
for x in a:
    s += k_left * (x - y) # добавляем стоимость доставки слева от завода
    s -= k_right * (x - y)  # вычитаем стоимость доставки справа от завода
    s_min = min (s_min, s) # находим минимальную стоимость
    k_left += a[x] # прибавляем бидоны справа
    k_right -= a[x] # убавляем бидоны слева
    y = x # предыдущий пункт

print (s_min)

Ответ:  

33058055  108822623461383

 

ВАРИАНТ 5

Дана последовательность из 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)

Ответ:  

1 3
 

ВАРИАНТ 6

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

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

Даны два входных файла (файл А и файл В), каждый из которых содержит в первой строке количество чисел 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=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)

Ответ:  

2 3
 
ВАРИАНТ 7

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

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

Даны два входных файла (файл А и файл В), каждый из которых содержит в первой строке количество чисел 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=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
        
ВАРИАНТ 8

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

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

Даны два входных файла (файл А и файл В), каждый из которых содержит в первой строке количество чисел 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=157
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 = 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
 

ВАРИАНТ 9

Имеется набор данных, состоящий из пар положительных целых чисел. Необходимо выбрать из каждой пары ровно одно число так, чтобы сумма всех выбранных чисел не делилась на 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

 

ВАРИАНТ 10

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

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

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

Даны два входных файла (файл А и файл В), каждый из которых содержит в первой строке количество пар 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('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

 
ВАРИАНТ 11

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

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

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

Даны два входных файла (файл А и файл В), каждый из которых содержит в первой строке количество пар 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('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

 
ВАРИАНТ 12

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

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

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

Даны два входных файла (файл А и файл В), каждый из которых содержит в первой строке количество пар 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('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

 
ВАРИАНТ 13

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

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

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

Даны два входных файла (файл А и файл В), каждый из которых содержит в первой строке количество пар 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('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

 
ВАРИАНТ 14

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

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

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

Даны два входных файла (файл А и файл В), каждый из которых содержит в первой строке количество пар 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('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

ВАРИАНТ 15

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

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

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

Даны два входных файла (файл А и файл В), каждый из которых содержит в первой строке количество пар 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('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

ВАРИАНТ 16

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

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

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

Даны два входных файла (файл А и файл В), каждый из которых содержит в первой строке количество пар 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('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

ВАРИАНТ 17

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

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

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

Даны два входных файла (файл А и файл В), каждый из которых содержит в первой строке количество пар 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('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

ВАРИАНТ 18

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

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

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

Даны два входных файла (файл А и файл В), каждый из которых содержит в первой строке количество пар 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('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

ВАРИАНТ 19

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

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

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

Даны два входных файла (файл А и файл В), каждый из которых содержит в первой строке количество пар 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('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

ВАРИАНТ 20

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

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

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

Даны два входных файла (файл А и файл В), каждый из которых содержит в первой строке количество пар 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('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