Сообщения

Подпоследовательность с максимальной суммой, кратной 43

Подпоследовательность с максимальной суммой, кратной 43.   Хотите готовиться со мной к ЕГЭ? Пишите: ydkras@mail.ru Немного обо мне .   Рассмотрим следующую задачу из демонстрационного варианта ФИПИ ЕГЭ по информатике 2022 г. (она также включена в вариант 3 на сайте Полякова): Дана последовательность из N натуральных чисел. Рассматриваются все её непрерывные подпоследовательности, такие что сумма элементов каждой из них кратна k = 43. Найдите среди них подпоследовательность с максимальной суммой, определите её длину. Если таких подпоследовательностей найдено несколько, в ответе укажите количество элементов самой короткой из них. Входные данные . Даны два входных файла ( файл A и файл B ), каждый из которых содержит в первой строке количество чисел N (2 ≤ N ≤ 10 8 ). Каждая из следующих N строк содержит натуральное число, не превышающее 10000. Пример входного файла : 7 21 13 9 19 17 26 95 В этом наборе можно выбрать последовательности 21+13+9 (сумма 43) и 17+26 (сумма 4...

Теория игр, информатика и питон. Задачи ЕГЭ 19-21

Теория игр, информатика и питон. Задачи ЕГЭ 19-21.   Хотите готовиться со мной к ЕГЭ? Пишите: ydkras@mail.ru Немного обо мне .   Внимание! Данный материал устарел! Новую версию статьи читайте здесь: https://ege-informatika-yk.blogspot.com/2024/02/19-21.html       В задачах 19-21 ЕГЭ по информатике требуется проанализировать некую простую игру. Однако хотя игра и проста, её анализ может оказаться достаточно хитрым делом. Поэтому приходит мысль: а нельзя ли, чтобы этот анализ выполнил компьютер? (Спойлер: Можно!) Немного теории. Основную идею, лежащую в основе теории игр, подобных описанным в задачах ЕГЭ, можно выразить в двух словах: игроки умные. Это означает, что если у кого-то из игроков в текущей позиции есть возможность сделать выигрышный ход, то он этот ход сделает. Таким образом, если в текущей позиции у игрока есть хотя бы один ход, ведущий к выигрышу, то это - выигрышная позиция для данного игрока.  Если же в ответ на любой ход текущего игрока его п...

Задача 16 - рекурсивная функция

Задача 16 - рекурсивная функция Хотите готовиться со мной к ЕГЭ? Пишите: ydkras@mail.ru Немного обо мне .   Задача 16 ЕГЭ по информатике посвящена рекурсивным функциям.  Рекурсивные функции - такие функции, которые обращаются к самим себе. Рассмотрим задачу 16 из демонстрационного варианта ЕГЭ 2022 г. с сайта ФИПИ: Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями: F(n) = 1 при n = 1; F(n) = n + F(n − 1), если n чётно, F(n) = 2 × F(n − 2), если n > 1 и при этом n нечётно. Чему равно значение функции F(26)? Вообще говоря, данная задача решается на бумаге. Для этого придется составить таблицу, содержащую значения F(1), F(2) и т.д. - до F(26) включительно. Но составлять таблицу из 26 строк вручную несколько трудоемко, да и вероятность ошибиться ненулевая. Гораздо проще составить эту таблицу в excel.   Но, на мой взгляд, ещё проще решать данную задачу программно. Сначала напишем рекурсивную функцию на Питоне: def F(n)...

Слова по порядку (задача 8)

Слова по порядку (задача 8)   Хотите готовиться со мной к ЕГЭ? Пишите:  ydkras@mail.r u Немного обо мне .   Рассмотрим типичную задачу ЕГЭ по информатике по теме 8 ("Перебор слов и системы счисления"). Все 5-буквенные слова, составленные из букв Л, Н, Р, Т, записаны в алфавитном порядке. Вот начало списка: 1. ЛЛЛЛЛ 2. ЛЛЛЛН 3. ЛЛЛЛР 4. ЛЛЛЛТ 5. ЛЛЛНЛ Запишите слово, которое стоит на 150-м месте от начала списка. (Задача 7755 с сайта "Решу ЕГЭ".) В принципе эта задача решается довольно просто. Данные слова можно рассматривать как числа в системе счисления с основанием 4, причем вместо цифры 0 используется буква Л, вместо 1 - Н, вместо 2 - Р и вместо Т - 3.  Заметим, что под номером 1 стоит число 0, под номером 2 - число 1 и т.д. Таким образом, под номером 150 будет стоять число 149. Надо перевести число 149 в систему счисления с основанием 4, затем заменить в нем цифру 0 на букву Л, 1 - на Н и т.д.  Это не так уж сложно сделать вручную, но можно и написать прог...
 Простые числа: как их находить? Многие задачи ЕГЭ требуют либо находить простые числа, либо проверять их на простоту. В этой статье мы рассмотрим, как быстро проверять, является ли данное число простым, а также находить простые числа. Метод "грубой силы": просто, но медленно Если чисел немного и они на слишком велики, то вполне годится "метод грубой силы": пробуем делить наше число на все числа меньше его. Если не найдется чисел, на которые наше число делится без остатка, то оно простое. Приведем фрагмент программы, который осуществляет проверку числа n:   prime = True for i in range(2,n):     if n%i == 0:         prime = False         break  По завершении цикла переменная prime будет иметь значение True, если число n простое, и False в противном случае. Процедуру можно существенно ускорить, если проверять делимость на числа в диапазоне от 2 до квадратного корня из проверяемого числа. Мо...
Длинный диктант - вычеркнуть букву, чтобы число букв "A" на четных и нечетных местах было одинаковым. Эта задача не из ЕГЭ, но алгоритм решения получился красивым, поэтому хотелось бы им поделиться. Задача формулируется следующим образом: Есть длинная (до миллиона символов) строка, состоящая из букв "A" и "B". Надо вычеркнуть из неё один символ так, чтобы количество букв "A", стоящих на нечетных местах, было бы равно количеству букв "A" на четных местах. Простой способ решения - подсчитать для каждой позиции в строке, сколько букв "A" на нечетных и четных местах до этой позиции включительно. Тогда при вычеркивании какой-либо буквы нечетные места после неё станут чётными и наоборот. Нужно сложить сумму нечетных до и сумму четных после, а также сумму четных до и сумму нечетных после. Если эти числа совпадут, то данная буква годится для вычеркивания. Приведем законченную программу на С. #include <stdio.h> #include <strin...

Числа вида 2m•3n

Числа вида 2 m •3 n Хотите готовиться со мной к ЕГЭ? Пишите:  ydkras@mail.r u Немного обо мне .   Рассмотрим следующую задачу для подготовки к ЕГЭ с сайта Полякова (задача 25 из варианта 19):   (№ 3977) Найдите все натуральные числа, N, принадлежащие отрезку [150 000 000; 300 000 000], которые можно представить в виде N = 2 m •3 n , где m – чётное число, n – нечётное число. В ответе запишите все найденные числа в порядке возрастания, а справа от каждого числа – сумму m+n.    Первая мысль - делить наше число сперва на два до тех пор, пока оно делится, а потом на три. При делении считать, сколько делений было выполнено (т.е. определить степени m и n). Если после таких делений получается 1, то число k не содержит других простых делителей, кроме 2 и 3. Если число m четное,  а число n - нечетное, то напечатать число и сумму m+n. Программа выглядит так:   for i in range(150000000, 300000000+1):     k=i     m...