5 - Анализ алгоритмов для исполнителя
Источники:
сайт Полякова (https://kpolyakov.spb.ru/)
демонстрационная версия станции КЕГЭ (https://kompege.ru/)
Embedded Files
1) (№ 4222 В.Н.Шубинкин) На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом:
1) Строится шестнадцатеричная запись числа N // 2, где "//" - операция деления нацело.
2) К этой записи дописывается ещё три разряда по следующему правилу: если N не делится на 4, то слева к нему приписывается "F", а справа - "A0". В противном случае слева приписывается "15", а справа "C".
Например, N = 410 => 216 => 152C16 = 542010 = R.
Полученная таким образом запись (в ней на три разряда больше, чем в записи исходного числа N) является шестнадцатеричной записью искомого числа R. Укажите наибольшее число N, для которого результат работы алгоритма меньше 65536. В ответ запишите это число в десятичной системе счисления.
Решение
p="0123456789abcdef"
for n in range(20000):
m=hex(n//2)[2:]
if n%4: m='f'+m+'a0'
else: m='15'+m+'c'
r=0
ss=1
for i in m[::-1]:
r+=p.find(i)*ss
ss*=16
if r<65536: maxn=n
print(maxn)
Ответ: 31
2) (№ 4221 В.Н.Шубинкин) На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом:
1) Строится четверичная запись числа N.
2) К этой записи дописывается ещё три или четыре разряда по следующему правилу: если N нечётное, то слева к нему приписывается "2", а справа - "11". В противном случае слева приписывается "13", а справа "02".
Например, N = 4510 = 2314 => 2231114 = 277310 = R.
Полученная таким образом запись (в ней на три или четыре разряда больше, чем в записи исходного числа N) является четверичной записью искомого числа R. Укажите наименьшее число R, большее 1000, которое может быть получено с помощью описанного алгоритма. В ответ запишите это число в десятичной системе счисления.
Решение
minn=999999999
for n in range(20000):
m=''
x=n
while x>0:
m=str(x%4)+m
x//=4
if n%2: m='2'+m+'11'
else: m='13'+m+'02'
r=0
ss=1
for i in m[::-1]:
r+=int(i)*ss
ss*=4
if r>1000:
minn=min(r,minn)
print(minn)
Ответ: 1858
3) (№ 4220 В.Н.Шубинкин) На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом:
1) Строится двоичная запись числа N.
2) К этой записи дописывается ещё три или четыре разряда по следующему правилу: если N нечётное, то слева к нему приписывается "10", а справа - "11". В противном случае слева приписывается "1", а справа "00".
Например, N = 510 = 1012 => 10101112 = 8710 = R.
Полученная таким образом запись (в ней на три или четыре разряда больше, чем в записи исходного числа N) является двоичной записью искомого числа R. Укажите наименьшее число R, большее 1023, которое может быть получено с помощью описанного алгоритма. В ответ запишите это число в десятичной системе счисления.
Решение
minn=999999999
for n in range(20000):
m=bin(n)[2:]
if n%2: m='10'+m+'11'
else: m='1'+m+'00'
r=0
ss=1
for i in m[::-1]:
r+=int(i)*ss
ss*=2
if r>1023: minn=min(r,minn)
print(minn)
Ответ: 1287
4) (№ 4219 В.Н.Шубинкин) На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом:
1) Строится двоичная запись числа N.
2) К этой записи дописывается ещё три или четыре разряда по следующему правилу: если N нечётное, то слева к нему приписывается "1", а справа - "11". В противном случае слева приписывается "11", а справа "00".
Например, N = 510 = 1012 => 1101112 = 5510 = R
Полученная таким образом запись (в ней на три или четыре разряда больше, чем в записи исходного числа N) является двоичной записью искомого числа R. Укажите наибольшее число R, меньшее 127, которое может быть получено с помощью описанного алгоритма. В ответ запишите это число в десятичной системе счисления.
Решение
maxm=0
for n in range(20000):
m=bin(n)[2:]
if n%2: m='1'+m+'11'
else: m='11'+m+'00'
r=0
ss=1
for i in m[::-1]:
r+=int(i)*ss
ss*=2
if r<127:
maxm=max(r,maxm)
print(maxm)
Ответ: 120
5) (№ 4194 С.Скопинцева) Алгоритм получает на вход натуральное число N > 1 и строит по нему новое число R следующим образом:
1) Число N переводим в двоичную запись.
2) К этой записи дважды справа дописывается один разряд по следующему правилу: если количество единиц в двоичной записи числа больше количества нулей, то справа дописывается единица, иначе дописывается 0.
Полученная таким образом запись (в ней на два разряда больше, чем в записи исходного числа N) является двоичной записью искомого числа R. Укажите наибольшее число R, меньшее 57, которое может быть получено в результате работы данного алгоритма. В ответе это число запишите в десятичной системе счисления.
Решение
maxm=0
for n in range(20000):
m=bin(n)[2:]
for i in range(2):
if m.count('1')>m.count('0'): m+='1'
else: m+='0'
r=0
ss=1
for i in m[::-1]:
r+=int(i)*ss
ss*=2
if r<57:
maxm=max(r,maxm)
print(maxm)
Ответ: 55
6) (№ 4131 А.Богданов) Алгоритм получает на вход натуральное число N > 1 и строит по нему новое число R следующим образом:
1) Число N переводим в двоичную запись.
2) Инвертируем все биты числа кроме первого.
3) Переводим в десятичную запись.
4) Складываем результат с исходным числом N.
Полученное число является искомым числом R. Укажите наименьшее нечетное число N, для которого результат работы данного алгоритма больше 99. В ответе это число запишите в десятичной системе счисления.
Решение
pr='10'
minn=99999999999
for n in range(1,20000,2):
m=bin(n)[2:]
mr='1'
for i in m[1:]:
mr+=pr[int(i)]
r=0
ss=1
for i in mr[::-1]:
r+=int(i)*ss
ss*=2
if r+n > 99:
minn=min(n,minn)
print(minn)
Ответ: 65
7) (№ 4047) Алгоритм получает на вход натуральное число N > 1 и строит по нему новое число R следующим образом:
1) Если исходное число кратно 3, оно делится на 3, иначе из него вычитается 1.
2) Если полученное на предыдущем шаге число кратно 5, оно делится на 5, иначе из него вычитается 1.
3) Если полученное на предыдущем шаге число кратно 11, оно делится на 11, иначе из него вычитается 1.
4) Число, полученное на шаге 3, считается результатом работы алгоритма.
Сколько существует различных натуральных чисел N, при обработке которых получится R = 8?
Решение
k=0
for n in range(2,20000):
if n%3: n-=1
else:n//=3
if n%5: n-=1
else:n//=5
if n%11: n-=1
else:n//=11
if n==8: k+=1
print(k)
Ответ: 4
8) (№ 4046) Алгоритм получает на вход натуральное число N > 1 и строит по нему новое число R следующим образом:
1) Если исходное число кратно 3, оно делится на 3, иначе из него вычитается 1.
2) Если полученное на предыдущем шаге число кратно 7, оно делится на 7, иначе из него вычитается 1.
3) Если полученное на предыдущем шаге число кратно 11, оно делится на 11, иначе из него вычитается 1.
4) Число, полученное на шаге 3, считается результатом работы алгоритма.
Сколько существует различных натуральных чисел N, при обработке которых получится R = 6?
Решение
k=0
for n in range(2,20000):
if n%3: n-=1
else:n//=3
if n%7: n-=1
else:n//=7
if n%11: n-=1
else:n//=11
if n==6: k+=1
print(k)
Ответ: 7
9) (№ 4045) Алгоритм получает на вход натуральное число N > 1 и строит по нему новое число R следующим образом:
1) Если исходное число кратно 2, оно делится на 2, иначе из него вычитается 1.
2) Если полученное на предыдущем шаге число кратно 5, оно делится на 5, иначе из него вычитается 1.
3) Если полученное на предыдущем шаге число кратно 7, оно делится на 7, иначе из него вычитается 1.
4) Число, полученное на шаге 3, считается результатом работы алгоритма.
Сколько существует различных натуральных чисел N, при обработке которых получится R = 6?
Решение
k=0
for n in range(2,20000):
if n%2: n-=1
else:n//=2
if n%5: n-=1
else:n//=5
if n%7: n-=1
else:n//=7
if n==6: k+=1
print(k)
Ответ: 3
10) (№ 3941 Е.Джобс) Алгоритм получает на вход натуральное число N > 1 и строит по нему новое число R следующим образом:
1) Строится двоичная запись числа N.
2) В этой записи последний ноль заменяется на первые две цифры полученной записи. Если нуля нет, алгоритм аварийно завершается.
3) Запись записывается справа налево (в обратную сторону).
4) Результат переводится в десятичную систему счисления.
Для скольких значений N в результате работы алгоритма получится число 127?
Решение
kol=0
for n in range(2,2000):
m=(bin(n)[2:])[::-1]
p=m.find('0')
#print(p,m,m[:p],m[-2:],m[p+1:])
if p>=0:
m=m[:p]+m[-2:]+m[p+1:]
# print(m)
k=0
ss=1
for i in m[::-1]:
k+=int(i)*ss
ss*=2
if k==127:kol+=1
print(kol)
Ответ: 4
11) (№ 3940 Е.Джобс) Алгоритм получает на вход натуральное число N > 1 и строит по нему новое число R следующим образом:
1) Строится двоичная запись числа N.
2) В этой записи последний ноль заменяется на первые две цифры полученной записи. Если нуля нет, алгоритм аварийно завершается.
3) Запись записывается справа налево (в обратную сторону).
4) Результат переводится в десятичную систему счисления.
Для какого минимального значения N в результате работы алгоритма получится число 123?
Решение
kol=0
for n in range(2,2000):
m=(bin(n)[2:])[::-1]
a='01'
minn=2000
for n in range(2,2000):
m=(bin(n)[2:])[::-1]
p=m.find('0')
if p>=0:
m=m[:p]+m[-2:]+m[p+1:]
k=0
ss=1
for i in m[::-1]:
k+=int(i)*ss
ss*=2
if k==123:minn=min(minn,n)
print(minn)
Ответ: 47
12) (№ 3906) Алгоритм получает на вход натуральное число N > 1 и строит по нему новое число R следующим образом:
1) Строится двоичная запись числа N.
2) Подсчитывается количество нулей и единиц в полученной записи. Если их количество одинаково, в конец записи добавляется её последняя цифра. В противном случае в конец записи добавляется цифра, которая встречается реже.
3) Шаг 2 повторяется ещё два раза.
4) Результат переводится в десятичную систему счисления.
При каком наименьшем исходном числе N > 60 в результате работы алгоритма получится чётное число, которое не делится на 4?
Решение
n=60
r=1
while not(r%2==0 and r%4!=0):
n+=1
r=bin(n)[2:]
for i in range(3):
if r.count('0')==r.count('1'): r+=r[-1]
elif r.count('0')>r.count('1'):r+='1'
else: r+='0'
r=int(r,2)
print(n)
Ответ: 67
13) (№ 3912) Алгоритм получает на вход натуральное число N > 1 и строит по нему новое число R следующим образом:
1) Строится двоичная запись числа N.
2) Подсчитывается количество нулей и единиц в полученной записи. Если их количество одинаково, в конец записи добавляется её последняя цифра. В противном случае в конец записи добавляется цифра, которая встречается реже.
3) Шаг 2 повторяется ещё два раза.
4) Результат переводится в десятичную систему счисления.
При каком наименьшем исходном числе N > 100 в результате работы алгоритма получится число, которое делится на 4 и не делится на 8?
Решение
n=100
r=1
while not(r%4==0 and r%8!=0):
n+=1
r=bin(n)[2:]
for i in range(3):
if r.count('0')==r.count('1'): r+=r[-1]
elif r.count('0')>r.count('1'):r+='1'
else: r+='0'
r=int(r,2)
print(n)
Ответ: 135
14) (№ 3203) Автомат обрабатывает натуральное число N > 1 по следующему алгоритму:
1) Строится двоичная запись числа N.
2) В конец записи (справа) дописывается вторая справа цифра двоичной записи.
3) В конец записи (справа) дописывается вторая слева цифра двоичной записи.
4) Результат переводится в десятичную систему.
Пример. Дано число N = 11. Алгоритм работает следующим образом.
1) Двоичная запись числа N: 11 = 10112
2) Вторая справа цифра 1, новая запись 101112.
3) Вторая слева цифра 0, новая запись 1011102.
4) Десятичное значение полученного числа 46.
При каком наименьшем числе N в результате работы алгоритма получится R > 100? В ответе запишите это число в десятичной системе счисления.
Решение
n=1
r=0
while r<=100:
n+=1
r=bin(n)[2:]
r+=r[-2]+r[1]
r=int(r,2)
print(n)
Ответ: 25
15) (№ 3455) Автомат обрабатывает десятичное натуральное число N по следующему алгоритму:
1) Строится двоичная запись числа N.
2) К полученному числу справа дописывается 0, если в числе единиц больше, чем нулей; иначе дописывается 1.
3) Из середины двоичного числа убирается 2 разряда, если количество разрядов получилось четным, и 3 разряда, если нечетное.
4) Результат переводится в десятичную систему.
Пример. Дано число N = 11. Алгоритм работает следующим образом.
1) Двоичная запись числа N: 11 = 10112
2) Единиц больше, чем нулей, новая запись 101102.
3) Длина начётная, удаляем три средних разряда, новая запись 102.
4) Десятичное значение полученного числа 2.
Сколько различных значений может получиться на отрезке [50; 100] в результате работы автомата?
Решение
a,b=1,1000
m=[]
for i in range(a,b+1):
x=bin(i)[2:]
if x.count('0')<x.count('1'): x+='0'
else:x+='1'
if len(x)%2==0: p=(len(x)-2)//2
else: p=(len(x)-3)//2
y=int(x[:p]+x[-p:],2)
if not(y in m) and 50<=y<=100:m.append(y)
print(len(m))
Ответ: 13
16) (№ 1759) Автомат обрабатывает натуральное число N < 256 по следующему алгоритму:
1) Строится восьмибитная двоичная запись числа N.
2) Инвертируются все разряды исходного числа (0 заменяется на 1, 1 на 0).
3) Полученное число переводится в десятичную систему счисления.
4) Из нового числа вычитается исходное, полученная разность выводится на экран.
Для какого значения N результат работы алгоритма равен –21?
Решение
Решение 1
for i in range(256):
a=bin(i)[2:]
a='0'*(8-len(a))+a
b=a.replace('0','*').replace('1','0').replace('*','1')
if int(b,2)-int(a,2)==-21:
print(i)
break
Решение 2
a - введенное число
b - полученное число
a + b = 255 (сумма простого числа и его реверса)
b - a = -21
Решаем систему уравнений.
b = a - 21
a + a - 21 = 255
2 * a = 276
a = 276 / 2 = 138
Ответ: 138
17) (№ 1758) Автомат обрабатывает натуральное число N < 256 по следующему алгоритму:
1) Строится восьмибитная двоичная запись числа N.
2) Инвертируются все разряды исходного числа (0 заменяется на 1, 1 на 0).
3) Полученное число переводится в десятичную систему счисления.
4) Из нового числа вычитается исходное, полученная разность выводится на экран.
Для какого значения N результат работы алгоритма равен 45?
Решение
Решение 1
for i in range(256):
a=bin(i)[2:]
a='0'*(8-len(a))+a
b=a.replace('0','*').replace('1','0').replace('*','1')
if int(b,2)-int(a,2)==45:
print(i)
break
Решение 2
a - введенное число
b - полученное число
a + b = 255 (сумма простого числа и его реверса)
b - a = 45
Решаем систему уравнений.
b = a + 45
a + a + 45 = 255
2 * a = 210
a = 210 / 2 = 105
Ответ: 105
18) (№ 2925 Апробация 19 февраля 2022 года, Москва ) На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.
1. Строится двоичная запись числа N.
2. К этой записи дописываются справа ещё несколько разрядов по следующему правилу:
а) Если N чётное, то к нему справа приписывается в двоичном виде сумма цифр его двоичной записи;
6) Если N нечётное, то к нему справа приписываются два нуля, а слева единица.
Полученная таким образом запись (в ней как минимум на один разряд больше, чем в записи исходного числа N) является двоичной записью искомого числа R.
Например, запись числа 1101 будет преобразована в 1110100.
Укажите такое наименьшее число N, для которого результат работы данного алгоритма больше числа 215. В ответе это число запишите в десятичной системе счисления.
Решение
n,r=0,0
while r<=215:
n+=1
r=bin(n)[2:]
if n%2: r='1'+r+'00'
else: r+=bin(r.count('1'))[2:]
r=int(r,2)
print(n)
Ответ: 23
19)(№ 5449 Е.Джобс) На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.
1) Строится двоичная запись числа N.
2) Из полученной записи убирается старшая (левая) единица.
3) Если в полученной записи количество единиц четное, то слева дописывается 10, иначе слева дописывается 1, а справа – 0. Полученная таким образом запись является двоичной записью искомого числа R.
Например, для исходного числа 410 = 1002 результатом будет являться число 810 = 10002, а для исходного числа 610 = 1102 результатом будет являться число 1210 = 11002.
Укажите максимальное десятичное число R, меньшее 450, которое может являться результатом работы алгоритма. В ответе запишите это число в десятичной системе счисления.
Решение
maxr=0
for a in range(1,450):
a2=bin(a)[3:]
if a2.count('1')%2==0: a2='10'+a2
else: a2='1'+a2+'0'
if int(a2,2)<450: maxr=max(maxr,int(a2,2))
print(maxr)
Ответ: 444
20)(№ 5440 А.Сардарян) На вход алгоритма подаётся два натуральных числа N и M. Алгоритм строит по ним новое число R следующим образом.
1) Вычисляется число SN как квадрат суммы цифр двоичной записи числа N.
2) Вычисляется число SM как квадрат суммы цифр двоичной записи числа M.
3) Результат R вычисляется как SN – SM.
Укажите минимальную сумму чисел N и M, при которых получается R = 33.
Решение
mins=10**99
for a in range(1,1000):
sa=bin(a)[2:].count('1')
for b in range(1,1000):
sb=bin(b)[2:].count('1')
if sa**2-sb**2==33:
mins=min(mins,a+b)
print(mins)
Ответ: 142
21)(№ 5439 А.Сардарян) На вход алгоритма подаётся четырёхзначное натуральное число N. Алгоритм строит по нему новое число R следующим образом.
1) Если число N четное, то цифры этого числа сортируются в порядке убывания, затем полученное число делится на 2 нацело (остаток отбрасывается). Полученное значение является числом R.
Пример: N = 1488 => R = 8841//2 = 4420.
2) Если число N нечетное, то цифры этого числа сортируются в порядке возрастания, затем полученное число умножается на 2. Полученное значение является числом R.
Пример: N = 3807 => R = 378·2 = 756.
Укажите наименьшее число R, которое больше соответствующего исходного числа N на 1.
Решение
minr=10**10
for n in range(1000,10000):
s=''
for c in sorted(str(n)): s+=c
if n%2==0:
s=s[::-1]
r=int(s)//2
else:
r=int(s)*2
if n==r-1:
minr=min(minr,r)
print(minr)
Ответ: 2105
22)(№ 5445 В.Шубинкин) Автомат производит первичную проверку правильности номера банковской карты. Он получает на вход число N из 16 цифр и обрабатывает его по следующему правилу (вариант алгоритма Лу́на):
1) Цифры числа нумеруются справа налево, начиная с нуля.
2) Цифры, стоящие на нечётных позициях, увеличиваются в два раза. Если при этом получается двузначное число, его цифры складываются.
3) Складываются все цифры на чётных позициях и преобразованные цифры на нечётных позициях.
4) Если полученная сумма кратна 10, считается, что номер корректный.
Например, для числа 4096 8308 0309 8323 сумма цифр на чётных позициях (с конца) 3+3+9+3+8+3+6+0=35, сумма преобразованных цифр на нечётных позициях 4+7+0+0+0+7+9+8=35. Общая сумма 70 кратна 10, значит номер корректен.
Определите наименьшее число N, большее 1234 5678 9101 1121, которое может быть корректным номером согласно указанному алгоритму. Укажите в ответе последние 8 цифр числа.
Решение
a=1234567891011121+1
while True:
ar=str(a)[::-1]
arr=''
for i in range(len(ar)):
if i%2:
c=int(ar[i])*2
arr+=str(c%10+c//10)
else:
arr+=ar[i]
s=0
for i in arr: s+=int(i)
if s%10==0:
print(str(a)[-8:])
break
a+=1
Ответ: 91011128
23)(№ 5448 В.Шубинкин) На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.
1) Строится двоичная запись числа N.
2) Складываются все цифры двоичной записи числа N. Если полученная сумма чётна, из числа убирают ведущую единицу (а также ставшие незначащими нули). В противном случае слева приписывается 1, а справа – два ноля.
3) Над новой записью снова производятся действия, описанные в пункте 2.
4) Результат переводится в десятичную систему и выводится на экран.
Например, N = 510 = 1012 => 1 => 11002 = 1210 = R
Укажите такое наименьшее число N, для которого результат работы данного алгоритма больше 100. В ответе это число запишите в десятичной системе счисления.
Решение
for n in range(1,2000):
n2=bin(n)[2:]
if n2.count('1')%2==0:n2=str(int(n2[1:]))
else:n2='1'+n2+'00'
if n2.count('1')%2==0:n2=str(int(n2[1:]))
else:n2='1'+n2+'00'
if int(n2,2)>100:
print(n)
break
Ответ: 26
24)(№ 142) На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.
1. Строится двоичная запись числа N.
2. К этой записи дописываются справа ещё два разряда по следующему правилу:
а) складываются все цифры двоичной записи, и остаток от деления суммы на 2 дописывается в конец числа (справа). Например, запись 11100 преобразуется в запись 111001;
б) над этой записью производятся те же действия – справа дописывается остаток от деления суммы цифр на 2.
Полученная таким образом запись (в ней на два разряда больше, чем в записи исходного числа N) является двоичной записью искомого числа R. Укажите такое наименьшее число R, которое превышает 43 и может являться результатом работы алгоритма. В ответе это число запишите в десятичной системе счисления.
Решение
for n in range(1,2000):
n2=bin(n)[2:]
n2+=str(n2.count('1')%2)+'0'
if int(n2,2)>43:
print(int(n2,2))
break
Ответ: 46
25)(№ 145) Автомат получает на вход трёхзначное число. По этому числу строится новое число по следующим правилам.
1. Перемножаются первая и вторая, а также вторая и третья цифры.
2. Полученные два числа записываются друг за другом в порядке неубывания без разделителей.
Пример. Исходное число: 631. Произведение: 6*3 = 18; 3*1 = 3. Результат: 318. Укажите наибольшее число, при обработке которого автомат выдаёт результат 621.
Решение
for c in range(100,1000):
cc=str(c)
p1=int(cc[0])*int(cc[1])
p2=int(cc[1])*int(cc[2])
if p1 > p2: p1,p2=p2,p1
r=str(p1)+str(p2)
if r=='621': x=c
print(x)
Ответ: 732
26)(№ 147) На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.
1. Строится двоичная запись числа N.
2. К этой записи дописываются справа ещё два разряда по следующему правилу:
а) складываются все цифры двоичной записи, и остаток от деления суммы на 2 дописывается в конец числа (справа). Например, запись 11100 преобразуется в запись 111001;
б) над этой записью производятся те же действия – справа дописывается остаток от деления суммы цифр на 2.
Полученная таким образом запись (в ней на два разряда больше, чем в записи исходного числа N) является двоичной записью искомого числа R. Укажите такое наименьшее число R, которое превышает 150 и может являться результатом работы алгоритма. В ответе это число запишите в десятичной системе счисления.
Решение
for n in range(1,1000):
n2=bin(n)[2:]
n2+=str(n2.count('1')%2)+'0'
if int(n2,2)>150:
print(int(n2,2))
break
Ответ: 154
27)(№ 1718) Автомат получает на вход трёхзначное число. По этому числу строится новое число по следующим правилам.
1. Из цифр, образующих десятичную запись N, строятся наибольшее и наименьшее возможные двузначные числа (числа не могут начинаться с нуля).
2. На экран выводится разность полученных двузначных чисел.
Пример. Дано число N = 351. Наибольшее двузначное число из заданных цифр – 53, наименьшее – 13. На экран выводится разность 53 – 13 = 40.
Чему равно количество чисел N на отрезке [500; 600], в результате обработки которых на экране автомата появится число 10?
Решение
k=0
for n in range(501,600):
a,b,c=sorted(str(n))
maxc=int(c+b)
if a=='0': minc=int(b+a)
else: minc=int(a+b)
if maxc-minc==10: k+=1
print(k)
Ответ: 6
28)(№ 1726) Автомат получает на вход трёхзначное число. По этому числу строится новое число по следующим правилам.
1. Из цифр, образующих десятичную запись N, строятся наибольшее и наименьшее возможные двузначные числа (числа не могут начинаться с нуля).
2. На экран выводится разность полученных двузначных чисел.
Пример. Дано число N = 351. Наибольшее двузначное число из заданных цифр – 53, наименьшее – 13. На экран выводится разность 53 – 13 = 40.
Чему равно наименьшее возможное трёхзначное число N, в результате обработки которого на экране автомата появится число 60?
Решение
for n in range(100,1000):
a,b,c=sorted(str(n))
maxc=int(c+b)
if a=='0': minc=int(b+a)
else: minc=int(a+b)
if maxc-minc==60:
print(n)
break
Ответ: 117
29)(№ 1738) На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.
1. Строится двоичная запись числа N.
2. К этой записи дописываются справа ещё два разряда по следующему правилу:
а) складываются все цифры двоичной записи, и остаток от деления суммы на 2 дописывается в конец числа (справа). Например, запись 11100 преобразуется в запись 111001;
б) над этой записью производятся те же действия – справа дописывается остаток от деления суммы цифр на 2.
Полученная таким образом запись (в ней на два разряда больше, чем в записи исходного числа N) является двоичной записью искомого числа R. Какое наибольшее число, меньшее 130, может быть получено в результате работы автомата?
Решение
maxr=0
for n in range(130):
r=bin(n)[2:]
r+=str(r.count('1')%2)+'0'
if int(r,2)<130: maxr=max(maxr,int(r,2))
print(maxr)
Ответ: 126
30)(№ 1745) На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.
1. Строится двоичная запись числа N без ведущих нулей.
2. Если в полученной записи единиц больше, чем нулей, то справа приписывается единица. Если нулей больше или нулей и единиц поровну, справа приписывается ноль.
Полученная таким образом запись (в ней на один разряд больше, чем в записи исходного числа N) является двоичной записью искомого числа R. Какое наибольшее число, меньшее 90, может быть получено в результате работы автомата?
Решение
maxr=0
for n in range(130):
r=bin(n)[2:]
r+=str(int(r.count('1')*2>len(r)))
if int(r,2)<90: maxr=max(maxr,int(r,2))
print(maxr)
Ответ: 88
31)(№ 1767) Автомат обрабатывает натуральное число N по следующему алгоритму:
1) Строится двоичная запись числа N.
2) Запись «переворачивается», то есть читается справа налево. Если при этом появляются ведущие нули, они отбрасываются.
3) Полученное число переводится в десятичную систему счисления и выводится на экран.
Какое наименьшее число, превышающее 500, после обработки автоматом даёт результат 15?
Решение
n=501
while int(bin(n)[:1:-1],2)!=15:n+=1
print(n)
Ответ: 960
32)(№ 1780) На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.
1) Строится двоичная запись числа N.
2) К этой записи дописывается (дублируется) последняя цифра.
3) Затем справа дописывается 0, если в двоичном коде числа N чётное число единиц, и 1, если нечётное.
4) К полученному результату дописывается ещё один бит чётности так, чтобы количество единиц в двоичной записи полученного числа стало чётным.
Полученная таким образом запись (в ней на три разряда больше, чем в записи исходного числа N) является двоичной записью искомого числа R. Укажите минимальное число N, после обработки которого автомат получает число, большее 90. В ответе это число запишите в десятичной системе.
Решение
n=0
while True:
r=bin(n)[2:]
r+=r[-1]
r+=str(r.count('1')%2)+'0'
if int(r,2)>90: break
n+=1
print(n)
Ответ: 11
33)(№ 2775 А.М.Кабанов) Автомат обрабатывает натуральное число N по следующему алгоритму:
1) Строится двоичная запись числа N.
2) Из записи удаляются две последние цифры.
3) Полученное число переводится в десятичную запись и выводится на экран.
Сколько разных значений будет показано на экране автомата при последовательном вводе всех натуральных чисел от 20 до 600?
Решение
Вариант 1
m=set()
for x in range(20,601):m.add(int(bin(x)[2:-2],2))
print(len(m))
Вариант 2
s,k=':',0
for x in range(20,601):
y=int(bin(x)[2:-2],2)
if not(':'+str(y)+':' in s):
k+=1
s+=str(y)+':'
print(k)
Ответ: 146
34)(№ 2776 А.Богданов) Автомат обрабатывает натуральное число N по следующему алгоритму:
1) Строится двоичная запись числа N.
2) Все кроме первой значащие цифры инвертируются (0 заменяется на 1, а 1 на 0).
3) Полученное число переводится в десятичную запись.
4) Новое число складывается с исходным, полученная сумма выводится на экран.
Пример. Дано число N = 13. Алгоритм работает следующим образом.
1) Двоичная запись числа N: 13 = 11012
2) Все кроме первой значащие цифры инвертируются: 10102.
3) Десятичное значение полученного числа 10.
4) На экран выводится число 13 + 10 = 23.
Укажите такое наибольшее число N, для которого результат работы алгоритма не превышает 123?
Решение
for n in range(1,1000):
r=bin(n)[2:]
rr=r[0]
for c in r[1:]: rr+=str(abs(int(c)-1))
if n+int(rr,2)<123: maxn=n
print(maxn)
Ответ: 63
35)(№ 2777 А.М.Кабанов) Автомат обрабатывает натуральное число N<256 по следующему алгоритму:
1) Строится восьмибитная двоичная запись числа N.
2) Инвертируются все разряды исходного числа (0 заменяется на 1, 1 на 0).
3) К полученному двоичному числу прибавляют единицу.
4) Полученное число переводится в десятичную систему счисления.
Чему равен результат работы алгоритма для N = 80?
Решение
n,r=80,''
for s in '0'*(10-len(bin(n)))+bin(n)[2:]: r+=str(abs(int(s)-1))
print(int(r,2)+1)
Ответ: 176
36)(№ 3031) Автомат обрабатывает натуральное число N < 256 по следующему алгоритму:
1) Строится восьмибитная двоичная запись числа N-1.
2) Инвертируются все разряды исходного числа (0 заменяется на 1, 1 на 0).
3) Полученное число переводится в десятичную систему счисления.
Для какого значения N результат работы алгоритма равен 204?
Решение
for n in range(1,256):
r=bin(n-1)[2:]
r='0'*(8-len(r))+r
rr=''
for s in r: rr+=str(abs(int(s)-1))
if int(rr,2)==204: break
print(n)
Ответ: 52
37)(№ 3204) Автомат обрабатывает натуральное число N > 1 по следующему алгоритму:
1) Строится двоичная запись числа N.
2) В конец записи (справа) дописывается вторая справа цифра двоичной записи.
3) В конец записи (справа) дописывается вторая слева цифра двоичной записи.
4) Результат переводится в десятичную систему.
Пример. Дано число N = 11. Алгоритм работает следующим образом.
1) Двоичная запись числа N: 11 = 10112
2) Вторая справа цифра 1, новая запись 101112.
3) Вторая слева цифра 0, новая запись 1011102.
4) Десятичное значение полученного числа 46.
При каком наименьшем числе N в результате работы алгоритма получится R > 170? В ответе запишите это число в десятичной системе счисления.
Решение
n=2
while True:
r=bin(n)[2:]
r+=r[-2]+r[1]
if int(r,2)>170: break
n+=1
print(n)
Ответ: 43
38)(№ 3204) Алгоритм получает на вход натуральное число N > 1 и строит по нему новое число R следующим образом:
1) Строится двоичная запись числа N.
2) Подсчитывается количество нулей и единиц в полученной записи. Если их количество одинаково, в конец записи добавляется её последняя цифра. В противном случае в конец записи добавляется цифра, которая встречается реже.
3) Шаг 2 повторяется ещё два раза.
4) Результат переводится в десятичную систему счисления.
При каком наименьшем исходном числе N > 80 в результате работы алгоритма получится число, кратное 4?
Решение
n=81
while True:
r=bin(n)[2:]
for i in range(3):
k=r.count('1')
if k*2==len(r): r+=r[-1]
elif k*2<len(r): r+='1'
else: r+='0'
if int(r,2)%4==0: break
n+=1
print(n)
Ответ: 87
39)(№ 3938) Алгоритм получает на вход натуральное число N > 1 и строит по нему новое число R следующим образом:
1) Строится двоичная запись числа N.
2) Складываются все цифры полученной двоичной записи. В конец записи (справа) дописывается остаток от деления полученной суммы на 2.
3) Если количество единиц в двоичной записи числа N больше количества нулей, справа дописывается 0, иначе 1.
4) Результат переводится в десятичную систему счисления.
Сколько различных чисел, принадлежащих отрезку [50; 80], может получиться в результате работы автомата?
Решение
m=set()
for n in range(1000):
r=bin(n)[2:]
r+=str(r.count('1')%2)
r=int(r+str(int(r.count('1')*2<=len(r))),2)
if 50<=r<=80: m.add(r)
print(len(m))
Ответ: 7
40)(№ 4444 А. Богданов) На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.
1) Строится двоичная запись числа N.
2) Если N нечетное, то в конец полученной записи (справа) дописывается 0, в начало 1; если N четное в конец и начало дописывается по две единицы.
3) Результат переводится в десятичную систему и выводится на экран.
Например, N = 1410 = 11102. Число четное, следовательно, добавляем по две единицы по краям, получается 111110112 = 25110.
Укажите наибольшее число, меньшее 126, которое может являться результатом работы автомата.
Решение
maxr=0
for n in range(1000):
r=bin(n)[2:]
if n%2!=0: r='1'+r+'0'
else:r='11'+r+'11'
if int(r,2)<126:
maxr=max(maxr,int(r,2))
print(maxr)
Ответ: 123
41)(№ 1772) На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.
1. Строится двоичная запись числа N.
2. К этой записи дописывается (дублируется) последняя цифра.
3. Затем справа дописывается бит чётности: 0, если в двоичном коде полученного числа чётное число единиц, и 1, если нечётное.
4. К полученному результату дописывается ещё один бит чётности.
Полученная таким образом запись (в ней на три разряда больше, чем в записи исходного числа N) является двоичной записью искомого числа R. Какое минимальное число R, большее 66, может быть получено в результате работы автомата?
Решение
n,r=0,0
while r<=66:
n+=1
r=bin(n)[2:]
r=r+r[-1]
r=int(r+str(r.count('1')%2)+'0',2)
print(r)
Ответ: 78
42)(№ 11478 PRO100_ЕГЭ) На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.
1. Строится троичная запись числа N.
2. К этой записи дописываются справа ещё несколько разрядов по следующему правилу:
а) если N чётное, то к нему справа приписываются два нуля, а слева единица;
б) если N нечётное, то к нему справа приписывается в троичном виде сумма цифр его троичной записи;
Полученная таким образом запись (в ней как минимум на один разряд больше, чем в записи исходного числа N) является троичной записью искомого числа R.
Например, исходное число 410 = 113 преобразуется в число 111003 = 11710, а исходное число 710 = 213 преобразуется в число 21103 = 6610.
Укажите такое наименьшее число N, для которого число R больше числа 168. В ответе запишите это число в десятичной системе счисления.
Решение
for n in range(1,500):
nt=n
s=''
while nt>0:
s=str(nt%3)+s
nt//=3
if n%2==0:
s='1'+s+'00'
else:
sc=sum(list(map(int,s)))
sd=''
while sc>0:
sd=str(sc%3)+sd
sc//=3
s+=sd
if int(s,3)>168:
print(n)
break
Ответ: 10
43)(№ 8493 Апробация 17.05 ) На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.
1. Строится двоичная запись числа N.
2. Далее эта запись обрабатывается по следующему правилу:
а) если число N делится на 3, то к этой записи дописываются три последние двоичные цифры;
б) если число N на 3 не делится, то остаток от деления умножается на 3, переводится в двоичную запись и дописывается в конец числа.
Полученная таким образом запись является двоичной записью искомого числа R.
3. Результат переводится в десятичную систему и выводится на экран.
Например, для исходного числа 12 = 11002 результатом является число 11001002 = 100, а для исходного числа 4 = 1002 результатом является число 100112 = 19.
Укажите максимальное число N, после обработки которого с помощью этого алгоритма получается число R, меньшее чем 76.
Решение
for n in range(1,1000):
n2=bin(n)[2:]
if n%3==0:
if len(n2)>2:
n2+=n2[-3:]
else:
n2+=bin(n%3*3)[2:]
if int(n2,2)<76: maxn=n
print(maxn)
Ответ: 16
44)(№ 5233) На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.
1. Строится двоичная запись числа N.
2. Далее эта запись обрабатывается по следующему правилу:
а) если сумма цифр в двоичной записи числа чётная, то к этой записи слева дописывается 10, а затем два правых разряда заменяются на 00;
б) если сумма цифр в двоичной записи числа нечётная, то к этой записи слева дописывается 11, а затем два правых разряда заменяются на 11.
Полученная таким образом запись является двоичной записью искомого числа R.
Например, для исходного числа 610 = 1102 результатом является число 101002 = 2010, а для исходного числа 410 = 1002 результатом является число 111112 = 3110.
Укажите сумму различных чисел R, кратных 3, которые могут быть получены при обработке всех чисел N на отрезке [100; 200].
Решение
s=0
b=[]
for n in range(100,201):
n2=bin(n)[2:]
if n2.count('1')%2==0:n2='10'+n2[:-2]+'00'
else:n2='11'+n2[:-2]+'11'
r=int(n2,2)
if r%3==0:b.append(r)
print(sum(set(b)))
Ответ: 11400
45)(№ 6779 PRO100 ЕГЭ) На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.
1. Строится двоичная запись числа N.
2. Далее эта запись обрабатывается по следующему правилу:
а) если сумма цифр в двоичной записи числа чётная, то к этой записи справа дописывается 0, а затем три левых разряда заменяются на 101;
б) если сумма цифр в двоичной записи числа нечётная, то к этой записи справа дописывается 11, а затем два левых разряда заменяются на 10.
Полученная таким образом запись является двоичной записью искомого числа R.
Например, для исходного числа 610 = 1102 результатом является число 10102 = 1010, а для исходного числа 410 = 1002 результатом является число 100112 = 1910.
Укажите минимальное число N, после обработки которого с помощью этого алгоритма получается число R, большее 68. В ответе запишите это число в десятичной системе счисления.
Решение
for n in range(1,1000):
n2=bin(n)[2:]
if n2.count('1')%2==0: n2='101'+n2[3:]+'0'
else:n2='10'+n2[2:]+'11'
if int(n2,2)>68:print(n);break
Ответ: 19
46)(№ 1776 Досрочный ЕГЭ-2018) На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число следующим образом.
1) Строится двоичная запись числа N.
2) К этой записи дописываются справа ещё два разряда по следующему правилу: если N чётное, в конец числа (справа) дописываются два нуля, в противном случае справа дописываются две единицы.
Например, двоичная запись 1001 числа 9 будет преобразована в 100111.
Полученная таким образом запись (в ней на два разряда больше, чем в записи исходного числа N) является двоичной записью числа – результата работы данного алгоритма. Укажите минимальное число N, для которого результат работы алгоритма будет больше 115. В ответе это число запишите в десятичной системе счисления.
Решение
for n in range(300):
n2=bin(n)[2:]
if n%2==0: n2+='00'
else: n2+='11'
if int(n2,2)>115: print(n);break
Ответ: 29
47)(№ 1748) Автомат обрабатывает натуральное число N < 256 по следующему алгоритму:
1) Строится восьмибитная двоичная запись числа N.
2) Инвертируются все разряды исходного числа, кроме последней единицы и стоящих за ней нулей (0 заменяется на 1, 1 на 0).
3) Полученное число переводится в десятичную систему счисления.
Для какого значения N результат работы алгоритма равен 171?
Решение
for n in range(1,256):
n2=bin(n)[2:].zfill(8)
n2r=''
for c in n2[:n2.rfind('1')]:n2r+=str(abs(int(c)-1))
n2r+=n2[n2.rfind('1'):]
if int(n2r,2)==171:break
print(n)
Ответ: 85
48)(№ 1736) На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.
1. Строится двоичная запись числа N.
2. К этой записи дописываются справа ещё два разряда по следующему правилу:
а) складываются все цифры двоичной записи, и остаток от деления суммы на 2 дописывается в конец числа (справа). Например, запись 11100 преобразуется в запись 111001;
б) над этой записью производятся те же действия – справа дописывается остаток от деления суммы цифр на 2.
Полученная таким образом запись (в ней на два разряда больше, чем в записи исходного числа N) является двоичной записью искомого числа R. Какое наименьшее число, большее 108, может быть получено в результате работы автомата?
Решение
m=[]
for n in range(1,108):
n2=bin(n)[2:]
n2+=str(n2.count('1')%2)+'0'
r=int(n2,2)
if r>108:m.append(r)
print(min(m))
Ответ: 114
49)(№2781 А.М.Кабанов) Автомат обрабатывает натуральное число N<256 по следующему алгоритму:
1) Строится восьмибитная двоичная запись числа N.
2) Инвертируются все разряды исходного числа (0 заменяется на 1, 1 на 0).
3) К полученному двоичному числу прибавляют единицу.
4) Полученное число переводится в десятичную систему счисления.
Для какого числа N результат работы алгоритма равен 221?
Решение
for n in range(1,256):
n2=bin(n)[2:].zfill(8)
n2r=''
for c in n2:n2r+=str(abs(int(c)-1))
if int(n2r,2)+1==221:break
print(n)
Ответ: 35
50)(№7667 П. Финкель) На вход алгоритма подаётся шестизначное натуральное число N. Алгоритм строит по нему новое число R следующим образом:
1. Число N переводится в систему счисления с основанием 19.
2. Далее эта запись обрабатывается по следующему правилу:
а) согласные буквы (В, C, D, F, G, H) заменяются на 5;
б) в начало полученной записи дописывается остаток от деления числа N на 19 в 19-ричной системе счисления;
в) две последние цифры записи переставляются в начало (например, из строки 12345 получается 45123).
3. Действия а)-в) в п. 2. повторяются еще раз.
Полученная таким образом запись записью искомого числа R в системе счисления с основанием 19. Укажите максимальное число R с суммой цифр, кратной 7, которое может быть получено в результате работы алгоритма. Запишите его в ответе в десятичной системе счисления.
Решение
def f(x,y):
global al
s=''
while x>0: s+=al[x%y]; x//=y
return s[::-1]
def s(x):
global al
k=0
for c in x: k+=al.find(c)
return k
max19=0
al='0123456789'
for i in range(26):al+=chr(ord('A')+i)
for n in range(10**5,10**6):
n19=f(n,19)
for j in range(2):
for c in 'BCDFGH': n19=n19.replace(c,'5')
n19=al[n%19]+n19
n19=n19[-2:]+n19[:-2]
while n19[0]=='0':n19=n19[1:]
if s(n19)%7==0:max19=max(max19,int(n19,19))
print(max19)
Ответ: 893871724
51)(№7666 П.Финкель) На вход алгоритма подаётся пятизначное натуральное число N. Алгоритм строит по нему новое число R следующим образом:
1. Число N переводится в двадцатеричную систему счисления.
2. Далее эта запись обрабатывается по следующему правилу:
а) гласные буквы (A, E, I) заменяются на 1;
б) в конец полученной записи дописывается остаток от деления числа N на 20 в двадцатеричной системе счисления;
в) первая цифра переставляется в конец записи.
3. Действия а)-в) в п. 2. повторяются еще раз.
Полученная таким образом запись записью искомого числа R в двадцатеричной системе счисления. Укажите максимальное число R, кратное 2030, которое может быть получено в результате работы алгоритма. Запишите его в ответе в десятичной системе счисления.
Решение
def f(x,y):
global al
s=''
while x>0: s+=al[x%y]; x//=y
return s[::-1]
al='0123456789'
for i in range(26):al+=chr(ord('A')+i)
max20=0
for n in range(10**4,10**5):
n20=f(n,20)
for i in range(2):
n20=n20.replace('A','1').replace('E','1').replace('I','1')+al[n%20]
n20=n20[1:]+n20[0]
r=int(n20,20)
if r%2030==0:max20=max(max20,r)
print(max20)
Ответ: 63656740
52)(№7650 Н.Сафронов) На вход алгоритма подаётся натуральное четырехзначное число N, в десятичной записи которого есть как чётные, так и нечётные цифры (к другим числам алгоритм неприменим). Алгоритм строит по нему новое число R следующим образом:
1. Если в числе N четных чисел больше, то вычисляется сумма всех четных цифр числа N, иначе вычисляется сумма всех нечетных цифр числа N.
2. Если на предыдущем шаге получилось четное число, то к нему справа приписывается максимальная четная цифра числа N, иначе слева приписывается минимальная нечетная цифра числа N.
Сколько существует чисел N, для которых результат работы автомата R равен 111?
Решение
def f(x):
m1,m2=[],[]
for c in str(x):
if c in '13579':m1.append(int(c))
else: m2.append(int(c))
return m1,m2
k=0
for n in range(10**3,10**4):
a,b=f(n)
if len(a)*len(b)!=0:
if len(a)<len(b):s=sum(b)
else:s=sum(a)
if s%2==0: s=s*10+max(b)
else: s=min(a)*10**len(str(s))+s
if s==111: k+=1
print(k)
Ответ: 228
53)(№7649 Н.Сафронов) На вход алгоритма подаётся натуральное четырехзначное число N, в десятичной записи которого есть как чётные, так и нечётные цифры (к другим числам алгоритм неприменим). Алгоритм строит по нему новое число R следующим образом:
1. Из всех четных цифр числа N составляется наибольшее число.
2. Из всех нечетных цифр числа N составляется наименьшее число.
3. Вычисляется сумма двух чисел
, построенных в результате шагов 1 и 2.
Укажите максимальное число R, которое может быть результатом работы данного алгоритма и в котором все цифры десятичной записи идут в порядке убывания.
Решение
def f(x):
m1,m2=[],[]
for c in str(x):
if c in '13579':m1.append(int(c))
else: m2.append(int(c))
return m1,m2
maxr=0
for n in range(10**3,10**4):
a,b=f(n)
if len(a)*len(b)>0:
a1,b1=0,0
for x in sorted(a): a1=a1*10+x
for x in sorted(b)[::-1]:b1=b1*10+x
r=b1+a1;rs=str(r)
fl=1
for i in range(len(rs)-1):
if rs[i]<=rs[i+1]:fl=0;break
if fl and maxr<r:maxr=r
print(maxr)
Ответ: 875
54)(№7649 Н.Сафронов) На вход алгоритма подаётся натуральное четырехзначное число N, в десятичной записи которого есть как чётные, так и нечётные цифры (к другим числам алгоритм неприменим). Алгоритм строит по нему новое число R следующим образом:
1. Из всех четных цифр числа N составляется наибольшее число.
2. Из всех нечетных цифр числа N составляется наименьшее число.
3. Вычисляется сумма двух чисел, построенных в результате шагов 1 и 2.
Укажите минимальное число R, которое может быть результатом работы данного алгоритма и в котором все цифры десятичной записи идут в порядке убывания.
Решение
def f(x):
m1,m2=[],[]
for c in str(x):
if c in '13579':m1.append(int(c))
else: m2.append(int(c))
return m1,m2
minr=10**6
for n in range(10**3,10**4):
a,b=f(n)
if len(a)*len(b)>0 and not(b == [0,0] or b==[0,0,0]):
a1,b1=0,0
for x in sorted(a): a1=a1*10+x
for x in sorted(b)[::-1]:b1=b1*10+x
r=b1+a1;rs=str(r)
fl=1
for i in range(len(rs)-1):
if rs[i]<=rs[i+1]:fl=0;break
if fl and minr>r:minr=r
print(minr)
Ответ: 31
55)(№7639 Демо-2025) На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.
1. Строится двоичная запись числа N.
2. Далее эта запись обрабатывается по следующему правилу:
а) если число чётное, то к двоичной записи числа слева дописывается 10;
б) если число нечётное, то к двоичной записи числа слева дописывается 1 и справа дописывается 01.
Полученная таким образом запись (в ней на два разряда больше, чем в записи исходного числа N) является двоичной записью искомого числа R.
Например, для исходного числа 4 = 1002 результатом является число 20 = 101002, а для исходного числа 5 = 1012 это число 53 = 1101012.
Укажите максимальное число R, которое может быть результатом работы данного алгоритма, при условии, что N не больше 12. В ответе запишите это число в десятичной системе счисления.
Решение
m=[]
for n in range(1,12):
n2=bin(n)[2:]
if n%2==0: n2='10'+n2
else: n2='1'+n2+'01'
m.append(int(n2,2))
print(max(m))
Ответ: 109
56)(№7406 А.Минак) На вход алгоритма подаётся натуральное число N > 143. Алгоритм строит по нему новое число R следующим образом.
1. Строится запись числа N в двенадцатеричной системе счисления.
2. Далее эта запись обрабатывается по следующему правилу:
а) если N делится на 12, то в конец этой записи дописываются три её последние цифры;
б) если число N на 12 не делится, то остаток от деления умножается на 3, переводится в двенадцатеричную запись и дописывается в начало числа.
Полученная таким образом запись является двенадцатеричной записью искомого числа R.
Например, для исходного числа 204 = 15012 результатом является число 15015012 = 352716, а для исходного числа 275 = 1AB12 это число 291AB12 = 57299.
Укажите такое число N, после обработки которого с помощью этого алгоритма получится наибольшее число R, которое меньше 58000.
Решение
def f(x,y):
r=''
while x>0: r+=al[x%y]; x//=y
return r[::-1]
maxr=0
al='0123456789'
for i in range(26):al+=chr(ord('A')+i)
for n in range(144,58000):
n12=f(n,12)
if n%2==0:r=int(n12+n12[-3:],12)
else: r=int(f(n%12*3,12)+n12,12)
if r<58000 and maxr<r: maxr=r;maxn=n
print(maxn)
Ответ: 971
57)(№7405 А.Минак) На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.
1. Строится запись числа N в тринадцатеричной системе счисления.
2. Далее эта запись обрабатывается по следующему правилу:
а) складываются числовые значения всех цифр этой тринадцатеричной записи, и остаток от деления этой суммы на 13 в тринадцатеричной системе счисления дописывается в конец числа (справа);
б) над этой записью производятся те же действия – справа дописывается остаток от деления суммы числовых значений её цифр на 13.
Полученная таким образом запись является тринадцатеричной записью искомого числа R.
Например, для исходного числа 77 = 5C13 результатом является число 5C4813 = 13073.
Укажите число N, после обработки которого с помощью этого алгоритма получается наибольшее число R, меньшее 6000.
Решение
def f(x,y):
r=''
while x>0: r+=al[x%y];x//=y
return r[::-1]
def fs(x):
s=0
for c in x: s+=al.find(c)
return s
al='0123456789'
for i in range(26):al+=chr(ord('A')+i)
maxr=0
for n in range(1,6000):
n13=f(n,13)
for i in range(2): n13=n13+al[int(fs(n13))%13]
r=int(n13,13)
if r<6000 and maxr<r: maxr=r;maxn=n
print(maxn)
Ответ: 34
58)(№7370 Н.Леко) Автомат обрабатывает десятичное целое число N (0 ≤ N ≤ 255) по следующему алгоритму:
1. Строится восьмибитная двоичная запись числа N.
2. Все разряды двоичной записи инвертируются (0 заменяется на 1, 1 на 0).
3. Если полученное число кратно 5, то в двоичной записи старшие три разряда заменяются на 100, в противном случае в двоичной записи старшие три разряда заменяются на 101.
Полученная таким образом запись является двоичной записью искомого числа R. Сколько существует чисел N, из которых в результате выполнения алгоритма может получиться число 180?
Решение
k=0
for n in range(256):
n2=bin(n)[2:].zfill(8)
n2r=''
for c in n2:n2r+=str(abs(int(c)-1))
if len(n2r)>2:
if int(n2r,2)%5==0:n2r='100'+n2r[3:]
else:n2r='101'+n2r[3:]
if int(n2r,2)==180: k+=1
print(k)
Ответ: 6
59)(№7055 PRO100-ЕГЭ) На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.
1. Строится троичная запись числа N.
2. К этой записи дописываются справа ещё несколько разрядов по следующему правилу:
а) если N чётное, то к нему справа приписываются два нуля, а слева единица;
б) если N нечётное, то к нему справа приписывается в троичном виде сумма цифр его троичной записи.
Полученная таким образом запись (в ней как минимум на один разряд больше, чем в записи исходного числа N) является троичной записью искомого числа R.
Например, исходное число 410 = 113 преобразуется в число 111003 = 11710, а исходное число 710 = 213 преобразуется в число 21103 = 6610.
Укажите такое наименьшее число N, для которого число R больше числа 168. В ответе запишите это число в десятичной системе счисления.
Решение
def f(x):
n3=''
while x>0: n3=str(x%3)+n3;x//=3
return n3
for n in range(168):
n3=f(n)
if n%2==0: n3='1'+n3+'00'
else: n3=n3+f(sum(map(int,n3)))
if int(n3,3)>168:print(n);break
Ответ: 10
60)(№7000 Е.Джобс) Автомат обрабатывает натуральное девятиразрядное число N по следующему алгоритму:
1. Находится сумма разрядов числа N.
2. Полученное число переводится в двоичную систему счисления.
3. К записи, полученной на предыдущем этапе, дописываются разряды по следующему правилу:
a) Если количество единиц четное дописывается единица слева и два нуля справа,
b) Если количество единиц нечетное дописывается 10 слева и 1 справа.
Полученная таким образом запись является двоичной записью искомого числа R.
Пример. Дано число N = 123456789. Алгоритм работает следующим образом:
1. Сумма разрядов 45.
2. Двоичная запись 101101.
3. Единиц четное количество, следовательно, получаем 1+101101+00 = 110110100.
4. 1101101002 = 436.
Сколько существует чисел N, для которых результат работы автомата равен 21?
Решение
Программное решение перебором выполняется за 35 мин.
Ручной способ (рассуждениями).
1. Переводим число 21 в двоичный код. 21 => 101012
2. Число 21 получено по правилу b. 101012=10 + 102 + 1
3. 102=2. Из этого делаем вывод - в нашем числе есть только две 1 или одна 2.
4. 110000000, 101000000, 100100000, 100010000, 100001000, 100000100, 10000010, 100000001, 200000000 - всего 9 чисел
Ответ: 9
61)(№ 6883 К.Багдасарян ) Алгоритм получает на вход натуральное число N > 4 и строит по нему новое число R следующим образом:
1. Строится пятеричная запись числа N.
2. Далее эта запись обрабатывается по следующему правилу:
а) если число N делится на 5, то в конец дописываются две последние цифры пятеричной записи числа;
б) если число N на 5 не делится, то остаток от его деления на 5 умножается на 7, переводится в пятеричную запись и дописывается в конец числа.
Полученная таким образом запись является пятеричной записью искомого числа R.
Укажите минимальное число R, большее 200, которое может быть получено с помощью описанного алгоритма. В ответе запишите это число в десятичной системе счисления.
Решение
def f(x,y):
al='0123456789'
s=''
while x>0: s+=al[x%y]; x//=y
return s[::-1]
minr=10**16
for n in range(4,1000):
n5=f(n,5)
if n%5==0: n5+=n5[-2:]
else:n5+=f(n%5*7,5)
r=int(n5,5)
if r>200:minr=min(minr,r)
print(minr)
Ответ: 221
62)(№ 1786) На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.
1) Строится двоичная запись числа N.
2) Затем справа дописываются два разряда: символы 01, если число N чётное, и 10, если нечётное.
Полученная таким образом запись (в ней на два разряда больше, чем в записи исходного числа N) является двоичной записью искомого числа R. Укажите минимальное число N, после обработки которого автомат получает число, большее 73. В ответе это число запишите в десятичной системе.
Решение
for n in range(1000):
n2=bin(n)[2:]
if n%2==0: n2+='01'
else:n2+='10'
r=int(n2,2)
if r>73: print(n); break
Ответ: 19
Page updated
Google Sites
Report abuse