Исполнитель математик преобразует целые числа у исполнителя есть две команды которым присвоены
Перейти к содержимому

Исполнитель математик преобразует целые числа у исполнителя есть две команды которым присвоены

Исполнитель математик преобразует целые числа у исполнителя есть две команды которым присвоены

Скачай курс
в приложении

Перейти в приложение
Открыть мобильную версию сайта

© 2013 — 2023. Stepik

Наши условия использования и конфиденциальности

Get it on Google Play

Public user contributions licensed under cc-wiki license with attribution required

Разбор демоверсии ЕГЭ по информатике 2022 (22-27 Задание)

Продолжаем анализ демонстрационного варианта ЕГЭ по информатике 2022.

В этой статье разберём с 22-ого по 27 задание.

ЕГЭ по информатике 2022 будет повержено!

Ниже на четырёх языках программирования записан алгоритм. Получив на вход число x, этот алгоритм печатает два числа: L и M. Укажите наибольшее число x, при вводе которого алгоритм печатает сначала 4, а потом 5.

ЕГЭ по информатике демоверсия 2022 - задание 12

Решение данного задания будет похоже на решение 6 задания из ЕГЭ по информатике 2022.

С помощью перебора на языке Python найдём при каких значениях переменная L=4 И переменная M=5 в конце программы.

for i in range(1, 1000): X=i Q=9 L=0 while X >= Q: L = L + 1 X = X - Q M=X if M < L: M = L L = X if L==4 and M==5: print(i)

Наибольшее значение равно 49.

Исполнитель преобразует число на экране.

У исполнителя есть две команды, которым присвоены номера:

 1. Прибавить 1 2. Умножить на 2 

Программа для исполнителя – это последовательность команд. Сколько существует программ, для которых при исходном числе 1 результатом является число 20, и при этом траектория вычислений содержит число 10?

Траектория вычислений программы – это последовательность результатов выполнения всех команд программы. Например, для программы 121 при исходном числе 7 траектория будет состоять из чисел 8, 16, 17.

Решим задачу c помощью шаблона на языке Python.

def F(x, y): if x == y: return 1 if x > y: return 0 if x < y: return F(x+1, y) + F(x*2, y) print(F(1, 10)*F(10, 20))

Число x, это то число, с которым мы работаем. Число y — это куда нужно прийти.

Если число x достигло пункта назначения, то возвращаем 1. Если оно перескочило y, то возвращаем 0. А если ещё не дошло до y, то продолжаем вычисления с помощью рекурсии.

У нас число 10 обязательное, поэтому разбиваем функцию следующим образом F(1, 10)*F(10, 20), через умножение. Это и будет ответ. Получается 28.

Текстовый файл состоит из символов P, Q, R и S.

Определите максимальное количество идущих подряд символов в прилагаемом файле, среди которых нет идущих подряд символов P. Для выполнения этого задания следует написать программу.

Решение:

Напишем решение на языке Python.

f=open('24.txt') s=f.read() count=1 mx=0 for i in range(0, len(s)-1): if s[i]=='P' and s[i+1]=='P': count=1 else: count=count+1 mx = max(mx, count) print(mx)

Подсчитываем символы, пока не встретилась комбинация двух P подряд. Как только встретилась данная комбинация, сбрасываем счётчик на 1. Здесь мы сбрасываем счётчик на значение 1, чтобы учесть один символ, которые находится в самой комбинации PP. И в начале мы тоже устанавливаем счётчик в значение 1 по этой же причине.

ЕГЭ по информатике демоверсия 2022 - задание 24 решение

Мы проходим в цикле for до длины строки минус один. Значение 1 в счётчике при сбросе и в начале программы так же компенсирует и тот момент, что мы не подсчитываем последний символ!

При изменении счётчика, сохраняем максимальное значение в переменной mx

Если бы у нас была вместо PP другая комбинация, состоящая к примеру из 5 символов, то мы бы тогда в начале и при сбросе писали в счётчик значение 5-1=4.

В этой задаче получается ответ 188.

Пусть M – сумма минимального и максимального натуральных делителей целого числа, не считая единицы и самого числа. Если таких делителей у числа нет, то значение M считается равным нулю.

Напишите программу, которая перебирает целые числа, бо́льшие 700 000, в порядке возрастания и ищет среди них такие, для которых значение M оканчивается на 8. Выведите первые пять найденных чисел и соответствующие им значения M.

Формат вывода: для каждого из пяти таких найденных чисел в отдельной строке сначала выводится само число, затем – значение М. Строки выводятся в порядке возрастания найденных чисел.

Количество строк в таблице для ответа избыточно.

ЕГЭ по информатике демоверсия 2022 - задание 25

На ЕГЭ по информатике 2022 удобно писать программы на языке Python.

import math count=0 for i in range(700001, 800000): b=0 for j in range(2, int(math.sqrt(i)) + 1): if i%j==0: b=round(i/j) break if b==0: M=0 else: M=j+b if M!=0 and M%10==8: count=count+1 print(i, M) if count==5: break 

В данной программе перебираются числа в цикле for, начиная с 700001.

Переменная b-считается наибольшим делителем числа i. Затем, с помощью ещё одного цикла for перебираются числа с 2 до корня числа i (включительно). Ищем тем самым наименьший делитель.

Если до корня числа включительно не встретился ни один делитель, значит, у числа нет делителей, кроме 1 и самого числа.

ЕГЭ по информатике демоверсия 2022 - задание 25 поиск делителей

Пусть у нас есть число A. Если у этого числа есть делитель d1, то он находится до корня этого числа. А вот то число (так же делитель), на которое умножается это число d1, чтобы получить A, будет находиться после корня A.

Получается, что у каждого делителя есть своя пара. У единицы — это само число. Причём один делитель из пары находится до корня, другой после корня. Исключением будет тот случай, когда из числа А извлекается целый корень. Тогда для этого корня не будет пары (парой и будет само это число √A * √A = A).

Таким образом, первый найденный делитель будет являться наименьшим делителем. А вот делительный, который находится в паре с наименьшим делителем, будет наибольшим.

После того, как мы нашли наименьший делитель (он будет сидеть в переменной j) и наибольший делитель b, выходим из второго цикла for.

Если переменная b осталась равна нулю, то, значит, у числа i нет указанных делителей, и переменная M должна равняться 0. Если b не равна нулю, то M=j+b.

Проверить, на что оканчивается число, можно узнав остаток от деления числа на 10.

Переменная count следит, чтобы было распечатано ровно 5 чисел, которые удовлетворяют условию задачи.

Ответ:

700005 233338
700007 100008
700012 350008
700015 140008
700031 24168

Системный администратор раз в неделю создаёт архив пользовательских файлов. Однако объём диска, куда он помещает архив, может быть меньше, чем суммарный объём архивируемых файлов.

Известно, какой объём занимает файл каждого пользователя.

По заданной информации об объёме файлов пользователей и свободном объёме на архивном диске определите максимальное число пользователей, чьи файлы можно сохранить в архиве, а также максимальный размер имеющегося файла, который может быть сохранён в архиве, при условии, что сохранены файлы максимально возможного числа пользователей.

В первой строке входного файла находятся два числа: S – размер свободного места на диске (натуральное число, не превышающее 10 000) и N – количество пользователей (натуральное число, не превышающее 1000). В следующих N строках находятся значения объёмов файлов каждого пользователя (все числа натуральные, не превышающие 100), каждое – в отдельной строке.

Запишите в ответе два числа: сначала наибольшее число пользователей, чьи файлы могут быть помещены в архив, затем – максимальный размер имеющегося файла, который может быть сохранён в архиве, при условии, что сохранены файлы максимально возможного числа пользователей.

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

При таких исходных данных можно сохранить файлы максимум двух пользователей. Возможные объёмы этих двух файлов – 30 и 40, 30 и 50 или 40 и 50. Наибольший объём файла из перечисленных пар – 50, поэтому ответ для приведённого примера:

Решим задачу с помощью Excel. Чтобы открыть текстовый файл в программе Excel, выбираем Файл->Открыть, выбираем нужную папку и указываем, чтобы в папке были видны все типы файлов.

ЕГЭ по информатике демоверсия 2022 - задание 26 решение

И выбираем наш текстовый файл.

Выскочит окно Мастер текстов (импорт). Здесь оставляем выбранный пункт с разделителями и кликаем Далее.

В следующем окне поставим ещё галочку пробел. В итоге Символами-разделителем будут знак табуляции и пробел.

Кликаем ещё раз Далее и Готово.

Наши данные вставятся, как нужно!

ЕГЭ по информатике демоверсия 2022 - задание 26 решение 2

Число 8200 (размер свободного места) нужно запомнить или записать на черновике. Число 970 (количество файлов) нам в принципе не нужно при таком подходе решения.

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

1. Найдём максимальное количество файлов.

Выделяем весь столбец A и сортируем его по возрастанию.

ЕГЭ по информатике демоверсия 2022 - задание 26 решение 3

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

ЕГЭ по информатике демоверсия 2022 - задание 26 сумма ячеек

Мы должны выделить максимальное количество ячеек, но чтобы сумма не превышала число 8200.

Получается максимальное количество файлов, которое можно сохранить, равно 568.

2. Найдём максимальный размер файла при максимальном количестве файлов.

Если мы сохраним максимальное количество файлов, то у нас ещё останется свободное место 8200-8176=24, т.к. сумма выделенных ячеек равна 8176.

Мы можем заменить наибольший файл (последняя выделенная ячейка равная 29) ещё большим файлом, размер которого не превышает 24+29=53.

Если покрутим таблицу вниз, то найдём такой файл размером 50. Это и будет наибольший файл при максимальном количестве файлов.

Ответ:

568 50

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

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

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

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

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

Напишем программу на Python.

f=open('27_B.txt') n=int(f.readline()) sum_ost=[1096594666]*43 #Массив, который содержит минимальные суммы для разных остатков k=[0]*43 #Запоминаем, при каком i сохранили в sum_ost очередную сумму. mx=0 #Максимальная сумма нужной цепочки в данный момент времени ln=0 #Длина нужной цепочки s=0 #Сумма цепочки с первого до i-ого элемента sum_ost[0]=0 #Для остатка ноль ничего от s отнимать не нужно k[0]=-1 #Для остатка ноль индекс равен -1, чтобы правильно считалась длина цепочки for i in range(n): x=int(f.readline()) s = s + x ost = s % 43 if s-sum_ost[ost]==mx: ln=min(ln, i - k[ost]) if s-sum_ost[ost] > mx: mx = s - sum_ost[ost] ln = i - k[ost] if sum_ost[ost]==1096594666: sum_ost[ost] = s k[ost] = i print(ln)

Переменная s — это сумма от первого до текущего элемента i. На каждом шаге вычисляется остаток от деления s на 43. И записывается в массив sum_ost эта сумма s для каждого остатка.

Тогда кандидатом для ответа будет цепочка, которая получается, если от цепочки с суммой s «отрезать» цепочку с суммой из массив sum_ost, которая соответствует текущему остатку (переменная ost).

ЕГЭ по информатике демоверсия 2022 - задание 27 решение

В массив sum_ost для каждого остатка записывается сумма только один раз, т.к. нам нужна именно минимальная сумма для каждого остатка, чтобы кандидат для ответа был как можно больше.

В начале массив sum_ost инициализируется очень большим числом 1096594666. Это число больше, чем сумма всех элементов в файле. Оно было найдено до основного решения, с помощью простой программы.

В процессе решения мы ищем среди кандидатов для ответа цепочку с максимальной суммой. Делаем это стандартным образом: кто больше, то и победил. Мы инициализируем большими числом 1096594666 элементы массива sum_ost для того, чтобы условие нормально сработало, когда в массиве sum_ost ещё нет суммы для данного остатка.

Так же мы сохраняем индексы элементов в массив k, когда записываем суммы для различных остатков в массив sum_ost. Это делается для того, чтобы можно было вычислить длину цепочки.

Для случая, когда остаток равен 0, устанавливаем сумму в массиве sum_ost равной нулю, потому что кандидатом на ответ будет цепочка от самого первого до i-ого элемента. Это, можно сказать, исключительный случай. И чтобы правильно вычислялась длина цепочки, для случая, когда остаток равен нулю, индекс в массив k делаем равным -1.

Ответ:

185 329329

Демоверсия ЕГЭ по информатике 2023 (Задания 22-27)

Продолжаем решать демоверсию ЕГЭ по информатике 2023.

В этой статье разберём задания 22-27.

В файле содержится информация о совокупности N вычислительных процессов, которые могут выполняться параллельно или последовательно. Будем говорить, что процесс B зависит от процесса A, если для выполнения процесса B необходимы результаты выполнения процесса A. В этом случае процессы могут выполняться только последовательно.

Информация о процессах представлена в файле в виде таблицы. В первой строке таблицы указан идентификатор процесса (ID), во второй строке таблицы – время его выполнения в миллисекундах, в третьей строке перечислены с разделителем «;» ID процессов, от которых зависит данный процесс. Если процесс является независимым, то в таблице указано значение 0.

ЕГЭ по информатике демоверсия 2023 - задание 22

Определите минимальное время, через которое завершится выполнение всей совокупности процессов, при условии, что все независимые друг от друга процессы могут выполняться параллельно.

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

Здесь есть процессы, которые зависят от других процесов. В столбце D вычислим время для всех процесов, с учётом зависимости.

Если процесс зависит от двух процессов, то время ожидания будет равно самому медленному из этих процессов.

В столбце D пишем для каждой строчки: время процесса + время ожидания самого медленного процесса, от которого зависит этот процесс (если такие есть).

Получается такая картина:

ЕГЭ по информатике демоверсия 2023 - задание 22 решение

Система заврешить работу, когда завершится самый медленный процесс.

Задание 23

Исполнитель преобразует число на экране.

У исполнителя есть две команды, которым присвоены номера:

1. Прибавить 1
2. Умножить на 2

Программа для исполнителя – это последовательность команд. Сколько существует программ, для которых при исходном числе 1 результатом является число 35, при этом траектория вычислений содержит число 10 и не содержит 17?

Траектория вычислений программы – это последовательность результатов выполнения всех команд программы. Например, для программы 121 при исходном числе 7 траектория будет состоять из чисел 8, 16, 17.

Будем решать с помощью шаблона на языке Python, который был представлен в видеокурсе по подготовке к ЕГЭ по информатике.

def F(x, y): if x == y: return 1 if x > y or x==17: return 0 if x < y: return F(x+1, y) + F(x*2, y) print(F(1, 10)*F(10, 35))

Задание 24

Текстовый файл состоит из символов A, B, C, D и O.

Определите максимальное количество идущих подряд пар символов вида

в прилагаемом файле.

Для выполнения этого задания следует написать программу.

Подобная задача была рассмотрена в видеокурсе к ЕГЭ по информатике.

f=open('24_10.txt') s=f.read() s=s.replace('BA', '1') s=s.replace('CA', '1') s=s.replace('DA', '1') s=s.replace('BO', '1') s=s.replace('CO', '1') s=s.replace('DO', '1') k=0 kmax=0 for i in range(0, len(s)): if s[i]=='1': k=k+1 kmax=max(k, kmax) else: k=0 print(kmax)

Ответ получается 24, но в официальном ответе 95. Дело в том, что в файле присутствует буква F, хотя в условии сказано, что файл состоит только из букв A, B, C, D и O. Следовательно, файл к задаче не верный.

Назовём маской числа последовательность цифр, в которой также могут встречаться следующие символы:

– символ «?» означает ровно одну произвольную цифру;

символ «*» означает любую последовательность цифр произвольной длины; в том числе «*» может задавать и пустую последовательность.

Например, маске 123*4?5 соответствуют числа 123405 и 12300405. Среди натуральных чисел, не превышающих 10 10 , найдите все числа, соответствующие маске 1?2139*4, делящиеся на 2023 без остатка.

В ответе запишите в первом столбце таблицы все найденные числа в порядке возрастания, а во втором столбце – соответствующие им результаты деления этих чисел на 2023.

Количество строк в таблице для ответа избыточно.

Подобная задача так же обсуждалась в видеокурсе и на обзоре реального экзамена ЕГЭ по информатике от 20.06.22

Если не учитывать звёздочку, число 1?21394 имеет семь разрядов. Максимальная верхняя граница 10 10 . Значит, для звёздочки есть три разряда.

#Вместо звёздочки ноль разрядов for x in '0123456789': s = '1' + x + '21394' i=int(s) if i%2023==0: print(i, i//2023) #Вместо звёздочки один разряд for x in '0123456789': for y in '0123456789': s = '1' + x + '2139' + y + '4' i=int(s) if i%2023==0: print(i, i//2023) #Вместо звёздочки два разряда for x in '0123456789': for y in '0123456789': for z in '0123456789': s = '1' + x + '2139' + y + z + '4' i=int(s) if i%2023==0: print(i, i//2023) #Вместо звёздочки три разряда for x in '0123456789': for y in '0123456789': for z in '0123456789': for w in '0123456789': s = '1' + x + '2139' + y + z + w + '4' i=int(s) if i%2023==0: print(i, i//2023)

Ответ:

162139404 80148
1321399324 653188
1421396214 702618
1521393104 752048

Задание 26

В магазине для упаковки подарков есть N кубических коробок. Самой интересной считается упаковка подарка по принципу матрёшки — подарок упаковывается в одну из коробок, та в свою очередь в другую коробоку и т.д. Одну коробку можно поместить в другую, если длина её стороны хотя бы на 3 единицы меньше длины стороны другой коробки. Определите наибольшее количество коробок, которое можно использовать для упаковки одного подарка, и максимально возможную длину стороны самой маленькой коробки, где будет находиться подарок. Размер подарка позволяет поместить его в самую маленькую коробку.

В первой строке входного файла находится число N — количество коробок в магазине (натуральное число, не превышающая 10 000). В следующих N строках находятся значения длин сторон коробок (все числа натуральные, не превышающие 10 000), каждое — в отдельной строке.

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

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

Пример входного файла приведён для пяти коробок и случая, когда минимальная допустимая разница между длинами сторон коробок, подходящих упаковки «матрёшки», составлят 3 единицы.

При таких исходных данных условию задачи удовлетворяют наборы коробок с длинами сторон 30, 40 и 43 или 32, 40 и 43 соответственно, т.е. количество коробок равно 3, а длина стороны самой маленькой коробки равна 32.

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

f=open('26.txt') n=int(f.readline()) a=[] for i in range(n): x=int(f.readline()) a.append(x) a.sort(reverse=True) k=1 p=a[0] for i in range(1, len(a)): if p-a[i]>=3: k=k+1 p=a[i] print(k, p)

В начале считываем все числа в массив (список) a. Сортируем их в порядке убывания.

Приступаем собирать упаковку. Начинаем с самой большой упаковки. Большую упаковку точно можно взять в наш подарок. Переменная p — это размер последний коробки, которую мы взяли. Переменная k — количество коробок в подарке на текущий момент времени.

Если следующая коробка подходит по условию, то мы её берём в наш подарок. Кто-то может подумать, что может выгоднее взять не самую большую коробку, а предпоследнего размера. Но все размеры которые будут подходить для предпоследнего элемента, точно будут подходить и для последнего, и количество упаковок точно не будет меньше, если мы берём самую большую коробку.

Дубликаты не влияют на ответы.

Если мы начинаем с самой большой коробки, то в самом конце в переменной p окажется максимальный размер самой маленькой коробки.

Ответ:

2767 51

Задание 27

У медицинской компании есть N пунктов приёма биоматериалов на анализ. Все пункты расположены вдоль автомагистрали и имеют номера, соответствующие расстоянию от нулевой отметки до конкретного пункта. Известно количество пробирок, которое ежедневно принимают в каждом из пунктов. Пробирки перевозят в специальных транспортировочных контейнерах вместимостью не более 36 штук. Каждый транспортировочный контейнер упаковывается в пункте приёма и вскрывается только в лаборатории. Компания планирует открыть лабораторию в одном из пунктов. Стоимость перевозки биоматериалов равна произведению расстояния от пункта до лаборатории на количество контейнеров с пробирками. Общая стоимость перевозки за день равна сумме стоимостей перевозок из каждого пункта в лабораторию. Лабораторию расположили в одном из пунктов приёма биоматериалов таким образом, что общая стоимость доставки биоматериалов из всех пунктов минимальна.

Определите минимальную общую стоимость доставки биоматериалов из всех пунктов приёма в лабораторию.

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

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

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

Типовой пример организации данных во входном файле
6
1 100
2 200
5 4
7 3
8 2
10 190

При таких исходных данных и вместимости транспортировочного контейнера, составляющей 96 пробирок, компании выгодно открыть лабораторию в пункте 2. В этом случае сумма транспортных затрат составит: 1*2 + 3*1 + 5*1 + 6*1 + 8*2.

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

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

import math f=open('27B.txt') k=9999995 n=int(f.readline()) a=[0]*k sm=0 for i in range(n): x, y = f.readline().split() x=int(x) y=int(y) z = math.ceil(y/36) a[x] = z sm = sm + (x-1)*z # Вспомогательные суммы s1=[] s2=[] s1.append(0) s2.append(0) s1.append(0) s2.append(0) for i in range(1, k): s1[1] = s1[1] + a[i] for i in range(2, k): s1.append(s1[i-1] - a[i-1]) s2.append(s2[i-1] + a[i-1]) # Ищем минимальное значение mn=sm for i in range(2, k): sm = sm - s1[i] + s2[i] mn=min(mn, sm) print(mn)

Переменная k — это количество приёмных пунктов (Т.е. длина массива a). Превая ячейка соответсвует приёмному пункту под номером 1, вторая ячейка под номером 2 и т.д. Само значение для k мы смотрим в конце файла. Например, для файла A значение напишем 999. Всего 998 приёмных пунктов, но т.к. индексы в массиве начинаются с 0, то мы должны завести 999 ячеек. Т.е. нулевая ячейка не будет никак задействована. Для файла B устанавливаем k в 9999995.

В сами ячейки массива мы поместим для каждого приёмного пункта количество контейнеров. Их легко вычислить. Если количество пробирок не нулевое, то мы должны это количество разделить на 36 и округлить в большую сторону. Количество контейниров в нашей программе для каждого приёмного пункта — это переменная z.

Пусть лаборатория расположена в первом пункте. Тогда вычислим для неё стоимость доставки:

Здесь m — это последний индекс массива a (m = k-1). Пусть лаборатория будет во втором пункте, тогда:

sm2= a[3]*1 + a[4]*2 + . + a[n]*(m-2) + a[1] = sm1 — (a[2] + a[3] + a[4] + . + a[m]) + a[1]

Отсюда мы понимаем, что достаточно вычислить стоимость доставки sm1 по формуле, которую нам дали в задаче, только один раз для первого пункта. Для второго пункта вычисляем: sm2 = sm1 — (a[2] + a[3] + a[4] + . + a[m]) + a[1]. Для третьего sm3 = sm2 — (a[3] + a[4] + . + a[m]) + a[2] + a[1] и т.д.

Значит, для каждого приёмного пункта i мы должны иметь уже готовую вспомагательную сумму s1[i] = a[i] + a[i+1] + . + a[m], а так же сумму s2, т.е. сумма элементов, которые идут левее i (само a[i] уже не берётся): s2[i] = s[1] + s[2] + . + s[i-1].

Сумму s1[i] мы должны отнимать, а s2[i] прибавлять. По мерее продвижения по нашим приёмным пунктам, s1[i] будет уменьшаться, а s2[i] увеличиваться.

Но вспомогательные суммы s1[i] и s2[i] нужно тоже вычислисть, как можно эффективней. Достаточно вычислить для s1[1] и s2[1] (для первого приёмного пункта), а дальше можно воспользоваться закономерностью: s1[2] = s1[1]-a[1], s1[3] = s1[2]-a[2]. и т.д. Так же s2[2] = s[1]+a[1], s[3] = s[2]+a[2] и т.д.

s1[0] и s2[0] не нужны, они соответствуют a[0], а она не используется при решении задачи. Значение s1[1] вычисляем «честно» с помощью цикла. Значение s2[1] = 0 (левее нет ячеек).

В самом первом цикле вычисляется значение для переменной sm — это стоимость перевозки, если лаборатория стоит в первом пункте. В последнем цикле программы вычисляем стоимость для всех остальных приёмных пунктов, используя вышеописанные алгоритмы. И находим минимальное значение среди всех значений для переменной sm.

Ответ:

51063 5634689219329

22. Линейные программы и ветвление

Исполнитель МЕГАТРОН преобразует число, записанное на экране.
У исполнителя есть две команды, которым присвоены номера:
1. Прибавь 1,
2. Прибавь 2.
Первая из них увеличивает число на экране на 1, вторая — увеличивает его на 2.
Программа для МЕГАТРОНа — это последовательность команд.
Сколько есть программ, которые преобразует число 1 в число 9?

Количество программ, которые преобразуют число 1 в число \(n,\) обозначим \(R(n).\) Число 1 у нас уже есть, значит, его можно получить с помощью “пустой” программы. Любая непустая программа увеличит исходное число, т.е. даст число, больше 1. Значит, \(R(1) = 1.\) Для каждого следующего числа рассмотрим, из какого числа оно может быть получено за одну команду исполнителя. Число “2” может быть получено только из числа “1” командой под номером 1. Отсюда \(R(2) = 1.\) Число “3” можем получить из чисел 1 и 2 — \(R(3) = R(1) + R(2) = 2.\) Число “4” получаем из 2 и 3 — \(R(4) = R(2) + R(3) = 3.\) Можем заметить, что количество программ для получения числа n находится по формуле — \(R(n) = R(n-2) + R(n-1).\) Составим таблицу по данной формуле:
\[\begin <|c|c|c|c|c|c|c|c|c|>\hline \text& 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ \hline \text& 1 & 2 & 3 & 5 & 8 & 13 & 21 & 34 \\ \hline \end\] Отсюда видим, что имеем 34 возможных программ для получения числа 9.

Задание 2 #9792

Исполнитель Калькулятор преобразует число, записанное на экране.
У исполнителя есть три команды, которым присвоены номера:
1. Прибавь 2,
2. Умножь на 3.
Первая из них увеличивает число на экране на 2, вторая — увеличивает его в 3 раза.
Программа для Калькулятора — это последовательность команд.
Сколько есть программ, которые преобразуют число 2 в число 42?

Количество программ, которые преобразуют число 2 в число \(n,\) обозначим \(R(n).\) Число 2 у нас уже есть, значит, его можно получить с помощью “пустой” программы. Любая непустая программа увеличит исходное число, т.е. даст число, больше 2. Значит, \(R(2) = 1.\) Для каждого следующего числа рассмотрим, из какого числа оно может быть получено за одну команду исполнителя. Если число не делится на три, то оно может быть получено только из предыдущего с помощью команды прибавь 2. Значит, количество искомых программ для такого числа равно количеству программ для предыдущего возможного числа: \(R(n) = R(n-2).\)
Если число на три делится, то вариантов последней команды два: прибавь 2 и умножь на 3, тогда \(R(n) = R(n-2) + R(n:3).\) Заполним таблицу по данной формуле:
\[\begin <|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|>\hline \text& 4 & 6 & 8 & 10 & 12 & 14 & 16 & 18 & 20 & 22 & 24 & 26 & 28 & 30 & 32 & 34 & 36 & 38 & 40 & 42 \\ \hline \text& 1 & 2 & 2 & 2 & 3 & 3 & 3 & 5 & 5 & 5 & 7 & 7 & 7 & 9 & 9 & 9 & 12 & 12 & 12 & 15 \\ \hline \end\] Отсюда видим, что всего программ 15.

Задание 3 #9793

Исполнитель ХЛЕБУШЕК преобразует число, записанное на экране.
У исполнителя есть три команды, которым присвоены номера:
1. Прибавь 1,
2. Прибавь 2,
3. Прибавь 3.
Первая из них увеличивает число на экране на 1, вторая — увеличивает его на 2, третья — увеличивает его на 3.
Программа для ХЛЕБУШКа — это последовательность команд.
Сколько есть программ, которые преобразуют число 1 в число 14?

Количество программ, которые преобразуют число 1 в число n, обозначим \(R(n).\) Число 1 у нас уже есть, значит, его можно получить с помощью “пустой” программы. Любая непустая программа увеличит исходное число, т.е. даст число, больше 1. Значит, \(R(1) = 1.\) Для каждого следующего числа рассмотрим, из какого числа оно может быть получено за одну команду исполнителя. Число “2” может быть получено только из числа “1” командой под номером 1. Отсюда \(R(2) = 1.\) Число “3” можем получить из чисел 1 и 2 — \(R(3) = R(1) + R(2) = 2.\) Число “4” получаем из 1, 2 и 3 — \(R(4) = R(1) + R(2) + R(3) = 6.\) Заметим, что количество программ для получения числа n находится по формуле — \(R(n) = R(n-3) + R(n-2) + R(n-1).\) Составим таблицу по данной формуле:
\[\begin <|c|c|c|c|c|c|c|c|c|c|c|c|c|c|>\hline \text& 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 \\ \hline \text& 1 & 2 & 4 & 7 & 13 & 24 & 44 & 81 & 149 & 274 & 504 & 927 & 1705 \\ \hline \end\] Отсюда получаем искомое количество программ — 1705.

Задание 4 #9796

Исполнитель Прибавлялка имеет две команды, которым присвоены номера:
1. Прибавь 1,
2. Увеличь старшую цифру числа на 1.
Первая из них увеличивает число на экране на 1, вторая увеличивает на 1 старшую (левую) цифру числа, например число 63 с помощью такой команды превратится в число 73. Если старшая цифра числа равна 9, то вторая команда оставляет это число неизменным.
Программа для Прибавлялки — это последовательность команд.
Сколько есть программ, которые число 31 преобразуют в число 53?

Обе команды увеличивают исходное число. Старшая цифра — 3, следовательно, использовать команду 2 более двух раз бессмысленно.
Выпишем программы, в которых команда 2 используется два раза: 1122, 2211, 1212, 2121, 2112, 1221. Итого 6 программ.
Выпишем программы, в которых команда 2 используется один раз. Использовав эту команду в первой позиции, мы получим из числа 31 число 41, следовательно, после этого необходимо будет дописать ещё 12 команд 1 чтобы получить число 53. Таким образом, получаем программы: \(211\dots1,\) \(121\dots1,\) и. т. д. Итого имеем 13 программ (двойка побывала в каждой позиции).
Существует лишь одна программа, в которой команда 2 не используется: \(111\dots1.\)
Таким образом получаем \(6 + 13 + 1 = 20.\)

Задание 5 #9798

Исполнитель М.Е.М.249 преобразует целое число, записанное на экране.
У исполнителя две команды, которым присвоены номера:
преобразует целое число, записанное на экране.
1. Прибавить 1,
2. Прибавить 2,
3. Прибавить предыдущее.
Первая команда увеличивает число на экране на 1, вторая увеличивает это число на 2, третья прибавляет к числу на экране число, меньшее на 1 (к числу 3 прибавляется 2, к числу 11 прибавляется 10 и т. д.).
Программа для исполнителя М.Е.М.249 – это последовательность команд.
Сколько существует программ, которые число 1 преобразуют в число 10?

Обозначим число программ, преобразующих число 2 в число n как \(R(n).\) Тогда число \(n\) может быть получено либо прибавлением к \(n-1,\) либо к \(n-2,\) либо из некоторого числа \(х\) увеличением на \(x-1,\) так что \(n = x + x — 1,\) откуда \(x = \frac;\) так могут быть получены только нечетные числа.
Тогда для четных чисел \(R(n) = R(n-1) + R(n-2),\) а для нечетных — \(R(n) = R(n-1) + R(n-2) + R(\frac\) ). Заполним таблицу по данным формулам:
\[\begin <|c|c|c|c|c|c|c|c|c|c|>\hline \text& 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ \hline \text& 1 & 3 & 4 & 10 & 14 & 28 & 42 & 80 & 122 \\ \hline \end\] Отсюда получаем искомое количество программ — 122.

Задание 6 #13361

Исполнитель УВЕЛИЧИТЕЛЬ9000 преобразует целое число, записанное на экране.

У исполнителя три команды. Каждой команде присвоен номер:

1. Прибавить 1,

2. Прибавить 2,

3. Умножить на 4

Первая из них увеличивает число на экране на 1, второе — увеличивает его на 2, третья — увеличивает его в 4 раза.

Программа для УВЕЛИЧИТЕЛЯ9000 — это последовательность команд.

Сколько есть программ, которые преобразуют число 2 в число 17?

Количество программ, которые преобразуют число 2 в число n, обозначим R(n). Число 2 у нас уже есть, значит, его можно получить с помощью “пустой” программы. Любая непустая программа увеличит исходное число, т.е. даст число, больше 2. Значит, R(2) = 1. Для каждого следующего числа рассмотрим, из какого числа оно может быть получено за одну команду исполнителя. Если число не делится на 4, то оно может быть получено командами 1 и 2. Значит, количество искомых программ для такого числа равно количеству программ для предыдущего возможного числа: \(R(n) = R(n-1) + R(n-2)\) .

Если число делится на 4, то вариантов последней команды три: прибавить 1, прибавить 2 и умножить на 4, тогда \(R(n) = R(n-1) + R(n-2) + R(n:4)\) . Заполним таблицу по данной формуле:
\[\begin <|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|>\hline \text& 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 \\ \hline \text& 1 & 2 & 3 & 5 & 8 & 14 & 22 & 36 & 58 & 95 & 153 & 248 & 401 & 651 & 1052 \\ \hline \end\] Отсюда получаем искомое количество программ — 1052.

Задание 7 #16120

Исполнитель ЕЩЕНКО преобразует целое число, записанное на экране.
У исполнителя две команды, которым присвоены номера:
1. Прибавь 2,
2. Умножь на 10.
Первая из них увеличивает число на экране на 2, второе — увеличивает его в 10 раз.
Программа для Калькулятора — это последовательность команд.
Сколько есть программ, которые преобразуют число 2 в число 40?

Количество программ, которые преобразуют число 2 в число n, обозначим \(R(n)\) . Число 2 у нас уже есть, значит, его можно получить с помощью “пустой” программы. Любая непустая программа увеличит исходное число, т.е. даст число, больше 2. Значит, \(R(2) = 1\) . Для каждого следующего числа рассмотрим, из какого числа оно может быть получено за одну команду исполнителя. Если число не делится на десять, то оно может быть получено только из предыдущего с помощью команды прибавь 2. Значит, количество искомых программ для такого числа равно количеству программ для предыдущего возможного числа: \(R(n) = R(n-2)\) .
Если число делится на 10, то вариантов последней команды два: прибавь 2 и умножь на 10, тогда \(R(n) = R(n-2) + R(n:10)\) . Заполним таблицу по данной формуле:
\[\begin <|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|>\hline \text& 4 & 6 & 8 & 10 & 12 & 14 & 16 & 18 & 20 & 22 & 24 & 26 & 28 & 30 & 32 & 34 & 36 & 38 & 40 \\ \hline \text& 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 2 & 2 & 2 & 2 & 2 & 2 & 2 & 2 & 2 & 2 & 3 \\ \hline \end\]

Отсюда получаем искомое количество программ — 3.

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *