Калужский Александр: Пришлите ссылку на задачу...
25-04-2024
Читать статью
didnt respond: Почему на РешуЕгэ условие стратегии побе..
///: Спасибо Вам большое! Всё очень понятно!!..
22-04-2024
Продолжаем разбор задач из реального экзамен ЕГЭ по информатике 2022, который прошёл 20.06.22
Все задачи взяты с сайта: https://kompege.ru/variant?kim=25012688
Далее будем решать задачи из теории игр.
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч (по своему выбору) один камень или увеличить количество камней в куче в два раза. Для того чтобы делать ходы, у каждого игрока есть неограниченное количество камней.
Игра завершается в тот момент, когда суммарное количество камней в кучах снатовится не менее 259. Победителем считается игрок, сделавший последний ход, т.е. первым получивший такую позицию, при которой в кучах будет 259 или больше камней.
В начальный момент в первой куче было 17 камней, во второй куче - S камней; 1 <= S <= 241. Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.
Известно, что Ваня выиграл своим первым ходом после неудачного первого хода Пети. Укажите минимальное значение S, когда такая ситуация возможна.
Решим задачу с помощью шаблона на языке программирования Python.
Введём параметр p, который будет олицетворять позицию игры (ход).
def F(x, y, p): if x + y >= 259 and p==3: return True if x + y < 259 and p==3: return False return F(x+1, y, p+1) or F(x*2, y, p+1) or F(x, y+1, p+1) or F(x, y*2, p+1) for s in range(1, 242): if F(17, s, 1): print(s)
Заводим функцию F. Т.к. у нас две кучи, то она принимает параметры: x - количество камней в первой куче, y - количество камней во второй куче, p-позиция игры.
Дальше описываем победу. Если x + y >= 259 и позиция равна 3 (1 Ход Вани), то возвращаем True, что означает победу.
Если, позиция уже равна 3, но камней меньше, чем должно быть для победы, то возвращаем False (проигрыш).
Если мы не вышли на первых двух условиях, то, значит, продолжаем прокручивать ходы, рекурсивно запускаем функцию F. Между запусками ставим союз ИЛИ.
В конце перебираем все возможные значения для s через цикл for, ищём те значения, которые подходят по условию задачи.
Для игры, описанной в предыдущем задании, найдите два нименьших значения S, при которых у Пети есть выиграшная стратегия, причём одновременно выполняются два условия:
- Петя не может выиграть за один ход.
- Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.
Найденные значения запишите в ответе в порядке возрастания.
def F(x, y, p): if x + y >= 259 and p==4: return True if x + y < 259 and p==4: return False if x + y >= 259: return False if p%2==0: return F(x+1, y, p+1) and F(x*2, y, p+1) and F(x, y+1, p+1) and F(x, y*2, p+1) else: return F(x+1, y, p+1) or F(x*2, y, p+1) or F(x, y+1, p+1) or F(x, y*2, p+1) for s in range(1, 242): if F(17, s, 1): print(s)
Теперь должен выигрывать Петя на своём втором ходе. Поэтому в условиях ставим позицию p=4.
Добавляется третье условие. Если кто-то выиграл, но на первых двух условиях мы не вышли из функции, то, значит, выиграл не тот, кто нам нужен, следовательно, возвращаем Fasle.
Здесь вопрос отличается от 19 задания. Здесь Петя должен побеждать при любом ходе соперника, а не при одном неудачном ходе Вани, поэтому добавляется ещё условие.
Для чётных p (это ходы Пети), возвращаем разные ходы через and, т.к. он должен побеждать в любом случае.
Для нечётных p (это ходы Вани), возвращаем ходы через or.
Для игры, описанной в задании 19, найдите мнимальное значение S, при котором одновременно выполняются два условия:
- у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;
-у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.
Опять используем прошлый шаблон, но немного модернизируем.
def F(x, y, p): if x + y >= 259 and (p==3 or p==5): return True if x + y < 259 and p==5: return False if x + y >= 259: return False if p%2==1: return F(x+1, y, p+1) and F(x*2, y, p+1) and F(x, y+1, p+1) and F(x, y*2, p+1) else: return F(x+1, y, p+1) or F(x*2, y, p+1) or F(x, y+1, p+1) or F(x, y*2, p+1) def F1(x, y, p): if x>=259 and p==3: return True if x<259 and p==3: return False if x>=259: return False if p%2==1: return F1(x+1, y, p+1) and F1(x*2, y, p+1) and F1(x, y+1, p+1) and F1(x, y*2, p+1) else: return F1(x+1, y, p+1) or F1(x*2, y, p+1) or F1(x, y+1, p+1) or F1(x, y*2, p+1) for s in range(1, 242): if F(17, s, 1): print(s) print() for s in range(1, 242): if F1(17, s, 1): print(s)
Здесь Ваня должен выигрывать либо на первом своём ходе (p=3), либо на втором своём ходе (p=5).
Т.к. Ваня не должен гарантированно выиграть своим первым ходом, то мы создаём ещё одну функцию F1, похожую на основную функцию F, которая вычисляет, когда Ваня именно гарантированно выигрывает на своём первом ходе (p=3). И, затем, мы из тех чисел, которые получились в первой функции F, исключаем числа, которые получились во второй функции F1.
В первой функции получилось 111, 119, а во второй результатов нет. Получается ответ 111.
Ниже на четырёх языках программирования записан алгоритм. Получив на вход число x, этот алгоритм печатает два числа: L и M. Укажите наибольшее число x, при вводе которого алгоритм печатает сначала 8, а потом 21.
*На этом сайте программа приведена на одном языке.
Будем решать методом перебора.
for i in range(0, 10000): x = i Q = 6 P = 10 K1 = 0 K2 = 0 while x <= 100: K1 = K1 + 1 x = x + P while x >= Q: K2 = K2 + 1 x = x - Q L = x + K1 M = x + K2 if L==8 and M==21: print(i)
Исполнитель преобразует число на экране.
У исполнителя есть две команды, которым присвоены номера:
1. Вычти 1
2. Найди целую часть от деления на 2
Первая из них уменьшает число на экране на 1, вторая заменяет число на экране на целую часть от деления числа на 2.
Программа для исполнителя - это последовательность команд.
Сколько существует программ, для которых при исходном числе 30 результатом является на число 1, и при этом траектория вычислений содержит число 12?
Траектория вычислений программы - это последователность результатов выполнения всех команд программы.
Например, для программы 122 при исходном числе 10 траектория состоит из чисел 9, 4, 2.
Будем решать с помощью шаблона на языке 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(30, 12)*F(12, 1))
Текстовый файл состоит из символов 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)
Назовём маской числа последовательность цифр, в которой также могут встречаться следующие символы:
— символ "?" означает ровно одну произвольную цифру;
— символ "*" означает любую последовательность цифр произвольной длины; в том числе "*" может задавать и пустую последовательность.
Например, маске 123*4?5 соответсвуют числа 123405 и 12300405.
Среди натуральных чисел, не превышающих 108, найдите все числа, соответствующие маске 1234*7, делящиеся на 141 без остатка.
В ответе запишите в первом столбце таблицы все найденные числа в порядке возрастания, а во втором столбце — соответствующие им результаты деления этих чисел на 141.
Здесь самый главный момент заключается в том, что есть верхняя граница 108. Т.е. самое большое число, которое нужно рассмотреть 1234[999]7 <= 108 = 100000000. Нижняя граница тоже задана, когда вместо звёздочки ни одной цифры не будет 12347.
i=12347 #Вместо звёздочки ноль разрядов if i%141==0: print(i, i//141) #Вместо звёздочки один разряд for x in '0123456789': s = '1234' + x + '7' i=int(s) if i%141==0: print(i, i//141) #Вместо звёздочки два разряда for x in '0123456789': for y in '0123456789': s = '1234' + x + y + '7' i=int(s) if i%141==0: print(i, i//141) #Вместо звёздочки три разряда for x in '0123456789': for y in '0123456789': for z in '0123456789': s = '1234' + x + y + z + '7' i = int(s) if i%141==0: print(i, i//141)
Таким образом, нужно рассмотреть, когда вместо звёздочки ноль разрядов, один разряд, два разряда и три разряда.
Каждый разряд перебираем как цифры (символы). Формируем строку s, а затем её переводим в тип int.
Когда два разряда или три разряда нужно перебирать строку с помощью вложенных циклов.
В магазине для упаковки подарков есть 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 окажется максимальный размер самой маленькой коробки.
У медицинской компании есть N пунктов приёма биоматериалов на анализ. Все пункты расположены вдоль автомагистрали и имеют номера, соответствующие расстоянию от нулевой отметки до конкретного пункта. Известно количество пробирок, которое ежедневно принимают в каждом из пунктов. Пробирки перевозят в специальных транспортировочных контейнерах вместимостью не более 36 штук. Каждый транспортировочный контейнер упаковывается в пункте приёма и вскрывается только в лаборатории. Компания планирует открыть лабораторию в одном из пунктов. Стоимость перевозки биоматериалов равна произведению расстояния от пункта до лаборатории на количество контейнеров с пробирками. Общая стоимость перевозки за день равна сумме стоимостей перевозок из каждого пункта в лабораторию. Лабораторию расположили в одном из пунктов приёма биоматериалов таким образом, что общая стоимость доставки биоматериалов из всех пунктов минимальна.
Определите минимальную общую стоимость доставки биоматериалов из всех пунктов приёма в лабораторию.
Входные данные
Дано два входных файла (файл А и файл B), каждый из которых в первой строке содержит число N ( 1 ≤ N ≤ 10 000 000) - количество пунктов приёма биоматериалов. В каждой из следующих N строк находится два числа: номер пункта и количество пробирок в этом пункте (все числа натуральные, количество пробирок в каждом пункте не превышает 1000). Пункты перечислены в порядке их расположения вдоль дороги, начиная от нулевой отметки.
В ответе укажите два числа: сначала значение искомой величины для файла A, затем - для файла B.
При таких исходных данных и вместимости транспортировочного контейнера, составляющей 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). Пусть лаборатория будет во втором пункте, тогда:
Отсюда мы понимаем, что достаточно вычислить стоимость доставки 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.
