Избранные задачи ЕГЭ по информатике презентация

PascalABC.NET
Содержание
15 – математическая логика
24 – обработка символьных строк
Языки программирования
Python
Java
C++
C#

Задача 15
Математическая логика
Избранные задачи
ЕГЭ по информатике

Задача 15-1 (Демо-2022)
На числовой прямой даны два отрезка:
D = [17; 58] и C = [29; 80]. Укажите наименьшую возможную длину такого отрезка A, для которого логическое выражение
(x ∈ D) → ((¬(x ∈ C) /\ ¬(x ∈ A)) → ¬(x ∈ D))
истинно (т.е. принимает значение 1) при любом значении переменной х.
D := x ∈ D,
C := x ∈ C,
A := x ∈ A

Формулы, которые нужно знать

Задача 15-1 (Демо-2022)
D = [17; 58]
C = [29; 80]
12

Задача 15-1 (Демо-2022)
D = [17; 58]
C = [29; 80]
К.Ю. Поляков, Множества и логика в задачах ЕГЭ // Информатика, № , 2015, с. 38-42.
12

def D(x): return 17 <= x <= 58
def C(x): return 29 <= x <= 80
Amin = []
for x in range(0,100):
F = D(x) <= ((not C(x)) <= (not D(x)))
if not F: # без A ложно
Amin.append(x);
print( min(Amin), max(Amin) )
Задача 15-1 (Демо-2022) – программа
17, 28

def D(x): return 170 <= x <= 580
def C(x): return 290 <= x <= 800
Amin = []
for x in range(0, 1000 ):
F = D(x) <= ((not C(x)) <= (not D(x)))
if not F: # без A ложно
Amin.append(x);
print( min(Amin), max(Amin) )
Задача 15-1 (Демо-2022) – программа
170, 289
Шаг 0,1
170
290
1000
800
580
17, 29

##
function D(x: integer) := x in 170..580 ;
function C(x: integer) := x in 290..800 ;
var Amin := new integer[0];
foreach var x in 0..1000 do begin
var F := D(x) <= ((not C(x)) <= (not D(x)));
if not F then // без A ложно
Amin := Amin + |x|;
end;
Println( min(Amin), max(Amin) )
Задача 15-1 (Демо-2022) – PascalABC.NET
170, 289
Шаг 0,1
170..580
290..800
1000
17, 29

##
var D := 170..580;
var C := 290..800;
var allA := (0..1000).Where(
x-> not((x in D) <=
((x not in C) <= (x not in D))));
Print( allA.Min, allA.Max );
Задача 15-1 (Демо-2022) – PascalABC.NET
170, 289
Шаг 0,1
17, 29
возможные x, где А должно быть = 1
Автор: А. Богданов

def D(x): return 17 <= x <= 58
def C(x): return 29 <= x <= 80
def F(x, a, b):
return D(x) <= ((not C(x) and
not (a<=x<=b) ) <= (not D(x)))
Amin = (0, 100)
for a in range(0,100):
for b in range(a,100):
if all( F(x/10,a,b)
for x in range(0,1000) ) and \
(b - a) < (Amin[1] - Amin[0]):
Amin = (a, b)
print( Amin )
Задача 15-1 (Демо-2022) – программа
Полный перебор всех отрезков
17, 29
Автор: Е. Джобс
all( F(x/10,a,b)
for x in range(0,1000) )
шаг 0,1
A = [a; b]

##
function D(x: real) := (17 <= x) and (x <= 58);
function C(x: real) := (29 <= x) and (x <= 80);
function F(x: real; a, b: integer) :=
D(x) <= ((not C(x) and
not ((a<=x) and (x<=b))) <= (not D(x)));
var Amin := (0,100);
for var a:=0 to 100 do
for var b:=a to 100 do
if (0..1000).All( x->F(x/10,a,b) )
and ((b-a) < (Amin[1]-Amin[0])) then
Amin := (a, b);
Println( Amin )
Задача 15-1 (Демо-2022) – PascalABC.NET
Полный перебор всех отрезков
17, 29
Автор: Е. Джобс

Решение задач 15 с помощью программы
Не решайте задачи с отрезками с помощью программы!

Задача 15-2
На числовой прямой даны два отрезка:
P = [10; 20] и Q = [25; 55]. Укажите наибольшую возможную длину такого отрезка A, что выражение
(x ∈ A) → ((x ∈ P) ∨ (x ∈ Q))
истинно при любом значении переменной х.

Задача 15-2

Задача 15-3
На числовой прямой даны два отрезка:
P = [10; 20] и Q = [25; 55]. Укажите наименьшую возможную длину такого отрезка A, что выражение
((x ∈ P) ∨ (x ∈ Q)) →(x ∈ A)
истинно при любом значении переменной х.

Задача 15-4
Для какого наибольшего натурального числа a выражение
¬ДЕЛ(x, a) → (¬ ДЕЛ(x, 21) ∧ ¬ДЕЛ(x, 35))
тождественно истинно?
Если x делится на 21 или на 35, то x делится на a.
Amax = 7

def nD(x,d): return x % d != 0
for A in range(1,1000):
OK = True
for x in range(1,1000):
F = nD(x,A) <= (nD(x,21) and nD(x,35))
if not F:
OK = False
break
if OK:
print( A )
Задача 15-4 – программа
¬ДЕЛ(x, a) → (¬ ДЕЛ(x, 21) ∧ ¬ДЕЛ(x, 35))
1
7

def nD(x,d): return x % d != 0
for A in range(1,1000):
for x in range(1,1000):
if not nD(x,A) <= (nD(x,21) and nD(x,35))
break
else:
print( A )
Задача 15-4 – программа c for-else
¬ДЕЛ(x, a) → (¬ ДЕЛ(x, 21) ∧ ¬ДЕЛ(x, 35))
1
7
else:

##
function nD(x, d: integer) := x mod d <> 0;
foreach var A in 1..1000 do begin
var OK := True;
foreach var x in 1..1000 do begin
var F := nD(x,A) <= (nD(x,21) and nD(x,35));
if not F then begin
OK := False;
break
end
end;
if OK then
Println( A )
end
Задача 15-4 – PascalABC.NET
¬ДЕЛ(x, a) → (¬ ДЕЛ(x, 21) ∧ ¬ДЕЛ(x, 35))
1
7

def nD(x, d): return x % d != 0
def F(x, A):
return nD(x,A) <= (nD(x,21) and nD(x,35))
for A in range(1,1000):
if all( F(x,A) for x in range(1,1000) ):
print( A )
Задача 15-4 – кратко
¬ДЕЛ(x, a) → (¬ ДЕЛ(x, 21) ∧ ¬ДЕЛ(x, 35))
1
7
F(x,A) for x in range(1,1000)
массив логических значений

Задача 15-4 – PascalABC.NET
¬ДЕЛ(x, a) → (¬ ДЕЛ(x, 21) ∧ ¬ДЕЛ(x, 35))
function nD(x, d: integer) := x mod d <> 0;
var AA := 1..1000;
var XX := 1..1000;
AA.Where( A->XX.All(
x-> nD(x,A) <= (nD(x,21) and nD(x,35))
) ).Println;
1 7
nD(x,A) <= (nD(x,21) and nD(x,35))

Задача 15-5
(В. Шубинкин) Для какого наименьшего натурального числа А формула
((ДЕЛ(x, A) ∧ ДЕЛ(x, 36)) → ДЕЛ(x, 324)) ∧ (A > 100)
тождественно истинна?
def D(x,d): return x % d == 0
allA = [ A for A in range(101,1000)
if all(
(D(x,A) and D(x,36)) <= D(x,324)
for x in range(1, 1000 ) ) ]
print( allA )
101
10000
162

Задача 15-5 – PascalABC.NET
((ДЕЛ(x, A) ∧ ДЕЛ(x, 36)) → ДЕЛ(x, 324)) ∧ (A > 100)
function D(x, d: integer) := x mod d = 0;
var AA := 101..1000;
var XX := 1.. 10000;
AA.Where( A->XX.All(
x-> (D(x,A) and D(x,36)) <= D(x,324)
) ).First.Println;
162
10000

Задача 24
Символьные строки
Избранные задачи
ЕГЭ
по информатике

Чтение строки из файла
Классика:
F = open("24.txt")
s = F.readline()
F.close()
Модерн:
with open("24.txt") as F:
s = F.readline()
s = open("24.txt").readline()
или:
print( s[:10] ) # для проверки

Чтение строки из файла (PascalABC.NET)
Классика:
var F: Text;
var s: string;
Assign( F, '24.txt' );
Reset( F );
Readln( F, s );
Close( F );

Чтение строки из файла (PascalABC.NET)
Классика:
var s: string;
Assign( input, '24.txt' );
Readln( s );
Модерн:
var s := ReadLines( '24.txt' ).First;
s[:10].Println; // для проверки

Задача 24-1 (демо-2022)
Текстовый файл состоит из символов P, Q, R и S.
Определите максимальное количество идущих подряд символов в прилагаемом файле, среди которых нет идущих подряд символов P.

Задача 24-1 (демо-2022)
s = open("24.txt").readline()
prev, L, maxLen = "_", 0, 0
for c in s:
if c == 'P' and prev == 'P':
L = 1
else:
L += 1
maxLen = max(L, maxLen )
prev = c
print( maxLen )

Задача 24-1 (демо-2022) – PascalABC.NET
##
var s := ReadLines('24.txt').First;
var (prev, L, maxLen) := ('_', 0, 0);
foreach var c in s do begin
if (c = 'P') and (prev = 'P') then
L := 1
else begin
L += 1;
maxLen := max( L, maxLen )
end;
prev := c
end;
Print( maxLen );

Задача 24-1 (демо-2022)
s = open("24.txt").readline()
L, maxLen = 0, 0
for cur, nxt in zip(s, s[1:]) :
if cur == nxt == 'P':
L = 1
else:
L += 1
maxLen = max(L, maxLen)
print( maxLen )
Автор: Е. Джобс
zip(s, s[1:])
cur
nxt

Задача 24-1 (демо-2022) – PascalABC.NET
##
var s := ReadLines('24.txt').First;
var (L, maxLen) := (0, 0);
foreach var pair in s.Pairwise do
if (pair[0] = 'P') and (pair[1] = 'P') then
L := 1
else begin
L += 1;
maxLen := max(L, maxLen)
end;
Print( maxLen );
Автор: Е. Джобс
Пары соседних символов

Задача 24-1 (демо-2022)
s = open("24.txt").readline()
while 'PP' in s:
s = s.replace('PP', 'P P')
# PPabcPPPabcdePPPPabcdefPPPPabcdefgh
# P PabcP P PabcdeP P P PabcdefP P P Pabcdefgh
maxLen = max( len(chunk)
for chunk in s.split() )
print( maxLen )
Автор: А. Кабанов

Задача 24-1 (демо-2022) – PascalABC.NET
##
var s := ReadLines('24.txt').First;
while 'PP' in s do s := s.Replace('PP', 'P P');
var maxLen := s.Split()
.Select( chunk->Length(chunk) )
.Max;
Print( maxLen );
Автор: А. Богданов
s.Split().Max( chunk->Length(chunk) ).Print;

Задача 24-1 (демо-2022)
s = open("24.txt").readline()
maxLen = 0
while( s ):
posPP = s.find( "PP" );
if posPP < 0:
maxLen = max( len(s), maxLen )
break
chunk = s[:posPP+1]
maxLen = max( len(chunk), maxLen )
s = s[posPP+1:]
print( maxLen )
s = s[posPP+1:]
Перераспределение памяти!

Задача 24-1 (демо-2022) – PascalABC.NET
##
var s := ReadLines('24.txt').First;
var maxLen := 0;
while Length(s) > 0 do begin
var posPP := Pos( 'PP', s );
if posPP = 0 then begin
maxLen := max( Length(s), maxLen );
break
end;
var chunk := s[:posPP+1];
maxLen := max( Length(chunk), maxLen );
s := s[posPP+1:];
end;
Print( maxLen );
s := s[posPP+1:];

Задача 24-2 (Статград)
Текстовый файл содержит только заглавные буквы латинского алфавита (ABC…Z). Определите максимальное количество идущих подряд символов, среди которых нет ни одной буквы A и при этом не менее трёх букв E.

Задача 24-2 (Статград)
s = open("24.txt").readline()
L = maxLen = countE = 0
for c in s:
if c != 'A':
L += 1
if c == 'E':
countE += 1
if countE >= 3 and L > maxLen:
maxLen = L
else:
L = countE = 0
print( maxLen )
Автор: А Богданов (www.youtube.com/watch?v=fHfUY9XerWE)

Задача 24-2 (Статград) – PascalABC.NET
##
var s := ReadLines('24.txt').First;
var (L, maxLen, countE) := (0, 0, 0);
foreach var c in s do begin
if c <> 'A' then begin
L += 1;
if c = 'E' then
countE += 1;
if (countE >= 3) and (L > maxLen) then
maxLen := L;
end else
(L, countE) := (0, 0)
end;
Print( maxLen );

Задача 24-2 (Статград)
s = open("24.txt").readline()
maxLen = 0
for chunk in s.split('A'):
if chunk.count('E') >= 3:
maxLen = max( len(chunk), maxLen )
print( maxLen )

Задача 24-2 (Статград)
s = open("24.txt").readline()
chunks = s.split('A')
allLen = [ len(c) for c in chunks
if c.count('E') >= 3 ]
maxLen = max( allLen )
print( maxLen )

Задача 24-2 (Статград)
s = open("24.txt").readline()
print( max(
len(chunk) for chunk in s.split('A')
if chunk.count('E') >= 3 ) )
##
ReadLines('24.txt').First
.Split('A')
.Where( c-> c.CountOf('E') >= 3 )
.Max( c-> Length(c) ).Print;
PascalABC.NET

Задача 24-3 (А. Комков)
Текстовый файл состоит не более чем из 106 заглавных латинских букв E, G, K. Определите максимальное количество идущих подряд символов, среди которых сочетания символов KEGE повторяются не более двух раз.
...KEGE......KEGE.......KEGE.....KEGE

Задача 24-3 (А. Комков)
s = open("24.txt").readline()
stopPoints = [0, 0, 0]
maxLen = 0
for i in range(3,len(s)):
if s[i-3:i+1] == "KEGE":
stopPoints.append( i-2 )
maxLen = max( i - stopPoints[-3] + 1,
maxLen )
print( maxLen )

Задача 24-3 (А. Комков) – PascalABC.NET
##
var s := ReadLines('24-175.txt').First;
var (stopPoints, maxlen) := (|0, 0, 0|, 0);
for var i:=4 to Length(s) do begin
if s[i-3:i+1] = 'KEGE' then
stopPoints := stopPoints + | i-2 |;
maxLen := max( i - stopPoints[^3] + 1,
maxLen );
end;
Print( maxLen );

Задача 24-3 (А. Комков)
...KEGE......KEGE.......KEGE.....KEGE..
p = s.split("KEGE")
maxLen = 0
for i in range(len(p)-2):
chunk = p[i] + "KEGE" + p[i+1] + \
"KEGE" + p[i+2];
if i != 0: chunk = "EGE" + chunk
if i+2 != len(p)-1: chunk = chunk + "KEG"
maxLen = max( len(chunk), maxLen )
print( maxLen )
Автор: А. Кабанов

Задача 24-3 (А. Комков) – PascalABC.NET
##
var s := ReadLines('24-175.txt').First
.Replace('KEGE', '#');
var maxLen := 0;
var p := s.Split('#');
for var i:=0 to p.Length-3 do begin
var chunk := p[i] + 'KEGE' + p[i+1] +
'KEGE' + p[i+2];
if i <> 0 then chunk := 'EGE' + chunk;
if i+2 <> p.Length-1 then chunk += 'KEG';
maxLen := max( Length(chunk), maxLen );
end;
Print( maxLen );
Автор: А. Кабанов

Задача 24-3 (А. Комков) – PascalABC.NET
##
var s := ReadLines('24-175.txt').First
.Replace('KEGE', '#');
var allLen := s.Split('#')
.Select(s->s.Length).ToArray;
allLen[0] -= 3; allLen[^1] -= 3;
allLen.NWise(3) // все соседние тройки
.Max( v -> v.Sum+2*4+2*3 ).Print
Автор: А. Богданов
2 "KEGE"
"EGE" "KEG"

Задача 24-4
Текстовый файл содержит строку из заглавных латинских букв и точек, всего не более чем из 106 символов. Определите максимальное количество идущих подряд символов, среди которых нет точек, а количество гласных (букв A, E, I, O, U, Y) не превышает 3.
BCDAR.BCABCDEBCDFIBCDFGOBCDFGHUBCDFGH

Задача 24-4
s = open("24.txt").readline()
K = 3 # сколько гласных разрешается
stopPoints = [-1]*(K+1)
maxLen = 0
for i in range(len(s)):
if s[i] == '.':
stopPoints = [i]*(K+1)
if s[i] in "AEIOUY":
stopPoints.insert( 0, i )
maxLen = max( i - stopPoints[K], maxLen )
print( maxLen )

Задача 24-4 – PascalABC.NET
##
var s := ReadLines('24-181.txt').First;
var K := 3; // сколько гласных разрешается
var stopPoints := |-1|*(K+1);
var maxLen := 0;
for var i:=1 to Length(s) do begin
if s[i] = '.' then
stopPoints := |i|*(K+1);
if s[i] in 'AEIOUY' then
stopPoints := |i| + stopPoints;
maxLen := max( i - stopPoints[K], maxLen )
end;
Print( maxLen );

Задача 24-4
s = open("24.txt").readline()
K = 3 # сколько гласных разрешается
stopPoints = [-1]
maxLen = 0
for i in range(len(s)):
if s[i] == '.':
stopPoints = [i]
if s[i] in "AEIOUY":
if len(stopPoints) > K:
stopPoints.pop(0)
stopPoints.append( i )
maxLen = max( i - stopPoints[0], maxLen )
print( maxLen )
Автор: А. Егоров
убираем лишнюю точку
активная
точка - первая

Задача 24-4 – PascalABC.NET
##
var s := ReadLines('24.txt').First;
var K := 3; // сколько гласных разрешается
var stopPoints := |-1|;
var maxLen := 0;
for var i:=1 to Length(s) do begin
if s[i] = '.' then
stopPoints := |i|;
if s[i] in 'AEIOUY' then begin
if Length(stopPoints) > K then
stopPoints := stopPoints[1:];
stopPoints := stopPoints + |i|
end;
maxLen := max( i - stopPoints[0], maxLen )
end;
Print( maxLen );
Автор: А. Егоров

Задача 24-4
s = open("24.txt").readline()
K = 3 # сколько гласных разрешается
for c in 'AEIOUY': s = s.replace( c, '*' )
maxLen = 0
for chunk in s.split('.'):
if chunk.count('*') <= K:
maxLen = max( len(chunk), maxLen )
else:
p = chunk.split('*')
for i in range(len(p)-K-1):
L = sum(len(p[k])
for k in range(i,i+K+1)) + K
maxLen = max( L, maxLen )
print( maxLen )
Автор: А. Кабанов
K гласных

Задача 24-4 – PascalABC.NET
##
var s := ReadLines('24.txt').First;
var K := 3; // сколько гласных разрешается
foreach var c in 'AEIOUY' do
s := s.Replace( c, '*' );
var maxLen := 0;
foreach var chunk in s.Split('.') do begin
if chunk.CountOf('*') <= K then
maxLen := max( Length(chunk), maxLen )
else begin
var p := chunk.Split('*');
for var i:=0 to Length(p)-K-1 do begin
var L := p[i:i+K+1].Select(x->Length(x)).Sum + K;
maxLen := max( L, maxLen )
end
end
end;
Print( maxLen );
Автор: А. Кабанов

Задача 24-5
Текстовый файл состоит не более чем из 106 заглавных латинских букв (A..Z). Текст разбит на строки различной длины. Необходимо найти строку, содержащую наименьшее количество букв A (если таких строк несколько, надо взять ту, которая в файле встретилась раньше). Определите, какая буква встречается в этой строке чаще всего. Если таких букв несколько, надо взять ту, которая стоит последней в алфавите. Запишите в ответе эту букву, а
затем – сколько раз она встречается во всем файле.

Перебор строк из файла
Классика:
F = open("24.txt")
while True:
s = F.readline()
if not s: break
# обработать s
F.close()
Модерн:
for s in open("24.txt"):
# обработать s

Перебор строк из файла (PascalABC.NET)
Классика:
var F: Text;
var s: string;
Assign( F, '24.txt' );
Reset( F );
while not Eof(F) do begin
Readln( F, s );
// обработать s
end;
Close( F );

Перебор строк из файла (PascalABC.NET)
Классика:
var s: string;
Assign( input, '24.txt' );
while not Eof do begin
Readln( s );
// обработать s
end;
Модерн:
foreach var s in ReadLines('24.txt') do
// обработать s

Задача 24-5
sMinA, fullText = "", ""
for s in open("24.txt"):
if not sMinA or \
s.count('A') < sMinA.count('A'):
sMinA = s
fullText += s
...
берём первую по порядку
собираем весь текст

Задача 24-5
from string import ascii_uppercase
mostFreq = None
for c in ascii_uppercase:
freq = sMinA.count(c) if not mostFreq or freq >= mostFreq[1]:
mostFreq = (c, freq)
print( mostFreq[0],
fullText.count(mostFreq[0]) )
последняя
по алфавиту

Задача 24-5 – PascalABC.NET
##
var allLines := ReadAllLines('24.txt');
var sMinA := allLines.MinBy( s -> s.CountOf('A') );
var letCount :=
('A'..'Z').Select( c-> (c, sMinA.CountOf(c)) );
var maxCount :=
letCount.MaxBy( \(c,count)->count )[1];
var letter :=
letCount.Where( \(c,count)-> count = maxCount )
.Select( \(c,count)-> c ).Last;
var count := allLines.Select( s->s.CountOf(letter) )
.Sum;
Print( letter, count );

Это интересно
Алексей Богданов (Alex Danov)
https://www.youtube.com/AlexDanov
https://vk.com/inf_intensive
Алексей Кабанов
https://www.youtube.com/user/axelofan2010
https://vk.com/ege_info_open
Евгений Джобс
https://www.youtube.com/EvgenijJobs
https://vk.com/inform_web