Калужский Александр: Пришлите ссылку на задачу...
25-04-2024
Читать статью
didnt respond: Почему на РешуЕгэ условие стратегии побе..
///: Спасибо Вам большое! Всё очень понятно!!..
22-04-2024
Продолжаем разбирать задачи из досрочного ЕГЭ по информатике 2023.
Ещё лучше подготовится к ЕГЭ по информатике, Вы можете по материалам сайта Code-Enjoy.
Файлы, ответы и формулировки могут не совпадать с реальным досрочным экзаменом, а данная статья лишь примерно показывает прототипы задач.
При регистрации в компьютерной системе каждому объекту сопоставляется идентификатор, состоящий из 35 символов и содержащий только символы из 8-символьного набора. В базе данных для хранения сведений о каждом объекте отведено одинаковое и минимально возможное целое число байт. При этом используют посимвольное кодирование идентификаторов, все символы кодируют одинаковым и минимально возможным количеством бит.
Определите объём памяти (в Кбайтах), необходимый для хранения сведений о 20 480 объектах. В ответе запишите только целое число – количество Кбайт.
Воспользуемся формулой для 11-ого задания из ЕГЭ по информатике.
Вместо N подставляем 8 символов, которые претендуют в одну ячейку. Тогда
Т.е. 3 бита точно хватит, чтобы закодировать 8 символов.
В идентификаторе всего 35 ячеек. Найдём сколько будет "весить" один идентификатор: 3 * 35 = 105 бит. Узнаем, сколько байт потребуется для одного идентификатора 105 / 8 = 14 байт (округляем в большую сторону, чтобы точно хватило).
У нас всего 20480 идентификаторов. Тогда нам потребуется 20480 * 14 = 286720 байт. Переведём в Кб: 716800 / 1024 = 280 Кб.
Исполнитель Редактор получает на вход строку символов и преобразовывает её. Редактор может выполнять две команды, в обеих командах v и w обозначают цепочки символов.
Эта команда заменяет в строке первое слева вхождение цепочки v на цепочку w. Например, выполнение команды заменить (111, 27) преобразует строку 05111150 в строку 0527150. Если в строке нет вхождений цепочки v, то выполнение команды заменить (v, w) не меняет эту строку.
Эта команда проверяет, встречается ли цепочка v в строке исполнителя Редактор. Если она встречается, то команда возвращает логическое значение «истина», в противном случае возвращает значение «ложь». Строка исполнителя при этом не изменяется.
Дана программа для Редактора:
НАЧАЛО ПОКА нашлось (25) ИЛИ нашлось (333) ИЛИ нашлось (555) ЕСЛИ нашлось (25) ТО заменить (25, 3) КОНЕЦ ЕСЛИ ЕСЛИ нашлось (355) ТО заменить (355, 52) КОНЕЦ ЕСЛИ ЕСЛИ нашлось (555) ТО заменить (555, 23) КОНЕЦ ЕСЛИ КОНЕЦ ПОКА КОНЕЦ
На вход приведённой выше программе поступает строка, начинающаяся с цифры «3», а затем содержащая n цифр «5» (n > 3).
Определите наименьшее значение n, при котором сумма числовых значений цифр строки, получившейся в результате выполнения программы, равняется 18.
Напишем программу на языке Python.
def F(s): sm=0 for x in s: sm=sm+int(x) return sm for n in range(4, 300): s = '3' + n*'5' while '25' in s or '333' in s or '555' in s: if '25' in s: s=s.replace('25', '3', 1) if '355' in s: s=s.replace('355', '52', 1) if '555' in s: s=s.replace('555', '23', 1) if F(s) == 18: print(n)
Функция F() подсчитывает сумму цифр в строке.
Пробуем с помощью цикла for использовать разное количество пятёрок в первоначальной строке s. Если после выполнения программы для редактора, строка будет удовлетворять условию задачи, значит, печатаем то количество пятёрок (переменная n), при котором это произошло.
Более подробно, как решать задачи из 12 Задания, можете почитать в этой статье.
Наименьшее n равно 9.
На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, К, Л, М, Н, И. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей, ведущих из города А в город Н?
Решим по известной технике для 13 задания из ЕГЭ по информатике, о которой Вы можете прочитать на страницах данного сайта.
Операнды арифметического выражения записаны в системе счисления с осно-ванием 15.
В записи чисел переменной x обозначена неизвестная цифра из алфавита 15-ричной системы счисления. Определите наибольшее значение x, при котором значение данного арифметического выражения кратно 14. Для найденного значения x вычислите частное от деления значения арифметического выражения на 14 и укажите его в ответе в десятичной системе счисления. Основание системы счисления в ответе указывать не нужно.
Как решать такой "новый тип" задания 14 из ЕГЭ по информатике, читатели моего сайта отлично знают. Об этом мы говорили в этой статье.
for x in range(0, 15): a=1*15**0+2*15**1+x*15**2+8*15**3+6*15**4+9*15**5+7*15**6+9*15**7 b=3*15**0+2*15**1+x*15**2+7*15**3 if (a+b)%14==0: print((a+b)//14)
Последнее выведенное число соответствует наибольшему значению x.
Для какого наименьшего целого неотрицательного A выражение
тождественно истинно, т.е. принимает значение 1 при любых целых неотрицательных x и y?
Из 4 шаблонов выбираем нужный!
for A in range(0, 300): k=0 for x in range(0, 300): for y in range(0, 300): if (x >= 9) or (2*x < y) or (x*y < A): k=k+1 if k==300*300: print(A)
Наименьшее значение A будет равно 129.
Алгоритм вычисления значения функции F(n), где n – натуральное число, за-дан следующими соотношениями:
F(n) = n при n ≥ 2025;
F(n) = n + F(n + 2), если n < 2025.
Чему равно значение выражения F(2020) - F(2023)?
Здесь мы видим большие числа, которые передаются функции F(), поэтому будем решать с помощью инструмента lru_cache.
from functools import lru_cache @lru_cache(None) def F(n): if n>=2025: return n if n<2025: return n+F(n+2) for i in range(2025, 0, -1): F(i) print(F(2020)-F(2023))
Функция возрастающая, поэтому мы запускаем функцию в цикле в начале с большими числами, а потом числа убывают.
В файле содержится последовательность натуральных чисел. Элементы последовательности могут принимать целые значения от 1 до 100 000 включительно. Определите количество пар последовательности, в которых только одно число является двузначным, а сумма пары кратна минимальному двузначному числу во всём файле. В ответе запишите количество найденных пар, затем максимальную из сумм элементов таких пар. В данной задаче под парой подразумевается два идущих подряд элемента последовательности.
В начале найдём минимальное двухзначное число во всём файле.
f=open('17_dosrok.txt') mn=10**10 for s in f.readlines(): x=int(s) if x>9 and x<100: mn=min(mn, x) print(mn)
Получается число 32.
Теперь найдём ответы на вопросы, связанные с парами чисел.
f=open('17_dosrok.txt') mx=0 k=0 n1=int(f.readline()) for s in f.readlines(): n2=int(s) if ((10<=n1<=99) != (10<=n2<=99)) and ((n1+n2)%32==0): k=k+1 mx = max(mx, n1+n2) n1=n2 print(k, mx)
Если первое число двухзначное, то второе не должно быть двухзначным или наоборот, если второе число двухзначное, то первое не должно быть двухзначным. Эта операция называется "исключающее ИЛИ". Мы логические операции разбирали в этой статье. Исключающее ИЛИ может быть представлено, как отрицание равносильности.
Так же сумма элементов пары должна делиться на 32 (наименьшее двухзначное число всей последовательности).
В остальном же решаем по схеме, о которой мы говорили в этой статье по 17 заданию из ЕГЭ по информатике.
Квадрат разлинован на N × N клеток (1 < N < 30). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде вправо Робот перемещается в соседнюю правую клетку, по команде вниз – в соседнюю нижнюю. Квадрат ограничен внешними стенами. Между соседними клетками квадрата также могут быть внутренние стены. Сквозь стену Робот пройти не может.
Перед каждым запуском Робота в каждой клетке квадрата лежит монета до-стоинством от 1 до 100. Посетив клетку, Робот забирает монету с собой; это также относится к начальной и конечной клеткам маршрута Робота.
Определите максимальную и минимальную денежные суммы, которые может собрать Робот, пройдя из левой верхней клетки в правую нижнюю. В ответе укажите два числа – сначала максимальную сумму, затем минимальную.
Исходные данные представляют собой электронную таблицу размером N × N, каждая ячейка которой соответствует клетке квадрата. Внутренние и внешние стены обозначены утолщёнными линиями.
Открываем файл в программе Excel.
Выделим все ячейки с числами, нажмём "вырезать", используя контекстное меню. Вставим данные на 1 столбец вправо. Это делаем потому, что будем использовать для решения формулу, которая будет обращаться к ячейке слева.
Мысленно представим пространство на 1 строчку ниже, чем область, где находятся числа. Это пространство будет таким же по размерам, как и область с числами. В этом пространстве и будет наше решение.
Отметим особым цветом те ячейки, которые "спрятаны" от движения Робота стенками.
Для этих ячеек будем составлять другие формулы, в отличии от обычных ячеек.
Цвет ячейки можно поменять, нажав на кнопку "Цвет заливки" на главной вкладке программы.
Т.к. Робот направляется из левой верхней ячейки, то мы сначала и напишем формулу для этой ячейки. Пишем для ячейки B22:
Робот в любую ячейку может прийти либо сверху, либо слева. Для подсчёта максимального количества монет, мы должны выбрать максимальное предыдущее значение. Это и делаем формула. Плюс Робот должен взять монеты с текущей клетки.
Распространим формулу на всё пространство, не трогая закрашенные клетки.
Получается такая картина:
Для вертикальных подкрашенных полосок, Робот может попасть только сверху! Поэтому пишем формулу для ячейки, к примеру, для E25:
Распространяем формулу по всему закрашенному столбцу. Аналогично делаем для всех вертикальны подкрашенных полосок.
В ячейки для горизонтально подкрашенных полосок, Робот может попасть только слева! Поэтому пишем формулу, к примеру, для ячейки I35:
Распространяем формулу по всей закрашенной строчке. Аналогично делаем со всеми горизонтальными полосками.
В правом нижнем углу нашего рабочего пространства получается максимальное количество монет, которое может собрать Робот. В ячейке U41 получается число 2502.
Чтобы получить минимальную возможную сумму, в главной формуле функцию МАКС нужно заменить на МИН!
Удобно воспользоваться автоматической заменой через Ctrl+F.
Минимальная сумма равна 1124.
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один камень, четыре камня или увеличить количество камней в куче в три раза. Для того чтобы делать ходы, у каждого игрока есть неограниченное количество камней.
Игра завершается в тот момент, когда количество камней в куче становится не менее 46. Победителем считается игрок, сделавший последний ход, т.е. первым получивший кучу из 46 или больше камней.
В начальный момент в куче было S камней, 1 ≤ S ≤ 45.
Будем говорить, что игрок имеет выигрышную стратегию, если он может вы-играть при любых ходах противника.
Укажите такое значение S, при котором Петя не может выиграть за один ход, но при любом ходе Пети Ваня может выиграть своим первым ходом.
Решим задачу с помощью шаблона на Python.
def F(x, p): if x>=46 and p==3: return True if x<46 and p==3: return False if x>=46: return False if p%2==1: return F(x+1, p+1) and F(x+4, p+1) and F(x*3, p+1) else: return F(x+1, p+1) or F(x+4, p+1) or F(x*3, p+1) for s in range(1, 46): if F(s, 1): print(s)
Для игры, описанной в предыдущем задании, найдите два наименьших значения S, при которых у Пети есть выигрышная стратегия, причём одновременно выполняются два условия:
− Петя не может выиграть за один ход;
− Петя может выиграть своим вторым ходом независимо от того, как бу-дет ходить Ваня.
Найденные значения запишите в ответе в порядке возрастания.
немного подправим прошлый шаблон и получаем 20 задачу.
def F(x, p): if x>=46 and p==4: return True if x<46 and p==4: return False if x>=46: return False if p%2==0: return F(x+1, p+1) and F(x+4, p+1) and F(x*3, p+1) else: return F(x+1, p+1) or F(x+4, p+1) or F(x*3, p+1) for s in range(1, 46): if F(s, 1): print(s)
Для игры, описанной в задании 19, найдите минимальное значение S, при ко-тором одновременно выполняются два условия:
– у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;
– у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.
Об этих шаблонах мы говорили в этой статье.
def F(x, p): if x>=46 and (p==3 or p==5): return True if x<46 and p==5: return False if x>=46: return False if p%2==1: return F(x+1, p+1) and F(x+4, p+1) and F(x*3, p+1) else: return F(x+1, p+1) or F(x+4, p+1) or F(x*3, p+1) def F1(x, p): if x>=46 and p==3: return True if x<46 and p==3: return False if x>=46: return False if p%2==1: return F1(x+1, p+1) and F1(x+4, p+1) and F1(x*3, p+1) else: return F1(x+1, p+1) or F1(x+4, p+1) or F1(x*3, p+1) for s in range(1, 46): if F(s, 1): print(s) print() for s in range(1, 46): if F1(s, 1): print(s)
