Информатика, ЕГЭ, Питон и т.п.

Подпоследовательность с максимальной суммой, кратной 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 (сумма 43). Самая

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

Задача 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):     if n==1: retu

Слова по порядку (задача 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 до квадратного корня из проверяемого числа. Можно также отдельно проверить делимость на 2, а потом - только на нечетные числа

Длинный диктант - вычеркнуть букву, чтобы число букв "A" на четных и нечетных местах было одинаковым. Эта задача не из ЕГЭ, но алгоритм решения получился красивым, поэтому хотелось бы им поделиться. Задача формулируется следующим образом: Есть длинная (до миллиона символов) строка, состоящая из букв "A" и "B". Надо вычеркнуть из неё один символ так, чтобы количество букв "A", стоящих на нечетных местах, было бы равно количеству букв "A" на четных местах. Простой способ решения - подсчитать для каждой позиции в строке, сколько букв "A" на нечетных и четных местах до этой позиции включительно. Тогда при вычеркивании какой-либо буквы нечетные места после неё станут чётными и наоборот. Нужно сложить сумму нечетных до и сумму четных после, а также сумму четных до и сумму нечетных после. Если эти числа совпадут, то данная буква годится для вычеркивания. Приведем законченную программу на С. #include <stdio.h> #include <strin

Числа вида 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=0     while k%2 == 0:         k //= 2         m += 1     n=0     while k%3 ==

Сумма-палиндром Хотите готовиться со мной к ЕГЭ? Пишите:  ydkras@mail.r u Немного обо мне .   Рассмотрим следующую задачу для подготовки к ЕГЭ с сайта К.Полякова (задача 25, вариант 1):   (№ 4410) (Л. Шастин) Среди чисел, больших 520000, найти такие, сумма всех делителей которых, не считая единицы и самого числа, образует число-палиндром (например, число 1221: если его «перевернуть», получается то же самое число). Вывести первые пять чисел, удовлетворяющих вышеописанному условию, справа от каждого числа вывести его максимальный делитель.     Получить список делителей числа можно с помощью функции divisors, описанной в статье " Разложение на множители и простые числа ". Как определить, является ли число палиндромом? Наверно, самый короткий способ - преобразовать число в символьную строку и проверить строку "на палиндромность". Самое простое - сравнить исходную строку с "перевернутой задом наперед". В Питоне получить из некой строки s перевернутую стр

Питон и таблицы истинности   Хотите готовиться со мной к ЕГЭ? Пишите:  ydkras@mail.r u Немного обо мне .   Таблица истинности - это таблица, где перечисляются комбинации аргументов некой логической функции и указывается, какие значения принимает эта функция. В задаче 2 ЕГЭ по информатике требуется 1) уметь строить таблицы истинности логического выражения и 2) уметь сравнивать построенную таблицу истинности с таблицей, приведенной в условии задачи. Первый пункт можно выполнить на компьютере, написав несложную (менее 10 строк) программу на Питоне.  Вообще говоря, в Питоне, как и в паскале, есть специальные логические значения True и False. Но в логических выражениях можно использовать и числа. При этом значение 0 считается ложью, а всё, отличное от нуля - истиной. (Тут создатель Питона позаимствовал идею из С.) Рассмотрим  задачу с сайта "Решу ЕГЭ". В ней требуется сопоставить переменные, входящие в логическую функцию ((x → y ) ∧ (y → w)) ∨ (z ≡ ( x ∨ y)) и таблицу Переменная

Соседние места в концертном зале   Хотите готовиться со мной к ЕГЭ? Пишите:  ydkras@mail.r u Немного обо мне .   Язык Питон позволяет решать задачи ЕГЭ по информатике существенно проще, чем другие языки, которые можно использовать на ЕГЭ. Рассмотрим задачу 26 варианта 1 с сайта Полякова: (№ 4214) Организация купила для своих сотрудников все места в нескольких подряд идущих рядах на концертной площадке. Известно, какие места уже распределены между сотрудниками. Найдите ряд с наибольшим номером, в котором есть два соседних места, таких что слева и справа от них в том же ряду места уже распределены (заняты). Гарантируется, что есть хотя бы один ряд, удовлетворяющий условию. Входные данные представлены в файле 26-59.txt следующим образом. В первой строке входного файла находится одно число: N – количество занятых мест (натуральное число, не превышающее 10 000). В следующих N строках находятся пары чисел: ряд и место выкупленного билета, не превышающие 100000. В ответе запишите

 Как отсортировать массив В задачах ЕГЭ по информатике часто возникает потребность отсортировать массив, то есть переставить его элементы так, чтобы они расположились по возрастанию (или по убыванию).  Самый простой способ (на Питоне) Если нужно упорядочить массив a, то самый простой способ сделать это - метод sort: a.sort() После этого массив a будет отсортирован по возрастанию. Можно сортировать и по убыванию: a.sort(reverse=True) Метод работает очень быстро: массив из миллиоа элементов упорядочивается за доли секунды. Всё дальнейшее - скорее для общего развития либо для случая, если вы используете какой-то другой язык программирования. Некоторые другие способы сортировки. Если массив сравнительно небольшой (скажем, 10 тысяч элементов), то эта задача решается буквально в пять строк на Питоне (a - массив, который надо отсортировать): n=len(a) for i in range(n-1):     for j in range(i+1,n):         if a[i] > a[j]:             a[i],a[j] = a[j],a[i] Для массива из 10 тысяч элементов в

Задача про сумму делителей На сайте Полякова приводится следующая задача (задача 25 из варианта 4): (№ 4211) (А. Комков) Обозначим через S сумму делителей числа, не являющихся простыми, кроме единицы и самого числа. Если таких делителей у числа нет, то S равно нулю. Напишите программу, которая перебирает нечетные целые числа, меньшие 912673, в порядке убывания и ищет среди них первые 5 чисел, которые кратны S. Для каждого из найденных чисел в отдельной строке сначала выводится само число, затем значение S. Строки выводятся в порядке убывания найденных чисел.  Воспользуемся для решения этой задачи алгоритмами разложения числа на множители и проверки чисел на простоту, подробно описанными в статье Разложение на множители и простые числа . Напишем функцию, вычисляющую значение S: def S(n):     d = divisors(n)     s=0     for i in range(len(d)):         if not isprime(d[i]): s += d[i]     return s Эта функция использует функцию divisors, возвращающую массив делителей числа, и функцию

Задача 25 ЕГЭ по информатике: разложение на множители, простые числа, количество делителей. В задачах ЕГЭ по информатике часто требуется находить множители числа и проверять, является ли данное число простым. Рассмотрим способы делать это достаточно быстро. Разложение на множители. Самый простой способ разложения числа на множители: проверить его делимость на все числа, начиная с 2 и кончая числом, равным половине исходного. Но этот способ - слишком медленный.  Ускорить процедуру можно, если учесть тот факт, что если число n делится на число k, то оно делится и на n//k. Тогда можно проверить лишь числа от 2 до квадратного корня из n. Когда мы находим число k, на которое делится число n, то добавляем в список делителей два делителя: k и n//k. Один тонкий момент: если число n является точным квадратом числа k, то и k, и n//k - это одинаковые числа. Поэтому нужно ввести проверку и добавлять в список делителей n//k только в том случае, если это число не равно k. Тем самым мы избежим включе

Подсчет подмножеств, сумма элементов которых делится на 3   Хотите готовиться со мной к ЕГЭ? Пишите:  ydkras@mail.r u Немного обо мне .   Рассмотрим задачу 27 для подготовки к ЕГЭ по информатике с сайта Полякова (вариант 20): № 3822) (А. Кабанов) В файле записана последовательность натуральных чисел. Гарантируется, что все числа различны. Рассматриваются всевозможные группы чисел, состоящие из любого количества элементов последовательности. Необходимо найти количество таких групп, для которых сумма элементов кратна 3. Входные данные . Даны два входных файла (файл A и файл B ), каждый из которых содержит в первой строке количество чисел N (1 ≤ N ≤ 100000). Каждая из следующих N строк содержит одно натуральное число, не превышающее 10 8 . Пример входного файла : 4 5 7 12 23 Для указанных данных можно выбрать следующие группы: {12}; {7, 23}; {7, 12, 23}; {5, 7}; {5, 7, 12}. Программа должна вывести количество этих групп – 5. В ответе укажите два числа: сначала искомое значени