№ 2
Логическая функция F задаётся выражением (x → y /\ ¬ z) \/ w. На рисунке приведён частично заполненный фрагмент таблицы истинности функции F, содержащий неповторяющиеся строки. Определите, какому столбцу таблицы истинности функции F соответствует каждая из переменных x, y, z, w.
? ? ? ? F
1 0
0 1
1 1
В ответе напишите буквы x, y, z, w в том порядке, в котором идут соответствующие им столбцы. Буквы в ответе пишите подряд, никаких разделителей между буквами ставить не нужно.
print('x y z w')
for x in range(2):
for y in range(2):
for z in range(2):
for w in range(2):
if (((x<=y)and not z)or w)==False:
print(x,y,z,w)
x y z w
0 0 1 0
0 1 1 0
1 0 0 0
1 0 1 0
1 1 1 0
анализируем таблицу-результат, определяем последовательность переменных
№ 2
Логическая функция F задаётся выражением
(х → y) \/ ¬( w → z). На рисунке приведён фрагмент таблицы истинности функции F, содержащий все наборы аргументов, при которых функция F ложна. Определите, какому столбцу таблицы истинности функции F соответствует каждая из переменных w, x, y, z.
Перем. 1 Перем. 2 Перем. 3 Перем. 4 Функция F
1 0 0 1 0
0 0 0 1 0
1 0 1 1 0
В ответе напишите буквы w, x, y, z в том порядке, в котором идут соответствующие им столбцы.
print('x y z w')
for x in range(2):
for y in range(2):
for z in range(2):
for w in range(2):
a=(x<=y)
b=(not (w<=z))
if a or b==False:
print(x,y,z,w)
x y z w
1 0 0 0
1 0 1 0
1 0 1 1
Обратите внимание! В этом решении все логическое выражение мы разбиваем на части и используем логические переменные a и b. В результате запись логического выражения упрощается и снижается вероятность ошибки в логическом выражении при неправильном расставлении скобок.
ответ zywx
№ 5
На вход алгоритма подаётся натуральное число N.
Алгоритм строит по нему новое число R следующим образом.
1. Строится двоичная запись числа N.
2. Далее эта запись обрабатывается по следующему правилу:
а) если сумма цифр в двоичной записи числа чётная, то к этой записи справа дописывается 0, а затем два левых разряда заменяются на 10;
б) если сумма цифр в двоичной записи числа нечётная, то к этой записи справа дописывается 1, а затем два левых разряда заменяются на 11.
Полученная таким образом запись является двоичной записью искомого числа R.
Например, для исходного числа 610 = 1102 результатом является число 10002 = 810, а для исходного числа 410 = 1002 результатом является число 11012 = 1310. Укажите минимальное число N, после обработки которого с помощью этого алгоритма получается число R, не меньшее, чем 16.
for n in range(1,100):
s = bin(n)[2::]
if s.count('1')%2==0:
s = '10'+s[2::]+'0'
else:
s = '11'+s[2::]+'1'
if int(s,2)>=16:
print(n)
break
Рекомендации к задаче:чтобы быть уверенным на 100% в ответе необходимо запустить программу с исходным числом 610 = 1102 , программа должна выдать результат число 10002 = 810,а для исходного числа 410 = 1002 результатом должно быть число 11012 = 1310.
№ 5
На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.
1. Строится четверичная запись числа N.
2. Далее эта запись обрабатывается по следующему правилу:
а) если число N делится на 4, то к этой записи дописываются две последние четверичные цифры;
б) если число N на 4 не делится, то остаток от деления умножается на 2, переводится в четверичную запись и дописывается в конец числа.
Полученная таким образом запись является четверичной записью искомого числа R.
3. Результат переводится в десятичную запись и выводится на экран.
Например, для исходного числа 1110 = 234 результатом является число 23124 = 18210, а для исходного числа 1210 = 304 результатом является число 30304 = 20410. Укажите максимальное число N, после обработки которого с помощью этого алгоритма получается число R, меньшее 261.
def four(x):
s=''
while x>0:
s=str(x%4)+s
x=x//4
return s
for n in range(1,1000):
s=four(n)
if n%4==0:
s=s+s[-2:]
else:
ost=(n%4)*2
s=s+four(ost)
r=int(s,4)
if r<261:
print(n)
№ 6
Исполнитель Черепаха действует на плоскости с декартовой системой координат. В начальный момент Черепаха находится в начале координат, её голова направлена вдоль положительного направления оси ординат, хвост опущен. При опущенном хвосте Черепаха оставляет на поле след в виде линии. В каждый конкретный момент известно положение исполнителя и направление его движения. У исполнителя существует 6 команд: Поднять хвост, означающая переход к перемещению без рисования; Опустить хвост, означающая переход в режим рисования; Вперёд n (где n – целое число), вызывающая передвижение Черепахи на n единиц в том направлении, куда указывает её голова; Назад n (где n – целое число), вызывающая передвижение в противоположном голове направлении; Направо m (где m – целое число), вызывающая изменение направления движения на m градусов по часовой стрелке, Налево m (где m – целое число), вызывающая изменение направления движения на m градусов против часовой стрелки.
Запись Повтори k [Команда1 Команда2 … КомандаS] означает, что последовательность из S команд повторится k раз.
Черепахе был дан для исполнения следующий алгоритм:
Направо 90
Повтори 3 [Направо 45 Вперёд 10 Направо 45]
Направо 315 Вперёд 10
Повтори 2 [Направо 90 Вперёд 10].
Определите, сколько точек с целочисленными координатами будут находиться внутри области, которая ограничена линией, заданной алгоритмом. Точки на линии учитывать не следует.
from turtle import *
tracer(0)
screensize(10000,10000)
c = 20
t = Turtle()
t.lt(90)
t.up()
t.rt(90)
t.down()
for n in range(3):
t.rt(45)
t.fd(10*c)
t.rt(45)
t.rt(315)
t.fd(10*c)
for n in range(2):
t.rt(90)
t.fd(10*c)
t.up()
for x in range(-20,20):
for y in range(-30,30):
t.goto(x*c,y*c)
t.dot(3,'red')
done()
№ 8
Вася составляет 6-буквенные слова, в которых могут быть использованы только буквы В, И, Ш, Н, Я, причём буква В используется не более одного раза. Каждая из других допустимых букв может встречаться в слове любое количество раз или не встречаться совсем. Слово не должно начинаться с буквы Ш и оканчиваться гласными буквами. Словом считается любая допустимая последовательность букв, не обязательно осмысленная. Сколько существует таких слов, которые может написать Вася?
программа:
k=0
for a in 'вишня':
for b in 'вишня':
for c in 'вишня':
for d in 'вишня':
for e in 'вишня':
for f in 'вишня':
word=a+b+c+d+e+f
if word.count('в')<=1 and word[0]!='ш' and word[5]!='и' and word[5]!='я':
k+=1
print(k)
№ 9
Откройте файл электронной таблицы, содержащей в каждой строке шесть натуральных чисел. Определите количество строк таблицы, содержащих числа, для которых выполнены оба условия:
– в строке только одно число повторяется дважды;
– среднее арифметическое неповторяющихся чисел строки не больше суммы повторяющихся чисел.
f=open('9.txt')
k=0
for s in f:
a=list(map(int,s.split()))
povtorch=sum(a)-sum(set(a))
if len(set(a))==5 and ((sum(set(a))-povtorch)/4)<=2*povtorch:
k+=1
print(k)
№ 9
Откройте файл электронной таблицы, содержащей в каждой строке семь натуральных чисел. Определите количество строк таблицы, для чисел которых выполнены оба условия:
- в строке есть ровно одно число, которое повторяется дважды, и пять чисел без повторений;
- произведение трёх наименьших среди неповторяющихся чисел строки больше квадрата повторяющегося числа.
В ответе запишите только число.
f = open('9_16375.txt')
k=0
for s in f:
a = [int(x) for x in s.split()]#помещаем строку в массив
a2 = [x for x in a if a.count(x)==2]#помещаем повторяющиеся числа в массив a2
a5 = [x for x in a if a.count(x)==1]#помещаем неповторяющиеся числа в массив a5
a5.sort()#сортируем массив a5 по возрастанию
if len(a2)==2 and len(a5)==5 and (a5[0] * a5[1] * a5[2])>a2[0]**2:
k+=1
print(k)
Ответ
293
Файлы к заданию:9.xlsx
№ 12
Какая строка получится в результате применения приведённой ниже программы к строке, состоящей из 83 идущих подряд цифр 1? В ответе запишите полученную строку.
НАЧАЛО
ПОКА нашлось (11111) ИЛИ нашлось (888)
ЕСЛИ нашлось 11111)
ТО заменить (11111, 88)
ИНАЧЕ заменить (888,8)
КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА
КОНЕЦ
s = '1'*83
while '11111'in s or '888'in s:
if '11111'in s:
s=s.replace('11111','888',1)
else:
s=s.replace('888','8',1)
print(s)
№ 12
На вход программы поступает строка, начинающаяся с символа «>», а затем содержащая 39 цифр «0», n цифр «1» и 39 цифр «2», расположенных в произвольном порядке.
Определите наименьшее значение n, при котором сумма числовых значений цифр строки, получившейся в результате выполнения программы, является простым числом.
Дана программа для Редактора:
НАЧАЛО
ПОКА нашлось (>1) ИЛИ нашлось (>2) ИЛИ нашлось (>0)
ЕСЛИ нашлось (>1)
ТО заменить (>1, 22>)
КОНЕЦ ЕСЛИ
ЕСЛИ нашлось (>2)
ТО заменить (>2, 2>)
КОНЕЦ ЕСЛИ
ЕСЛИ нашлось (>0)
ТО заменить (>0, 1>)
КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА
КОНЕЦ
На вход приведённой выше программе поступает строка, начинающаяся с символа «>», а затем содержащая 39 цифр «0», n цифр «1» и 39 цифр «2», расположенных в произвольном порядке.
Определите наименьшее значение n, при котором сумма числовых значений цифр строки, получившейся в результате выполнения программы, является простым числом.
for n in range(1,1000+1):
s='>'+'0'*39+'1'*n+'2'*39
while '>1' in s or '>2' in s or'>0' in s:
if '>1' in s:
s=s.replace('>1', '22>', 1)
if '>2' in s:
s=s.replace('>2', '2>', 1)
if '>0' in s:
s=s.replace('>0', '1>', 1)
a=s.count('1')+s.count('2')*2
flag=True
for d in range(2,a):
if a%d==0:
flag=False
break
if flag==True:
print(n)
break
Ответ:5
№ 13
В терминологии сети TCP/ IP маской сети называют двоичное число, которое показывает какая часть адреса относится к адресу сети, а какая к адресу узла в этой сети. Адрес сети получается в результате применения поразрядной конъюнкции к адресу узла и маски. Сеть задана ip-адресом 255. 211.33.160 и маской сети 255.255. А. 0, где А- допустимое для записи маски число. Определите минимальное значение А, для которого для всех ip-адресов этой сети в двоичной записи ip-адреса суммарное количество единиц в левых двух байтах не менее суммарного количества единиц в правых двух байтов В ответе укажите только число.
from ipaddress import *
for k in range(16,25):
flag=True
arr=ip_network(f'255.211.33.160/{k}',0)
for ip in arr:
if f'{ip:b}'[:16].count('1') < f'{ip:b}'[16:].count('1'):
flag=False
break
if flag==True:
print(k)
print (int('11110000',2))
№ 14
Значение арифметического выражения 6 × 34**381 − 49**15 + 5 × 7 − 9 записали в системе счисления с основанием 9. Сколько цифр «6» содержится в этой записи?
x = 6*343**81-49**15+5*7-9
k=0
while x>0:
z = x % 9
if z==6:
k+=1
x=x//9
print(k)
Ответ 20
№ 14
Значение арифметического выражения 7 · 512**120 – 6 · 64**100 + 8**210 – 255 записали в системе счисления с основанием 8. Сколько цифр 0 содержится в этой записи?
программа:
x=7*512**120-6*64**100+8**210-255
k=0
while x>0:
d=x%8
if d==0:
k+=1
x=x//8
print(k)
ответ 151
№ 14
Операнды арифметического выражения записаны в системе счисления с основанием 15.
123x5 15 + 1x23315
В записи чисел переменной x обозначена неизвестная цифра из алфавита 15-ричной системы счисления. Определите наименьшее значение x, при котором значение данного арифметического выражения кратно 14. Для найденного значения x вычислите частное от деления значения арифметического выражения на 14 и укажите его в ответе в десятичной системе счисления. Основание системы счисления в ответе указывать не нужно.
for x in range(0,15,1):
s1=1*15**4+2*15**3+3*15**2+x*15+5
s2=1*15**4+x*15**3+2*15**2+3*15+3
a=s1+s2
if a%14==0:
print(a/14)
break
№ 15
Обозначим через ДЕЛ(n, m) утверждение «натуральное число n делится без остатка на натуральное число m». Для какого наибольшего натурального числа A формула
ДЕЛ(120, A) /\ ((ДЕЛ(x, 70) /\ ДЕЛ(x, 30)) → ДЕЛ(x, A)) тождественно истинна
def F(n,m):
return n % m==0
for A in range(1,1001):
flag=True
for x in range(1,1001):
a=(120 % A )== 0
b=F(x, 70)
c=F(x, 30)
d=F(x, A)
e=a and ((b and c) <= d)
if e==False:
flag=False
break
if flag==True:
print(A)
№ 15
Обозначим через m & n поразрядную конъюнкцию неотрицательных целых
чисел m и n. Например, 14 & 5 = 11102 & 01012 = 01002 = 4.
Для какого наименьшего неотрицательного целого числа А формула
x & 73 = 0 → (x & 28 ≠ 0 → x & А ≠ 0)
тождественно истинна (т. е. принимает значение 1 при любом неотрицательном целом значении переменной х)?
for A in range(1,1001):
flag=True
for x in range(1,1001):
a = x & 73 == 0
b= x & 28 != 0
c= x & A != 0
if (a <= (b<=c))==False:
flag=False
break
if flag==True:
print(A)
break
№ 15
Для какого наименьшего целого неотрицательного числа А формула
(x < A) ∨ (y < A) ∨ (x + 2y > 150)
тождественно истинна (т.е. принимает значение 1) при любых целых неотрицательных x и y.
for A in range(1,1001):
flag=True
for x in range(100):
for y in range(100):
b=x<A
c=y<A
d=x+2*y>150
f=b or c or d
if f==False:
flag=False
break
if flag==True:
print(A)
break
№ 15
На числовой прямой даны два отрезка: P = [13; 19] и Q = [17; 23]. Укажите наибольшую возможную длину такого отрезка A, что формула
¬(¬(x ∈ P) → (x ∈ Q)) → ((x ∈ A) →(¬(x ∈ Q)→(x ∈ P)))
тождественно истинна, то есть принимает значение 1 при любых x.
def P(x):
return 13<=x<=19
def Q(x):
return 17<=x<=23
def A(x):
return False
x = 11
while x <= 24:
a = (not(P(x))) <= Q(x)
b = (not(Q(x))) <= P(x)
c = A(x) <= b
F = (not(a)) <= c
print(x, F)
x += 0.25
№ 16
Алгоритм вычисления значения функции F(n), где n - натуральное число, задан
следующими соотношениями:
F(n) = 0, при n <= 1
F(n) = 2 * F(n-1), при n > 1 и n - нечетное
F(n) = F(n-1) + 1, при n > 1 и n - четное
Найти F(27)
def F(n):
if n <=1:
return 0
elif n % 2 != 0:
return 2*F(n-1)
elif n % 2 == 0:
return F(n-1)+1
print(F(27))
№ 16
Алгоритм вычисления значения функции F(n), где n – натуральное число,задан следующими соотношениями:
F(n) = 1 при n = 1;
F(n) = n + F(n − 1), если n чётно;
F(n) = 2 × F(n − 2), если n > 1 и при этом n нечётно.
Чему равно значение функции F(24)?
def F(n):
if n==1:
return 1
elif n%2==0:
return n+F(n-1)
else:
return 2*F(n-2)
print(F(24))
ответ 2072
№ 16
Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями:
F(n) = 1 при n = 1;
F(n) = n × F(n − 1), если n > 1.
Чему равно значение выражения F(2023) / F(2020)?
1 вариант
def F(n):
a=[0,1]
for i in range (2,n+1):
a.append(a[i-1]*i)
return a[n]
print (F(2023)/F(2020))
2 вариант
import sys
sys.setrecursionlimit(5000)
def F(n):
if n ==1:
return 1
if n>1:
return n*F(n-1)
print(F(2023)/F(2020))
3 вариант
F(2023)=2023*F(2022)=2023*2022*F(2021)=2023*2022*2021*F(2020)
F(2023)/F(2020)=(2023*2022*2021*F(2020))/F(2020)=2023*2022*202
№ 17
В файле 17-1.txt содержится последовательность целых чисел.Элементы последовательности могут принимать целые значения от -10 000 до 10 000 включительно. Определите и запишите в ответе сначала количество пар элементов последовательности,в которых хотя бы одно число делится на 7, а другое при этом не делится на 17. Затем - минимальную из сумм элементов таких пар.
В данной задаче под парой подразумевается два идущих подряд элемента последовательности. Например, для последовательности
-45; 14; 22; -21; 34 ответом будет пара чисел: 3 и -31.
f=open('17-1.txt')
a = []
for s in f:
a.append(int(s))
k=0
s=0
smin=0
for i in range(len(a)-1):
if a[i]%7==0 and a[i+1]%17!=0 or a[i]%17!=0 and a[i+1]%7==0:
k+=1
s=a[i]+a[i+1]
if s<smin:
smin=s
print(k,smin)
№ 17
Определите количество пар, в которых хотя бы один из двух элементов делится на 3 и хотя бы один из двух элементов меньше среднего арифметического всех чётных элементов последовательности. Выведите сначала количество найденных пар, а затем – максимальную сумму элементов таких пар.
f=open('17.txt')
a=[]
for s in f:
a.append(int(s))
s=0
for i in range(len(a)):
if a[i]%2==0:
s+=a[i]
sr=s/len(a)
k=0
sumpr=0
maxsum=0
for i in range(len(a)-1):
if (a[i]%3==0 or a[i+1]%3==0) and (a[i]<sr or a[i+1]<sr):
k+=1
sumpr=a[i]+a[i+1]
maxsum=max(maxsum, sumpr)
print(k,maxsum)
№ 17
a=[]
f=open('17_7596.txt')
for s in f:
a.append(int(s))
mina=10**8
count=0
mins=10**8
for x in a:
if 100 <= x <= 999 and x%10==5 and mina > x:
mina = x
for i in range(len(a)-1):
b=100 <= a[i] <= 999
c=100 <= a[i+1] <= 999
d=(a[i]+a[i+1])%mina==0
if ((b==1 and c==0) or (b==0 and c==1)) and d==1:
count+=1
mins=min(mins, (a[i]+a[i+1]))
print(count, mins)
№ 17
В файле содержится последовательность целых чисел. Элементы последовательности могут принимать целые значения от –10 000 до 10 000 включительно. Определите количество пар последовательности, в которых только одно число оканчивается на 3, а сумма квадратов элементов пары не меньше квадрата максимального элемента последовательности, оканчивающегося на 3. В ответе запишите два числа: сначала количество найденных пар, затем максимальную из сумм квадратов элементов таких пар. В данной задаче под парой подразумевается два идущих подряд элемента последовательности.
a=[]
f=open('17.txt')
k=0
max3=-1000000
maxsp=-10**20
for s in f:
a.append(int(s))
#print (a)
for i in range (len (a)):
if a[i]%10==3 and a[i] > max3:
max3=a[i]
#print(max3)
for i in range (len(a)-1):
sp= a[i]**2+a[i+1]**2
if ((abs(a[i])%10==3 and abs(a[i+1])%10!=3) or\
(abs(a[i])%10!=3 and abs(a[i+1])%10==3)) and sp>= max3**2:
k+=1
#print(a[i],a[i+1])
maxsp=max(maxsp,sp)
print(k,maxsp)
№ 17
В файле содержится последовательность натуральных чисел. Элементы последовательности могут принимать целые значения от 1 до 100 000 включительно. Определите количество пар последовательности, в которых хотя бы одно из чисел больше чем максимальный элемент последовательности, кратный 11. Гарантируется, что такой элемент в последовательности есть. В ответе запишите количество найденных пар, затем минимальную из сумм элементов таких пар.
В данной задаче под парой подразумевается два идущих подряд элемента последовательности.
f=open('17.txt')
a=[]
ans=[]
for s in f:
a.append(int(s))
max11=-100000
for x in a:
if x%11==0:
max11=max(max11,x)
for i in range(len(a)-1):
if a[i]>max11 or a[i+1]>max11:
ans.append(a[i]+a[i+1])
print(len(ans),min(ans))
№ 17
В файле содержится последовательность натуральных чисел. Элементы последовательности могут принимать целые значения от 1 до 100 000 включительно. Определите количество троек последовательности, в которых только одно из чисел является четырёхзначным, а сумма элементов тройки не меньше максимального элемента последовательности, оканчивающегося на 15. В ответе запишите количество найденных троек, затем максимальную из сумм элементов таких троек. В данной задаче под тройкой подразумевается три идущих подряд элемента последовательности.
f=open('17_2023.txt')
a=[]
for s in f:
a.append(int(s))
max15=-1
for i in range(len(a)):
if a[i]%100==15:max15=max(max15,a[i])
print(max15)
k=0
maxs=-1
for i in range(len(a)-2):
ch1=ch2=ch3=0
if 1000<=a[i]<=9999:ch1=1
if 1000<=a[i+1]<=9999:ch2=1
if 1000<=a[i+2]<=9999:ch3=1
b=[ch1,ch2,ch3]
s=a[i]+a[i+1]+a[i+2]
if b.count(1)==1 and s>=max15:
k+=1
maxs=max(s,maxs)
print(k,maxs)
№ 17
Файл содержит последовательность натуральных чисел, не превышающих 100 000. Назовём тройкой три идущих подряд элемента последовательности.
Определите количество троек, для которых выполняются следующие условия:
– ровно два числа в тройке четырёхзначные;
– хотя бы одно число в тройке делится на 5;
– сумма элементов тройки больше максимального последовательности, запись которого заканчивается на 17 (Гарантируется, что в последовательности есть хотя бы один элемент, запись которого заканчивается на 17.)
В ответе запишите два числа: сначала количество найденных троек, затем максимальную величину суммы элементов этих троек.
f = open('17_13088.txt')
a = []
for s in f:
a.append(int(s))
maxx = 0
for x in a:
if x % 100 == 17:
maxx = max(maxx,x)
k = 0
ans = []
for i in range(len(a)-2):
x,y,z = a[i],a[i+1],a[i+2]
if (((len(str(x)) == 4) + (len(str(y)) == 4) + (len(str(z)) == 4)) == 2) and (x%5 == 0 or y%5 == 0 or z%5 == 0) and ((x+y+z) > maxx):
ans.append(x+y+z)
print(len(ans),max(ans))
№ 17
В файле содержится последовательность целых чисел. Элементы последовательности могут принимать целые значения от –100 000 до 100 000 включительно. Определите количество четвёрок элементов последовательности, в которых или только одно из чисел или все четыре числа являются двузначным, а сумма элементов четвёрки не меньше максимального элемента последовательности, оканчивающегося на 68.
В ответе запишите количество найденных четвёрок чисел, затем максимальную из сумм элементов таких четвёрок.
В данной задаче под четвёркой подразумевается четыре идущих подряд элемента последовательности.
f = open('17_11949.txt')
a = []
for s in f:
a.append(int(s))
maxx = -100000000
for x in a:
if x % 100 == 68:
maxx = max(maxx,x)
ans = []
for i in range(len(a) - 3):
x,y,z,w = a[i],a[i+1],a[i+2],a[i+3]
pr = ()
if ((((len(str(abs(x))) == 2) + (len(str(abs(y))) == 2) + (len(str(abs(z))) == 2) + (len(str(abs(w))) == 2)) == 1) or \
(((len(str(abs(x))) == 2) + (len(str(abs(y))) == 2) + (len(str(abs(z))) == 2) + (len(str(abs(w))) == 2)) == 4)) and (x+y+z+w) >= maxx :
ans.append(x+y+z+w)
print(len(ans),max(ans))
№ 19-21
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч (по своему выбору) два камня, или увеличить количество камней в куче в два раза. Например, пусть в одной куче 10 камней, а в другой 5 камней; такую позицию в игре будем обозначать (10, 5). Тогда за один ход можно получить любую из четырёх позиций: (12, 5), (20, 5), (10, 7), (10, 10). Для того чтобы делать ходы, у каждого игрока есть неограниченное количество камней.
Игра завершается в тот момент, когда произведение количеств камней в кучах становится не менее 123. Победителем считается игрок, сделавший последний ход, т.е. первым получивший такую позицию, при которой произведение числа камней в кучах будет 123 или более.
В начальный момент в первой куче было 3 камня, во второй куче - S камней; 1 ≤ S ≤ 40.
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.
Найдите максимальное значение S, при котором Ваня выигрывает своим первым ходом после неудачного хода Пети.
Задание 20.
Для игры, описанной в предыдущем задании, найдите два наибольших значения S, при которых у Пети есть выигрышная стратегия, причём одновременно выполняются два условия:
• Петя не может выиграть за один ход;
• Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.
Найденные значения укажите в порядке возрастания.
Задание 21.
Для игры, описанной в задании 19, найдите наибольшее значение S, при котором одновременно выполняются два условия:
• у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;
• у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.
def f(a,b,m):
if a*b >= 123: return m%2 == 0
if m == 0: return 0
h = [f(a+2,b,m-1),f(a*2,b,m-1),f(a,b+2,m-1),f(a,b*2,m-1)]
return any(h) if (m-1)%2 == 0 else all(h)
print('19)', [s for s in range(1,41) if f(3,s,2)])
print('20)', [s for s in range(1,41) if not f(3,s,1) and f(3,s,3)])
print('21)', [s for s in range(1,41) if not f(3,s,2) and f(3,s,4)])
№ 22
Ниже записана программа. Получив на вход число x, эта программа печатает два числа a и b. При каком наименьшем значении x после выполнения программы на экран будет #выведено два числа 10, а затем 6
for x in range(1,1001):
answer=x
a,b=0,0
while x > 0:
c = x % 10
a = a + c
if b<c:
b=c
x = x // 10
if a==10 and b==6:
print(answer)
break
Ответ 46
№ 23
Исполнитель Минус преобразует число на экране.
У исполнителя есть две команды, которым присвоены номера:
1. Вычесть 2
2. Вычесть 5
Первая команда уменьшает число на экране на 2, вторая уменьшает это число на 5. Программа для исполнителя Минус – это последовательность команд. Сколько существует программ, которые число 23 преобразуют в число 2?
решение с помощью ЭТ:
https://docs.google.com/spreadsheets/d/1uwwtZo4XvvEw55EGjAF92EXVzhe5Z7tdutnfHXbD9Os/edit?usp=sharing
решение с помощью динамического программирования:
def task23(start,end):
if start==end:
return 1
if start< end:
return 0
return task23(start -2,end)+task23(start-5,end)
print(task23(23,2))
ответ 29
Примечание
Если в условии есть запрещенное число, в функцию добавляем еще один условный оператор:
If x==10:
return 0
Если траектория вычислений обязательно должна содержать число 10: последняя строка функции записывается так:
Return task23(23,10)*task23(10,2)
№ 23
Разрешенные команды исполнителя калькулятор Прибавь 1,Прибавь 2,Умножь на 3. Сколько существует программ, которые преобразуют число 1 в число 15, при этом траектория вычислений содержит число 10, но не содержит число 14.
def F( start, end ):
if start==end:
return 1
if start>end:
return 0
if start==14:
return 0
return F(start+1,end) + F(start+2,end)+F(start*3,end)
print(F(1,10)*F(10,15))
№ 24
Текстовый файл 24_2.txt'состоит не более чем из 106 символов X, Y и Z. Определите максимальное количество идущих подряд символов, среди которых каждые два соседних различны.
f=open('24_2.txt')
k,maxl=1,1
s=f.readline()
for i in range(len(s)-1):
if s[i]!=s[i+1]:
k+=1
if k>maxl:
maxl=k
else:
k=1
print(maxl)
№ 24
определите максимальное количество идущих подряд символов, среди которых не более одной буквы A
f=open('24-10.txt')
maxl=0
for s in f:
s=s.split('A')
print(s)
for i in range(len(s)-1):
l=len(s[i])+1+len(s[i+1])
maxl=max(maxl,l)
print(maxl)
№ 24
найти максимальную длину строки в которой символы A и С не стоят рядом
f=open('24-9.txt')
k=0
maxk=0
for s in f:
s=s.replace('AC', 'A C')
s=s.replace('CA', 'C A')
for i in range(len(s)):
if s[i]!=' ':
k+=1
maxk=max(maxk,k)
else:
k=0
print(maxk)
№ 24
найти максимальную длину строки в которой все соседние символы различны
f=open('242021.txt')
k=1
maxk=-1
for s in f:
for i in range(len(s)-1):
if s[i]!=s[i+1]:
k+=1
if k>maxk:
maxk=k
else:
k=1
print(maxk)
№ 24
Определите максимальное количество идущих подряд символов, среди которых нет ни одной буквы A и при этом не менее трёх букв E.
f=open('24-test.txt')
maxl=0
for s in f:
s=s.split('A')
print(s)
maxl=-1
for i in range(len(s)-1):
if s[i].count('E')>=3:
l=len(s[i])
maxl=max(maxl,l)
print(maxl)
№ 24
Текстовый файл 24-181.txt содержит строку из заглавных латинских букв и точек, всего не более чем из 106 символов. Определите максимальное количество идущих подряд символов, среди которых не более 5 точек.
f=open('24-181.txt')
d=f.readline()
l=len(d)
max=0
k=0
m=0
i=0
r=0
while i<l:
while m<=6:
if d[i]!='.':
k=k+1
else:
m=m+1
if m==5:
r=r+1
i=i+1
if i==l:
break
if max<k:
max=k
m=0
k=r
r=0
print(max)
№ 24
Текстовый файл состоит не более чем из 1200000 символов, которые являются прописными буквами латинского алфавита. Определите максимальное количество идущих подряд символов, среди которых нет символов G, W, P.
Для выполнения этого задания следует написать программу.
f=open('test.txt')
for s in f:
s=s.replace('G',' ')
s=s.replace('W',' ')
s=s.replace('P',' ')
s=s.split(' ')
print(s)
maxl=0
for x in s:
l=len(x)
maxl=max(l,maxl)
print(maxl)
№ 24
Текстовый файл состоит не более чем из 1200000 символов, которые являются прописными буквами латинского алфавита. Определите максимальное количество идущих подряд символов, среди которых нет подстроки XYZ.
Для выполнения этого задания следует написать программу.
f=open('test.txt')
for s in f:
s=s.replace('XYZ','XY YZ')
s=s.split(' ')
print(s)
maxl=0
for x in s:
l=len(x)
maxl=max(l,maxl)
print(maxl)
№ 24
Текстовый файл состоит не более чем из 1 200 000 символов X, Y, и Z. Определите максимальное количество идущих подряд символов, среди которых нет подстроки XZZY. Для выполнения этого задания следует написать программу.
F = open('24.txt')
maxl=3
k=3
for s in F:
for i in range(len(s)-2):
if s[i:i+4]!='XZZY':
k += 1
if k > maxl:
maxl=k
else:
k=3
print(maxl)
Ответ:1713
№ 24
Текстовый файл состоит из символов A, B и цифр 1, 2.
Определите максимальное количество идущих подряд троек символов вида двузначное число + буква в прилагаемом файле.
Для выполнения этого задания следует написать программу.
f=open('test.txt')
for s in f:
s=s.replace('2','1')
s=s.replace('B','A')
s=s.replace('11A','*')
s=s.replace('1',' ')
s=s.replace('A',' ')
s=s.split(' ')
print(s)
maxl=0
for x in s:
l=len(x)
maxl=max(l,maxl)
print(maxl)
№ 24
Текстовый файл состоит не более, чем из 1 200 000 прописных символов латинского алфавита. Определите максимальное количество идущих подряд символов, среди которых любые два символа из набора Q, R, S в различных комбинациях (с учётом повторений) не стоят рядом.
Для выполнения этого задания следует написать программу.
for s in f:
s=s.replace('QQ', ' ')
s=s.replace('QR', ' ')
s=s.replace('RQ', ' ')
s=s.replace('RR', ' ')
s=s.replace('RS', ' ')
s=s.replace('QS', ' ')
s=s.replace('SR', ' ')
s=s.replace('SQ', ' ')
s=s.replace('SS', ' ')
s=s.split(' ')
for i in range(len(s)):
l=len(s[i])
if l > maxl:
maxl = l
print(maxl+2)
Текстовый файл состоит из символов A, B, C, D, E, F и G.
Определите в прилагаемом файле минимальное количество идущих подряд символов (длину непрерывной подпоследовательности), среди которых символ A встречается не более 700 раз, а символ E не встречается совсем.
f=open('24var04.txt').readline()
s=f.split('E')
maxlen = 0
for x in s:
if x.count('A') <= 700:
lenn = len(x)
maxlen = max(maxlen,lenn)
else:
x = x.split('A')
for i in range(len(x)-700):
c = 'A'.join(x[i:i+701])
maxlen = max(maxlen,len(c))
print(maxlen)
№ 25
Среди чисел больших 500000 и R, где R сумма всех делителей включая 1 и само число при этом R оканчивается на 4. Вывести 5 таких чисел и их R
k=0
for x in range(5*10**5+1,5*10**5+100):
R=0
for d in range (1,int(x**0.5)):
if x%d==0:
R=R+d+x//d
if d*d==x:
R+=d
if R%10==4:
print(x,R)
k+=1
if k==5:
break
№ 25
Пусть M (N) – сумма двух наибольших различных натуральных делителей натурального числа N, не считая самого числа. Если у числа N меньше двух таких делителей, то M (N) считается равным 0.Найдите 5 наименьших натуральных чисел, превышающих 10 000 000, для которых
0 < M (N) < 10 000.
kx=0
for x in range(1*10**7+1,1*10**7+10000):
k=0
s=0
for d in range(2,int(x**0.5)):
if x%d==0:
s=s+x//d
k+=1
if k==2:
break
if 0<s<10000:
print(x)
kx+=1
if kx==5:
break
#10000043
#10000117
#10000153
#10000163
#10000183
№ 25
Пусть M – сумма минимального и максимального натуральных делителей целого числа, не считая единицы и самого числа. Если таких делителей у числа нет, то считаем значение M равным нулю. Напишите программу, которая перебирает целые числа, большие 452 021, в порядке возрастания и ищет среди них такие, для которых значение M при делении на 7 даёт в остатке 3. Вывести первые 5 найденных чисел и соответствующие им значения M.
Формат вывода: для каждого из 5 таких найденных чисел в отдельной строке сначала выводится само число, затем – значение М. Строки выводятся в порядке возрастания найденных чисел. Например, для числа 20 М = 2 + 10 = 12. Количество строк в таблице для ответа избыточно.
k=0
for n in range(452021,452201+1000):
a=[]
d=2
while d*d<n:
if n%d==0:
a.append(d)
a.append(n//d)
break
d+=1
if sum(a)%7==3:
print(n,sum(a))
k+=1
if k==5:
break
Ответ:
452021 2250
452025 150678
452029 23810
452034 226019
452048 226026
№ 25
Назовём маской числа последовательность цифр, в которой также могут встречаться следующие символы:
— символ «?» означает ровно одну произвольную цифру;
— символ «*» означает любую последовательность цифр произвольной длины; в том числе «*» может задавать и пустую последовательность.
Например, маске 123*4?5 соответствуют числа 123405 и 12300405.
Среди натуральных чисел, не превышающих 108, найдите все числа, соответствующие маске 2*5443?1, делящиеся на 23 без остатка.
В ответе запишите в первом столбце таблицы все найденные числа в порядке возрастания, а во втором столбце — соответствующие им результаты деления этих чисел на 23.
Количество строк в таблице для ответа избыточно.
for x in range (23,10**8+1,23):
s=str(x)
if s[0]=='2' and s[-1]=='1'\
and s[-6:-2]=='5443' and x%23==0:
print(x,x//23)
№ 25
Назовём маской числа последовательность цифр, в которой также могут встречаться следующие символы:
– символ «+» означает ровно одну произвольную цифру;
– символ «#» означает любую последовательность цифр произвольной длины; в том числе «#» может задавать и пустую последовательность.
Например, маске 123#4+5 соответствуют числа 123405 и 12300405.
Среди натуральных чисел, не превышающих 106, найдите все числа, делящиеся на 23 без остатка, для которых их наибольший делитель, не равный самому числу, соответствует маске #6215.
В ответе запишите в первом столбце таблицы все найденные числа в порядке возрастания, а во втором столбце – соответствующие им наибольшие делители, не равные самим числам.
from fnmatch import *
def F(x):
y = 0
for d in range(2,x):
if x % d == 0:
y = x//d
break
return y
for x in range(23,10**6,23):
z = F(x)
if fnmatch(str(z), '*6215'):
print(x,z)
№ 25
Назовём маской числа последовательность цифр, в которой также могут встречаться следующие символы:
символ «?» означает ровно одну произвольную цифру;
символ «*» означает любую последовательность цифр произвольной длины; в том числе «*» может задавать и пустую последовательность.
Например, маске 123*4?5 соответствуют числа 123405 и 12300405.
Среди натуральных чисел, не превышающих 107, найдите все простые числа, соответствующие маске 3?1111*.
В ответе запишите все найденные числа в порядке возрастания.
Количество строк в таблице для ответа избыточно.
from fnmatch import *
def F(x):
for d in range(2,x):
if x % d == 0:
return False
return True
for x in range(1,10**7):
if fnmatch(str(x), '3?1111*') and F(x) == 1:
print(x)
№ 27
Дана последовательность целых чисел. Необходимо найти максимально возможную сумму её непрерывной подпоследовательности, в которой количество положительных нечётных элементов кратно k = 30.
f=open('27-A.txt')
n=int(f.readline())
min_ps=[100000000000]*30
min_ps[0]=0
s=0
kcp=0
ans=-1000000000
for i in range(n):
x=int(f.readline())
s+=x
if x%2==0 and x>0:
kcp+=1
if (s-min_ps[kcp%30])>ans:
ans=s-min_ps[kcp%30]
if s<min_ps[kcp%30]:
min_ps[kcp%30]=s
print(ans)
№ 27
Метеорологическая станция ежеминутно снимали показания прибора в течение N минут (N – целое число), которое измеряет количество осадков в условных единицах за минуту, предшествующую снятию показаний. Необходимо найти максимальную сумму двух показаний, между которыми прошло не менее K минут.
Входные данные
Даны два входных файла (файл A и файл B), каждый из которых
в первой строке содержит число K – минимальное время, которое должно пройти между двумя снятиями показаний. Во второй строке число N (1 ≤ N ≤ 10 000 000, N > K) – количество измерений показателя. В каждой из следующих N строк находятся одно число: количество осадков (все числа неотрицательные, не превышающие 10 000 000). Числа указаны в порядке снятия показаний прибора, начиная с первой минуты.
В ответе укажите два числа: сначала значение искомой величины для файла А, затем – для файла B.
Типовой пример организации данных во входном файле
3
5
15
2
0
10
30
При таких исходных данных, когда минимальное время между двумя снятиями показаний составляет 3 минуты, максимальная сумма показаний равна 45.
Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов.
Предупреждение: для обработки файла B не следует использовать переборный алгоритм, вычисляющий сумму для всех возможных вариантов, поскольку написанная по такому алгоритму программа будет выполняться слишком долго.
Файлы к заданию:27_A.txt 27_B.txt
Показать ответ
19974 18469835
f = open('27_B_7627.txt')
k = int(f.readline())
n = int(f.readline())
a = [int(x) for x in f]
max1,maxs = -10000000000,-10000000000
for i in range(k,len(a)):
max1 = max(max1,a[i-k])
maxs = max(maxs, max1 + a[i])
print(maxs)
№ 27
Имеется набор данных, состоящий из троек положительных целых чисел. Необходимо выбрать из каждой тройки ровно одно число так, чтобы сумма всех выбранных чисел не делилась на k = 109 и при этом была максимально возможной. Гарантируется, что искомую сумму получить можно. Программа должна напечатать одно число – максимально возможную сумму, соответствующую условиям задачи.
Входные данные.
Даны два входных файла (файл A и файл B), каждый из которых содержит в первой строке количество троек N (1 ≤ N ≤ 1 000 000). Каждая из следующих N строк содержит три натуральных числа, не превышающих 12 000.
Пример организации исходных данных во входном файле:
6
1 3 7
5 12 6
6 9 11
5 4 8
3 5 4
1 1 1
Для указанных входных данных, в случае, если k = 5, значением искомой суммы является число 44.
В ответе укажите два числа: сначала значение искомой суммы для файла А, затем для файла B. Предупреждение: для обработки файла B не следует использовать переборный алгоритм, вычисляющий сумму для всех возможных вариантов, поскольку написанная по такому алгоритму программа будет выполняться слишком долго.
f = open('27_B.txt')
n=int(f.readline())
sum_final = 0
min_razn=100000000000
for i in range(n):
x,y,z=map(int,f.readline().split())
troiki=[x,y,z]
troiki.sort()
sum_final+=troiki[2]
if (troiki[2] -troiki[1])% 109!=0 and (troiki[2] -troiki[1])<min_razn:
min_razn=troiki[2] -troiki[1]
if (troiki[2] -troiki[0])% 109!=0 and (troiki[2] -troiki[0])<min_razn:
min_razn=troiki[2] -troiki[1]
print(sum_final-min_razn)
ответ 8819096369
№ 27
Метеорологическая станция ежеминутно снимали показания прибора в течение N минут (N – целое число), которое измеряет количество осадков в условных единицах за минуту, предшествующую снятию показаний. Необходимо найти максимальную сумму двух показаний, между которыми прошло не менее K минут.
Входные данные: Даны два входных файла (файл A и файл B), каждый из которых в первой строке содержит число K – минимальное время, которое должно пройти между двумя снятиями показаний. Во второй строке число N (1 ≤ N ≤ 10 000 000, N > K) – количество измерений показателя. В каждой из следующих N строк находятся одно число: количество осадков (все числа неотрицательные, не превышающие 10 000 000). Числа указаны в порядке снятия показаний прибора, начиная с первой минуты.
В ответе укажите два числа: сначала значение искомой величины для файла А, затем – для файла B.
Типовой пример организации данных во входном файле
3
5
15
2
0
10
30
При таких исходных данных, когда минимальное время между двумя снятиями показаний составляет 3 минуты, максимальная сумма показаний равна 45.
Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов.
Предупреждение: для обработки файла B не следует использовать переборный алгоритм, вычисляющий сумму для всех возможных вариантов, поскольку написанная по такому алгоритму программа будет выполняться слишком долго.
Файлы к заданию:27_A.txt 27_B.txt
f = open('27_B_7627.txt')
k = int(f.readline())
n = int(f.readline())
a = [int(x) for x in f]
max1,maxs = -10000000000,-10000000000
for i in range(k,len(a)):
max1 = max(max1,a[i-k])
maxs = max(maxs, max1 + a[i])
print(maxs)
ответ 19974 18469835
№ 27
По каналу связи передаётся последовательность целых чисел – показания прибора. В течение N мин. (N – натуральное число) прибор ежеминутно регистрирует значение силы тока (в условных единицах) в электрической сети и передаёт его на сервер.
Определите три таких переданных числа, чтобы между моментами передачи любых двух из них прошло не менее K мин., а сумма этих чисел была минимально возможной. Запишите в ответе найденную сумму.
Входные данные
Даны два входных файла (файл A и файл B), каждый из которых в первой строке содержит натуральное число K – минимальное количество минут, которое должно пройти между моментами передачами любых двух из трёх показаний, а во второй – количество переданных показаний N (1 ≤ N ≤ 10 000 000, N > K). В каждой из следующих N строк находится одно натуральное число, не превышающее 10 000 000, которое обозначает значение силы тока в соответствующую минуту.
Запишите в ответе два числа: сначала значение искомой величины для файла А, затем – для файла B.
Типовой пример организации данных во входном файле
2
6
15
14
20
23
21
10
При таких исходных искомая величина равна 45 – это сумма значений, зафиксированных на первой, третьей и шестой минутах измерений.
Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов.
Файлы к заданию:27_A.txt27_B.txt
f = open('27_B_9755.txt')
k = int(f.readline())
n = int(f.readline())
b = [int(x) for x in f.readlines()]
minsum = 100000000000000
minum1 = 100000000000000
minum2 = 100000000000000
for i in range(2*k, n-k):
minum1 = min(minum1, b[i-2*k])
minum2 = min(minum2, minum1+b[i-k])
minsum = min(minsum, b[i] + minum2)
print(minsum)
Ответ 166998 15102
№ 27
Менеджер по работе с персоналом присваивает рейтинговый балл каждому из N кандидатов, резюме которых он изучает. Он хочет нанять двух специалистов с суммарным рейтингом не менее К баллов.
Требуется по имеющимся данным о баллах N кандидатов определить, сколько различных пар кандидатов можно выбрать так, чтобы их суммарный рейтинговый балл составлял не менее К. Две пары кандидатов считаются различными, если хотя бы один из членов пары не присутствует в другой паре. Запишите в ответе найденное количество пар.
Входные данные
Даны два входных файла (файл А и файл В), каждый из которых в первой строке содержит натуральное число К — ограничение на суммарный рейтинг двух кандидатов в баллах, а во второй — количество кандидатов N (1 < К < 10 000 000, 1 < N < 10 000 000).
В каждой из следующих N строк находится одно число: рейтинговый балл соответствующего кандидата. Данные кандидатов отсортированы в порядке неубывания.
В ответе укажите два числа: сначала значение искомой величины для фаила A, затем — для фаила В.
Типовой пример организации данных во входном файле
100
5
20
50
50
100
200
При таких исходных данных искомая величина равна 8. Первый кандидат может составлять пары с двумя последними; второй кандидат с рейтингом 50 может быть в паре с третьим, четвёртым или пятым; третий имеет такой же рейтинг, как второй, и может составлять пару с четвёртым или пятым кандидатом, которые, в свою очередь, образуют допустимую пару друг с другом.
Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов.
Предупреждение: для обработки файла В не следует использовать переборный алгоритм, вычисляющий искомую величину для всех возможных вариантов, поскольку написанная по такому алгоритму программа будет выполняться слишком долго.
Файлы к заданию:27_A.txt27_B.txt
f = open('27_B_9794.txt')
k = int(f.readline())
n = int(f.readline())
a = [int(x) for x in f.readlines()]
left = 0
right = n - 1
ans = 0
while left < right:
if a[left] + a[right] >= k:
ans = ans + (right - left)
right -= 1
else:
left += 1
print(ans)
Ответ 43666 1303810249487
№ 27
досрочный вариант 2024
На кольцевой автодороге с двусторонним движением находится N бензоколонок (не более одной бензоколонки на каждом километре дороги). Длина кольцевой автодороги равна K км. Нулевой километр и K-й километр находятся в одной точке. Известно количество топлива, которое ежедневно на каждую бензоколонку доставляет отдельный бензовоз. Для перевозки топлива используются бензовозы вместимостью 11 м3. Стоимость доставки топлива вычисляется как произведение количества рейсов бензовоза на расстояние от нефтехранилища до бензоколонки. Пробег пустого бензовоза не учитывается. Определите минимальные расходы на доставку топлива до всех бензоколонок, если нефтехранилище расположено на кольцевой автодороге на территории одной из бензоколонок.
Входные данные
Даны два входных файла (файл A и файл B), каждый из которых в первой строке содержит два числа: N, K (1 ≤ N ≤ 10 000 000, 1 ≤ K ≤ 10 000 000) – соответственно количество бензоколонок на кольцевой автодороге и длина автодороги в километрах. В каждой из следующих N строк находятся два числа: номер километра кольцевой автодороги, на котором расположена бензоколонка, и количество топлива в кубометрах (все числа натуральные, количество топлива на каждой бензоколонке не превышает 1000). Данные указаны в порядке расположения бензоколонок на автодороге.
В ответе укажите два числа: сначала значение искомой величины для файла А, затем – для файла B.
Типовой пример организации данных во входном файле
6 40
2 1
9 5
16 20
25 2
32 22
40 6
При таких исходных данных и вместимости бензовоза 3 м3 минимальные расходы на доставку топлива из оптимально расположенного нефтехранилища составят:
10 ∙ 1 + 17 ∙ 2 + 16 ∙ 7 + 7 ∙ 1 + 0 ∙ 8 + 8 ∙ 2.
Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов.
Предупреждение: для обработки файла B не следует использовать переборный алгоритм, вычисляющий сумму для всех возможных вариантов, поскольку написанная по такому алгоритму программа будет выполняться слишком долго.
Файлы к заданию:27A.txt27B.txt
Ответы 2485441 799644133992
f = open('27B_15342.txt')
n, k=map(int,f.readline().split())
a =[0]*k #в массив будем сохранять информацию о количестве рейсов в каждую бензоколонку, которая расположена на i км
for i in range(n):
km, t = map(int,f.readline().split())
if t%11==0:
a[km]=t//11
else:
a[km]=t//11+1
res=0
s = sum(a)
a = a*2
#вычисляем затраты, когда бензохранилище располагается в нулевом км
for i in range(k):
res += min(i, k - i)*a[i]
#инициализуруем начальное значения переменных, хранящих количество рейсов в правую сторону и в левую относительно бензохранилища
minres=res
right_sum= sum(a[1:k//2+1])
left_sum = s - right_sum
for i in range(1,k):
res = res - right_sum + left_sum #при сдвиге местоположения бензохранилища на 1 км правые бензоколонки становятся ближе, левые дальше. Воспользуемся идеей динамического программирования: для получения результата уменьшим предыдущую сумму на величину правой суммы, а также увеличим ее на величину левой суммы. Почему?.Каждое слагаемое в правой сумме уменьшается на величину, равную количеству рейсов, н-р нужно сделать 2 рейса на расстояние 9 км (затраты 2*9км=18), при смещении на 1 км затраты уменьшатся 2*8км=16 на 2, это можно записать как 18-2=16, где 2 –a[9] количество рейсов к бензоколонке на 9 км дороги. В целом, чтобы не изменять каждое слагаемое в суммах отдельно, заметим, что общее изменение всех слагаемых это и есть правая сумма, поэтому результат можно изменять сразу на величину значения правой суммы. Аналогично с левой суммой, там затраты будут увеличиваться.
if a[i] != 0: minres=min(minres,res) #для ненулевых км результат будем обновлять
# При смещении еще на 1 км значения правой и левой сумм надо будет обновить
right_sum = right_sum -a[i]+ a[i+k//2]
left_sum= s-right_sum
print(minres)
Только программа без комментариев
f = open('27B_15342.txt')
n, k=map(int,f.readline().split())
a =[0]*k
for i in range(n):
km, t = map(int,f.readline().split())
if t%11==0:
a[km]=t//11
else:
a[km]=t//11+1
res=0
s = sum(a)
a = a*2
for i in range(k):
res += min(i, k - i)*a[i]
minres=res
right_sum= sum(a[1:k//2+1])
left_sum = s - right_sum
for i in range(1,k):
res = res - right_sum + left_sum
if a[i] != 0: minres=min(minres,res)
right_sum = right_sum -a[i]+ a[i+k//2]
left_sum= s-right_sum
print(minres)
проверка решения на тестовом примере:
f = open('27B_15342test.txt')
n, k=map(int,f.readline().split())
a =[0]*(k+1)
for i in range(n):
km, t = map(int,f.readline().split())
if t%3==0:
a[km]=t//3
print(*a)
else:
a[km]=t//3+1
print(*a)
a = a[1:]
print(*a)
res=0
s = sum(a)
a = a*2
for i in range(k):
res += min(i, k - i)*a[i]
print(a[i],min(i, k - i),res)
minres=res
right_sum= sum(a[1:k//2+1])
left_sum = s - right_sum
print(right_sum,left_sum)
for i in range(1,k):
res = res - right_sum + left_sum
if a[i] != 0: minres=min(minres,res)
right_sum = right_sum -a[i]+ a[i+k//2]
left_sum= s-right_sum
if a[i] != 0:print(a[i],right_sum,left_sum, res, minres)
print(minres)
вывод на экран
#заполнение массива
0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 2 0 0 0 0 0 0 7 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 2 0 0 0 0 0 0 7 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 2 0 0 0 0 0 0 7 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 8 0 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 2 0 0 0 0 0 0 7 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 8 0 0 0 0 0 0 0 2
0 1 0 0 0 0 0 0 2 0 0 0 0 0 0 7 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 8 0 0 0 0 0 0 0 2
#расчет начального значения res
0 0 0
1 1 1
0 2 1
0 3 1
0 4 1
0 5 1
0 6 1
0 7 1
2 8 17
0 9 17
0 10 17
0 11 17
0 12 17
0 13 17
0 14 17
7 15 122
0 16 122
0 17 122
0 18 122
0 19 122
0 20 122
0 19 122
0 18 122
0 17 122
1 16 138
0 15 138
0 14 138
0 13 138
0 12 138
0 11 138
0 10 138
8 9 210
0 8 210
0 7 210
0 6 210
0 5 210
0 4 210
0 3 210
0 2 210
2 1 212
10 11
#пересчет значения res при смещении бензохранилища и обновление minres
1 9 12 213 212
2 8 13 226 212
7 9 12 197 197
1 11 10 198 197
8 5 16 179 179
2 10 11 211 179
179
к заданию № 27
ЗАПРОС СУММЫ НА ОТРЕЗКЕ (МАССИВ ПРЕФИКСНЫХ СУММ)
a=[-10,12,14,-100,55,63,71,-20,0,1]
n=10
p = [0] * (n + 1)
for i in range(1, n + 1):
p[i] = p[i - 1] + a[i -1]
m = int(input())# количество запросов
for j in range(m):
l, r = map(int, input().split()) #границы
print(p[r + 1] - p[l])
'''3
3 6
89 # сумма с 3 по 6 элемент
5 7
114 # сумма с 5 по 7 элемент
1 2
26 # сумма с 1 по 2 элемент'''
НАХОЖДЕНИЕ МАКСИМАЛЬНОЙ СУММЫ
(МАССИВ ПРЕФИКСНЫХ СУММ)
a=[-10,12,14,-100,55,63,71,-20,0,1]
n=10
p = [0] * (n + 1)
for i in range(1, n + 1):
p[i] = p[i - 1] + a[i -1]
ibest = 0
jbest = 0
imin = 0
for j in range(1, n + 1):
if p[j] < p[imin]:
imin = j
if p[j] - p[imin] > p[jbest] - p[ibest]:
jbest = j
ibest = imin
print(ibest, jbest)
#ответ с 4 по 7 элемент будет максимальная сумма
УДАЧИ НА ЭКЗАМЕНЕ!!!
Префиксные суммы
https://notes.algoprog.ru/shortideas/03_x_prefix_sums.html
Два указателя
https://silvertests.ru/GuideView.aspx?id=30837
