Решу егэ информатика 33763

Дан квадрат 15 × 15 клеток, в каждой клетке которого записано целое число. В левом верхнем углу квадрата стоит ладья. За один ход ладья может переместиться в пределах квадрата на любое количество клеток вправо или вниз (влево и вверх ладья ходить не может). Необходимо переместить ладью в правый нижний угол так, чтобы сумма чисел в клетках, в которых ладья останавливалась (включая начальную и конечную), была минимальной. В ответе запишите минимально возможную сумму.

Исходные данные записаны в электронной таблице.

Задание 18

Пример входных данных (для таблицы размером 4 × 4):

Для указанных входных данных ответом будет число −10 (ладья проходит через клетки с числами −6, 1, −3, −5, 3).

Задание 2. Информатика. Апробация 10.03.2023

from itertools import permutations, product

def F(x, y, z, w):
    return (x <= (not y <= z)) or w

for perm in permutations('xyzw'):
    for a,b,c,d,e,f,g in product([0,1], repeat=7):
        table = [[a,0,b,0,0],
                 [1,c,d,e,0],
                 [0,1,f,g,0]]
        if table[0] == table[1]:
            continue
        if all(F(**dict(zip(perm,row))) == row[-1] for row in table):
            print(*perm)

Тренировочный вариант и ответы с решением пробник ЕГЭ 2023 по информатике 11 класс ФИПИ состоит из 27 заданий с кратким ответом, выполняемых с помощью компьютера. На выполнение экзаменационной работы по информатике и ИКТ отводится 3 часа 55 минут (235 минут).

Скачать тренировочный вариант с ответами

Скачать файлы для варианта

Другие тренировочные варианты

ege_2023_informatika_23_02

Разбор варианта. ЕГЭ по Информатике 2023

1. На рисунке справа схема дорог Н-ского района изображена в виде графа, в таблице содержатся сведения о длинах этих дорог (в километрах). Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. В таблице в левом столбце указаны номера пунктов, откуда совершается движение, в первой строке – куда. Определите минимально возможную длину пути BDE. Передвигаться можно только по указанным дорогам.

2. Логическая функция F задаётся выражением w ∨ (y → z) ∧ x. На рисунке приведён частично заполненный фрагмент таблицы истинности функции F, содержащий неповторяющиеся строки. Определите, какой столбец в таблице каждой переменной в выражении. В ответе напишите буквы x, y, z, w в том порядке, в котором идут соответствующие им столбцы. Буквы в ответе пишите подряд, никаких разделителей между буквами ставить не нужно.

3. В файле приведён фрагмент базы данных «Продукты» о поставках товаров в магазины районов города. База данных состоит из трёх таблиц. Таблица «Движение товаров» содержит записи о поставках товаров в магазины в течение первой декады августа 2021 г., а также информацию о проданных товарах. Поле Тип операции содержит значение Поступление или Продажа, а в соответствующее поле Количество упаковок внесена информация о том, сколько упаковок товара поступило в магазин или было продано в течение дня. Заголовок таблицы имеет следующий вид.

4. Все заглавные буквы русского алфавита закодированы неравномерным двоичным кодом, в котором никакое кодовое слово не является началом другого кодового слова. Это условие обеспечивает возможность однозначной расшифровки закодированных сообщений. Известно, что слово СПОРТЛОТО кодируется как 10010100110011110000100. Какой код соответствует букве Л, если известно, что коды подбирались под минимальную длину заданного слова.

5. На вход алгоритма подаётся натуральное число N большее 4. Алгоритм строит по нему новое число R следующим образом. 1. Строится двоичная запись числа N. 2. Далее эта запись обрабатывается по следующему правилу: а) если количество цифр в двоичной записи числа нечётное, то центральный бит двоичного представления инвертируется; б) если количество цифр в двоичной записи числа чётное, то два центральных бита двоичного представления инвертируется; Например, для исходного числа 610 = 1102 результатом является число 1002 = 410, а для исходного числа 910 = 10012 результатом является число 11112 = 1510. Укажите минимальное число N, после обработки которого с помощью этого алгоритма получается число R, большее 100 и меньшее N. В ответе запишите это число в десятичной системе счисления.

6. Исполнитель Черепаха действует на плоскости с декартовой системой координат. В начальный момент Черепаха находится в начале координат, её голова направлена вдоль положительного направления оси ординат, хвост опущен. При опущенном хвосте Черепаха оставляет на поле след в виде линии. В каждый конкретный момент известно положение исполнителя и направление его движения. У исполнителя существует 5 команд: Поднять хвост, означающая переход к перемещению без рисования; Опустить хвост, означающая переход в режим рисования; Вперёд n (где n – целое число), вызывающая передвижение Черепахи на n единиц в том направлении, куда указывает её голова; Назад n (где n – целое число), вызывающая передвижение в противоположном голове направлении; Направо m (где m – целое число), вызывающая изменение направления движения на m градусов по часовой стрелке, Налево m (где m – целое число), вызывающая изменение направления движения на m градусов против часовой стрелки. Запись Повтори k [Команда1 Команда2 … КомандаS] означает, что последовательность из S команд повторится k раз.

7. Спутник каждую секунду делает снимок 20 на 7.6 километра. Размер пикселя на местности 0.65х0.65 метра. Цвет пикселя выбирается из палитры в 256 цветов. Оцените объем памяти (в МБ) для хранения одного изображения. Сжатие не производится. Ответ округлите до большего целого числа.

8. Определите количество десятизначных чисел, записанных в восьмеричной системе счисления, в записи которых ровно пять цифры 7 и при этом никакая нечетная цифра не стоит рядом с цифрой 7.

9. Откройте файл электронной таблицы, содержащей в каждой строке шесть натуральных чисел. Определите количество строк таблицы, содержащих числа, для которых выполнено строго одно из условий: – в строке есть повторяющиеся числа; – в строке есть ровно три нечетных числа. В ответе запишите только число.

10. Текст произведения Ника Горькавого «Теория Катастроф» представлен в виде текстового файла. Откройте файл и определите, сколько бифуркационных технологий содержал итоговый список. В ответе запишите только число.

11. Вася решил закодировать персональные данные всех 1347 учеников всей школы. Для каждого ученика был сформирован ID из нескольких полей: номер класса, буква (а,б,в,г,д), пол, день и месяц рождения, номер имени по таблице имен (всего 103), номер фамилии по таблице фамилий (всего 733). Сперва Вася для каждого поля выделил минимальное количество байт. Затем попробовал закодировать все поля непрерывной битовой строкой и для каждого ID выделил минимальное количество байт. Сколько байт сэкономил Вася во втором случае для кодирования всех учеников школы?

12. Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в обеих командах v и w обозначают цепочки цифр) А) заменить(v, w). Эта команда заменяет в строке первое слева вхождение цепочки v на цепочку w. Например, выполнение команды заменить(111, 27) преобразует строку 05111150 в строку 0512750. Если в строке нет вхождений цепочки v, то выполнение команды заменить(v, w) не меняет эту строку. Б) нашлось(v). Эта команда проверяет, встречается ли цепочка v в строке исполнителя Редактор. Если она встречается, то команда возвращает логическое значение «истина», в противном случае возвращает значение «ложь». Строка исполнителя при этом не изменяется. Цикл выполняется, пока условие истинно.

13. На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Определите количество различных путей ненулевой длины, которые начинаются и заканчиваются в городе Е, не содержат этот город в качестве промежуточного пункта и проходят через промежуточные города не более одного раза.

14. Дано выражение 12×4536 + 1×12345 В записи чисел переменной x обозначена неизвестная цифра из допустимого алфавита для указанных систем счисления. Определите наибольшее значение x, при котором значение данного арифметического выражения кратно 13. Для найденного значения x вычислите частное от деления значения арифметического выражения на 13 и укажите его в ответе в десятичной системе счисления.

15. На числовой прямой даны два отрезка: B = [23;37] и C = [41;73]. Укажите наименьшую длину такого отрезка А, для которого логическое выражение ¬((¬(x ∈ B) → (x ∈ C)) → (x ∈ A)) ложно (т.е. принимает значение 0) при любом значении переменной x.

16. Обозначим частное от деления натурального числа a на натуральное число b как a//b, а остаток как a%b. Например, 17//3 = 5, 17%3 = 2. Алгоритм вычисления значения функции F(n), где n – целое неотрицательное число, задан следующими соотношениями: F(n) = n при n < 10; F(n) = F(n//10) + F(n%10) , если 10 ⩽ n < 1000; F(n) = F(n//1000) — F(n%1000) , если n ⩾ 1000. Определите количество значений n, не превышающих 106 , для которых F(n) = 0?

17. В файле содержится последовательность целых чисел по модулю менее 10000. а) рассматриваются только пары в которых строго одно число оканчивается на 7. б) квадрат разности элементов пары меньше модуля разности квадратов хотя бы одной пары (отвечающей условию а). В ответе запишите два числа: сначала количество найденных пар, затем минимальный квадрат разности. В данной задаче под парой подразумевается два идущих подряд элемента последовательности.

18. Квадрат разлинован на N×N клеток (1 < N < 30). Роботу нужно перейти через поле с севера (верхняя строка) на юг (нижняя строка). Он может начать переход с любой клетки первой строки и закончить на любой клетке нижней строки. С каждым шагом Робот переходит в следующую строку и может за одно перемещение попасть в одну из трех клеток следующей строки (на клетку прямо вниз или на одну из клеток слева/справа от неё). Ходы только влево или вправо (без смены строки), назад (в предыдущую строку) и за границы поля запрещены. В каждой клетке поля лежит монета достоинством от 1 до 100. Робот собирает все монеты по пройденному маршруту. Определите максимальную возможную денежную сумму и количество монет с чётным значением, которую может собрать Робот, пройдя с северной границы поля (сверху) до южной границы поля (снизу). В ответе укажите два числа: сначала максимальную сумму, затем количество монет с четным значением по маршруту с максимальной суммой.

19. Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в меньшую кучу один или три камня. Изменять количество камней в большей куче не разрешается. Игра завершается, когда количество камней в кучах становится равным. Победителем считается игрок, сделавший последний ход, то есть первым сравнявшим количество камней в двух кучах. Игроки играют рационально, т.е. без ошибок. В начальный момент в первой куче было 13 камней, а во второй – S камней, 1 ≤ S ≤ 23? Укажите такое минимальное значение S, при котором Петя не может выиграть за один ход, но при любом ходе Пети Ваня может выиграть своим первым ходом.

20. Для игры, описанной в задании 19, найдите два наименьших значения S, при которых у Пети есть выигрышная стратегия, причём одновременно выполняются два условия: – Петя не может выиграть за один ход; – Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня. Найденные значения запишите в ответ в порядке возрастания

21. Для игры, описанной в задании 19, найдите два значения S, при котором одновременно выполняются три условия: – у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети; – у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом; – Петя может выбирать, каким ходом выиграет Ваня;

22. В файле содержится информация о совокупности N вычислительных процессов, которые могут выполняться параллельно или последовательно. Будем говорить, что процесс B зависит от процесса A, если для выполнения процесса B необходимы результаты выполнения процесса A. В этом случае процессы могут выполняться только последовательно. Информация о процессах представлена в файле в виде таблицы. В первом столбце таблицы указан идентификатор процесса (ID), во втором столбце таблицы – время его выполнения в миллисекундах, в третьем столбце перечислены с разделителем «;» ID процессов, от которых зависит данный процесс. Если процесс является независимым, то в таблице указано значение 0. Определите максимальное количество процессов, которые завершатся за 73 мс, при условии, что все независимые друг от друга процессы могут выполняться параллельно.

23. У исполнителя Кузнечик есть 4 команды: 1. Прибавить 1 2. Прибавить 3 3. Вычесть 1 4. Вычесть 3 Сколько существует программ, для которых при исходном числе 42 результатом будет являться число 42, при этом траектория вычисления содержит только числа от 40 до 49, притом не более 1 раза, т.е. без повторов.

24. Текстовый файл содержит строку из десятичных цифр и букв латинского алфавита. Найдите минимальную длину подстроки включающей все шестнадцатеричные цифры. Строка может включать повторяющиеся цифры и другие символы. В ответе укажите найденную длину..

25. Назовём маской числа последовательность цифр, в которой также могут встречаться следующие символы:  символ «?» означает ровно одну произвольную цифру;  символ «*» означает любую последовательность цифр произвольной длины; в том числе «*» может задавать и пустую последовательность. Например, маске 123*4?5 соответствуют числа 123405 и 12300405. Найдите все натуральные числа, не превышающие 1010, которые соответствуют маске 1?1?1?1*1 и при этом без остатка делятся на 2023, а сумма цифр числа равна 22. В ответе запишите все найденные числа в порядке возрастания. Количество строк в таблице для ответа избыточно.

26. В сетевом приложении реализован кэш размером V МБ для файлов размером от 1 до 999 МБ. Пользователи запрашивают файлы в порядке, заданном в исходном файле. Алгоритм кэширования сперва заполняет весь кэш. Для размещение следующего файла кэш нужно освободить. Для этого из кэша удаляется один подходящий файл, так чтобы свободное место было минимальным и достаточным для размещения нового файла. Если удаление даже самого большого файла не освобождает необходимого места, то удаляется самый большой файл и алгоритм рекурсивно повторяется, пока не будет достаточного места для нового файла.

27. Дана последовательность натуральных чисел. Расстояние между элементами последовательности – это разность их порядковых номеров. Например, если два элемента стоят в последовательности рядом, расстояние между ними равно 1, если два элемента стоят через один – расстояние равно 2 и т. д. Назовём тройкой любые три числа из последовательности, расстояние между которыми не меньше 17. Необходимо определить количество троек, в которых сумма чисел в тройке делится без остатка на 7717.

ПОДЕЛИТЬСЯ МАТЕРИАЛОМ

Привет! В этой статье посмотрим некоторые задачи из 26 задания ЕГЭ по информатике.

Стоит отменить, что задачи из 26 задания являются одними из самых сложных во всем экзамене, и найти какой-то конкретный шаблон для всех типов задач не получится.

Но обычно в 26 задании нужно использовать сортирку.

Решать задачи будем преимущественно на языке Python.

Задача (Классическая, Демо 2021)

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

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

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

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

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

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

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

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

Решение:

Первый способ (с помощью Excel).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Ответ получается 568 50.

Второй способ (с помощью Python).

f=open('26.txt')
st = f.readline().split()
s=int(st[0])
n=int(st[1])

a=[]

#Записываем данные в список a
for i in range(n):
    x=int(f.readline())
    a.append(x)
    
#Сортируем список
a.sort()

b=[]

for i in range(n):
    if sum(b) + a[i] <= s:
        b.append(a[i])
    else:
        break

b=b[:-1]

for i in range(len(a)-1, -1, -1):
    if sum(b) + a[i] <= s:
        b.append(a[i])
        break

print(len(b), b[-1])

В начале подвязываемся к файлу. С помощью команды readline() считываем первую строчку. С помощью команды split() разбиваем строчку по пробелу на два числа. Переменная st — это список. В st[0] — будет подстрока с первым числом, в st[1] со вторым.

Переменная s — это размер свободного пространства на диске, n — это количество пользователей. Мы должны использоваться функцию int(), чтобы перевести из текстового типа данных в целый числовой.

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

Команда .sort() сортирует (раскладывает по порядку) по возрастанию элементы списка.

Заводим список b. В него будем класть элементы, которые записываем на диск. Т.к. числа отсортированы, то, начиная с самого маленького файла, мы сможем заполнить диск максимальным количеством файлов.

С помощью цикла пробегаемся по всем элементам. В начале проверяем, есть ли место для очередного элемента, а потом записываем элемент в список b. Таким образом, сможем найти максимальное количество.

Чтобы найти максимальный элемент при максимальном количестве, удаляем из списка b последний самый большой элемент.

Пробегаемся по списку a, начиная с конца. Ищем кем можно заменить удалённый элемент. Мы идём с конца, поэтому в приоритете будут самый большие элементы.

После того, как найденный элемент будет умещаться в список b, можно печатать ответ.

Ответ:

Задача (Двумерные списки)

В лесничестве саженцы сосны высадили параллельными рядами, которые пронумерованы идущими подряд натуральными числами. Растения в каждом ряду пронумерованы натуральными числами начиная с единицы.

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

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

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

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

Два целых неотрицательных числа: наибольший номер ряда и наименьший номер места в выбранной последовательности из 13 мест, подходящих для посадки новых сосен.

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

7
40 3
40 7
60 33
50 125
50 129
50 68
50 72

Для приведённого примера, при условии, что необходимо 3 свободных места, ответом является пара чисел: 50; 69.

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

Решение:

f=open('26_dm.txt')

n=int(f.readline())

a=[0]*100001

for i in range(0, 100001):
    a[i]=[]


#Заполняем списки
for i in range(0, n):
    s=f.readline()
    b=s.split()
    a[int(b[0])].append(int(b[1]))


#Сортируем списки
for i in range(0, len(a)):
    a[i].sort()


flag_stop=0

for i in range(len(a)-1, -1, -1):
    for j in range(0, len(a[i])-1):
        if a[i][j+1]-a[i][j]==14:
            print(i, a[i][j]+1)
            flag_stop=1
            break

    if flag_stop==1:
        break 

Всего у нас может быть сто тысяч рядов. Поэтому мы заводим 100000 списков. Каждый список — это очередной ряд. Но в программе завели 1000001, т.к. нулевой список использоваться не будет.

В каждый ряд добавляются номера деревьев. Это и будут элементы для каждого списка. Если не будет деревьев в ряду, то список останется пустым.

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

Если в каком-нибудь списке числа имеют разницу в 14 единиц, то значит между ними ровно 13 свободных мест. Например, числа 10 и 24. Между ними 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23. Всего 13 чисел.

Чтобы проанализировать двумерный массив, используем вложенные циклы. Ряды перебираем сверху вниз. Как только найдём нужный ряд, выйдем из цикла, и в переменной i будет наибольший нужный ряд.

Сами же ряды перебираем в порядке возрастания. Как только между числами разница будет в 14 единиц, то значение j+1 наименьший свободный номер из промежутка в 13 деревьев.

Чтобы вовремя выйти из вложенных циклов, используем дополнительный флаг (переменную flag_stop).

Ответ:

Задача (Демо 2023)

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

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

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

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

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

5
43
40
32
40
30

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

Ответ:

Задача (Разные типы товаров)

На закупку товаров типов A, B, C, D и E выделена определённая сумма денег. Эти товары есть в продаже по различной цене. Необходимо на выделенную сумму закупить как можно больше товаров пяти типов (по общему количеству). Если можно разными способами купить максимальное количество пяти типов товаров, то нужно выбрать способ, при котором будет закуплено как можно больше товаров типа A. Если при этих условиях есть несколько способов закупки, нужно потратить как можно меньше денег.

Определите, сколько будет закуплено товаров типа A и сколько денег останется.

Входные данные представлены в файле следующим образом. Первая строка входного файла содержит два целых числа: N – общее количество товаров и M – сумма выделенных на закупку денег (в рублях). Каждая из следующих N строк содержит целое число (цена товара в рублях) и символ (латинская буква), определяющий тип товара. Все данные в строках входного файла отделены одним пробелом.

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

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

6 110
40 E
50 A
50 D
30 C
20 B
10 A

В данном случае можно купить не более четырёх товаров, из них не более двух товаров типа A. Минимальная цена такой покупки 110 рублей (покупаем товары 10 A, 20 B, 30 C, 50 A). Останется 0 рублей. Ответ: 2 0.

Решение:

f=open('26-rtt.txt')

s=f.readline().split()
n=int(s[0])
m=int(s[1])

X, Y, Z = [], [], []

for i in range(n):
    s=f.readline().split()
    X.append((int(s[0]), s[1]))

X.sort()

sm=0

for i in range(n):
    if sm+X[i][0]<= m:
        sm=sm+X[i][0]
        Y.append(X[i])
    else:
        if X[i][1]=='A':
            Z.append(X[i])


j=0
for i in range(len(Y)-1, -1, -1):

    if Y[i][1]=='A': continue
    
    if sm - Y[i][0] + Z[j][0] <= m:
        sm = sm - Y[i][0] + Z[j][0]
        Y[i] = Z[j]
    else:
        break

    j=j+1

count = 0
for i in range(len(Y)):
    if Y[i][1]=='A':
        count=count+1

print(count, m-sm)

В этом решении участвуют три списка. Список X — это все товары из нашего файла. Каждый товар — это отдельный список, состоящий из двух элементов: стоимости и типа товара.

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

Список Y — это те товары, которые мы взяли при вычислении предыдущего шага. Переменная sm — это та сумма, которую потратим при нахождении максимального количества товаров в независимости от типа товаров.

Список Z — это те товары, которые мы НЕ взяли в предыдущем шаге, но только с типами A.

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

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

При заменах меняем и значение суммы выбранных элементов (переменная sm).

Когда замены больше невозможны, то остаётся только посчитать количество элементов с типом A в списке Y.

Ответ:

Задача (Интересный шаблон)

Предприятие производит оптовую закупку изделий A и C, на которую выделена определённая сумма денег. У поставщика есть в наличии партии этих изделий различных модификаций по различной цене. На выделенные деньги необходимо приобрести как можно больше изделий C (независимо от модификации). Закупать можно любую часть каждой партии. Если у поставщика закончатся изделия C, то на оставшиеся деньги необходимо приобрести как можно больше изделий A. Известна выделенная для закупки сумма, а также количество и цена различных модификаций данных изделий у поставщика. Необходимо определить, сколько будет закуплено изделий A и какая сумма останется неиспользованной. Если возможно несколько вариантов решения (с одинаковым количеством закупленных изделий A), нужно выбрать вариант, при котором оставшаяся сумма максимальна.

Входные данные представлены в файле следующим образом. Первая строка входного файла содержит два целых числа: N – общее количество партий изделий у поставщика и S – сумма выделенных на закупку денег (в рублях). Каждая из следующих N строк описывает одну партию изделия: сначала записана буква A или C (тип изделия), а затем – два целых числа: цена одного изделия в рублях и количество изделий в партии. Все данные в строках входного файла разделены одним пробелом.

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

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

4 1000
A 14 12
C 30 7
A 40 24
C 50 15

В данном случае сначала нужно купить изделия C: 7 изделий по 30 рублей и 15 изделий по 50 рублей. На это будет потрачено 960 рублей. На оставшиеся 40 рублей можно купить 2 изделия A по 14 рублей. Таким образом, всего будет куплено 2 изделия A и останется 12 рублей. В ответе надо записать числа 2 и 12.

Решение:

Создадим список. Каждый элемент списка будет является тоже списком из трёх элементов: тип изделия, цена изделия и количество изделий данной модификации.

Нам потребуется отсортировать строчки файла сначала по типу изделия, т.к. нужно приобрести как можно больше изделий типа C. После этого нужно сделать сортировку второго уровня, отсортировать строчки по цене. Ведь так мы сможем взять максимальное количество изделий на выделенную сумму.

Рассмотрим интересный шаблон для подобного рода задач.

a=[]
a.append((5, 1, 6))
a.append((7, 7, 3))
a.append((3, 4, 5))
a.append((3, 1, 2))
a.append((3, 3, 2))

a.sort(key=lambda d: (d[0], d[1]))
print(a)

Получается результат:

Видим, что сначала элементы расположились по первому числу, затем уже по второму.

Напишем решение для нашей задачи.

f=open('26_4.txt')
st=f.readline().split()

n=int(st[0])
s=int(st[1])

k=0

a=[]

for i in range(n):
    st=f.readline().split()
    if st[0]=='A': st[0]='D'
    if st[0]=='C': st[0]='B'
    a.append((st[0], int(st[1]), int(st[2])))


a.sort(key=lambda d:(d[0], d[1]))

for i in range(len(a)):
    for j in range(a[i][2]):
        if s-a[i][1]>=0:
            s=s-a[i][1]
            if a[i][0] == 'D':
                k=k+1

print(k, s)

Т.к. нужно в начале набрать изделий типа С как можно больше, то хотелось бы видеть именно в начале этот тип после сортировки. Чтобы добиться желаемого, обозначим букву С за букву B, а букву A за D. Сортировку по цене делаем в возрастающем порядке.

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

Ответ:

Задача (Бинарный поиск)

В текстовом файле записан набор натуральных чисел, не превышающих 10⁹. Гарантируется, что все числа различны. Необходимо определить, сколько в наборе таких пар чётных чисел, что их среднее арифметическое тоже присутствует в файле, и чему равно наибольшее из средних арифметических таких пар.

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

Первая строка входного файла содержит целое число N  — общее количество чисел в наборе. Каждая из следующих N строк содержит одно число.

В ответе запишите два целых числа: сначала количество пар, затем наибольшее среднее арифметическое.

Пример входного файла:
6
3
8
14
11
2
17

В данном случае есть две подходящие пары: 8 и 14 (среднее арифметическое 11), 14 и 2 (среднее арифметическое 8). В ответе надо записать числа 2 и 11.

Решение:

f=open('26_6.txt')
n=int(f.readline())

k=0
mx=0
a=[]

for i in range(n):
    x=int(f.readline())
    a.append(x)

a.sort()

for i in range(0, len(a)-1):
    if a[i]%2==0:
        for j in range(i+1, len(a)):
            if a[j]%2==0:

                sr = (a[i] + a[j]) // 2

                # Бинарный поиск
                l=0
                r=len(a)-1
                index=0

                while(l <= r):
                    
                    index = (r + l) // 2

                    if a[index] == sr:
                        k=k+1
                        mx=max(mx, a[index])
                        break
                    if a[index] < sr:
                        l=index+1
                    else:
                        r=index-1

print(k, mx)

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

После идут два вложенных цикла — мы перебираем все пары в массиве a. Берём только чётные числа.

Чтобы найти число в отсортированном массиве воспользуемся «бинарным поиском». Об этом приёме подробно рассказано в этой статье.

Ответ:

Надеюсь, Вам повезёт при решении 26 задания на ЕГЭ по информатике.