Вариант от 18.06.26¶
Задание 5¶
На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом:
- Строится двоичная запись числа N.
- К этой записи дописываются справа ещё два разряда по следующему правилу:
– складываются все цифры двоичной записи числа N, и остаток от деления суммы на 2 дописывается в конец числа (справа);
– над полученной записью производятся те же действия – справа дописывается остаток от деления суммы её цифр на 2.
Полученная таким образом запись является двоичной записью искомого числа R.
Укажите наименьшее число N, для которого результат работы алгоритма больше числа 253. В ответе запишите это число в десятичной системе счисления.
def per(num, base):
res = ""
while num > 0:
res += str(num % base)
num //= base
return res[::-1]
ans = []
for n in range(1, 1000):
bn = per(n, 2)
bn = bn + str(bn.count("1") % 2)
bn = bn + str(bn.count("1") % 2)
r = int(bn, 2)
if r > 253:
ans.append(n)
print(min(ans))
64
На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом:
- Строится двоичная запись числа N.
- К этой записи дописываются справа ещё несколько разрядов по следующим правилам:
– если число N четное, то справа и слева к этой записи дописывается 11;
– если число N нечетное, то справа к этой записи дописывается 00, а слева – 11
Полученная таким образом запись является двоичной записью искомого числа R.
Укажите наименьшее число R, большее 105, которое могло получиться в результате работы алгорит- ма. В ответе запишите число в десятичной системе счисления.
def per(num, base):
res = ""
while num > 0:
res += str(num % base)
num //= base
return res[::-1]
ans = []
for n in range(1, 1000):
bn = per(n, 2)
if n % 2 == 0:
bn = "11" + bn + "11"
else:
bn = "11" + bn + "00"
r = int(bn, 2)
if r > 105:
ans.append(r)
print(min(ans))
115
Задание 8¶
Определите количество пятизначных чисел, записанных в девятеричной системе счисления, в записи которых ровно две цифры 3, и при этом никакая нечётная цифра не стоит рядом с цифрой 2.
def notNear(slovo, subalf):
for ltr in subalf:
if ltr + '2' in slovo or '2' + ltr in slovo:
return False
return True
alf = '012345678'
k = 0
for q in '12345678':
for w in alf:
for e in alf:
for r in alf:
for t in alf:
slovo = q + w + e + r + t
if slovo.count('3') == 2 and notNear(slovo, '1357'):
k += 1
print(k)
3352
Все пятибуквенные слова, составленные из букв А, К, Ц, Е, Н, Т, записаны в алфавитном порядке и пронумерованы. Вот начало списка:
- AAAAA
- AAAAE
- ААААК
- ААААН
- AAAAТ
- ААААЦ
...
Определите, под каким номером в этом списке стоит первое слово, которое не начинается с букв А, Е и К и при этом содержит в своей записи не менее одной буквы Т.
Примечание. Слово – последовательность идущих подряд букв, не обязательно осмыслен- ная.
def notNear(slovo, subalf):
for ltr in subalf:
if ltr + '2' in slovo or '2' + ltr in slovo:
return False
return True
alf = sorted('акцент')
nomer = 0
ans = []
for q in alf:
for w in alf:
for e in alf:
for r in alf:
for t in alf:
nomer += 1
slovo = q + w + e + r + t
if q not in 'аек' and slovo.count('т') >= 1:
ans.append(nomer)
print(ans[0])
3893
Задание 13¶
Сеть задана IP-адресом одного из входящих в неё узлов 102.162.200.51 и сетевой маской
255.255.255.0.
Найдите в данной сети наибольший IP-адрес, который может быть назначен компьютеру. В
ответе укажите сумму числовых значений октетов найденного IP-адреса.
Например, если бы найденный адрес был равен 100.20.3.4, то в ответе следовало бы записать: 127.
from ipaddress import ip_network
ans = []
for ip in ip_network("102.162.200.51/255.255.255.0", strict=False):
ans.append(ip)
print(ans[-2])
102.162.200.254
Узел имеет IP-адрес 210.185.140.126. Маска сети равна 255.255.255.252. Определите наименьший возможный IP-адрес в этой сети (адрес сети) и в ответе запишите сумму значений его октетов.
from ipaddress import ip_network
ans = []
for ip in ip_network("210.185.140.126/255.255.255.252", strict=False):
ans.append(ip)
print(ans[0])
210.185.140.124
Сеть задана IP-адресом одного из входящих в неё узлов 188.163.128.179 и сетевой маской
255.255.240.0.
Определите наименьший IP-адрес данной сети, который может быть присвоен компьютеру.
В ответе укажите сумму октетов у найденного IP-адреса.
Например, если бы найденный адрес был равен 111.22.3.44, то в ответе следовало бы записать 180.
from ipaddress import ip_network
ans = []
for ip in ip_network("188.163.128.179/255.255.240.0", strict=False):
ans.append(ip)
print(ans[1])
188.163.128.1
Задание 14¶
Операнды арифметического выражения записаны в системе счисления с основанием 22.
$63x89875_{22} + 17x51_{22} + 75x3_{22}$
В записи чисел переменной x обозначена неизвестная цифра из алфавита 22-ричной системы счисления. Определите наибольшее значение x, при котором значение данного арифметического выражения кратно 21. Для найденного значения x вычислите частное от деления значения арифметического выражения на 21 и укажите его в ответе в десятичной системе счисления. Основание системы счисления указывать не нужно.
for x in "0123456789abcdefghijkl":
res = int(f'63{x}89875', 22) + int(f'17{x}51', 22) + int(f'75{x}3', 22)
if res % 21 == 0:
print(res // 21)
729719487 731437533 733155579
Ответ: 733155579
Значение арифметического выражения
$4 · 16^{25} + 2 · 8^{30} − 64^{10}$
записали в двоичной системе счисления. Сколько цифр 0 содержится в этой записи?
num = 4*16**25 + 2*8**30 - 64**10
base = 2
k = 0
while num > 0:
ost = num % base
if ost == 0:
k += 1
num //= base
print(k)
71
Значение арифметического выражения
$5 · 7776^{2013} + 4 · 1296^{2015} − 3 · 216^{2017} + 2 · 36^{2017} − 6^{2019} + 2021$
записали в 36-ричной системе счисления. Определите сумму цифр больших 9 в этой записи.
num = 5*7776**2013 + 4*1296**2015 - 3*216**2017 + 2*36**2017 - 6**2019 + 2021
base = 36
sm = 0
while num > 0:
ost = num % base
if ost > 9:
sm += ost
num //= base
print(sm)
70483
Значение арифметического выражения
$5^{150} + 5^{100} − x$,
где x – целое положительное число, меньшее 2030, записали в пятеричной системе счисления. Определите наименьшее значение x, при котором количество нулей в пятеричной записи числа, являющегося значением данного арифметического выражения, максимально.
В ответе запишите число в десятичной системе счисления.
def k0(num, base):
k = 0
while num > 0:
if num % base == 0:
k += 1
num //= base
return k
max0 = 0
minx = 0
for x in range(1, 2031):
num = 5**150 + 5**100 - x
k = k0(num, 5)
if k > max0:
max0 = k
minx = x
print(minx)
625
Задание 15¶
Обозначим через ДЕЛ(n, m) утверждение «натуральное число n делится без остатка на натуральное число m». Задан отрезок B = [15; 30]. Для какого наибольшего натурального числа A формула
ДЕЛ(x, A) ∨ (ДЕЛ(x, 23) → ¬(x ∈ B))
тождественно истинна (т.е. принимает значение 1) при любом натуральном значении переменной x?
def dl(n, m):
return n % m == 0
def checka(a):
for x in range(1, 500):
f = dl(x, a) or (dl(x, 23) <= (not (x in range(15, 31))))
if f == 0:
return False
return True
ans = []
for a in range(1, 500):
if checka(a):
ans.append(a)
print(max(ans))
23
Для какого наименьшего натурального числа A формула
(y > 10) ∨ (x · A > y + x)
тождественно истинна, то есть принимает значение 1 при любых натуральных x и y?
def checka(a):
for x in range(1, 100):
for y in range(1, 100):
f = (y > 10) or (x * a > y + x)
if f == 0:
return False
return True
ans = []
for a in range(1, 100):
if checka(a):
ans.append(a)
print(min(ans))
12
Задание 19¶
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней.
Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может:
– добавить в одну из куч (по своему выбору) 4 камня;
– увеличить количество камней в одной из куч (по своему выбору) в 2 раза.
Например, пусть в одной куче 20 камней, а в другой 30 камней; такую позицию в игре
обозначим (20, 30). Тогда за один ход можно получить любую из четырёх позиций: (24, 30),
(20, 34), (40, 30), (20, 60).
Для того чтобы делать ходы, у каждого игрока есть неограниченное количество камней. Иг
ра завершается в тот момент, когда суммарное количество камней в двух кучах становится
не менее 154. Победителем считается игрок, сделавший последний ход, то есть первым полу
чивший такую игровую позицию, при которой в двух кучах суммарно 154 камня или больше.
В начальный момент в первой куче 11 камней, во второй куче – S камней; 1 ≤ S ≤ 142.
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при
любых ходах противника.
Известно, что Ваня выиграл своим первым ходом после неудачного хода Пети. Укажите минимальное значение S, при котором это возможно.
from functools import lru_cache
def move(k1, k2):
res = [(k1+4, k2),
(k1, k2+4),
(k1*2, k2),
(k1, k2*2)]
return res
@lru_cache(None)
def game(k1, k2):
if k1 + k2 >= 154:
return 'w'
if any(game(*m) == 'w' for m in move(k1, k2)):
return 'p1'
if all(game(*m) == 'p1' for m in move(k1, k2)): # в задании 19 меняем на any при неудачном первом ходе Пети
return 'v1'
if any(game(*m) == 'v1' for m in move(k1, k2)):
return 'p2'
if all(game(*m) == 'p1' or game(*m) == 'p2' for m in move(k1, k2)):
return 'v2'
for s in range(1, 143):
if game(11, s) == 'v2':
print(s, end=' ')
60 61
Задание 19: 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71
Задание 20: 35 64 65 66 67 68 69
Задание 21: 60 61
Задание 23¶
Исполнитель Робот преобразует число, записанное на экране. У исполнителя есть две команды, которым присвоены номера:
- Прибавь 1;
- Поменять цифры в разряде единиц и десятков местами, если разряд десятков меньше разряда единиц.
Сколько есть программ, которые преобразуют число 100 в число 150?
def f(start, stop):
if start > stop:
return 0
if start == stop:
return 1
if start < stop:
res = f(start+1, stop)
r3 = start // 100
r2 = start // 10 % 10
r1 = start % 10
if r2 < r1:
new_ch = r3*100 + r1*10 + r2
res += f(new_ch, stop)
return res
print(f(100, 150))
35
Задание 25¶
Напишите программу, которая перебирает целые числа, большие 7 513 048, в порядке возрастания и ищет среди них числа, представленные в виде произведения ровно двух простых множителей, не обязательно различных, каждый из которых содержит в своей записи хотя бы одну цифру 1 и одну цифру 6.
В ответе для первых 5 найденных чисел запишите само число и наибольший из его простых множителей в соответствующие столбцы таблицы.
def isPrime(num):
if num < 4:
return True
for d in range(2, int(num**0.5) + 1):
if num % d == 0:
return False
return True
def check(num):
for d in range(2, int(num**0.5) + 1):
if num % d == 0:
par = num // d
if isPrime(d) and isPrime(par) and str(d).count('1') > 0 and str(d).count('6') and str(par).count('1') > 0 and str(par).count('6'):
return max(d, par)
return 0
k = 0
for num in range(7_513_049, 8_000_000):
res = check(num)
if res > 0:
k += 1
print(num, res)
if k == 5:
break
7513309 123169 7514761 16301 7514789 46103 7514909 11369 7517219 12263
Шаблоны¶
Задание 2¶
Миша заполнял таблицу истинности логической функции $F = x \land (z \rightarrow w) \land \neg y$, но успел заполнить лишь фрагмент из трёх различных её строк, даже не указав, какому столбцу таблицы соответствует каждая из переменных $w,x,y,z$.
| F | ||||
|---|---|---|---|---|
| 1 | 1 | |||
| 1 | 0 | 1 | ||
| 1 | 0 | 1 |
print("x y z w") #вывод названий столбцов
#перебор всех вариантов x,y,z,w
for x in range(2):
for y in range(2):
for z in range(2):
for w in range(2):
f = x and (z <= w) and not y #переписали функцию
if f == 1: #выводим только те строки, где f = 1 (как в таблице)
print(x, y, z, w) #дальше руками
x y z w 1 0 0 0 1 0 0 1 1 0 1 1
Задание 3¶
Для решения используется функция ВПР:
Функция ВПР используется для поиска значения в первом столбце таблицы и возврата соответствующего значения из указанного столбца той же строки.
Синтаксис
=ВПР(искомое_значение; таблица; номер_столбца; [интервальный_просмотр])
Аргументы
- искомое_значение — значение, которое необходимо найти в первом столбце таблицы.
- таблица — диапазон ячеек, содержащий данные для поиска.
- номер_столбца — номер столбца в указанном диапазоне, из которого нужно вернуть результат.
- интервальный_просмотр — необязательный параметр:
ЛОЖЬ(или 0) — точное совпадение;ИСТИНА(или 1) — приблизительное совпадение.
Пример
Таблица "Движение товаров"
| ID | Артикул | Операция |
|---|---|---|
| 1 | 114 | Продажа |
| 2 | 97 | Продажа |
Таблица "Товар"
| ID | Артикул | Наименование |
|---|---|---|
| 1 | 314 | Шкаф IKEA |
| 2 | 115 | Стул СТМ |
| 3 | 114 | Холод. LG |
| 4 | 97 | СВЧ Samsung |
Хотим добавить в таблицу Движение товаров добавить столбец с наименованием товара, которое надо подтягивать из другой таблицы Товар.
Для этого используем ВПР:
| ID | Артикул | Операция | Наименование |
|---|---|---|---|
| 1 | 114 | Продажа | =ВПР(B2; Товар!A:C; 3; 0) |
| 2 | 97 | Продажа | =ВПР(B3; Товар!A:C; 3; 0) |
Комментарий: Так как обращаемся к другой таблице, то параметр таблица начинается с названия таблицы, после которого идет специальный разделитель !
Результат
| ID | Артикул | Операция | Наименование |
|---|---|---|---|
| 1 | 114 | Продажа | Холод. LG |
| 2 | 97 | Продажа | СВЧ Samsung |
Задание 5¶
На вход алгоритма подается натуральное число N. Алгоритм строит по нему новое число R следующим образом:
- Строится троичная запись числа N.
- Далее эта запись обрабатывается по следующему правилу:
а) если число N не делится на 3, то к этой записи справа дописываются три её последние цифры, а слева – цифра 1;
б) если число N делится на 3, то сумма цифр троичной записи умножается на 8, переводится в троичную систему счисления и дописывается в конец числа.
Полученная таким образом запись является троичной записью искомого числа R. Например, для исходного числа 11 = 1023 результатом является число 11021023 = 1037, а для исходного числа 12 = 1103 результатом является число 1101213 = 340. Укажите число R, ближайшее к числу 1220, которое может быть получено в результате работы алгоритма.
#обязательно использовать функцию per!
def per(num, base):
res = ''
while num > 0:
res += str(num % base)
num //= base
return res[::-1]
ans = [] #в список будем складывать ответы
for n in range(1, 1000):
bn = per(n, 3) #1. перевод числа в 2 СС или 3 СС или куда скажут
#сумма цифр в троичной записи: sm = bn.count('1') + bn.count('2')*2
if n % 3 != 0: #какое-то условие на n или bn
#что-то делаем с bn
#последние две цифры bn: bn[-2:]
#дописать 11 справа: bn = bn + '11'
#дописать 00 слева: bn = '00' + bn
#заменить левые два разряда на 10: bn = '10' + bn[2:]
bn = '1' + bn + bn[-3:]
else:
#что-то другое делаем с bn
sm = bn.count('1') + bn.count('2')*2
sm *= 8
bn = bn + per(sm, 3)
R = int(bn, 3) #перевод обратно в 10 СС из 3 СС
if abs(R - 1220) < 50:#какое-то условие на R
#добавляем в список то, что просят найти (либо N либо R)
ans.append(R)
print(ans) #выводим макс/мин значение из списка
[1177, 1205, 1261, 1239]
В данном случае ближе всего число 1205
Пример 2¶
На вход алгоритма подается натуральное число N. Алгоритм строит по нему новое число R следующим образом.
- Строится двоичная запись числа N.
- Далее эта запись обрабатывается по следующему правилу:
• если число четное, то к двоичной записи числа слева дописывается 10;
• если число нечетное, то к двоичной записи числа слева дописывается 1 и справа дописывается 01.
Полученная таким образом запись является двоичной записью искомого числа R. - Результат переводится в десятичную систему и выводится на экран.
Например, для исходного числа $4_{10}$ = $100_2$ результатом является число $10100_2$ = $20_{10}$, а для исходного числа $5_{10}$ = $101_2$ это число $110101_2 = 53_{10}$. Укажите максимальное число N, после обработки которого с помощью этого алгоритма получается число R, меньшее, чем 30. В ответе запишите это число в десятичной системе счисления.
def per(num, base):
s = ""
while num > 0:
s += str(num % base)
num //= base
return s[::-1]
ans = []
for n in range(1, 1000):
bn = per(n, 2)
if n % 2 == 0:
bn = "10" + bn
else:
bn = "1" + bn + "01"
r = int(bn, 2)
if r < 30:
ans.append(n)
print(max(ans))
6
Пример 3¶
На вход алгоритма подается натуральное число N. Алгоритм строит по нему новое число R следующим образом.
- Строится троичная запись числа N.
- Далее эта запись обрабатывается по следующему правилу:
• если число N делится на 3, то слева к нему приписывается 1, а справа 02;
• если число N на 3 не делится, то остаток от деления на 3 умножается на 4, переводится в троичную запись и дописывается в конец числа.
Полученная таким образом запись является троичной записью искомого числа R. - Результат переводится в десятичную систему и выводится на экран.
Например, для исходного числа $11_{10} = 102_3$ результатом является число $10222_3 = 107_{10}$, а для исходного числа $12_{10} = 110_3$ это число $111002_3 = 353_{10}$.
Укажите максимальное число N, после обработки которого с помощью этого алгоритма получается число R, меньшее 100.
def per(num,base):
s=""
while num >0:
s+=str(num%base)
num//=base
return s[::-1]
ans=[]
for n in range(1,1000):
bn=per(n,3)
if n%3==0:
bn="1"+bn+"02"
else:
ost=(n%3)*4
bn=bn+per(ost,3)
r=int(bn,3)
if r < 100:
ans.append(n)
print(max(ans))
10
Пример 4¶
На вход алгоритма подается натуральное число N. Алгоритм строит по нему новое число R следующим образом.\
- Строится четверичная запись числа N.
- Далее эта запись обрабатывается по следующему правилу:
• если число N делится на 4, то к этой записи дописываются две первые четверичные цифры;
• если число N на 4 не делится, то остаток от деления умножается на 4, переводится в четверичную запись и дописывается в конец числа.
Полученная таким образом запись является четверичной записью искомого числа R. - Результат переводится в десятичную систему и выводится на экран.
Например, для исходного числа $11_{10} = 23_4$ результатом является число $2330_4 = 188_{10}$, а для исходного числа $12_{10} = 30_4$ это число $3030_4 = 204_{10}$. Укажите минимальное число R, большее 291, которое может быть получено с помощью описанного алгоритма. В ответе запишите это число в десятичной системе счисления.
def per(num,base):
s=""
while num>0:
s+=str(num%base)
num//=base
return s[::-1]
ans=[]
for n in range(1,1000):
bn=per(n,4)
if n%4==0:
bn=bn+bn[:3]
else:
ost=(n%4)*4
bn=bn+per(ost,4)
r=int(bn,4)
if r>291:
ans.append(r)
print(min(ans))
296
Пример 5¶
На вход алгоритма подается натуральное число N. Алгоритм строит по нему новое число R следующим образом.\
- Строится двоичная запись числа N.
- Далее эта запись обрабатывается по следующему правилу:
• в конец числа (справа) дублируется последняя цифра двоичной записи
• к этой записи дописывается справа остаток от деления ее суммы цифр на 2.
Полученная таким образом запись является двоичной записью искомого числа R. - Результат переводится в десятичную систему и выводится на экран.
Укажите максимальное число R, меньшее 13500, которое может являться результатом работы алгоритма. В ответе это число запишите в десятичной системе.
def per(num, base):
s = ""
while num > 0:
s += str(num % base)
num //= base
return s[::-1]
ans = []
for n in range(1, 20000):
bn = per(n, 2)
bn = bn + bn[-1]
bn = bn + str(bn.count("1") % 2)
r = int(bn, 2)
if r < 13500:
ans.append(r)
print(max(ans))
13497
Задание 6¶
Решается в питоне с помощью библиотеки turtle.
Основные функции:
| Функция | Назначение |
|---|---|
| forward(distance: float) | движение вперед на расстояние, равное distance |
| back(distance: float) | назад |
| right(angle: float) | поворот пр.ч.с. на угол angle |
| left(angle: float) | поворот п.ч.с. |
| penup() | поднять хвост |
| pendown() | опустить хвост |
Вспомогательные функции:
| Функция | Назначение |
|---|---|
| tracer(0) | делает отрисовку мгновенной |
| screensize(2000, 2000) | установка размера экрана |
| setpos(x, y) | перемещение в точку (x, y) |
| dot(5, 'red') | ставим точку размера 5, красного цвета |
| update() | тоже для мгновенной отрисовки |
| mainloop() | оставляет экран открытым, иначе он сразу закроется |
Черепаха выполнила следующую программу:
Повтори 3 [Вперёд 32 Направо 90 Вперёд 38 Направо 90]
Поднять хвост
Вперёд 25 Направо 90 Вперёд 21 Налево 90
Опустить хвост
Повтори 3 [Вперёд 29 Направо 90 Назад 18 Направо 90]
Определите, сколько точек с целочисленными координатами находятся внутри объединения фигур, ограниченного заданными алгоритмом линиями, включая точки на линиях.
import turtle
k = 20 # коэффициент масштабирования, чтобы рисунок был больше и виднее
turtle.tracer(0) # отключаем анимацию, чтобы рисовать быстрее
turtle.screensize(2000, 2000) # устанавливаем размер экрана, чтобы было достаточно места для рисунка
for i in range(3):
turtle.forward(32*k)
turtle.right(90)
turtle.forward(38*k)
turtle.right(90)
turtle.penup()
turtle.forward(25*k)
turtle.right(90)
turtle.forward(21*k)
turtle.left(90)
turtle.pendown()
for i in range(3):
turtle.forward(29*k)
turtle.right(90)
turtle.back(18*k)
turtle.right(90)
turtle.penup() # поднимаем хвост, чтобы не рисовать линии при перемещении
for x in range(-25, 40):
for y in range(-40, 5):
turtle.setpos(x*k, y*k) # устанавливаем позицию черепашки в точку (x*k, y*k)
turtle.dot(5, 'red') # рисуем красную точку диаметром 5 пикселей в текущей позиции черепашки
turtle.update() # обновляем экран, чтобы отобразить все нарисованные точки и линии
turtle.mainloop() # чтобы окно оставалось открытым
Задание 8¶
Прототип 1. Количество слов¶
Виктор составляет таблицу кодовых слов для передачи сообщений, каждому сообщению соответствует своё кодовое слово. В качестве кодовых слов Виктор использует 5-буквенные слова, в которых могут быть только буквы Д, Г, И, А, Ш, Э, причём слово не должно начинаться с гласной и не должно заканчиваться согласной. Сколько различных кодовых слов может использовать Виктор?
alf = "дгиашэ" #в виде строки задаем алфавит, который будем перебирать
k = 0 #счетчик кол-ва слов
for q in alf: #перебираем одну букву
for w in alf: #вторую
for e in alf: #и т.д.
for r in alf:
for t in alf:
#т.к. слово из 5 букв, то 5 циклов
slovo = q+w+e+r+t
if q not in 'иаэ' and t not in 'дгш':
k += 1
print(k)
1944
Прототип 2. Слова по алфавиту¶
Все шестибуквенные слова, в составе которых могут быть только буквы П, О, Б, Е, Д, А, записаны в алфавитном порядке и пронумерованы начиная с 1. Ниже приведено начало списка.
- AAAAAA
- АААААБ
- АААААД
- AAAAAE
- АААААО
- АААААП
Определите последний чётный номер слова, которое начинается с буквы О и в котором каждая буква встречается ровно один раз.
def netPovt(): #проверка, что буквы не повторяются
for b in slovo: #берем каждую букву в слове
if slovo.count(b) > 1: #если она повторяется, то не подходит слово
return False
return True #True только после проверки всех букв, т.е. после цикла
alf = sorted('победа') #чтобы по алфавиту слова шли, используем sorted
nomer = 0 #номер слова
for q in alf:
for w in alf:
for e in alf:
for r in alf:
for t in alf:
for y in alf:
nomer += 1 #каждое новое слово имеет номер на 1 больше прошлого
slovo = q+w+e+r+t+y
if q == 'о' and netPovt() and nomer % 2 == 0:
print(nomer)
Последний номер - 38306
Прототип 3. Числа¶
Сколько существует десятичных четырёхзначных чисел, в которых все цифры различны и никакие две чётные или две нечётные цифры не стоят рядом?
def netPovt(): #функция из прошлого примера
for b in slovo:
if slovo.count(b) > 1:
return False
return True
def isNear(sub_alf): #функция для проверки рядом стоящих пар
#sub_alf - символы, которые не должны стоять рядом. Например, четные цифры
for b1 in sub_alf: #перебор символов
for b2 in sub_alf: #тк ищем пары символов, то два цикла
if (b1+b2) in slovo: #если какая-то пара символов нашлась в слове, то не подходит
return False
return True
alf = '0123456789' #числа - это те же слова, в алфавите все цифры перечисляем
k = 0
for q in alf[1:]: #КЛЮЧЕВОЕ ОТЛИЧИЕ!! числа не начинаются с 0.
for w in alf:
for e in alf:
for r in alf:
slovo = q+w+e+r
if netPovt() and isNear('02468') and isNear('13579'): #проверили сначала четные, потом нечетные
k += 1
print(k)
720
Пример 4¶
ДВ от 18.06.26
В терминологии сетей TCP/IP маской сети называют двоичное число, которое показывает, какая часть IP-адреса узла сети относится к адресу сети, а какая– к адресу узла в этой сети. Обычно маска записывается по тем же правилам, что и IP-адрес,– в виде 4 байтов, причем каждый байт записывается в виде десятичного числа. Адрес сети получается в результате применения поразрядной конъюнкции к заданному IP-адресу узла и его маске.
Например, если IP-адрес узла равен 231.32.255.131, а маска равна 255.255.240.0, то адрес сети равен 231.32.240.0.
Узел имеет IP-адрес 210.185.140.126. Маска сети равна 255.255.255.252. Определите наименьший возможный IP-адрес в этой сети (адрес сети) и в ответе запишите сумму значений его октетов.
from ipaddress import ip_network
for ip in ip_network('210.185.140.126/255.255.255.252', strict=False):
print(ip)
210.185.140.124 210.185.140.125 210.185.140.126 210.185.140.127
210.185.140.124
Пример 5¶
Олег составляет таблицу кодовых слов для передачи сообщений, каждому сообщению соответствует свое кодовое слово. В качестве кодовых слов Олег использует 4- буквенные слова, в которых есть только буквы A, B, C, D, E, X, Z, причем буквы X и Z встречаются только на двух первых позициях, а буквы A, B, C, D, E — только на двух последних. Сколько различных кодовых слов может использовать Олег?
from itertools import product, repeat
a = "ABCDEXZ"
res=[]
for word in product(a,repeat = 4):
w=''.join(word)
if w[0] in "XZ" and w[1] in "XZ" and w[2] in "ABCDE" and w[3] in "ABCDE":
res.append(w)
print(len(res))
100
Пример 6¶
Андрей составляет 7- буквенные коды из букв А, Н, Д, Р, Е, Й. Буквы А и Й должны встречаться в коде ровно по одному разу, при этом буква Й не может стоять на первом месте. Остальные допустимые буквы могут встречаться произвольное количество раз или не встречаться совсем. Сколько различных кодов может составить Андрей?
from itertools import product, repeat
a = "АНДРЕЙ"
res=[]
for word in product(a,repeat = 7):
w=''.join(word)
if w[0] not in 'Й' and w.count('А') == 1 and w.count('Й') == 1:
res.append(w)
print(len(res))
36864
Пример 7¶
Ярослав составляет коды из букв, входящих в слово ЯРОСЛАВ. Код должен состоять из 5 букв, буквы в коде не должны повторяться, согласных в коде должно быть больше, чем гласных, две гласные буквы нельзя ставить рядом. Сколько кодов может составить Ярослав?
from itertools import *
def notNear():
for x in product("ЯОА", repeat=2):
x = ''.join(x)
if x in w :
return 0
return 1
a = "ЯРОСЛАВ"
res = []
for word in permutations(a, r=5):
w = ''.join(word)
if notNear() and (w.count('Я') + w.count('О')+ w.count('А') < w.count('Р')+ w.count('С')+ w.count('В')+ w.count('Л')):
res.append(w)
print(len(res))
1224
Пример 8¶
Вася составляет 6- буквенные слова, в которых могут быть использованы только буквы В, И, Ш, Н, Я, причём буква В используется не более одного раза. Каждая из других допустимых букв может встречаться в слове любое количество раз или не встречаться совсем. Слово не должно начинаться с буквы Ш и оканчиваться гласными буквами. Словом считается любая допустимая последовательность букв, не обязательно осмысленная. Сколько существует таких слов, которые может написать Вася?
from itertools import product, repeat
a = "ВИШНЯ"
res=[]
for word in product(a,repeat = 6):
w=''.join(word)
if w[0] not in 'Ш' and w[-1] not in 'ИЯ' and w.count('В') <= 1:
res.append(w)
print(len(res))
4352
Пример 9¶
Все четырехбуквенные слова, составленные из букв Р, Е, К, А, записаны в алфавитном порядке и пронумерованы, начиная с 1. Ниже приведено начало списка:
- АААА
- АААЕ
- АААК
- АААР
- ААЕА
...
Под каким номером в списке идет первое слово, в котором нет буквыА?
from itertools import product
a = sorted(['Р', 'Е', 'К', 'А'])
count = 0
for word in product(a, repeat=4):
count += 1
w = ''.join(word)
if w.count('А') == 0:
print(count)
break
86
Пример 10¶
Все пятибуквенные слова, в составе которых могут быть только русские буквы П, Р, Е, С, Т, О, Л, записаны в алфавитном порядке и пронумерованы начиная с 1. Ниже приведено начало списка:
- ЕЕЕЕЕ
- ЕЕЕЕЛ
- ЕЕЕЕО
- ЕЕЕЕП
- ЕЕЕЕР
...
Сколько слов в списке с нечетным номером оканчиваются на гласную букву и содержат не более трех согласных в своем составе? В ответе укажите только число.
from itertools import product
ans = []
n = 0
a = sorted("престол")
for word in product(a, repeat=5):
w = "".join(word)
n += 1
if w[-1] in "ео" and n % 2 != 0 and w.count("р") + w.count("п") + w.count("с") + w.count("т")+w.count("л") <= 3:
ans.append(n)
print(len(ans))
1776
Пример 11¶
Определите количество семизначных чисел, записанных в девятеричной системе счисления, учитывая, что числа не могут начинаться с цифр 2, 4 и 6 и не должны заканчиваться на тройку одинаковых цифр (например, на 000).
k = 0
alf = "012345678"
for q in "12345678":
for w in alf:
for e in alf:
for r in alf:
for t in alf:
for y in alf:
for u in alf:
s =q+w+e+r+t+y+u
if s[0] not in "246" and not (s[-1] == s[-2] == s[-3]):
k += 1
print(k)
2624400
Задание 10¶
| Тип задачи | Что делать |
|---|---|
| 1. Найти количество вхождений слова | Ctrl + F → ввести слово → посмотреть количество найденных совпадений (или пролистать все, если редактор не показывает число). |
| 2. Найти слова, начинающиеся на определённые буквы | Ctrl + H (или Ctrl + F → Расширенный поиск) →включить Подстановочные знаки → шаблон <абв*(в Word) или использовать регулярные выражения в LibreOffice. |
| 3. Найти слова, заканчивающиеся на определённые буквы | Расширенный поиск → Подстановочные знаки → шаблон *ость> (для окончания «ость»). |
| 4. Найти слова, содержащие определённую часть | Ctrl + F → ввести нужную часть слова (например, лог). |
| 5. Найти слова определённой длины | Подстановочные знаки → например ????> — слова из 5 букв (? = одна буква). |
| 6. Найти слова с двумя условиями (например, начинаются на “по” и заканчиваются на “ть”) | Подстановочные знаки → <по*ть>. |
| 7. Найти целое слово, а не часть другого | В параметрах поиска поставить галочку Только слово целиком. |
| 8. Учесть или не учитывать регистр | При необходимости включить Учитывать регистр. Если в условии про заглавные/строчные ничего нет — оставить выключенным. |
| 9. Найти слово после замены букв (например, е/ё) | Выполнить поиск по обоим вариантам (е и ё) либо использовать шаблон, если редактор поддерживает его. |
| 10. Подсчитать слова, удовлетворяющие нескольким признакам | Использовать расширенный поиск с шаблоном, затем просмотреть количество найденных совпадений. |
Самые полезные шаблоны Word (подстановочные знаки)
Перед использованием шаблонов откройте:
Главная → Найти → Расширенный поиск → Больше → поставить галочку «Подстановочные знаки».
Основные шаблоны
| Что нужно найти | Что вводить |
|---|---|
| Любое слово | <*> |
| Слова, начинающиеся на «при» | <при*> |
| Слова, заканчивающиеся на «ость» | <*ость> |
| Слова ровно из 6 букв | <??????> |
| Слова, начинающиеся на «с» и заканчивающиеся на «ть» | <с*ть> |
| Любое слово, содержащее «ова» | ова |
Что означает каждый символ
< — начало слова.
> — конец слова.
* — любое количество любых букв.
? — ровно одна любая буква.
Алгоритм решения почти любого задания №10
- Открыть файл с текстом.
- Нажать Ctrl + F.
- Если нужен простой поиск — сразу ввести слово.
- Если нужен поиск по шаблону:
- Главная → Найти → Расширенный поиск.
- Нажать «Больше».
- Поставить галочку «Подстановочные знаки».
- Ввести нужный шаблон.
- Посмотреть количество найденных совпадений.
- Записать ответ.
Задание 13¶
Прототип 1. Наибольший/наименьший адрес¶
В терминологии сетей ТСР/IР маской сети называют двоичное число, которое показывает, какая части IP-адреса узла сети относится к адресу сети, а какая - к адресу узла в этой сети. Адрес сети получается в результате применения поразрядной конъюнкции к заданному адресу узла и его маске. Широковещательным адресом называется специализированный адрес, в котором на месте нулей в маске стоят единицы, Адрес сети и широковещательный адрес не могут быть использованы для адресации сетевых устройств. Сеть задана IP-адресом одного из входящих неё узлов 190.202.83.62 и сетевой маской 255.255.252.0.
Найдите наибольший IP-адрес в данной сети, который может быть назначен компьютеру. В ответе укажите сумму числовых значений октетов найденного IP-адреса. Например, если бы найденный адрес был равен 100.20.3.4, то в ответе следовало бы записать: 127.
from ipaddress import ip_network
#в for указываем {узел & маска} и через / саму маску
for ip in ip_network(f"190.202.83.62/255.255.252.0", strict=False):
print(ip)
#самый первый адрес - наименьший (берем +1!!!)
#самый последний адрес - наибольший (берем -1!!!)
Правильный адрес: 190.202.83.254.
Для ответа нужно сложить все октеты (все 4 числа): 190 + 202 + 83 + 254 = 729
Ответ: 729
Если бы спросили наименьший адрес компа:
Правильный адрес: 190.202.80.1
Прототип 2. Работа с двоичной записью IP¶
В терминологии сетей ТСР/IР маской сети называют двоичное число, которое показывает, какая часть IP-адреса узла сети относится к адресу сети, а какая - к адресу узла в этой сети. Адрес сети получается в результате применения поразрядной конъюнкции к заданному адресу узла и его маске. Широковещательным адресом называется специализированный адрес, в котором на месте нулей в маске стоят единицы. Адрес сети и широковещательный адрес не могут быть использованы для адресации сетевых устройств. Сеть задана IP-адресом одного из входящих в неё узлов 111.222.0.124 и сетевой маской 255.255.224.0.
Найдите в данной сети наибольший IP-адрес, у которого произведение количества нулей и количества единиц в двоичной записи IP-адреса явялется нечётным числом. В ответе укажите сумму числовых значений октетов найденного IP-адреса. Например, если бы найденный адрес был равен 100.20.3.4, то в ответе следовало бы записать: 127.
from ipaddress import ip_network
#в for указываем {узел & маска} и через / саму маску
for ip in ip_network(f"111.222.0.124/255.255.224.0", strict=False):
ip2 = bin(int(ip))[2:].zfill(32) #перевод ip в 2 СС
#после перевода получаем строку из 0 и 1, делаем с ней что хотим
if ip2.count('0') * ip2.count('1') % 2 != 0:
print(ip)
Здесь никаких +- 1 не надо. Правильный адрес: 111.222.31.255
Ответ: 619
Пример 3¶
Сеть задана IP-адресом 172.16.96.0 и маской сети 255.255.224.0. Сколько в этой сети IP-адресов, для которых количество единиц в их двоичной записи кратно 2?
В ответе укажите только число.
from ipaddress import ip_network
k = 0
for ip in ip_network("172.16.96.0/255.255.224.0"):
ip_bin = bin(int(ip))[2:].zfill(32)
if ip_bin.count("1") % 2 == 0:
k += 1
print(k)
4096
Пример 4¶
Сеть задана IP-адресом одного из входящих неё узлов 190.202.83.62 и сетевой маской 255.255.252.0.
Найдите наибольший IP-адрес в данной сети, который может быть назначен компьютеру. В ответе укажите сумму числовых значений октетов найденного IP-адреса.
Например, если бы найденный адрес был равен 100.20.3.4, то в ответе следовало бы записать: 127.
from ipaddress import ip_network
for ip in ip_network("190.202.83.62/255.255.252.0", strict=False):
ip2 = bin(int(ip))[2:].zfill(32)
print(ip)
190.202.83.255
Пример 5¶
Сеть задана IP-адресом одного из входящих в неё узлов 172.95.116.174 и сетевой маской 255.255.192.0.
Найдите наименьший в данной сети IP-адрес, в котором количество единиц в двоичной записи кратно 5. В ответе укажите сумму числовых значений октетов найденного IP-адреса.
Например, если бы найденный адрес был равен 100.10.3.4, то в ответе следовало бы записать 117
from ipaddress import ip_network
ans=[]
for ip in ip_network("172.95.116.174/255.255.192.0",strict=False):
ip2=bin(int(ip))[2:].zfill(32)
if ip2.count("1")%5==0:
ans.append(ip)
print(min(ans))
172.95.64.15
Пример 6¶
Сеть задана IP-адресом одного из входящих в неё узлов 45.172.106.203 и сетевой маской 255.255.252.0.
Найдите наименьший в данной сети IP-адрес, который может быть назначен компьютеру. В ответе укажите найденный IP-адрес без разделителей.
Например, если бы найденный адрес был равен 111.22.3.44, то в ответе следовало бы записать 11122344
from ipaddress import ip_network
for ip in ip_network("45.172.106.203/255.255.252.0", strict=False):
print(ip)
break
45.172.104.0
Пример 7¶
Сеть задана IP-адресом 222.121.128.0 и маской сети 255.255.224.0.
Сколько в этой сети IP-адресов, которые оканчиваются на два одинаковых бита?
В ответе укажите только число.
from ipaddress import ip_network
k = 0
for ip in ip_network("222.121.128.0/255.255.224.0",strict=False):
ip_bin = bin(int(ip))[2:].zfill(32)
if ip_bin[-1]==ip_bin[-2]:
k += 1
print(k)
4096
Пример 8¶
Сеть задана IP-адресом одного из узлов 172.140.68.0 и маской сети 255.255.248.0.
Сколько в этой сети IP-адресов, в которых количество нулей в двоичной записи IP-адреса больше 15?
В ответе укажите только число.
from ipaddress import ip_network
k = 0
for ip in ip_network("172.140.68.0/255.255.248.0",strict=False):
ip_bin = bin(int(ip))[2:].zfill(32)
if ip_bin.count("0") > 15:
k += 1
print(k)
1981
Пример 9¶
Сеть задана IP-адресом 123.222.111.192 и маской сети 255.255.255.248.
Сколько в этой сети IP-адресов, для которых количество нулей в двоичной записи четвертого байта IP-адреса не делится без остатка на 3?
В ответе укажите только число.
from ipaddress import ip_network
k = 0
for ip in ip_network("123.222.111.192/255.255.255.248",strict=False):
ip_bin = bin(int(ip))[2:].zfill(32)
lus = ip_bin[24:]
if lus.count("0") % 3 != 0:
k += 1
print(k)
6
Задание 14¶
Прототип 1. Сложение в разных СС¶
Операнды арифметического выражения записаны в системах счисления с основаниями 14 и 17.
$4B3x1C7_{14} + 5xG83F7_{17}$
В записи чисел переменной x обозначена неизвестная допустимая цифра из алфавита данных систем счисления. Определите наименьшее значение x, при котором значение данного арифметического выражения кратно 15. Для найденного значения x вычислите частное от деления значения арифметического выражения на 15 и укажите его в ответе в десятичной системе счисления. Основание системы счисления указывать не нужно.
for x in "0123456789ABCD": #всегда выбираем наименьшую СС
res = int(f"4B3{x}1C7", 14) + int(f"5{x}G83F7", 17)
#в кавычках пишем число, которое дано. x берем в фигурные скобки
#после запятой обязательно указываем СС
if res % 15 == 0:
print(res // 15) #частное от деления!!
11401190
Прототип 2. Количество цифр в записи¶
Значение арифметического выражения
$5 \cdot 729^{2024} + 3 \cdot 243^{1413} - 7 \cdot 81^{169} - 2 \cdot 9^{107} + 3017$
записали в системе счисления с основанием 27. Определите сумму четных цифр с числовым значением, не превышающим 25, в записи этого числа.
num = 5*729**2024 + 3*243**1413 - 7*81**169 - 2*9**107 + 3017
base = 27
summa = 0 #сумма цифр
while num > 0: #перевод в 27 СС
ost = num % base #считаем остаток
if ost % 2 == 0 and ost <= 25: #учитываем только четные <=25
summa += ost #складываем остатки, т.е. цифры
num //= base
print(summa)
26
Пример 2¶
Значение арифметического выражения
$15625^{16}− 3125^3· 25^{19} + 625^4− 2005$
записали в системе счисления с основанием 25. Сколько значащих нулей содержится в этой записи?
f = 15625**16 - 3125**3 * 25**19 + 625**4 - 2005
k = 0
while f > 0:
ost = f % 25
if ost == 0:
k += 1
f //= 25
print(k)
18
Пример 3¶
Значение арифметического выражения $14^{1402} + 28^{501} - 14^{51} - 1400$ записали в системе счисления с основанием 14. Определите в 14-ричной записи числа количество цифр с числовым значением, равным С.
n = 14**1402 + 28**501 - 14**51 - 1400
k = 0
while n > 0:
ost = n % 14
if ost == 12:
k += 1
n //= 14
print(k)
8
Прототип 3. Перевод с неизвестным x¶
Значение арифметического выражения $7^{170} + 7^{100} - x$, где x - целое положительное число, не превышающее 2030, записали в 7-ричной системе счисления. Определите наибольшее значение х, при котором количество нулей в 7-ричной записи числа, являющегося значением данного арифметического выражения, максимально. В ответе запишите число в десятичной системе счисления.
def kolnul(num, base): #функция для подсчета нулей
k = 0
while num > 0:
if num % base == 0:
k += 1
num //= base
return k
mk0 = 0 #максимальное кол-во нулей
mx = 0 #максимальный x
for x in range(1, 2031):
num = 7**170 + 7**100 - x
k0 = kolnul(num, 7) #считаем кол-во нулей в 7 СС
if k0 >= mk0: #ищем максимальное кол-во нулей
mk0 = k0
mx = x
print(mx)
#если бы просили наименьший x, то писали бы
#if k > mk0
1715
Пример 2¶
Значение арифметического выражения $3^{100} - x$, где $х$ — целое положительное число, не превышающее 2030, записали в троичной системе счисления. Определите наибольшее значение $х$, при котором в троичной записи числа, являющегося значением данного арифметического выражения, содержится ровно пять нулей.
В ответе запишите число в десятичной системе счисления.
def k0(num, base):
k = 0
while num > 0:
if num % base == 0:
k += 1
num //= base
return k
ans = []
for x in range(1, 2031):
num = 3**100 - x
k = k0(num, 3)
if k == 5:
ans.append(x)
print(max(ans))
2024
Пример 3¶
Значение арифметического выражения $5^{150} + 5^{135} - x$, где $x$ – целое положительное число, не превышающее 5555, записали в 5-ричной системе счисления. Определите наибольшее значение $x$, при котором в 5-ричной записи числа, являющегося значением данного арифметического выражения, содержится ровно 134 цифры 4.
В ответе запишите число в десятичной системе счисления.
def k0(num, base):
k = 0
while num > 0:
if num % base == 4:
k += 1
num //= base
return k
ans = []
for x in range(1, 5556):
num = 5**150 + 5**135 - x
k = k0(num, 5)
if k == 134:
ans.append(x)
print(max(ans))
3126
Пример 4¶
Значение арифметического выражения $6^{900} + 6^{10} - x$, где $х$ – натуральное число, не превышающее 10000, записали в системе счисления с основанием 6. Определите максимальное значение $x$, при котором данная запись содержит одинаковое количество цифр «3» и «5».
def k0(num, base, zifr):
k = 0
while num > 0:
if num % base == zifr:
k += 1
num //= base
return k
ans = []
for x in range(1, 10001):
num = 6**900 + 6**10 - x
k3 = k0(num, 6, 3)
k5 = k0(num, 6, 5)
if k3 == k5:
ans.append(x)
print(max(ans))
9591
Задание 15¶
Новая реализация¶
Для какого наибольшего целого неотрицательного числа А выражение
$(x > A) \lor (y > A) \lor (x + 2y < 80)$
истинно (т.е. принимает значение 1) при любых целых неотрицательных х и у?
def checka(a):
for x in range(200):
for y in range(200):
f = (x > a) or (y > a) or (x + 2*y < 80)
if f == 0:
return False
return True
for a in range(200):
if checka(a) == True:
print(a, end=' ')
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
Ответ: 26
Еще пример¶
Обозначим через m & n поразрядную конъюнкцию неотрицательных целых чисел m и n. Так, например, $14 \& 5 = 1110_2 \& 0101_2 = 0100_2 = 4$.
Для какого наименьшего неотрицательного целого числа А логическое выражение
$(x \& 117 \neq 0) \land (x \& 91 = 0) \rightarrow \lnot (x \& A = 0)$
истинно (т.е. принимает значение 1) при любом неотрицательном целом значении переменной x?
def checka(a):
for x in range(300):
f = (((x & 117) != 0) and ((x & 91) == 0)) <= (not ((x & a) == 0))
if f == 0:
return False
return True
for a in range(300):
if checka(a) == True:
print(a, end=' ')
36 37 38 39 44 45 46 47 52 53 54 55 60 61 62 63 100 101 102 103 108 109 110 111 116 117 118 119 124 125 126 127 164 165 166 167 172 173 174 175 180 181 182 183 188 189 190 191 228 229 230 231 236 237 238 239 244 245 246 247 252 253 254 255 292 293 294 295
Ответ: 36
Прототип 1. Найти число А¶
Обозначим через ДЕЛ(n, m) утверждение «натуральное число n делится без остатка на натуралиное число m». Для какого наибольшего натурального числа А выражение
$\text{ДЕЛ}(x, 128) \rightarrow (\lnot \text{ДЕЛ}(x, A) \rightarrow \lnot \text{ДЕЛ}(x, 80))$
истинно (т.е. принимает значение 1) при любом натуральном значении переменной x?
def d(n, m): #реализация функции ДЕЛ(n, m)
return n % m == 0
for a in range(1, 700): #сначала перебор а
flag = 1 #флаг = 1, значит а подходит
for x in range(1, 700): #тот же диапазон, как у а
f = d(x, 128) <= ((not d(x, a)) <= (not d(x, 80))) #переписали функцию
if f == 0: #если ложь, то а не подходит
flag = 0 #флаг = 0, значит а не подходит
if flag == 1: #после перебора x проверили, что а подходит
print(a)
1 2 4 5 8 10 16 20 32 40 64 80 128 160 320 640
Ответ 640, тк просили наибольшее
Еще пример¶
Для какого наибольшего целого неотрицательного числа А выражение
$(x > A) \lor (y > A) \lor (x + 2y < 80)$
истинно (т.е. принимает значение 1) при любых целых неотрицательных х и у?
for a in range(100):
flag = True
for x in range(100):
for y in range(100):
f = (x > a) or (y > a) or (x + 2*y < 80)
if f == 0:
flag = False
break
if flag == True:
print(a, end=' ')
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
Здесь ответ 26
Прототип 2. Отрезки¶
Решать руками!
Пример 5¶
Для какого наименьшего целого неотрицательного числа А выражение
(x < A) ∨ (y < A) ∨ (x + 2y > 50)
тождественно истинно, т.е. принимает значение 1 при любых целых неотрицательных x и y?
ans = []
for a in range(0, 200):
flag = 1
for x in range(0, 200):
for y in range(0, 200):
f = (x < a) or (y < a) or (x + 2 * y > 50)
if f == 0:
flag = 0
break
if flag == 1:
ans.append(a)
print(min(ans))
17
Пример 6¶
Обозначим через ДЕЛ(n, m) утверждение «натуральное число n делится без остатка на натуральное число m». Для какого наименьшего натурального числа А формула
(A + x < 123) → ((x, 5) → ¬(x, 7))
тождественно истинна (т.е. принимает значение 1) при любом натуральном значении переменной х?
ans=[]
def DEL(n, m):
return n % m == 0
for a in range(1, 1500):
flag = 1
for x in range(1, 1500):
f = (a + x < 123) <= ((DEL(x, 5)) <= (not DEL(x, 7)))
if f == 0:
flag = 0
if flag == 1:
ans.append(a)
print(min(ans))
88
Пример 7¶
Для какого наименьшего целого неотрицательного числа А выражение
(x ≥ 27) ∨ (2x < 3y) ∨ ((x + 2)(y− 3) < A)
тождественно истинно, т.е. принимает значение 1 при любых целых неотрицательных x и y?
ans = []
for a in range(0, 500):
flag = 1
for x in range(0, 500):
for y in range(0, 500):
f = (x >= 27) or (2 * x < 3 * y) or ((x + 2) * (y - 3) < a)
if f == 0:
flag = 0
break
if flag == 1:
ans.append(a)
print(min(ans))
393
Пример 8¶
Обозначим через m&n поразрядную конъюнкцию неотрицательных целых чисел m и n. Так, например, 14&5 = 11102&01012 = 01002 = 4. Найдите минимальное значение А, при котором значение выражения
$(x \& 103 = 0) \land (x \& 94 \neq 0) \rightarrow (x \& A \neq 0)$
тождественно истинно, то есть принимает значение 1 при любом натуральном значении х.
ans=[]
for a in range(0,200):
flag =1
for x in range(0,200):
f =((x & 103 == 0) and (x & 94 != 0)) <= (x & a !=0)
if f == 0:
flag = 0
break
if flag == 1:
ans.append(a)
print(min(ans))
24
Задание 16¶
Прототип 1. Предыдущие значения¶
Алгоритм вычисления значения функции F(n), где n - целое число, задан следующими соотношениями:
$F(n) = n \text{ при } n < 10$
$F(n) = 3n + F(n-3) \text{ если } n \geq 10$
Чему равно значение выражения $(F(6250) + 2 \cdot F(6244))/F(6238)$?
from functools import lru_cache #импортируем кэш
@lru_cache(None) #включаем кэширование
def f(n): #переписываем функцию
if n < 10:
return n
if n >= 10:
return 3*n + f(n-3) #f(n-3) -> значит используются предыдущие значения
for i in range(6500): f(i) #сначала считаем f(0), f(1), ..., f(6500), чтобы они были в кэше
print((f(6250) + 2*f(6244))//f(6238)) #лучше использовать // вместо /
3
Прототип 2. Следующие значения¶
Алгоритм вычисления значения функции F(n), где n - целое число, задан следующими соотношениями:
$F(n) = 100 \text{ при } n > 80000\\$ $F(n) = F(n+1) \cdot n \text{ если } n \leq 80000$
Чему равно значение выражения $(F(50)/100 + F(53))/F(55)$?
from functools import lru_cache #импортируем кэш
@lru_cache(None) #включаем кэширование
def f(n): #переписываем функцию
if n > 80000:
return 100
if n <= 80000:
return f(n+1) * n #f(n+1) -> значит используются следующие значения
#здесь перебор в обратном порядке, тк f использует СЛЕДУЮЩИЕ значения, вместо предыдущих, как было в первом примере
#при этом диапазон выбираю исходя из условий в функции, на print не смотрю
for i in range(81000, 0, -1): f(i)
print((f(50) // 100 + f(53))//f(55))
3797874
Прототип 3. Две функции¶
Алгоритм вычисления значений функций $F(n)$ и $G(n)$, где $n$ - целое число, задан следующими соотношениями:
$F(n) = G(n-1) + G(n-3);$
$G(n) = 3 \cdot n \text{, если } n \leq 9;$
$G(n) = G(n-4) + 2 \text{, если } n > 9.$
Чему равно значение выражения $F(42999)$?
from functools import lru_cache
@lru_cache(None)
def f(n):
return g(n-1) + g(n-3)
@lru_cache(None)
def g(n):
if n <= 9:
return 3*n
if n > 9:
return g(n-4) + 2
#основная задача - определить, какую функцию считать первой
for i in range(45000): g(i)
for i in range(45000): f(i) #тк f зависит от g, то f считаем последней
print(f(42999))
43032
Пример 4¶
Алгоритм вычисления значения функции F (n), где n - натуральное число, задан следующими соотношениями:
F (n) = 1 при n ≤ 3;
F (n) = (n + 3) × F (n− 2), если n > 3.
Чему равно значение выражения F(2028)/F(2024)?
from functools import lru_cache
@lru_cache(None)
def f(n):
if n <= 3:
return 1
if n > 3:
return (n+3)*f(n-2)
for i in range(2500): f(i)
print(f(2028)//f(2024))
4120899
Пример 5¶
Алгоритм вычисления значения функции F (n), где n - натуральное число, задан следующими соотношениями:
F (n) = n при n < 52;
F (n) = 3 × F (n− 2)− n, если n ≥ 52.
Чему равно значение выражения F(15127)//F(15099)?
from functools import lru_cache
@lru_cache(None)
def f(n):
if n < 52:
return n
if n >= 52:
return 3*f(n-2)-n
for n in range(20000): f(n)
print(f(15127)//f(15099))
4782968
Пример 6¶
Алгоритм вычисления значения функции F (n), где n - натуральное число, задан следующими соотношениями:
F (n) = 1 при n = 1;
F (n) = 2· n + F (n− 1), если n > 1.
Чему равен квадрат суммы цифр значения функции F (57693)?
from functools import lru_cache
@lru_cache(None)
def f(n):
if n==1:
return 1
if n > 1:
return 2*n+f(n-1)
for i in range(60000): f(i)
print(f(57693))
3328539941
Пример 7¶
Алгоритм вычисления значения функций F (n) и G(n), где n - натуральное число, задан следующими соотношениями:
F (n) = G(n) = n, если n < 10;
F (n) = 3· n + G(n− 2), если n > 9.
G(n) = n− 2 + F (n− 1), если n > 9.
Чему равно значение выражения F (2204)− G(2200)?
from functools import lru_cache
@lru_cache(None)
def f(n):
if n < 10:
return n
if n > 9:
return 3 * n + g(n - 2)
@lru_cache(None)
def g(n):
if n < 10:
return n
if n > 9:
return n - 2 + f(n - 1)
for n in range(1000):g(n)
for n in range(1000, 0, -1):f(n)
print(f(2204)-g(2200))
12487
Пример 8¶
Алгоритм вычисления значения функции F (n), где n - натуральное число, задан следующими соотношениями:
F (n) = n при n ≥ 2010;
F (n) = F (n + 3) + F (n + 2) + F (n + 1), если n < 2010.
Чему равно значение выражения (F (2000)−2·(F (2002)+F (2003)))//F (2004)?
from functools import lru_cache
@lru_cache(None)
def f(n):
if n >= 2010:
return n
if n < 2010:
return f(n+3)+f(n+2)+f(n+1)
for n in range(2500): f(n)
print((f(2000)-2*(f(2002)+f(2003)))//f(2004))
1
Пример 9¶
Алгоритм вычисления значения функции F (n), где n - натуральное число, задан следующими соотношениями:
F (n) = n при n > 3000;
F (n) = (2· n + 4) × F (n + 2), если n ≤ 3000.
Чему равна сумма цифр значения выражения F (20)/F (28)?
from functools import lru_cache
@lru_cache(None)
def f(n):
if n>3000:
return n
if n<=3000:
return (2 *n+4)*f(n+2)
for n in range(3500,0,-1):f(n)
print(f(20)//f(28))
6150144
Пример 10¶
Алгоритм вычисления значения функций F (n) и G(n), где n - натуральное число, задан следующими соотношениями:
F (n) = G(n− 1) + G(n− 3);
G(n) = 3· n, если n ≤ 9.
G(n) = G(n− 4) + 2, если n > 9.
Чему равно значение выражения F (42999)?
from functools import lru_cache
@lru_cache(None)
def f(n):
return g(n-1) + g(n-3)
@lru_cache(None)
def g(n):
if n <= 9:
return 3 * n
return g(n - 4) + 2
for n in range(50000): f(n)
for n in range(50000, 0, -1): g(n)
print(f(42999))
43032
Аналитическое решение¶
Алгоритм вычисления значений функций $F(n)$, где $n$ - целое число, задан следующими соотношениями:
$F(n) = 1$ при $n < 10;$
$f(n) = (n + 3) \cdot F(n - 3)$, если $n \geq 10$.
Чему равно значение выражения $(F(247563)/519 - 477 \cdot F(247560))/F(247557)$?
Решение
Запишем исходное выражение в виде: $$ \frac{\frac{F(247563)}{519} - 477 \cdot F(247560)}{F(247557)} $$ Здесь $F(247563) = (247563 + 3) \cdot F(247560) = (247566) \cdot F(247560)$ $$ \frac{\frac{F(247563)}{519} - 477 \cdot F(247560)}{F(247557)} = \frac{\frac{247566 \cdot F(247560)}{519} - 477 \cdot F(247560)}{F(247557)} $$ Теперь можно вынести F(246563) за скобку как общий множитель: $$ \frac{\frac{247566 \cdot F(247560)}{519} - 477 \cdot F(247560)}{F(247557)} = \frac{F(247560) \cdot (\frac{247566}{519} - 477)}{F(247557)} $$ Далее расписываем $F(247560)$ и сокращаем: $$ \frac{F(247560) \cdot (\frac{247566}{519} - 477)}{F(247557)} = \frac{247563 \cdot F(247557) \cdot (\frac{247566}{519} - 477)}{F(247557)} = 247563 \cdot (\frac{247566}{519} - 477)$$ Остается только посчитать (в калькуляторе или в питоне).
Ответ: 1431
Задание 19-21¶
Прототип 1. Одна куча¶
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может:
добавить в кучу 2 камня;
добавить в кучу 4 камня;
увеличить количество камней в куче в 2 раза.
Например, из кучи в 20 камней за один ход можно получить кучу из 22, 24 или 40 камней. Чтобы делать ходы, у каждого игрока есть неограниченное количество камней. Игра завершается, когда количество камней в куче становится не менее 125. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу из 125 или более камней. В начальный момент в куче было S камней, 1 ≤ S ≤ 124. Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.
Укажите минимальное значение S, при котором Петя не может выиграть за один ход, но при любом ходе Пети Ваня может выиграть своим первым ходом.
Задание 20. Для игры, описанной в задании 19, найдите два наименьших значения S, при которых у Пети есть выигрышная стратегия, причём одновременно выполняются два условия:
- Петя не может выиграть за один ход;
- Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня. Найденные значения запишите в ответе в порядке возрастания.
Задание 21. Для игры, описанной в задании 19, найдите минимальное значение S, при котором одновременно выполняются два условия:
- у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;
- у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.
from functools import lru_cache
def move(k):
return [k+2, k+4, k*2] #указываем возможные ходы
@lru_cache(None)
def game(k):
if k >= 125: #условия победы
return 'w'
if any(game(m) == 'w' for m in move(k)):
return 'p1'
if all(game(m) == 'p1' for m in move(k)):
return 'v1'
if any(game(m) == 'v1' for m in move(k)):
return 'p2'
if all(game(m) == 'p2' or game(m) == 'p1' for m in move(k)):
return 'v2'
for s in range(1, 120):
if game(s) == 'v2': #v1 для №19, p2 для №20, v2 для №21
print(s)
55 56
Задание №19: 61
Задание №20: 31 57
Задание №21: 55
Прототип 2. Две кучи¶
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч (по своему выбору) три камня или увеличить количество камней в куче в три раза. Для того чтобы делать ходы, у каждого игрока есть неограниченное количество камней. Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее 77. Победителем считается игрок, сделавший последний ход, т.е. первым получивший такую позицию, при которой в кучах оказывается 77 или больше камней. В начальный момент в первой куче было 12 камней, во второй куче – S камней; 1 ≤ S ≤ 64. Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Укажите минимальное значение S, при котором Петя не может выиграть за один ход, но при любом ходе Пети Ваня может выиграть своим первым ходом.
Задание 20. Для игры, описанной в задании 19, найдите два наименьших значения S, при которых у Пети есть выигрышная стратегия, причём одновременно выполняются два условия: – Петя не может выиграть за один ход; – Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня. Найденные значения запишите в ответе в порядке возрастания.
Задание 21. Для игры, описанной в задании 19, найдите значения S, при которых одновременно выполняются два условия: – у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети; – у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом. В ответе укажите количество таких значений
from functools import lru_cache
def move(k1, k2): #все варианты пар
return [(k1+3, k2),
(k1, k2+3),
(k1*3, k2),
(k1, k2*3)]
@lru_cache(None)
def game(k1, k2):
if k1 + k2 >= 77: #сумма не меньше 77
return 'w'
if any(game(*x) == 'w' for x in move(k1, k2)): #теперь везде *x !!!!!!!
return 'p1'
if all(game(*x) == 'p1' for x in move(k1, k2)): #теперь везде *x !!!!!!!
return 'v1'
if any(game(*x) == 'v1' for x in move(k1, k2)): #теперь везде *x !!!!!!!
return 'p2'
if all(game(*x) == 'p2' or game(*x) == 'p1' for x in move(k1, k2)): #теперь везде *x !!!!!!!
return 'v2'
for s in range(1, 65):
if game(12, s) == 'v2': #в первой кучи известно, что 12 камней
print(s)
17 19
Задание 19: 21
Задание 20: 7 18
Задание 21: 2 (количество значений)
Задание 22¶
Задание 23¶
Исполнитель преобразует число на экране. У исполнителя есть три команды, которые обозначены латинскими буквами:
A. Прибавить 1
B. Прибавить 2
C. Умножить на 2
Программа для исполнителя - это последовательность команд. Сколько существует программ, для которых при исходном числе 3 результатом является число 20, при этом траектория вычислений содержит число 7 и не содержит 10?
Траектория вычислений программы - это последовательность результатов выполнения всех команд программы. Например, для программы СВА при исходном числе 7 траектория состоит из чисел 14, 16, 17.
def f(start, stop):
if start > stop or start == 10: #НЕ содержит 10
return 0
if start == stop:
return 1
if start < stop:
return f(start+1, stop) + f(start+2, stop) + f(start*2, stop)
print (f(3, 7) * f(7, 20))
#СОДЕРЖИТ 7: идем от 3 до 7, потом от 7 до 20
Пример 2¶
Исполнитель преобразует число на экране. У исполнителя есть три коман-
ды, которые обозначены латинскими буквами:
A. Прибавить 3
B. Прибавить 5
C. Возвести в квадрат
Программа для исполнителя – это последовательность команд. Сколько существует программ, для которых при исходном числе 3 результатом является число 51, и при этом траектория вычислений содержит число 16 и не содержит 27?
def f (start,stop):
if start>stop or start==27:
return 0
if start==stop:
return 1
if start<stop:
return f(start+3,stop)+f(start+5,stop)+f(start**2,stop)
print(f(3,16)*f(16,51))
225
Пример 3¶
Исполнитель преобразует число на экране. У исполнителя есть три команды, которые обозначены латинскими буквами:
A. Прибавить 3
B. Прибавить 7
C. Умножить на 3
Программа для исполнителя – это последовательность команд. Сколько существует таких программ, которые исходное число 12 преобразуют в 89, и при этом траектория вычислений программы содержит числа 40 и 72 и не содержит 56?
def f (start,stop):
if start>stop or start==56:
return 0
if start==stop:
return 1
if start<stop:
return f(start+3,stop)+f(start+7,stop)+f(start*3,stop)
print(f(12,40)*f(40,72)*f(72,89))
324
Пример 4¶
Исполнитель преобразует число на экране. У исполнителя есть три команды, которые обозначены латинскими буквами:
A. Вычесть 1
B. Вычесть 4
C. Найти целую часть от деления на 2
Программа для исполнителя – это последовательность команд. Сколько существует таких программ, которые исходное число 34 преобразуют в число 9, при этом траектория вычислений содержит числа 20 и 30, и не содержит числа 24?
def f (start,stop):
if start<stop or start==24:
return 0
if start==stop:
return 1
if start>stop:
return f(start-1,stop)+f(start-4,stop)+f(start//2,stop)
print(f(34,30)*f(30,20)*f(20,9))
264
Пример 5¶
Исполнитель преобразует число на экране. У исполнителя есть три команды, которые обозначены латинскими буквами:
A. Прибавить 1
B. Прибавить 2
C. Умножить на 2
Программа для исполнителя – это последовательность команд. Сколько существует программ, которые преобразуют число 7 в число 51, и при этом траектория вычислений содержит числа 13 и 15, но не содержит числа 35?
def f (start,stop):
if start>stop or start==35:
return 0
if start==stop:
return 1
if start<stop:
return f(start+1,stop)+f(start+2,stop)+f(start*2,stop)
print(f(7,13)*f(13,15)*f(15,51))
174034068
Задание 24¶
Прототип 1. Два указателя¶
Пример 1¶
Текстовый файл состоит из символов A, E, G, I, L, M и R.
Определите в прилагаемом файле максимальное количество идущих подряд символов (длину непрерывной подпоследовательности), среди которых символ M встречается не более 278 раз.
with open("24_19717.txt") as f:
line = f.readline()
lptr = 0
rptr = 0
max_len = 0
kz = 0
while rptr < len(line):
if line[rptr] == 'M':
kz += 1
while kz > 278:
if line[lptr] == 'M':
kz -= 1
lptr += 1
cur_len = rptr - lptr + 1
if cur_len > max_len: max_len = cur_len
rptr += 1
print(max_len)
2471
Пример 2¶
Текстовый файл состоит из десятичных цифр и заглавных букв латинского алфавита. Определите в прилагаемом файле максимальное количество идущих подряд символов, оканчивающихся подстрокой 2025, среди которых буква Y встречается не менее 140 раз, а подстрока 2025 содержится ровно 50 раз.
В ответе запишите число – количество символов в найденной последовательности.
Для выполнения этого задания следует написать программу.
with open('24_26549.txt') as f:
line = f.readline()
lptr = rptr = 0
mlen = 0
k2 = 0
ky = 0
lptr = 0
mlen = 0
k2 = 0
ky = 0
for rptr in range(len(line)):
if line[rptr] == 'Y':
ky += 1
if line[rptr-3:rptr+1] == '2025':
k2 += 1
while k2 > 50:
if line[lptr] == 'Y':
ky -= 1
if line[lptr:lptr+4] == '2025':
k2 -= 1
lptr += 1
if line[rptr-3:rptr+1] == '2025' and k2 == 50 and ky >= 140:
mlen = max(mlen, rptr - lptr + 1)
print(mlen)
938
Пример 3¶
Текстовый файл состоит из символов T, U, V, W, X, Y и Z. Определите в прилагаемом файле минимальное количество идущих подряд символов (длину непрерывной подпоследовательности), среди которых символ Z встречается не менее 270 раз. Для выполнения этого задания следует написать. программу.
with open("24_27634.txt") as f:
line = f.readline()
rptr = lptr = 0
kz = 0
mlen = 10**10
while rptr < len(line):
if line[rptr] == 'Z':
kz += 1
while kz >= 270:
mlen = min(mlen, rptr - lptr + 1)
if line[lptr] == 'Z':
kz -= 1
lptr += 1
rptr += 1
print(mlen)
1058
Прототип 2. Регулярные выражения¶
Пример 1¶
Текстовый файл состоит из десятичных цифр и заглавных букв латинского алфавита. Определите в этом файле последовательность идущих подряд символов, представляющих собой запись максимального 16-ричного числа, содержащего ровно 10 цифр «B». В ответе запишите количество символов (значащих цифр в записи числа) в этой последовательности.
Примечание. Латинские буквы A, B, C, D, E и F означают цифры из алфавита 16-ричной системы счисления.
import re
with open("24_21981.txt") as f:
line = f.readline()
num = "[1-9A-F][0-9A-F]*"
mask = f"({num})"
res = [x.group() for x in re.finditer(mask, line)]
print(len(max(res, key=lambda x: len(x) if x.count('B') == 10 else 0)))
333
Пример 2¶
Текстовый файл состоит из десятичных цифр и заглавных букв латинского алфавита. Onределите в этом файле последовательность идущих подряд символов, представляющих собой запись максимального нечётного 12-ричного числа. В ответе запишите индекс (номер) первого символа (первой значащей цифры), с которого начинается запись этого числа в прилагаемом файле. Нумерация символов в текстовом файле начинается с нуля.
Примечание. Латинские буквы А и В - цифры из алфавита 12-ричной системы счисления.
from re import finditer
file = open("24_22356.txt")
line = file.readline()
file.close()
num = "([123456789AB][0123456789AB]*|[13579B])"
mask = f'{num}'
res = [i.group() for i in finditer(mask, line)]
mx = 0
mx_exp = 0
for x in res:
if len(x) > mx:
mx = len(x)
mx_exp = x
if len(x) == mx:
if x > mx_exp:
mx_exp = x
#print(mx, mx_exp, sep='\n')
print(line.find(mx_exp))
8499457
Пример 3¶
Текстовый файл состоит из десятичных цифр и заглавных букв латинского алфавита. Определите в прилагаемом файле последовательность идущих подряд символов наибольшей длины, которая представляет собой запись чётного 8-ричного числа. Если таких последовательностей несколько, выберите последовательность с наименьшим числовым значением. В ответе запишите индекс (номер) первого символа (первой значащей цифры), с которого начинается запись этой последовательности в прилагаемом файле. Нумерация символов в текстовом файле начинается с нуля.
import re
with open("24_22361.txt") as f:
line = f.readline()
num = "[1234567][01234567]*[0246]"
mask = f"({num})"
max_len = 0
max_expr = ""
res = [x.group() for x in re.finditer(mask, line)]
for x in res:
if len(x) > max_len:
max_len = len(x)
max_expr = x
elif len(x) == max_len:
if int(x) < int(max_expr):
max_expr = x
print(max_expr)
print(line.find(max_expr))
10235647074152360 2494915
Пример 4¶
Текстовый файл состоит из десятичных цифр и заглавных букв латинского алфавита. Определите в прилагаемом файле последовательность идущих подряд символов наибольшей длины, которая представляет собой запись кратного трём 12-ричного числа. Если таких последовательностей несколько, выберите последовательность с наименьшим числовым значением. В ответе запишите индекс (номер) первого символа (первой значащей цифры), с которого начинается запись этой последовательности в прилагаемом файле. Нумерация символов в текстовом файле начинается с нуля.
Примечание. Латинские буквы А, В - цифры из алфавита 12-ричной системы счисления.
from re import finditer
file = open("24_22362.txt")
line = file.readline()
file.close()
num = "([123456789AB][0123456789AB]*[0369]|[0369])"
mask = f'{num}'
res = [i.group() for i in finditer(mask, line)]
mx = 0
mx_exp = 0
for x in res:
if len(x) > mx:
mx = len(x)
mx_exp = x
print(mx, mx_exp, sep='\n')
109 94B2008316297540136540892709165728304060159478230173286045907261084395032516408970957406823102739401685000240
Задание 25¶
Прототип 1. Маска¶
Назовём маской числа последовательность цифр, в которой также могут встречаться следующие символы:
– символ «?» означает ровно одну произвольную цифру;
– символ «*» означает любую последовательность цифр произвольной длины; в том числе «*» может задавать и пустую последовательность.
Например, маске 123*4?5 соответствуют числа 123405 и 12300405.
Среди натуральных чисел, не превышающих 10**10, найдите все числа, соответствующие маске 89*6?7?9?, делящиеся на 9874 без остатка. В ответе запишите в первом столбце таблицы все найденные числа в порядке возрастания, а во втором столбце – соответствующие им результаты деления этих чисел на 9874. Количество строк в таблице для ответа избыточно.
from fnmatch import fnmatch # импортируем функцию для проверки маски
for num in range(9874, 10**10 + 1, 9874): # перебираем числа, кратные 9874, от самого маленького до 10^10
if fnmatch(str(num), '89*6?7?9?'): # проверяем, соответствует ли число маске '89*6?7?9?'
print(num, num // 9874)
8901677598 901527 8905627198 901927 8912617990 902635 8941667298 905577 8952607690 906685 8970607992 908508 8988647790 910335
Прототип 2. Делители¶
Пример 1¶
Найдите 5 наименьших чисел, больших 700 000, таких, что среди их нетривиальных делителей есть число, сумма цифр которого равна 13. В качестве ответа приведите 5 наименьших чисел, соответствующих условию. Для каждого из 5 таких найденных чисел в отдельной строке сначала выводится само число, затем — минимальный нетривиальный делитель, сумма цифр которого равна 13.
def getsum(num): # функция для подсчета суммы цифр числа
s = 0
while num > 0:
s += num % 10
num //= 10
return s
def check(num):
res = [] # список для хранения делителей, сумма цифр которых равна 13
for d in range(2, int(num**0.5) + 1): # перебираем делители от 2 до квадратного корня из num
if num % d == 0: # если d является делителем num
if getsum(d) == 13: # проверяем, равна ли сумма цифр d числу 13
res.append(d) # добавляем делитель в список
par = num // d # другой делитель, который парный с d
if par != d and getsum(par) == 13: # проверяем другой делитель, исключая квадратные числа
res.append(par) # добавляем другой делитель в список, если он подходит
if len(res):
return min(res)
else:
return 0
k = 0
for num in range(700_001, 800_000): # перебираем числа, большие 700000
mdel = check(num)
if mdel != 0: # проверяем каждое число с помощью функции check
k += 1 # если число подходит, увеличиваем счетчик
print(num, mdel) # выводим число и его подходящий делитель
if k == 5: # если нашли 5 таких чисел, останавливаемся
break
700002 58 700004 139 700005 2029 700010 350005 700011 193
Пример 2¶
Напишите программу, которая перебирает целые числа, большие 8 996 452, в порядке возрастания и ищет среди них числа, представленные в виде произведения ровно двух простых множителей, не обязательно различных, каждый из которых содержит в своей записи ровно две цифры 3. В ответе в первом столбце таблицы запишите первые 5 найденных чисел в порядке возрастания, а во втором столбце - для каждого из чисел соответствующий им наибольший из найденных множителей. Количество строк в таблице для ответа избыточно.
def isprime(num): # функция для проверки, является ли число простым
if num < 4:
return True
for d in range(2, int(num**0.5) + 1):
if num % d == 0:
return False
return True
def kol3(num): # функция для подсчета количества цифр 3 в числе
count = 0
while num > 0:
if num % 10 == 3:
count += 1
num //= 10
return count
def check(num):
for d in range(2, int(num**0.5) + 1): # перебираем делители от 2 до квадратного корня из num
if num % d == 0: # если d является делителем num
par = num // d # другой делитель, который парный с d
if isprime(d) and kol3(d) == 2 and \
isprime(par) and kol3(par) == 2:
return par # если оба делителя простые, возвращаем True
return 0 # если не нашли подходящих делителей, возвращаем False
k = 0
for num in range(8_996_453, 9_500_000): # перебираем числа, большие 8996453
res = check(num)
if res != 0: # проверяем каждое число с помощью функции check
k += 1
print(num, res) # выводим число и его подходящий делитель
if k == 5:
break
9001609 24133 9002887 38639 9006149 38653 9012167 3853 9012373 23531
Пример 3¶
Пусть M – сумма минимального и максимального простых натуральных делителей целого числа, не считая самого числа. Если таких делителей у числа нет, то значение M считается равным нулю.
Напишите программу, которая перебирает целые числа, бо́льшие 7 800 000, в порядке возрастания и ищет среди них такие, для которых M оканчивается на 63 и кратно общему количеству различных простых делителей числа. В ответе запишите в первом столбце таблицы первые пять найденных чисел в порядке возрастания, а во втором столбце – соответствующие им значения M.
Например, для числа 14 М = 2 + 7 = 9.
def isprime(num): # функция для проверки, является ли число простым
if num < 4:
return True
for d in range(2, int(num**0.5) + 1):
if num % d == 0:
return False
return True
def findM(num):
res = []
for d in range(2, int(num**0.5) + 1): # перебираем делители от 2 до квадратного корня из num
if num % d == 0: # если d является делителем num
par = num // d # другой делитель, который парный с d
if isprime(d):
res.append(d) # если d простой, добавляем его в список
if par != d and isprime(par):
res.append(par) # если другой делитель простой, добавляем его в список, исключая квадратные числа
if len(res):
return min(res) + max(res), len(res) # если нашли простые делители, возвращаем сумму наименьшего и наибольшего, а также их количество
else:
return 0, 0 # если не нашли простых делителей, возвращаем 0 и 0
k = 0
for num in range(7_800_001, 8_000_000): # перебираем числа, большие 7800001
M, kol = findM(num)
if M % 100 == 63 and M % kol == 0: # проверяем каждое число с помощью функции findM
k += 1
print(num, M) # выводим число, если его наименьший и наибольший простые делители в сумме дают 149 и их количество равно 2
if k == 5:
break
7800610 780063 7801042 8463 7801312 1863 7801916 8163 7802032 69663
Пример 4¶
Напишите программу, которая перебирает целые числа, большие 1 350 050, в порядке возрастания и ищет среди них такие, у которых есть натуральный делитель, оканчивающийся на 11 и не равный ни самому числу, ни числу 11. В ответе запишите в первом столбце таблицы первые пять найденных чисел в порядке возрастания, а во втором столбце - для каждого числа соответствующий минимальный делитель, оканчивающийся на 11, не равный ни самому числу, ни числу 11. Количество строк в таблице для ответа избыточно.
def findD(num):
res = []
for d in range(2, int(num**0.5) + 1): # перебираем делители от 2 до квадратного корня из num
if num % d == 0: # если d является делителем num
par = num // d # другой делитель, который парный с d
if d != 11 and d % 100 == 11: # проверяем, что d заканчивается на 11
res.append(d) # если d подходит, добавляем его в список
if par != d and par % 100 == 11: # проверяем другой делитель
res.append(par) # если другой делитель подходит, добавляем его в список
if len(res):
return min(res) # если нашли подходящие делители, возвращаем наименьший из них
else:
return 0 # если не нашли подходящих делителей, возвращаем 0
k = 0
for num in range(1_350_051, 1_500_000): # перебираем числа, большие 1350051
D = findD(num)
if D != 0: # проверяем каждое число с помощью функции findD
k += 1
print(num, D) # выводим число и его наименьший делитель, который заканчивается на 11
if k == 5:
break
1350051 311 1350055 270011 1350062 511 1350063 40911 1350066 225011
Задание 26¶
Пример 1¶
В кондитерской есть N круглых форм для коржей. Специализация кондитерской – многоярусные торты, в которых диаметр каждого верхнего коржа меньше диаметра предыдущего. Один корж можно поместить на другой, если его диаметр хотя бы на 8 единиц меньше диаметра другого коржа. Определите наибольшее количество коржей, которое можно использовать для создания многоярусного торта, и максимально возможный диаметр самого маленького коржа.
Входные данные
В первой строке входного файла находится число N — количество форм для коржей в кондитерской (натуральное число, не превышающее 10000). В следующих N строках находятся значения диаметров форм для коржей (все числа натуральные, не превышающие 10 000), каждое - в отдельной строке. Диаметр формы равен диаметру коржа, который выпекается в этой в форме.
Выходные данные
Запишите в ответе два целых числа: сначала наибольшее количество коржей, которое можно использовать для создания одного многоярусного торта, затем - максимально возможный диаметр самого маленького коржа в таком торте.
Типовой пример организации данных во входном файле
5
43
40
32
40
30
Пример входного файла приведён для пяти коржей и случая, когда минимальная допустимая разница между диаметрами коржей, подходящих для изготовления многоярусного торта, составляет 3 единицы.
При таких исходных данных условию задачи удовлетворяют наборы коржей с диаметрами 30, 40 и 43 или 32, 40 и 43 соответственно, количество коржей равно 3, а максимально возможный диаметр самого маленького коржа равен 32.
with open('26_27779.txt') as f:
n = int(f.readline()) # читаем первое число из файла, которое задает количество строк
data = [int(line) for line in f] # читаем остальные строки и сохраняем их в список data
data.sort(reverse=True) # сортируем список data по убыванию
last_korz = data[0] # берем наибольший корж - это первый элемент отсортированного списка
k = 1 # счетчик количества коржей
for i in range(1, n): # перебираем остальные элементы списка
if data[i] <= last_korz - 8:
last_korz = data[i] # обновляем последний корж
k += 1 # увеличиваем счетчик количества коржей
print(k, last_korz) # выводим количество коржей и размер последнего коржа
1159 57
Пример 2¶
На грузовом космическом корабле необходимо перевезти на МКС контейнеры, имеющие одинаковые габариты и разные массы. Общая масса всех этих контейнеров превышает грузоподъёмность космического корабля. Количество грузовых мест на космическом корабле не меньше числа контейнеров, назначенных к перевозке.
Определите количество и наибольшую возможную суммарную массу контейнеров, которые останутся на космодроме, после того, как на космический корабль загрузят как можно большее возможное количество контейнеров.
Входные данные
В первой строке входного файла находятся два числа: S - грузоподъёмность космического корабля (натуральное число, не превышающее 100 000) и N - количество контейнеров (натуральное число, не превышающее 10 000). В следующих N строках находятся значения масс контейнеров, требующих транспортировки на МКС (все числа натуральные, не превышающие 100), каждое в отдельной строке.
Выходные данные
Два целых неотрицательных числа: минимальное количество контейнеров, которые нельзя перевезти на МКС за один рейс, и максимальная суммарная масса оставшихся на космодроме грузов.
Типовой пример организации данных во входном файле
100 4
80
30
50
40
При таких исходных данных можно транспортировать за один раз максимум два контейнера. Возможные массы этих двух контейнеров - 30 и 40, 30 и 50 или 40 и 50. Контейнеры с массами 50 и 80 могут быть не перевезены. Ответом для приведённого примера является пара чисел 2 и 130.
with open('26_27636.txt') as f:
s, n = [int(x) for x in f.readline().split()] # читаем грузоподъемность и количество строк
data = [int(line) for line in f] # читаем остальные строки и сохраняем их в список data
data.sort() # сортируем список data по возрастанию
k = 0 # счетчик количества грузов
cur_sum = 0 # текущая сумма грузов
for weight in data: # перебираем веса грузов в отсортированном списке
if cur_sum + weight <= s: # если текущая сумма грузов плюс вес нового груза не превышает грузоподъемность
cur_sum += weight # добавляем вес груза к текущей сумме
k += 1 # увеличиваем счетчик количества грузов
else:
break # если груз не помещается, прекращаем перебор
print(n - k, sum(data) - cur_sum) # выводим количество грузов и сумму оставшихся грузов
7347 472188
Задание 27¶
Пример 1¶
Фрагмент звёздного неба спроецирован на плоскость с декартовой системой координат. Учёный решил провести кластеризацию полученных точек, являющихся изображениями звёзд, то есть разбить их множество на N непересекающихся непустых подмножеств (кластеров), таких что точки каждого подмножества лежат внутри прямоугольника со сторонами длиной H и W, причём эти прямоугольники между собой не пересекаются. Стороны прямоугольников не обязательно параллельны координатным осям. Гарантируется, что такое разбиение существует и единственно для заданных размеров прямоугольников.
Будем называть центром кластера точку этого кластера, сумма расстояний от которой до всех остальных точек кластера минимальна. Для каждого кластера гарантируется единственность его центра. Расстояние между двумя точками на плоскости $A(x_1, y_1)$ и $B(x_2, y_2)$ вычисляется по формуле: $d(A, B) = \sqrt{(x_2 - x_1)^2 + (y_2 - y_1)^2}$
Каждая звезда помимо координат на плоской карте характеризуется своим спектральным классом и классом светимости. Спектральный класс определяет цвет (который связан с температурой звезды) согласно таблице. Каждый из спектральных классов, в свою очередь, делится на подклассы от 0 до 9 в порядке уменьшения температуры. Обозначение подкласса ставится после обозначения спектрального класса (например, B2). Класс светимости звезды обозначим римскими цифрами от I до VII.
| Обозначение | Цвет | Обозначение | размеров |
|---|---|---|---|
| O | голубой | I | сверхгигант |
| B | бело-голубой | II | яркий гигант |
| A | белый | III | гигант |
| F | жёлто-белый | IV | субгигант |
| G | жёлтый | V | карлик |
| K | оранжевый | VI | субкарлик |
| M | красный | VII | белый карлик |
В файле A хранятся данные о звёздах двух кластеров, где H=6,0, W=5,5 для каждого кластера. В каждой строке записана информация о расположении на карте одной звезды: сначала координата x, затем координата y. Далее в той же строке для звёзд классов светимости I–VI указываются спектральный класс, подкласс и класс светимости. Обозначения классов ничем не разделяются. Для звёзд класса светимости VII (Белый карлик) обозначения спектрального класса и подкласса в файле не указываются. Известно, что количество точек не превышает 2000.
В файле B хранятся данные о звёздах трёх кластеров, где H=6,0, W=5,5 для каждого кластера. Известно, что количество звёзд не превышает 10 000. Структура хранения информации о звездах в файле B аналогична файлу А.
Для файла А определите координаты центра каждого кластера, затем найдите два числа $A_x$ и $A_y$ – абсциссу и ординату красного гиганта, ближайшего к центру кластера, который содержит наименьшее количество точек.
Для файла Б определите координаты центра каждого кластера, затем найдите два числа: $B_1$ – расстояние между центрами кластеров с наименьшим и наибольшим количеством оранжевых гигантов, и $B_2$ – наибольшее расстояние между жёлтыми карликами одного кластера.
В ответе запишите четыре числа: в первой строке – сначала целую часть абсолютного значения произведения $A_y$ × 10 000, затем целую часть абсолютного значения произведения $A_y$ × 10 000; во второй строке – сначала целую часть произведения $B_1$ × 10 000, затем целую часть произведения $B_2$ × 10 000.
Пример организации данных в одном из исходных файлов для случая четырёх звёзд
5,01788 8,32466 G2V
4,289251 6,955186 VII
4,619358 5,524697 B7V
6,91934 20,425391 G2V
Файл А¶
def parseChar(line): # функция для разбивки char на цвет, освещенность и размер
return [line[0], line[1], line[2:]]
def dist(p1, p2): # функция для нахождения расстояния между двумя точками
x1, y1 = p1['x'], p1['y']
x2, y2 = p2['x'], p2['y']
return ((x1-x2)**2 + (y1-y2)**2)**0.5
def cent(cl_p): # функция для нахождения центра кластера
minl = 10**10 # задаем начальное значение для минимальной суммы расстояний
top_k = [] # переменная для хранения точки, которая будет центром кластера
for k in cl_p:
sum_d = 0 # переменная для хранения суммы расстояний от точки k до всех остальных точек в кластере
for o in cl_p:
d = dist(k, o) # считаем расстояние от точки k до другой точки o в кластере
sum_d += d # добавляем это расстояние к сумме расстояний для точки k
if sum_d < minl: # если сумма расстояний для точки k меньше минимальной суммы
minl = sum_d # обновляем минимальную сумму расстояний
top_k = k # обновляем точку, которая будет центром кластера
return top_k
def getRGdist(cl_p, centr): # функция для нахождения расстояния от центра кластера до нужной точки и ее координат
min_d = 10**10 # задаем начальное значение для минимального расстояния
for p in cl_p:
if p['color'] == 'M' and p['size'] == 'III': # проверяем, что точка - красный гигант
d = dist(centr, p) # считаем расстояние от центра кластера до точки p
if d < min_d: # если это расстояние меньше минимального расстояния
min_d = d # обновляем минимальное расстояние
x = p['x'] # обновляем координату x нужной точки
y = p['y'] # обновляем координату y нужной точки
return [min_d, x, y]
f = open('27_A_29357.txt').readlines() # открываем файл и читаем все строки в список
p = [] # список для хранения точек
cl = [[],[]] # список для хранения двух кластеров точек
for line in f: # перебираем каждую строку в файле
x, y, char = line.split() # разбиваем строку на x, y и char
char = parseChar(char) # разбиваем char на цвет, освещенность и размер
#point = [x, y, *char]
#создаем словарь для каждой точки, чтобы было удобнее обращаться к ее характеристикам
point = {"x" : float(x), "y" : float(y), "color" : char[0], "light" : char[1], "size" : char[2]}
p.append(point)
# для деления точек на кластеры нужно построить в excel точечную диаграмму
# для точек из файла и посмотреть, как их можно разделить на 2 кластера.
# В данном случае, по оси y видно, что точки можно разделить на 2 кластера,
# если провести горизонтальную линию примерно на уровне y=10.
# Поэтому, в коде ниже, мы проверяем координату y каждой точки и добавляем ее в соответствующий кластер.
for pnt in p:
x, y = pnt['x'], pnt['y']
if y > 10:
cl[0].append(pnt)
else:
cl[1].append(pnt)
cl.sort(key=lambda x: len(x)) # сортируем кластеры по количеству точек
centr = [cent(cl[0]), cent(cl[1])] # находим центры кластеров
a1, x1, y1 = getRGdist(cl[0], centr[0]) # находим расстояние от центра кластера до нужной точки и ее координаты
print(int(x1*10000), int(y1*10000))
print(len(cl[0]))
print(len(cl[1]))
print(centr[0])
44694 69754
114
121
{'x': 4.960398, 'y': 7.34545, 'color': 'O', 'light': '8', 'size': 'I'}
Файл В¶
def parseChar(line): # функция для разбивки char на цвет, освещенность и размер
return [line[0], line[1], line[2:]]
def dist(p1, p2): # функция для нахождения расстояния между двумя точками
x1, y1 = p1['x'], p1['y']
x2, y2 = p2['x'], p2['y']
return ((x1-x2)**2 + (y1-y2)**2)**0.5
def cent(cl_p): # функция для нахождения центра кластера
minl = 10**10 # задаем начальное значение для минимальной суммы расстояний
top_k = [] # переменная для хранения точки, которая будет центром кластера
for k in cl_p:
sum_d = 0 # переменная для хранения суммы расстояний от точки k до всех остальных точек в кластере
for o in cl_p:
d = dist(k, o) # считаем расстояние от точки k до другой точки o в кластере
sum_d += d # добавляем это расстояние к сумме расстояний для точки k
if sum_d < minl: # если сумма расстояний для точки k меньше минимальной суммы
minl = sum_d # обновляем минимальную сумму расстояний
top_k = k # обновляем точку, которая будет центром кластера
return top_k
def kOrangeGiants(cl_p): # функция для подсчета количества оранжевых гигантов в кластере
k = 0
for p in cl_p:
if p['color'] == 'K' and p['size'] == 'III':
k += 1
return k
def maxYelGnomeDist(cl_p): # функция для нахождения максимального расстояния между желтыми карликами в кластере
yel_gnome = []
for p in cl_p:
if p['color'] == 'G' and p['size'] == 'V': # проверяем, что точка - желтый карлик
yel_gnome.append(p)
max_dist = 0 # переменная для хранения максимального расстояния между желтыми карликами
for i in range(len(yel_gnome)): # перебираем все пары желтых карликов в кластере
for j in range(i+1, len(yel_gnome)):
d = dist(yel_gnome[i], yel_gnome[j])
if d > max_dist: # ищем наибольшее расстояние между желтыми карликами
max_dist = d
return max_dist
f = open('27_B_29357.txt').readlines() # открываем файл и читаем все строки в список
p = [] # список для хранения точек
cl = [[],[], []] # список для хранения трех кластеров точек
for line in f: # перебираем каждую строку в файле
x, y, char = line.split() # разбиваем строку на x, y и char
char = parseChar(char) # разбиваем char на цвет, освещенность и размер
#point = [x, y, *char]
#создаем словарь для каждой точки, чтобы было удобнее обращаться к ее характеристикам
point = {"x" : float(x), "y" : float(y), "color" : char[0], "light" : char[1], "size" : char[2]}
p.append(point)
for pnt in p:
x, y = pnt['x'], pnt['y']
if y < 30:
cl[0].append(pnt)
elif x < 16:
cl[1].append(pnt)
else:
cl[2].append(pnt)
cl.sort(key=kOrangeGiants) # сортируем кластеры по количеству оранжевых гигантов
centr = [cent(cl[0]), cent(cl[1]), cent(cl[2])] # находим центры кластеров
B1 = dist(centr[0], centr[2]) # находим расстояние между центрами кластеров с наибольшим и наименьшим количеством оранжевых гигантов
B2 = max(maxYelGnomeDist(cluster) for cluster in cl) # находим максимальное расстояние между желтыми карликами во всех кластерах
print(int(B1*10000), int(B2*10000))
138716 34029