На уроке рассмотрен материал для подготовки к ЕГЭ по информатике, разбор 26 задания. Объясняется тема о программной обработке целочисленной информации с использованием алгоритмов сортировки.
26-е задание: «Обработка целочисленной информации с использованием сортировки»
Уровень сложности
— высокий,
Требуется использование специализированного программного обеспечения
— да,
Максимальный балл
— 2,
Примерное время выполнения
— 35 минут.
Проверяемые элементы содержания: Умение обрабатывать целочисленную информацию с использованием сортировки
Выполнение 26 задания ЕГЭ
Плейлист видеоразборов задания на YouTube:
Задание демонстрационного варианта 2022 года ФИПИ
26_1.
26_1. Демоверсия варианта ЕГЭ по информатике 2021, ФИПИ:
Задание выполняется с использованием прилагаемых файлов
Системный администратор раз в неделю создаёт архив пользовательских файлов. Однако объём диска, куда он помещает архив, может быть меньше, чем суммарный объём архивируемых файлов.
Известно, какой объём занимает файл каждого пользователя.
По заданной информации об объёме файлов пользователей и свободном объёме на архивном диске определите максимальное число пользователей, чьи файлы можно сохранить в архиве, а также максимальный размер имеющегося файла, который может быть сохранён в архиве, при условии, что сохранены файлы максимально возможного числа пользователей.
Входные данные.
В первой строке входного файла находятся два числа: S – размер свободного места на диске (натуральное число, не превышающее 10 000) и N – количество пользователей (натуральное число, не превышающее 1000). В следующих N строках находятся значения объёмов файлов каждого пользователя (все числа натуральные, не превышающие 100), каждое в отдельной строке.
Запишите в ответе два числа: сначала наибольшее число пользователей, чьи файлы могут быть помещены в архив, затем максимальный размер имеющегося файла, который может быть сохранён в архиве, при условии, что сохранены файлы максимально возможного числа пользователей.
Пример входного файла:
100 4 80 30 50 40
При таких исходных данных можно сохранить файлы максимум двух пользователей. Возможные объёмы этих двух файлов 30 и 40, 30 и 50 или 40 и 50. Наибольший объём файла из перечисленных пар – 50, поэтому ответ для приведённого примера:
2 | 50
Ответ: 568 | 50
✍ Решение:
-
Проанализируем возможное решение:
- Чтобы вычислить максимальное число пользователей, чьи файлы можно сохранить в архиве, необходимо брать файлы с наименьшим объемом , пока суммарный объем этих файлов меньше свободного объема диска. Т.е. для нижеуказанного примера, будем брать
30 + 40
. Файл объемом 50 мы взять уже не сможем, так как70 + 50 = 120
, а это уже больше указанного объема диска (100):
100 4 80 30 50 40
100 - 70 = 30
30 - 40 <= запаса (30) 40 - 40 <= запаса (30) 50 - 40 <= запаса (30) 80 - 40 > запаса (30), не подходит
Теперь построим алгоритм на языках программирования:
PascalABC.net:
|
||
Python:
|
||
С++: |
Ответ: 568 | 50
📹 YouTube здесь
📹 Видеорешение на RuTube здесь
26_2.
26_2:
Задание выполняется с использованием прилагаемых файлов
В магазине электроники раз в месяц проводится распродажа. Из всех товаров выбирают K
товаров с самой большой ценой и делают на них скидку в 20%. По заданной информации о цене каждого из товаров и количестве товаров, на которые будет скидка, определите цену самого дорогого товара, не участвующего в распродаже, а также целую часть от суммы всех скидок.
Входные и выходные данные.
В первой строке входного файла 26-k1.txt
находятся два числа, записанные через пробел: N
– общее количество цен (натуральное число, не превышающее 10 000) и K
– количество товаров со скидкой. В следующих N
строках находятся значения цены каждого из товаров (все числа натуральные, не превышающие 10 000), каждое в отдельной строке.
Запишите в ответе два числа: сначала цену самого дорогого товара, не участвующего в распродаже, а затем целую часть от суммы всех скидок.
Пример входного файла:
10 3 1800 3600 3700 800 2600 2500 1800 1500 1900 1200
При таких исходных данных ответ должен содержать два числа – 2500 и 1980.
Пояснение: скидка будет на товары стоимостью 3700, 3600, 2600. Тогда самый дорогой товар без скидки стоит 2500, а сумма скидок 740+720+520 = 1980.
Ответ: 9000 | 190680
✍ Решение:
-
Теперь построим алгоритм на языках программирования:
PascalABC.net:
|
||
Python:
|
||
С++: |
📹 YouTube здесь
📹 Видеорешение на RuTube здесь
ЕГЭ информатика 26 задание разбор, теория, как решать.
Обработка целочисленной информации с использованием сортировки, (В) — 2 балла
Е26.17 В магазине для упаковки подарков есть N кубических коробок.
В магазине для упаковки подарков есть N кубических коробок. Самой интересной считается упаковка подарка по принципу матрёшки – подарок упаковывается в одну из коробок, та в свою очередь в другую коробку и т.д. Одну коробку можно поместить в другую, если длина её стороны хотя бы на 3 единицы меньше длины стороны другой коробки. Определите наибольшее …
Читать далее
Е26.16 В лесополосе осуществляется посадка деревьев.
В лесополосе осуществляется посадка деревьев. Причем саженцы высаживают рядами на одинаковом расстоянии. Через какое-то время осуществляется аэросъемка, в результате которой определяется, какие саженцы прижились. Необходимо определить ряд с максимальным номером, в котором есть подряд ровно 11 неприжившихся саженцев, при условии, что справа и слева от них саженц прижились. В ответе запишите сначала наибольший номер ряда, затем …
Читать далее
Е26.15 определить номер ряда с наибольшим количеством светлых точек в нечётных позициях
При проведении эксперимента заряженные частицы попадают на чувствительный экран, представляющий из себя матрицу размером 10 000 на 10 000 точек. При попадании каждой частицы на экран в протоколе фиксируются координаты попадания: номер ряда (целое число от 1 до 10 000) и номер позиции в ряду (целое число от 1 до 10 000). Точка экрана, в …
Читать далее
Е26.14 сначала наибольшее число пользователей, чьи файлы могут быть помещены в архив
Системный администратор раз в неделю создаёт архив пользовательских файлов. Однако объём диска, куда он помещает архив, может быть меньше, чем суммарный объём архивируемых файлов. Известно, какой объём занимает файл каждого пользователя. По заданной информации об объёме файлов пользователей и свободном объёме на архивном диске определите максимальное число пользователей, чьи файлы можно сохранить в архиве, а …
Читать далее
Е26.13 определить максимальную длину такой группы и номер ряда
При проведении эксперимента заряженные частицы попадают на чувствительный экран, представляющий из себя матрицу размером 10 000 на 10 000 точек. При попадании каждой частицы на экран в протоколе фиксируются координаты попадания: номер ряда (целое число от 1 до 10 000) и номер позиции в ряду (целое число от 1 до 10 000). Точка экрана, в …
Читать далее
Е26.12 определите цену самого дорогого товара, не участвующего в распродаже
В магазине электроники раз в месяц проводится распродажа. Из всех товаров выбирают К товаров с самой большой ценой и делают на них скидку в 20%, затем ещё М товаров с самой большой ценой и делают на них скидку 10%. По заданной информации о цене каждого из товаров и количестве товаров, на которые будет скидка, определите …
Читать далее
Е26.11 числа в паре имеют разную чётность, а их сумма тоже присутствует в файле
В текстовом файле записан набор натуральных чисел, не превышающих 109. Гарантируется, что все числа различны. Необходимо определить, сколько в наборе таких пар чисел, что числа в паре имеют разную чётность, а их сумма тоже присутствует в файле, и чему равна наибольшая из сумм таких пар. Входные данные Первая строка входного файла содержит целое число N …
Читать далее
Е26.10 Причем файлы размером больше 400 МБ записывает на диск A
Системный администратор раз в неделю создаёт архив пользовательских файлов. Причем файлы размером больше 400 МБ записывает на диск A, а меньшего размера на диск F. Известно, какой объём занимает файл каждого пользователя. Системный администратор старается сохранить как можно больше файлов. Необходимо найти, сколько файлов на каждом диске может сохранить системный администратор и максимальный размер сохраненного …
Читать далее
Е26.9 Спутник «М305» проводит измерения солнечной активности
Спутник «М305» проводит измерения солнечной активности, результат каждого измерения представляет собой натуральное число. Перед обработкой серии измерений из неё исключают K наибольших и K наименьших значений (как недостоверные). По заданной информации о значении каждого из измерений, а также количестве исключаемых значений, определите наибольшее достоверное измерение, а также целую часть среднего значения всех достоверных измерений. Входные …
Читать далее
Е26.8 чему равно наибольшее из средних арифметических таких пар
В текстовом файле записан набор натуральных чисел, не превышающих 109. Гарантируется, что все числа различны. Необходимо определить, сколько в наборе таких пар чётных чисел, что их среднее арифметическое тоже присутствует в файле, и чему равно наибольшее из средних арифметических таких пар. Входные данные Первая строка входного файла содержит целое число N – общее количество чисел …
Читать далее
Привет! В этой статье посмотрим некоторые задачи из 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.
Ответ:
Задача (Бинарный поиск)
В текстовом файле записан набор натуральных чисел, не превышающих 109. Гарантируется, что все числа различны. Необходимо определить, сколько в наборе таких пар чётных чисел, что их среднее арифметическое тоже присутствует в файле, и чему равно наибольшее из средних арифметических таких пар.
Входные данные.
Первая строка входного файла содержит целое число 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 задания на ЕГЭ по информатике.
Александр, будут ли разборы задач с чередующимися красными и синими коробками(как в 4 варианте сборника Крылова и Чуркиной)? Писал в школе пробник по этому варианту, и набрал 95 баллов, спасибо вам за отличные уроки, это очень эффективная подготовка
Спасибо за отзыв!) Посмотрю эту задачку, если что, разберу.
Александр, полагаю, у вас опечатка в задаче с «Интересным шаблоном».
Последняя строчка решения: «Посчитываем количество товаров типа С.» — В задаче говориться о типах А.
Автор материалов — Лада Борисовна Есакова.
В простых играх можно найти выигрышную стратегию, расписав все возможные ходы игроков. Такая схема ходов называется деревом игры.
Все позиции в простых играх делятся на выигрышные и проигрышные.
Выигрышная позиция – это такая позиция, в которой игрок, делающий первый ход, может гарантированно выиграть при любой игре соперника. При этом алгоритм выбора очередного хода, приводящего к выигрышу, называется выигрышной стратегией. Считается, что игрок, обладающий выигрышной стратегией, не ошибается.
Проигрышная позиция – это такая позиция, при которой игрок, делающий первый ход, проигрывает независимо от выбора очередного хода.
Определение выигравшего игрока при заданной начальной позиции
Пример 1.
Два игрока играют в следующую игру. Перед ними лежат две кучи камней, в первой из которых 3, а во второй – 6 камней. У каждого игрока неограниченно много камней. Игроки ходят по очереди. Ход состоит в том, что игрок или удваивает число камней в какой-то куче, или добавляет 2 камня в какую-то кучу. Выигрывает игрок, после хода которого общее число камней в двух кучах становится не менее 24 камней. Кто выигрывает при безошибочной игре обоих игроков – игрок, делающий первый ход, или игрок, делающий второй ход? Каким должен быть первый ход выигравшего игрока? Ответ обоснуйте.
Решение:
Для доказательства выигрыша нам достаточно привести неполное дерево игры, в котором рассмотрены все возможные ходы проигравшего игрока и одна любая, приводящая к выигрышу, последовательность ходов выигравшего игрока.
В приведенной таблице числа, разделенные запятой, соответствуют количеству камней в первой и второй кучах соответственно.
Выигрывает первый игрок. Своим первым ходом он должен добавить 2 камня в первую кучу.
Таблица содержит все возможные варианты ходов второго игрока и ходы, приводящие к победе первого.
Ответ: Выигрывает первый игрок. Своим первым ходом он должен добавить 2 камня в первую кучу.
Определение выигравшего игрока для различных начальных позиций
Пример 2.
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч (по своему выбору) один камень или увеличить количество камней в куче в два раза. Например, пусть в одной куче 10 камней, а в другой 7 камней; такую позицию в игре будем обозначать (10, 7). Тогда за один ход можно получить любую из четырёх позиций: (11, 7), (20, 7), (10, 8), (10, 14). Для того чтобы делать ходы, у каждого игрока есть неограниченное количество камней.
Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее 73. Победителем считается игрок, сделавший последний ход, т.е. первым получивший такую позицию, что в кучах всего будет 73 камня или больше.
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока – значит описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника. Например, при начальных позициях (6, 34), (7, 33), (9, 32) выигрышная стратегия есть у Пети. Чтобы выиграть, ему достаточно удвоить количество камней во второй куче.
Задание 1. Для каждой из начальных позиций (6, 33), (8, 32) укажите, кто из игроков имеет выигрышную стратегию. В каждом случае опишите выигрышную стратегию; объясните, почему эта стратегия ведёт к выигрышу, и укажите, какое наибольшее количество ходов может потребоваться победителю для выигрыша при этой стратегии.
Задание 2. Для каждой из начальных позиций (6, 32), (7, 32), (8, 31) укажите, кто из игроков имеет выигрышную стратегию. В каждом случае опишите выигрышную стратегию; объясните, почему эта стратегия ведёт к выигрышу, и укажите, какое наибольшее количество ходов может потребоваться победителю для выигрыша при этой стратегии.
Задание 3. Для начальной позиции (7, 31) укажите, кто из игроков имеет выигрышную стратегию. Опишите выигрышную стратегию; объясните, почему эта стратегия ведёт к выигрышу, и укажите, какое наибольшее количество ходов может потребоваться победителю для выигрыша при этой стратегии. Постройте дерево всех партий, возможных при указанной Вами выигрышной стратегии. Представьте дерево в виде рисунка или таблицы.
Решение:
Задание 1. В начальных позициях (6, 33), (8, 32) выигрышная стратегия есть у Вани. При начальной позиции (6, 33) после первого хода Пети может получиться одна из следующих четырёх позиций: (7, 33), (12, 33), (6, 34), (6, 66). Каждая из этих позиций содержит менее 73 камней. При этом из любой из этих позиций Ваня может получить позицию, содержащую не менее 73 камней, удвоив количество камней во второй куче. Для позиции (8, 32) после первого хода Пети может получиться одна из следующих четырёх позиций: (9, 32), (16, 32), (8, 33), (8, 64). Каждая из этих позиций содержит менее 73 камней. При этом из любой из этих позиций Ваня может получить позицию, содержащую не менее 73 камней, удвоив количество камней во второй куче. Таким образом, Ваня при любом ходе Пети выигрывает своим первым ходом.
Задание 2. В начальных позициях (6, 32), (7, 32) и (8, 31) выигрышная стратегия есть у Пети. При начальной позиции (6, 32) он должен первым ходом получить позицию (6, 33), из начальных позиций (7, 32) и (8, 31) Петя после первого хода должен получить позицию (8, 32). Позиции (6, 33) и (8, 32) рассмотрены при разборе задания 1. В этих позициях выигрышная стратегия есть у игрока, который будет ходить вторым (теперь это Петя). Эта стратегия описана при разборе задания 1. Таким образом, Петя при любой игре Вани выигрывает своим вторым ходом.
Задание 3. В начальной позиции (7, 31) выигрышная стратегия есть у Вани. После первого хода Пети может возникнуть одна из четырёх позиций: (8, 31), (7, 32), (14, 31) и (7, 62). В позициях (14, 31) и (7, 62) Ваня может выиграть одним ходом, удвоив количество камней во второй куче. Позиции (8, 31) и (7, 32) были рассмотрены при разборе задания 2. В этих позициях у игрока, который должен сделать ход (теперь это Ваня), есть выигрышная стратегия. Эта стратегия описана при разборе задания 2. Таким образом, в зависимости от игры Пети Ваня выигрывает на первом или втором ходу.
Ответ:
Задание 1. Ваня выигрывает своим первым ходом.
Задание 2. Петя выигрывает своим вторым ходом.
Задание 3. Ваня выигрывает первым или вторым ходом.
Определение начальной позиции, обеспечивающей выигрыш того или иного игрока
Пример 3.
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один камень или увеличить количество камней в куче в три раза. Например, имея кучу из 15 камней, за один ход можно получить кучу из 16 или 45 камней. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней.
Игра завершается в тот момент, когда количество камней в куче становится не менее 48. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 48 или больше камней. В начальный момент в куче было S камней, 1 ≤ S ≤ 47.
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока — значит описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника.
Выполните следующие задания. Во всех случаях обосновывайте свой ответ.
1. а) Укажите все такие значения числа S, при которых Петя может выиграть в один ход. Обоснуйте, что найдены все нужные значения S, и укажите выигрывающий ход для каждого указанного значения S.
б) Укажите такое значение S, при котором Петя не может выиграть за один ход, но при любом ходе Пети Ваня может выиграть своим первым ходом. Опишите выигрышную стратегию Вани.
2. Укажите два таких значения S, при которых у Пети есть выигрышная стратегия, причём (а) Петя не может выиграть за один ход и (б) Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня. Для каждого указанного значения S опишите выигрышную стратегию Пети.
3. Укажите значение S, при котором:
— у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети, и
— у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.
Для указанного значения S опишите выигрышную стратегию Вани. Постройте дерево всех партий, возможных при этой выигрышной стратегии Вани (в виде рисунка или таблицы). На рёбрах дерева указывайте, кто делает ход, в узлах — количество камней в куче.
Решение:
1. а) Петя может выиграть, если 16, …, 47. Во всех этих случаях достаточно утроить количество камней. При меньших значениях S за один ход нельзя получить кучу, в которой больше 47 камней.
б) Ваня может выиграть первым ходом (как бы ни играл Петя), если исходно в куче будет S = 15 камней. Тогда после первого хода Петя в куче будет 16 или 45 камней. В обоих случаях Ваня утраивает количество камней и выигрывает в один ход.
2. Возможные значения S: 5 и 14. В этих случаях Петя, очевидно, не может выиграть первым ходом. Однако он может получить кучу из 15 камней: в первом случае утроением, во втором добавлением одного камня. Эта позиция разобрана в п. 16. В ней игрок, который будет ходить (теперь это Ваня), выиграть не может, а его противник (то есть Петя) следующим ходом выиграет.
3. Возможное значение S: 13. После первого хода Пети в куче будет 14 или 39 камней. Если в куче станет 39 камней. Ваня утроит количество камней н выиграет первым ходом. Ситуация, когда в куче 14 камней, уже разобрана в п. 2. В этой ситуации игрок, который будет ходить (теперь это Ваня), выигрывает своим вторым ходом.
На рисунке изображено дерево игры. Выигрышные позиции подчеркнуты.
Ответ:
1. а) S от16 до 47
б) S = 15
2. S = 5 и S = 14
3. S = 13
Благодарим за то, что пользуйтесь нашими материалами.
Информация на странице «Задача №26. Построение дерева игры. Поиск выигрышной стратегии» подготовлена нашими авторами специально, чтобы помочь вам в освоении предмета и подготовке к экзаменам.
Чтобы успешно сдать нужные и поступить в высшее учебное заведение или колледж нужно использовать все инструменты: учеба, контрольные, олимпиады, онлайн-лекции, видеоуроки, сборники заданий.
Также вы можете воспользоваться другими статьями из разделов нашего сайта.
Публикация обновлена:
09.03.2023
В задание №26
Тема: Обработка массива целых чисел из файла. Сортировка.
Проверяется yмение обрабатывать целочисленную информацию с использованием сортировки
Примеры заданий:
Задание 26 Простое задание (Решу ЕГЭ)
Системный администратор раз в неделю создаёт архив пользовательских файлов. Однако объём диска, куда он помещает архив, может быть меньше, чем суммарный объём архивируемых файлов. Известно, какой объём занимает файл каждого пользователя.
По заданной информации об объёме файлов пользователей и свободном объёме на архивном диске определите максимальное число пользователей, чьи файлы можно сохранить в архиве, а также максимальный размер имеющегося файла, который может быть сохранён в архиве, при условии, что сохранены файлы максимально возможного числа пользователей.
Входные данные:
В первой строке входного файла находятся два числа: S — размер свободного места на диске (натуральное число, не превышающее 10 000) и N — количество пользователей (натуральное число, не превышающее 1000). В следующих N строках находятся значения объёмов файлов каждого пользователя (все числа натуральные, не превышающие 100), каждое в отдельной строке.
Запишите в ответе два числа: сначала наибольшее число пользователей, чьи файлы могут быть помещены в архив, затем максимальный размер имеющегося файла, который может быть сохранён в архиве, при условии, что сохранены файлы максимально возможного числа пользователей.
Пример входного файла:
100 4
80
30
50
40
При таких исходных данных можно сохранить файлы максимум двух пользователей. Возможные объёмы этих двух файлов 30 и 40, 30 и 50 или 40 и 50. Наибольший объём файла из перечисленных пар — 50, поэтому ответ для приведённого примера:
2 50
Проще всего 26-е задание решать в Excel. Можно решить задание и
с помощью программы, но это будет посложнее. На ЕГЭ решение через программы не рекомендуется.
Здесь и далее во всех задачах этого класса предполагается, что не все файлы могут быть сохранены на диске, то есть хотя бы для одного файла места не хватит.
Решаем с помощью Excel
- Сначала загружаем данные в электронную таблицу, отрываем файл, копируем (Ctrl+A) и вставляем в Excel (Ctrl+V), для удобства переносим первую строку, которая содержит не такие данные, как все остальные и сортируем по возрастанию столбец А
- Далее начинаем выделять ячейки первого столбца, отслеживая значение суммы в строке состояния, нужно выделить наибольшее количество данных, сумма которых не больше, чем 8200
- Получили:
— Количество строк 568 (это первый ответ)
— Сумма 8176
— Последний наибольший файл 29 - Попробуем заменить наибольший файл ещё большим, так как наш архив (8200) это позволяет сделать:
— убираем наш наибольший 29 из общей суммы 8176-29=8147
— из исходного объема архива отнимаем полученное 8200-8147=53, получается что нам надо поискать файл такого или немного поменьше размера. - Спускаемся по списку и находим, что нам подходит первый файл размером 50
Мы нашли максимальное количество файлов 568 и максимальный файл 50
Ответ: 56850
Задание 26 демо (ФИПИ-2022)
Организация засаживает ряды саженцев, которые идут параллельно друг другу.
Известно,какие места в рядах уже заняты саженцами. Найдите ряд с наибольшим номером(нумерация рядом идет по возрастанию), в котором есть 13 подряд
свободных мест, таких что слева и справа от них в том же ряду места уже засажены (заняты). Гарантируется, что есть хотя бы один ряд, удовлетворяющий этому
условию. В ответе запишите два целых числа: максимальный номер ряда и наименьший номер
места из найденных в этом ряду подходящих пар свободных мест.
Входные данные:
В первой строке входного файла 26 (3).txt находится число N – количество занятых
мест (натуральное число, не превышающее 10 000). Каждая из следующих N строк
содержит два натуральных числа, не превышающих 100 000: номер ряда и номер
занятого места.
Выходные данные:
Два целых неотрицательных числа: Максимальный номер ряда, где нашлись обозначенные в задаче места и минимальный номер подходящего свободного места.
Типовой пример организации входных данных:
7
40 3
40 7
60 33
50 125
50 129
50 68
50 72
Для приведённого примера, при условии, что необходимо
3 свободных места, ответом является пара чисел: 50; 69.
Типовой пример имеет иллюстративный характер. Для
выполнения задания используйте данные из прилагаемых
файлов.
Решаем с помощью Excel
Задание 26 Товар/Скидки (Решу ЕГЭ)
Как нас обманывают в магазинах 🙂
Продавец предоставляет покупателю, делающему большую закупку, скидку по следующим правилам:
- — на каждый второй товар стоимостью больше 50 рублей предоставляется скидка 25%;
- — общая стоимость покупки со скидкой округляется вверх до целого числа рублей;
- — порядок товаров в списке определяет продавец и делает это так, чтобы общая сумма скидки была наименьшей.
По известной стоимости каждого товара в покупке необходимо определить общую стоимость покупки с учётом скидки и стоимость самого дорогого товара, на который будет предоставлена скидка.
Входные данные:
Первая строка входного файла содержит число N — общее количество купленных товаров. Каждая из следующих N строк содержит одно целое число — стоимость товара в рублях.
Выходные данные:
В ответе запишите два целых числа: сначала общую стоимость покупки с учётом скидки, затем стоимость самого дорогого товара, на который будет предоставлена скидка.
Типовой пример организации входных данных:
6
125
50
490
215
144
320
В данном случае товар стоимостью 50 не участвует в определении скидки, остальные товары продавцу выгодно расположить в таком порядке цен: 490, 125, 215, 144, 320. Тогда скидка предоставляется на товары стоимостью 125 и 144. Стоимость этих двух товаров со скидкой составит 201,75 руб., после округления — 202 руб. Общая стоимость покупки составит:
50 + 490 + 215 + 320 + 202 = 1277 руб.
Самый дорогой товар, на который будет получена скидка, стоит 144 руб. В ответе нужно записать числа 1277 и 144.
Решаем с помощью Excel
- Отрываем файл, копируем (Ctrl+A) и вставляем в Excel (Ctrl+V), убираем первое число(N — общее количество купленных товаров) и сортируем по возрастанию
- Копируем диапазон товаров меньше 50, на который скидка не действует, переносим в отдельный столбец (С)
- Копируем диапазон от 50 и более, переносим в отдельные столбцы (Е и G)
- Столбец Е сортируем по убыванию, это будет более дорогой ПЕРВЫЙ товар, столбец G оставляем по возрастанию, это будет ВТОРОЙ по списку товар, на который действует скидка 25%
- Выделив столбец Е, мы видим, что ли количество товаров 965, делим его пополам и находим середину, между двумя столбцами, нижнюю половину удаляем
Мы нашли Самый дорогой товар, на который будет получена скидка, стоит 511 руб. - В ячейку Н2 вставляем формулу для переоценки каждого второго товара, т.е. цену умножаем на 0,75 (скидка 25%)
- Суммируем наш товар:
— сумма товара без скидки до 50 рублей 1042
— сумма КАЖДОГО ПЕРВОГО 366132
— сумму товара со скидкой округляем ВВЕРХ 102610
Сумма всего товара 469784
Ответ: 469784 511
Задание 26 Груз(Решу ЕГЭ)
Для перевозки партии грузов различной массы выделен грузовик, но его грузоподъёмность ограничена, поэтому перевезти сразу все грузы не удастся. Грузы массой от 200 до 210 кг грузят в первую очередь, гарантируется, что все такие грузы поместятся. На оставшееся после этого место стараются взять как можно больше грузов. Если это можно сделать несколькими способами, выбирают тот способ, при котором самый большой из выбранных грузов имеет наибольшую массу. Если и при этом условии возможно несколько вариантов, выбирается тот, при котором наибольшую массу имеет второй по величине груз, и т. д. Известны количество грузов, масса каждого из них и грузоподъёмность грузовика. Необходимо определить количество и общую массу грузов, которые будут вывезены при погрузке по вышеописанным правилам.
Входные данные:
Первая строка входного файла содержит два целых числа: N — общее количество грузов и M — грузоподъёмность грузовика в кг. Каждая из следующих N строк содержит одно целое число — массу груза в кг.
Выходные данные:
В ответе запишите два целых числа: сначала максимально возможное количество грузов, затем их общую массу.
Решаем с помощью Excel
- Отрываем файл, копируем (Ctrl+A) и вставляем в Excel (Ctrl+V), перемещаем первую ячейку (N — общее количество грузов и M — грузоподъёмность грузовика в кг) и сортируем по возрастанию данные в столбце А
- выбираем диапазон от 200 до 210 кг, можно его скопировать и вставить в отдельный столбик. Подсчитаем сумму и количество груза.
- Находим массу груза без главного 10000-2669=7331. В столбце А выделяем диапазон, который на превышает полученное число, фиксируем количество (110) и массу последнего большого груза (123).
- Стараются взять как можно больше грузов, если это можно сделать несколькими способами, выбирают тот способ, при котором самый большой из выбранных грузов имеет наибольшую массу. Если и при этом условии возможно несколько вариантов, выбирается тот, при котором наибольшую массу имеет второй по величине груз, и т. д.
- Постараемся найти такой груз, что бы грузоподъемность была наибольшей и количество грузов не поменялось. Будем подбирать
Ответ: 123 10000
Статьи
Среднее общее образование
Информатика
Предлагаем вашему вниманию разбор задания №26 ЕГЭ 2019 года по информатике и ИКТ. Этот материал содержит пояснения и подробный алгоритм решения, а также рекомендации по использованию справочников и пособий, которые могут понадобиться при подготовке к ЕГЭ.
30 января 2019
Что нового?
В предстоящем ЕГЭ не появилось никаких изменений по сравнению с прошлым годом.
Возможно, вам также будут интересны демоверсии ЕГЭ по математике и физике.
О нововведениях в экзаменационных вариантах по другим предметам читайте в наших новостях.
ЕГЭ-2020. Информатика. Тематические тренировочные задания
Пособие содержит задания, максимально приближенные к реальным, используемым на ЕГЭ, но распределенные по темам в порядке их изучения в 10-11-х классах старшей школы. Работая с книгой, можно последовательно отработать каждую тему, устранить пробелы в знаниях, а также систематизировать изучаемый материал. Такая структура книги поможет эффективнее подготовиться к ЕГЭ.
Купить
Источник: сайт
ФИПИ
Демоверсия КИМ ЕГЭ-2019 по информатике не претерпела никаких изменений по своей структуре по сравнению с 2018 годом. Это значимо упрощает работу педагога и, конечно, уже выстроенный (хочется на это рассчитывать) план подготовки к экзамену обучающегося.
Мы рассмотрим решение предлагаемого проекта (на момент написания статьи – пока еще проекта) КИМ ЕГЭ по информатике.
Часть 2
Для записи ответов на задания этой части (24–27) используйте БЛАНК ОТВЕТОВ № 2. Запишите сначала номер задания (24, 25 и т. д.), а затем полное решение. Ответы записывайте чётко и разборчиво.
Далее не видим необходимости придумывать что-то отличное от официального содержания КИМ демоверсии. Документ уже несет в себе «содержание верного ответа и указания по оцениванию», а также «указания для оценивания» и некоторые «примечания для эксперта».
Задание 26
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч (по своему выбору) один камень или увеличить количество камней в куче в три раза. Например, пусть в одной куче 10 камней, а в другой 7 камней; такую позицию в игре будем обозначать (10, 7). Тогда за один ход можно получить любую из четырёх позиций:
(11, 7), (30, 7), (10, 8), (10, 21).
Для того чтобы делать ходы, у каждого игрока есть неограниченное количество камней.
Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее 68. Победителем считается игрок, сделавший последний ход, т.е. первым получивший такую позицию, при которой в кучах будет 68 или больше камней.
В начальный момент в первой куче было шесть камней, во второй куче – S камней; 1 ≤ S ≤ 61.
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока – значит описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника. В описание выигрышной стратегии не следует включать ходы играющего по этой стратегии игрока, не являющиеся для него безусловно выигрышными, т.е. не являющиеся выигрышными независимо от игры противника.
Выполните следующие задания.
Задание 1
в) Укажите все такие значения числа S, при которых Петя может выиграть за один ход.
г) Известно, что Ваня выиграл своим первым ходом после неудачного первого хода Пети. Укажите минимальное значение S, когда такая ситуация возможна.
Задание 2
Укажите такое значение S, при котором у Пети есть выигрышная стратегия, причём одновременно выполняются два условия:
- Петя не может выиграть за один ход;
- Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.
Для указанного значения S опишите выигрышную стратегию Пети.
Задание 3
Укажите значение S, при котором одновременно выполняются два условия:
- у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;
- у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.
Для указанного значения S опишите выигрышную стратегию Вани.
Постройте дерево всех партий, возможных при этой выигрышной стратегии Вани (в виде рисунка или таблицы).
В узлах дерева указывайте позиции, на рёбрах рекомендуется указывать ходы. Дерево не должно содержать партии, невозможные при реализации выигрывающим игроком своей выигрышной стратегии. Например, полное дерево игры не является верным ответом на это задание.
Содержание верного ответа и указания по оцениванию |
Задание 1а) Петя может выиграть при 21 ≤ S ≤ 61. б) S = 7. Задание 2Возможное значение S: 20. В этом случае Петя, очевидно, не может выиграть первым ходом. Однако он может получить позицию (7, 20). После хода Вани может возникнуть одна из четырёх позиций: (8, 20), (21, 20), (7, 21), (7, 60). В каждой из этих позиций Петя может выиграть одним ходом, утроив количество камней во второй куче. Замечание для проверяющего. Ещё одно возможное значение S для этого задания – число 13. В этом случае Петя первым ходом должен утроить количество камней в меньшей куче и получить позицию (6 * 3, 13) = (18, 13). При такой позиции Ваня не может выиграть первым ходом, а после любого хода Вани Петя может выиграть, утроив количество камней в большей куче. Достаточно указать одно значение S и описать для него выигрышную стратегию. Задание 3
Возможное значение S: 19. После первого хода Пети возможны позиции: В таблице изображено дерево возможных партий (и только их) при описанной стратегии Вани. Заключительные позиции (в них выигрывает Ваня) выделены жирным шрифтом. На рисунке это же дерево изображено в графическом виде (оба способа изображения дерева допустимы).
Примечание для эксперта. Дерево всех партий может быть также изображено в виде ориентированного графа – так, как показано на рисунке, или другим способом. Важно, чтобы множество полных путей в графе находилось во взаимно однозначном соответствии со множеством партий, возможных при описанной в решении стратегии.
Рис. 1. Дерево всех партий, возможных при Ваниной стратегии. Ходы Пети показаны пунктиром; ходы Вани – сплошными линиями. Прямоугольником обозначены позиции, в которых партия заканчивается. Замечание для проверяющего. Не является ошибкой указание только одного заключительного хода выигрывающего игрока в ситуации, когда у него есть более одного выигрышного хода |
Указания по оцениванию |
Баллы |
В задаче требуется выполнить три задания. Их трудность возрастает. Количество баллов в целом соответствует количеству выполненных заданий (подробнее см. ниже). Ошибка в решении, не искажающая основного замысла и не приведшая к неверному ответу – например, арифметическая ошибка при вычислении количества камней в заключительной позиции – при оценке решения не учитывается. Задание 1 выполнено, если выполнены оба пункта: а) и б), т.е. для п. а) перечислены все значения S, удовлетворяющие условию (и только они), для п. б) указано верное значение S (и только оно). Задание 2 выполнено, если правильно указана позиция, выигрышная для Пети, и описана соответствующая стратегия Пети – так, как это сделано в примере решения, или другим способом, например, с помощью дерева всех возможных при выбранной стратегии Пети партий (и только их). Задание 3 выполнено, если правильно указана позиция, выигрышная для Вани, и построено дерево всех возможных при Ваниной стратегии партий (и только их). Во всех случаях стратегии могут быть описаны так, как это сделано в примере решения, или другим способом. |
|
Выполнены задания 1, 2 и 3. |
3 |
Не выполнены условия, позволяющие поставить 3 балла, и выполнено одно из следующих условий: 1. Выполнено задание 3 2. Выполнены задания 1 и 2 |
2 |
Не выполнены условия, позволяющие поставить 3 или 2 балла, и выполнено одно из следующих условий: 1. Выполнено задание 1 2. Выполнено задание 2 |
1 |
Не выполнено ни одно из условий, позволяющих поставить 3, 2 или 1 балл. |
0 |
3 |
#ADVERTISING_INSERT#