Структуры данных в Python и их применение в КЕГЭ

1.

К.Ю. Поляков
Структуры данных в
Python и их применение
для решении задач ЕГЭ
Задачи 5, 8, 15, 19-21, 22, 24, 26
К.Ю. Поляков, 2024
http://kpolyakov.spb.ru

2.

Структуры данных в Python и их применение для решении задач ЕГЭ
2
Структуры данных в Python
1)
2)
3)
4)
5)
6)
7)
строки (str)
списки (list)
кортежи (tuple)
словари (dict)
множества (set)
классы (class)
абстрактные типы данных (стек, очередь)
К.Ю. Поляков, 2024
http://kpolyakov.spb.ru

3.

Структуры данных в
Python и их применение
для решении задач ЕГЭ
Операции со списками
К.Ю. Поляков, 2024
http://kpolyakov.spb.ru

4.

Структуры данных в Python и их применение для решении задач ЕГЭ
4
Генератор списков
• создать новый список
A = [ x for x in range(100) ]
from random import randint
A = [ randint(10,100)
for x in range(100) ]
• с фильтрацией
A = [ x for x in range(100)
if x % 7 == 0 ]
К.Ю. Поляков, 2024
http://kpolyakov.spb.ru

5.

Структуры данных в Python и их применение для решении задач ЕГЭ
5
Генератор списков
• преобразовать элементы списка (map)
A = [ x*x for x in A ]
• построить список из элементов другого списка,
удовлетворяющих условию (filter)
B = [ x for x in A if x % 2 == 0 ]
• совмещение (map + filter)
B = [ x*x for x in A
if x % 2 == 0 ]
К.Ю. Поляков, 2024
http://kpolyakov.spb.ru

6.

Структуры данных в Python и их применение для решении задач ЕГЭ
6
all, any
• all – истинно для всех
if all( x > 0 for x in A ):
print( "Все > 0" )
• any – истинно хотя бы для одного
if any( x > 0 for x in A ):
print( "Есть какой-то > 0" )
К.Ю. Поляков, 2024
http://kpolyakov.spb.ru

7.

Структуры данных в
Python и их применение
для решении задач ЕГЭ
Словари
К.Ю. Поляков, 2024
http://kpolyakov.spb.ru

8.

Структуры данных в Python и их применение для решении задач ЕГЭ
8
Словари
Словарь – это (неупорядоченный) набор элементов, в
котором выполняется по ключу.
PascalABC.NET: Dictionary<Key, Value>
С++ (STL): map<string, int>
PHP: ассоциативные массивы
Perl, Ruby: «хэши»
JavaScript: объекты
Создание:
D = {}
# пустой словарь
D = { "бегемот": 0, "пароход": 2 }
К.Ю. Поляков, 2024
http://kpolyakov.spb.ru

9.

Структуры данных в Python и их применение для решении задач ЕГЭ
9
Генераторы словарей
data = [ ('дом', 32), ('кот', 15),
('сом', 2) ]
D = { k: v for k, v in data }
dict(data)
print( D )
{'дом': 32, 'кот': 15, 'сом': 2}
С преобразованием:
D = { k.upper(): 22*v for k, v in data
if v > 5 }
print( D )
{'ДОМ': 64, 'КОТ': 30}
К.Ю. Поляков, 2024
http://kpolyakov.spb.ru

10.

Структуры данных в Python и их применение для решении задач ЕГЭ
10
Генераторы словарей
{ 'A': 'BC', 'B': 'C',
'C': 'D', 'D': 'B' }
B
A
D
C
s = "ABC BC CD DB"
G = { p[0]: p[1:]
for p in s.split() }
print( G )
К.Ю. Поляков, 2024
http://kpolyakov.spb.ru

11.

Структуры данных в Python и их применение для решении задач ЕГЭ
11
Работа со словарями в Python
Добавление (изменение) элемента:
D["самолёт"] = 1
!
Создаётся новый элемент!
D["самолёт"] += 1
!
ошибка, если
ключа нет
Нужно проверить, есть ли элемент!
К.Ю. Поляков, 2024
http://kpolyakov.spb.ru

12.

Структуры данных в Python и их применение для решении задач ЕГЭ
12
Работа со словарями в Python
Изменение с проверкой:
if "самолёт" in D:
D["самолёт"] += 1
else:
D["самолёт"] = 1
или так:
D["самолёт"] = D.get ( "самолёт", 0 ) + 1
получить
значение по ключу
значение по
умолчанию (если
ключа нет)
Удаление элемента:
del D["самолёт"]
К.Ю. Поляков, 2024
http://kpolyakov.spb.ru

13.

Структуры данных в Python и их применение для решении задач ЕГЭ
13
Вывод результата
Получить всех ключи:
allKeys = D.keys()
отсортировать ключи:
sortKeys = sorted( D.keys() )
или так:
sortKeys = sorted( D )
Вывод результата:
F = open ( "output.txt", "w" )
for k in sorted( D ):
F.write ( f"{k}: {D[k]}\n" )
F.close()
пароход: 12
самолёт: 20
К.Ю. Поляков, 2024
http://kpolyakov.spb.ru

14.

Структуры данных в Python и их применение для решении задач ЕГЭ
14
Ещё о словарях
Перебор значений:
for i in D.values():
print ( i )
Перебор ключей и значений:
for k, v in D.items():
print ( k, "->", v )
список пар
(ключ, значение)
К.Ю. Поляков, 2024
http://kpolyakov.spb.ru

15.

Структуры данных в Python и их применение для решении задач ЕГЭ
15
Словарь и список пар
Список пар «ключ-значение»:
A = list(D.items())
список пар
(ключ, значение)
D = {"бам": 2, "там": 3}
A[0] кортеж A[1]
A =[("бам", 2), ("там", 3)]
A[0][0]
К.Ю. Поляков, 2024
A[0][1]
http://kpolyakov.spb.ru

16.

Структуры данных в Python и их применение для решении задач ЕГЭ
16
Словарь и список пар
Сортировка:
A.sort()
по ключам, если ключи
равны – по значениям
A.sort( key = lambda x: x[0])
по ключам
по значениям
A.sort( key = lambda x: x[1])
A.sort( key = lambda x: (x[1], x[0]))
по значениям, если они
равны – по ключам
A.sort( key = lambda x: (-x[1], x[0]))
К.Ю. Поляков, 2024
http://kpolyakov.spb.ru

17.

Структуры данных в Python и их применение для решении задач ЕГЭ
17
Словарь и список пар
Вывод списка пар
for x in A:
print( f"{x[0]}: {x[1]}" )
или так
for key, value in A:
print( f"{key}: {value}" )
К.Ю. Поляков, 2024
http://kpolyakov.spb.ru

18.

Структуры данных в
Python и их применение
для решении задач ЕГЭ
Кортежи
К.Ю. Поляков, 2024
http://kpolyakov.spb.ru

19.

Структуры данных в Python и их применение для решении задач ЕГЭ
19
Кортеж (tuple) – неизменяемый список
Создание:
T = (1, ) # из одного элемента
T = (1, "123")
T = (1, [2, "qwerty", 4] ) # ???
!
Адрес списка не изменяется!
T[0] = 12
# нельзя изменять
TypeError: 'tuple' object does not support item assignment
К.Ю. Поляков, 2024
http://kpolyakov.spb.ru

20.

Структуры данных в Python и их применение для решении задач ЕГЭ
20
Кортеж (tuple) – что хорошего?
время выполнения операций меньше примерно на
10% в сравнении со списками
может быть ключом в словаре (хэширование)
D = {}
D[(1,2)] = "1"
D[[1,2]] = "2"
TypeError: unhashable type: 'list'
К.Ю. Поляков, 2024
http://kpolyakov.spb.ru

21.

Структуры данных в Python и их применение для решении задач ЕГЭ
21
Кортеж (tuple) – что хорошего?
можно использовать для кэширования результатов
функции
from functools import cache
@cache
def F( d ):
Кортежи!
x, y = d
if x < 1: return 0
return F( (x-1,
(x-1, y)
y) ) + F( (x-1, y-1) )
!
print( F( (100,
(100, 100)
100) ) )
[x-1, y]
[x-1, y-1]
[100, 100]
TypeError: unhashable type: 'list'
К.Ю. Поляков, 2024
http://kpolyakov.spb.ru

22.

Структуры данных в
Python и их применение
для решении задач ЕГЭ
Множества
К.Ю. Поляков, 2024
http://kpolyakov.spb.ru

23.

Структуры данных в Python и их применение для решении задач ЕГЭ
23
Операции с множествами
Создание множества:
S = set()
S = {1, 2, "qwerty"}
Перебор элементов множества:
qwerty
for x in S:
В другом
print( x )
1
порядке
2
К.Ю. Поляков, 2024
http://kpolyakov.spb.ru

24.

Структуры данных в Python и их применение для решении задач ЕГЭ
24
Операции с множествами
Добавление элемента множества:
S.add( "cat" )
S.add( (5, 12) )
S.add( [5, 12] )
изменяемые
типы нельзя
Добавление множества к множеству:
S = { 1, 2, "qwerty" }
Q = { 4, "25", 15 }
print( id(S) )
# 825682851008
S = S | Q
# новый объект
print( id(S) )
# 825682851680
S |= Q
# расширение существующего
print( id(S) )
# 825682851680
К.Ю. Поляков, 2024
http://kpolyakov.spb.ru

25.

Структуры данных в Python и их применение для решении задач ЕГЭ
25
Операции с множествами
Удаление элементов множества:
S.remove( 1 )
S = S – {1, 7}
S -= {1, 7}
Удаление несуществующего элемента:
S = { 1, 2, "qwerty" }
S = S – {45}
S -= {45}
S.remove( 45 )
KeyError: 45
К.Ю. Поляков, 2024
http://kpolyakov.spb.ru

26.

Структуры данных в
Python и их применение
для решении задач ЕГЭ
Объекты-генераторы
К.Ю. Поляков, 2024
http://kpolyakov.spb.ru

27.

Структуры данных в Python и их применение для решении задач ЕГЭ
27
product
Декартово произведение: «каждый с каждым»
from itertools import product
for w in product( A, B ):
print( w )
(1,
(1,
(2,
(2,
(3,
(3,
for w in product(B, repeat=2 ):
print( w )
# print( ''.join(w) )
# -> ["AA", "AB", "BA", "BB"]
('A',
('A',
('B',
('B',
A = [1, 2, 3]
B = ['A','B']
К.Ю. Поляков, 2024
'A')
'B')
'A')
'B')
'A')
'B')
'A')
'B')
'A')
'B')
http://kpolyakov.spb.ru

28.

Структуры данных в Python и их применение для решении задач ЕГЭ
28
product – объект-генератор
from itertools import product
A = [1, 2, 3]
B = ['A','B']
P = product(A, B)
print( P )
(1, 'A')
(1, 'B')
'A')
<itertools.product (2,
object
at 0x33EF7C0>
(2, 'B')
for w in P:
(3, 'A')
print( w )
(3, 'B')
for w in P:
пусто
print( w )
К.Ю. Поляков, 2024
http://kpolyakov.spb.ru

29.

Структуры данных в Python и их применение для решении задач ЕГЭ
29
permutations – перестановки
from itertools import permutations
A = [1, 2, 3]
for w in permutations( A ):
print( w, end=" " )
(1, 2, 3) (1, 3, 2) (2, 1, 3) ...
B = "AB"
for w in permutations( B ):
print( w )
# print( ''.join(w) )
# -> ["AB", "BA"]
К.Ю. Поляков, 2024
('A', 'B')
('B', 'A')
http://kpolyakov.spb.ru

30.

Структуры данных в Python и их применение для решении задач ЕГЭ
30
zip
Соединение двух списков в пары:
A = [1, 2, 3, 4, 5]
B = ['A','B','C','D','E']
1,2,3,4,5
zip
(1,A),(2,B),(3,C)...
A,B,C,D,E
for p in zip(A, B):
print( p, end=" " )
(1, 'A') (2, 'B') (3, 'C') (4, 'D')
(5, 'E')
К.Ю. Поляков, 2024
http://kpolyakov.spb.ru

31.

Структуры данных в Python и их применение для решении задач ЕГЭ
31
zip
Соединение двух списков в пары:
A = [1, 2, 3, 4, 5]
B = ['A','B','C','D','E']
for a,
a, bb in zip(A, B):
print( a, b )
1
2
3
4
5
A
B
C
D
E
К.Ю. Поляков, 2024
http://kpolyakov.spb.ru

32.

Структуры данных в Python и их применение для решении задач ЕГЭ
32
zip
Все пары соседних элементов списка:
A = [1, 2, 3, 4, 5]
for a, b in zip(A, A[1:]):
print( a, b )
1,2,3,4,5
1
2
3
4
2
3
4
5
(1,2),(2,3),(3,4)...
2,3,4,5
s = "12345"
for a, b in zip(s, s[1:]):
print( a, b )
"2345"
К.Ю. Поляков, 2024
1
2
3
4
2
3
4
5
http://kpolyakov.spb.ru

33.

Структуры данных в Python и их применение для решении задач ЕГЭ
33
zip
Генераторы словарей:
keys = ["дом", "кот", "сом"]
values = [32, 15, 2]
D = { k.upper(): 2*v
zip(keys, values)
values)
for k, v in zip(keys,
if v > 5 }
print( D )
{'ДОМ': 64, 'КОТ': 30}
К.Ю. Поляков, 2024
http://kpolyakov.spb.ru

34.

Структуры данных в Python и их применение для решении задач ЕГЭ
34
zip
Передача аргументов функции:
def F( a, b, c ):
return a + b*c
names = ['c', 'b', 'a']
values = [3, 2, 1]
D = dict( zip(names, values) )
res = F( **D )
print( res )
7
К.Ю. Поляков, 2024
http://kpolyakov.spb.ru

35.

Структуры данных в
Python и их применение
для решении задач ЕГЭ
Задача 8.
Объекты-генераторы
К.Ю. Поляков, 2024
http://kpolyakov.spb.ru

36.

Структуры данных в Python и их применение для решении задач ЕГЭ
36
Использование product
Петя строит все возможные пятибуквенные слова из букв
В, Е, Н, О, К. Сколько он может построить слов, в которых
буква Н встречается ровно два раза?
from itertools import product
count = 0
for w in product('ВЕНОК',
product('ВЕНОК', repeat=5)
repeat=5) :
if w.count('Н') == 2:
длина слов
count += 1
print( count )
К.Ю. Поляков, 2024
http://kpolyakov.spb.ru

37.

Структуры данных в Python и их применение для решении задач ЕГЭ
37
Без счётчика
Петя строит все возможные пятибуквенные слова из букв
В, Е, Н, О, К. Сколько он может построить слов, в которых
буква Н встречается ровно два раза?
from itertools import product
good = [ w
for w in product('ВЕНОК', repeat=5)
if w.count('Н') == 2 ]
print( len(good) )
К.Ю. Поляков, 2024
генератор
списка
http://kpolyakov.spb.ru

38.

Структуры данных в Python и их применение для решении задач ЕГЭ
38
Без счётчика
Петя строит все возможные пятибуквенные слова из букв
В, Е, Н, О, К. Сколько он может построить слов, в которых
буква Н встречается ровно два раза?
генераторное
from itertools import product
выражение
print( sum( 1
for w in product('ВЕНОК', repeat=5)
if w.count('Н') == 2 ) )
from itertools import product
print( sum( w.count('Н') == 2
for w in product('ВЕНОК', repeat=5) ) )
К.Ю. Поляков, 2024
http://kpolyakov.spb.ru

39.

Структуры данных в Python и их применение для решении задач ЕГЭ
39
Использование product
Петя строит все возможные пятибуквенные слова из букв
В, Е, Н, О, К. Сколько он может построить слов, в которых
встречается сочетание букв «НК»?
Важно: нужно проверить сочетание символов
from itertools import product
count = 0
for w in product('ВЕНОК', repeat=5):
s = ''.join(w)
if 'НК' in s:
count += 1
print( count )
К.Ю. Поляков, 2024
http://kpolyakov.spb.ru

40.

Структуры данных в Python и их применение для решении задач ЕГЭ
40
Использование permutations
Маша составляет 5-буквенные коды из букв
В, У, А, Л, Ь. Каждую букву нужно использовать ровно 1
раз, при этом буква Ь не может стоять на первом месте и
перед A. Сколько различных кодов может составить
Маша?
from itertools import permutations
count = 0
for w in permutations('ВУАЛЬ') :
s = ''.join(w)
if s[0] != 'Ь' and 'ЬА' not in s:
count += 1
print( count )
К.Ю. Поляков, 2024
http://kpolyakov.spb.ru

41.

Структуры данных в Python и их применение для решении задач ЕГЭ
41
Использование zip
Артур составляет пятизначные числа. При этом он
считает подходящими только числа, в которых никакие
две чётные и никакие две нечётные цифры не стоят
рядом. Сколько различных подходящих чисел может
составить Артур?
def valid( w ):
if w[0] == '0': return False
zip(w, w[1:])
w[1:]) :
for a, b in zip(w,
if int(a) % 2 == int(b) % 2:
return False
return True
К.Ю. Поляков, 2024
http://kpolyakov.spb.ru

42.

Новые возможности
PascalABC.NET и Python
при решении задач ЕГЭ
Задачи 19-21
Теория игр. Использование
функций all и any
К.Ю. Поляков, 2024
http://kpolyakov.spb.ru

43.

Структуры данных в Python и их применение для решении задач ЕГЭ
43
19-21. Демо-2024
За один ход игрок может добавить в кучу один
камень или увеличить количество камней
в куче в два раза. Игра завершается в тот
момент, когда количество камней в куче
становится не менее 129. Победителем
считается игрок, первым получивший кучу из 129
или больше камней.
В начальный момент в куче было S камней,
1 ≤ S ≤ 128.
Укажите минимальное значение S, при котором
Петя не может выиграть за один ход, но при
любом ходе Пети Ваня может выиграть своим
первым ходом.
К.Ю. Поляков, 2024
http://kpolyakov.spb.ru

44.

Структуры данных в Python и их применение для решении задач ЕГЭ
44
19-21. Вспомогательные функции
def gameOver( pos ):
return pos >= 129
def moves( pos ):
return pos+1, 2*pos
Идея: написать остальные функции так, чтобы их
не нужно было изменять при изменении условия
задачи.
К.Ю. Поляков, 2024
http://kpolyakov.spb.ru

45.

Структуры данных в Python и их применение для решении задач ЕГЭ
45
19-21. Выигрыш за один ход
Выигрыш за один ход:
1) игра ещё не окончена и …
2) есть хотя бы один ход в позицию «игра
окончена»
def win1( pos ):
if gameOver(pos):
return False
for move in moves(pos):
if gameOver(move):
return True
return False
К.Ю. Поляков, 2024
некрасиво,
многословно
http://kpolyakov.spb.ru

46.

Структуры данных в Python и их применение для решении задач ЕГЭ
46
19-21. Выигрыш за один ход
def win1( pos ):
return not gameOver(pos) and \
any( gameOver(move)
for move in moves(pos) )
for S in range(129):
if win1(S): print(S)
К.Ю. Поляков, 2024
http://kpolyakov.spb.ru

47.

Структуры данных в Python и их применение для решении задач ЕГЭ
47
19-21. Проигрыш за один ход
Проигрыш за один ход: все ходы ведут в позиции
«выигрыш за один ход».
def lose1( pos ):
return all( win1(move)
for move in moves(pos) )
for S in range(129):
if lose1(S): print(S)
К.Ю. Поляков, 2024
http://kpolyakov.spb.ru

48.

Структуры данных в Python и их применение для решении задач ЕГЭ
48
19-21. Выигрыш за два хода
Выигрыш за два хода: хотя бы один ход ведёт в
позицию «проигрыш за один ход».
В реальных задачах ЕГЭ
всегда выполняется
def win2( pos ):
return not win1(pos) and \
any( lose1(move) for move in moves(pos) )
for S in range(129):
if win2(S): print(S)
К.Ю. Поляков, 2024
http://kpolyakov.spb.ru

49.

Структуры данных в Python и их применение для решении задач ЕГЭ
49
19-21. Проигрыш за два хода
Проигрыш за два хода:
1) все ходы ведут в позиции «выигрыш за один
ход» или «выигрыш за два хода»;
2) хотя бы один ход ведёт в позицию «выигрыш за
два хода».
def lose2( pos ):
return all( win1(move) or win2(move)
for move in moves(pos) ) and \
any( win2(move) for move in moves(pos) )
for S in range(129):
if lose2(S): print(S)
К.Ю. Поляков, 2024
http://kpolyakov.spb.ru

50.

Структуры данных в Python и их применение для решении задач ЕГЭ
50
19-21. (Демо-2021) Две кучи камней
За один ход игрок может добавить в одну из куч
один камень или увеличить количество
камней в куче в два раза. Игра завершается в
тот момент, когда количество камней в двух кучах
становится не менее 77. Победителем считается
игрок, первым получивший кучу из 77 или больше
камней. В начальный момент в первой куче было
7 камней, во второй – S камней, 1 ≤ S ≤ 69.
Укажите минимальное значение S, при котором
Петя не может выиграть за один ход, но при
любом ходе Пети Ваня может выиграть своим
первым ходом.
К.Ю. Поляков, 2024
http://kpolyakov.spb.ru

51.

Структуры данных в Python и их применение для решении задач ЕГЭ
51
19-21. Вспомогательные функции
pos – кортеж (x,y)
первая
куча
вторая
куча
def gameOver( pos ):
return sum(pos) >= 77
def moves( pos ):
x, y = pos
return (x+1,y), (2*x,y), (x,y+1), (x,2*y)
Не изменяются:
win1 lose1
К.Ю. Поляков, 2024
win2
lose2
http://kpolyakov.spb.ru

52.

Структуры данных в Python и их применение для решении задач ЕГЭ
52
19-21. (Демо-2021) Две кучи камней
# Выигрыш Вани за 1 ход
for S in range(70):
if lose1( (7,S) ): print( S )
# Выигрыш Пети за 2 хода
for S in range(70):
if win2( (7,S) ): print( S )
# Выигрыш Вани за 2 хода
for S in range(70):
if lose2( (7,S) ): print( S )
К.Ю. Поляков, 2024
http://kpolyakov.spb.ru

53.

Новые возможности
PascalABC.NET и Python
при решении задач ЕГЭ
Задача 22
Выполнение процессов.
Словари
К.Ю. Поляков, 2024
http://kpolyakov.spb.ru

54.

Структуры данных в Python и их применение для решении задач ЕГЭ
54
22. Процессы (демо-2023)
ID процесса
1
2
3
4
Время выполнения ID процесса(ов), от
(мс)
которых он зависит
4
0
3
0
1
1; 2
7
3
Определите, через какое время завершится вся
группа процессов.
?
К.Ю. Поляков, 2024
Демо-2024?
http://kpolyakov.spb.ru

55.

Структуры данных в Python и их применение для решении задач ЕГЭ
55
22. Процессы: Сохранить как CSV
Текст
!
Удалить заголовок!
ID процесса B;Время выполнения …
1;4;0;
зависимости (в
2;3;0;
одной ячейке)
3;1;"1; 2";
4;7;3;
5;6;3;
...
1) удалить кавычки
2) заменить «;» на пробелы
К.Ю. Поляков, 2024
http://kpolyakov.spb.ru

56.

Структуры данных в Python и их применение для решении задач ЕГЭ
56
22. Процессы: «наивное» решение
!
Допущение: процесс зависит только от
предыдущих (топологическая сортировка)!
Можно обрабатывать последовательно!
К.Ю. Поляков, 2024
http://kpolyakov.spb.ru

57.

Структуры данных в Python и их применение для решении задач ЕГЭ
57
22. «Наивное» решение
with open("22-0.csv") as F:
F.readline() # пропуск заголовка
finalTime = {0: 0} # фиктивный процесс
for s in F:
s = s.strip().replace('"', '') \
.replace(';', ' ')
pid, t, *dependsOn = map(int, s.split())
finalTime[pid] = t +
max( finalTime[p] for p in dependsOn )
print( max(finalTime.values()) )
К.Ю. Поляков, 2024
http://kpolyakov.spb.ru

58.

Структуры данных в Python и их применение для решении задач ЕГЭ
58
22. Процессы: чтение данных
!
Отдельно сохраняем данные процессов,
которые не закончились!
with open("22-0.csv") as F:
data = {} # данные
finalTime = {0: 0} # время завершения процесса
for s in F:
s = s.strip().replace('"', '') \
.replace(';', ' ')
pid, t, *dependsOn = map( int, s.split() )
data[pid] = ( t, dependsOn )
длительность
К.Ю. Поляков, 2024
зависимости
http://kpolyakov.spb.ru

59.

Структуры данных в Python и их применение для решении задач ЕГЭ
59
22. Процессы: решение
!
Допущение: решение есть!
словарь
while data:
изменяется в
for id in list(data.keys()):
цикле
t, dependsOn = data[id]
if all((x in finalTime) for x in dependsOn):
finalTime[id] = t +
max( finalTime[x] for x in dependsOn )
del data[id]
print( max(finalTime.values()) )
К.Ю. Поляков, 2024
http://kpolyakov.spb.ru

60.

Структуры данных в Python и их применение для решении задач ЕГЭ
60
22. Рекурсивное решение
!
Допущение: решение есть!
def findFinalTime( pid ):
if pid not in finalTime:
t, dependsOn = data[pid]
рекурсивный
finalTime[pid] = t + \
вызов
max( findFinalTime(p)
for p in dependsOn)
return finalTime[pid]
print( max( findFinalTime(pid)
for pid in data) )
К.Ю. Поляков, 2024
http://kpolyakov.spb.ru

61.

Структуры данных в
Python и их применение
для решении задач ЕГЭ
Задачи 5, 8.
Перебор вариантов.
Множества
К.Ю. Поляков, 2024
http://kpolyakov.spb.ru

62.

Структуры данных в Python и их применение для решении задач ЕГЭ
62
Где полезны множества?
Удаление дублей
(А.Н. Носкин) Петя составляет семибуквенные
слова перестановкой букв слова АССАСИН.
Сколько различных слов может составить Петя?
одинаковые буквы в
? В чём подвох?
слове при «тупом»
переборе дадут
дубли
from itertools import permutations
print( len(
set ( permutations('АССАСИН') ) ) )
set
К.Ю. Поляков, 2024
http://kpolyakov.spb.ru

63.

Структуры данных в Python и их применение для решении задач ЕГЭ
63
Где полезны множества?
Проверка «все символы различны»
№ 8. (Демо-2024) Сколько существует
восьмеричных пятизначных чисел, … в которых
все цифры различны и … ?
def valid( w ):
if len(w) != len( set (w)):
return False
# другие проверки
...
К.Ю. Поляков, 2024
http://kpolyakov.spb.ru

64.

Структуры данных в Python и их применение для решении задач ЕГЭ
64
Где полезны множества?
Проверка «все числа различны»
№ 9. В каждой строке файла записаны 5
натуральных чисел. Определите количество
строк таблицы, для которых:
– все числа в строке различны;
–…
def valid( arr ):
if len(arr) != len( set (arr)):
return False
# другие проверки
...
К.Ю. Поляков, 2024
http://kpolyakov.spb.ru

65.

Структуры данных в Python и их применение для решении задач ЕГЭ
65
Где полезны множества?
Подсчёт уникальных значений
№ 5. Алгоритм: … Определите, сколько
различных чисел R может быть получено в
результате работы алгоритма для N на отрезке
[10; 1000]?
def alg( N ):
return ...
res = set
set()
for N in range(10,1000+1):
res.add( alg(N) )
print( len(res) )
К.Ю. Поляков, 2024
http://kpolyakov.spb.ru

66.

Структуры данных в
Python и их применение
для решении задач ЕГЭ
Задача 15
Логика. Множества
К.Ю. Поляков, 2024
http://kpolyakov.spb.ru

67.

Структуры данных в Python и их применение для решении задач ЕГЭ
67
15. Множества
Элементами множеств А, P и Q являются
натуральные числа, причём
P = { 1, 2, 3, 4 } и Q = { 3, 4, 5, 6 }.
Известно, что выражение
¬(x ∈ A) → (¬(x ∈ P) ∨ ¬(x ∈ Q))
истинно (т. е. принимает значение 1) при любом
значении переменной x. Определите наименьшее
возможное количество элементов множества A.
!
К.Ю. Поляков, 2024
Истинно при A = P Q!
http://kpolyakov.spb.ru

68.

Структуры данных в Python и их применение для решении задач ЕГЭ
68
15. Решение
¬(x ∈ A) → (¬(x ∈ P) ∨ ¬(x ∈ Q))
def F( A, x ):
return (x not in A) <= \
((x not in P) or (x not in Q))
P = { 1, 2, 3, 4 }
def valid( A ):
Q = { 3, 4, 5, 6 }
for x in range(0, 8):
if not F(A, x): return False
return True
P = { 1, 2, 3, 4 }
Q = { 3, 4, 5, 6 }
A = P | Q
for a in P | Q:
if valid( A-{a} ):
A.remove( a )
print( len(A), A )
К.Ю. Поляков, 2024
http://kpolyakov.spb.ru

69.

Структуры данных в Python и их применение для решении задач ЕГЭ
69
15. Множества
Элементами множеств А, P и Q являются
натуральные числа, причём
P = { 1, 2, 3, 4 } и Q = { 3, 4, 5, 6 }.
Известно, что выражение
((x ∈ A) → (x ∈ P)) ∨ (¬(x ∈ Q) → ¬(x ∈ A))
истинно (т. е. принимает значение 1) при любом
значении переменной x. Определите наибольшую
возможную сумму элементов множества A.
!
К.Ю. Поляков, 2024
Истинно при A = {}!
http://kpolyakov.spb.ru

70.

Структуры данных в Python и их применение для решении задач ЕГЭ
70
15. Решение
((x ∈ A) → (x ∈ P)) ∨ (¬(x ∈ Q) → ¬(x ∈ A))
def F( A, x ):
return ((x in A) <= (x in P)) or \
((x not in Q) <= (x not in A))
P = { 1, 2, 3, 4 }
def valid( A ):
Q = { 3, 4, 5, 6 }
return all( F(A, x)
for x in range(0, 8) )
P = { 1, 2, 3, 4 }
Q = { 3, 4, 5, 6 }
A = set()
for a in P | Q:
if valid( A | {a} ):
A.add( a )
print( sum(A), A )
К.Ю. Поляков, 2024
http://kpolyakov.spb.ru

71.

Структуры данных в
Python и их применение
для решении задач ЕГЭ
Задача 24
Обработка символьных строк
К.Ю. Поляков, 2024
http://kpolyakov.spb.ru

72.

Структуры данных в Python и их применение для решении задач ЕГЭ
72
24. Цепочка одинаковых символов
Текстовый файл состоит из заглавных букв
латинского алфавита. Определите максимальное
количество идущих подряд символов A.
curLen
maxLen
продолжается
curLen += 1
maxLen = max(curLen,maxLen)
К.Ю. Поляков, 2024
прерывается
curLen = 0 # или 1
http://kpolyakov.spb.ru

73.

Структуры данных в Python и их применение для решении задач ЕГЭ
73
Чтение строки из файла (Python)
Классика:
F = open("24.txt")
s = F.readline()
F.close()
Модерн:
with open("24.txt") as F:
s = F.readline()
Убрать
"\n"
или:
s = open("24.txt").readline().rstrip()
print( s[:10] )
К.Ю. Поляков, 2024
# для проверки
http://kpolyakov.spb.ru

74.

Структуры данных в Python и их применение для решении задач ЕГЭ
74
24. Самое простое решение
s = open('24.txt').readline().rstrip()
count = 1
while 'A'*count in s:
count += 1
print( count - 1 )
К.Ю. Поляков, 2024
http://kpolyakov.spb.ru

75.

Структуры данных в Python и их применение для решении задач ЕГЭ
75
24. Решение
s = open('24.txt').readline().rstrip()
curLen = maxLen = 0
for c in s:
if c == 'A':
curLen += 1
maxLen = max( curLen, maxLen )
else:
или 1, если началась
curLen = 0
новая цепочка
print( maxLen )
К.Ю. Поляков, 2024
http://kpolyakov.spb.ru

76.

Структуры данных в Python и их применение для решении задач ЕГЭ
76
24. Решение через замены
Идея:
1) оставить только A (остальные заменить
пробелами)
2) разбить на слова
3) найти наибольшую длину слова
for c in set(s):
if c != 'A':
s = s.replace( c, ' ' )
генераторное
выражение
print( max( len(part)
for part in s.split() ) )
К.Ю. Поляков, 2024
http://kpolyakov.spb.ru

77.

Структуры данных в Python и их применение для решении задач ЕГЭ
77
24. Замены: небольшой алфавит
Текстовый файл состоит из букв латинского
алфавита A, B, C, D. Определите максимальное
количество идущих подряд символов A.
s = s.replace('B',' ').replace('C',' ') \
.replace('D',' ')
К.Ю. Поляков, 2024
http://kpolyakov.spb.ru

78.

Структуры данных в Python и их применение для решении задач ЕГЭ
78
24. Цепочка одинаковых пар
Текстовый файл состоит из заглавных букв
латинского алфавита. Определите максимальную
длину цепочки, состоящей из идущих подряд пар
символов AB.
s = s.replace( 'AB', '**' )
for c in set(s):
if c != '*':
s = s.replace( c, ' ' )
print( max( len(part)
for part in s.split() ) )
К.Ю. Поляков, 2024
http://kpolyakov.spb.ru

79.

Структуры данных в Python и их применение для решении задач ЕГЭ
79
24. Решение через рекурсию
def countAB( s, i ):
if i >= len(s)-1: return 0
if s[i:i+2] != 'AB': return 0
return 2 + countAB( s, i+2 )
print( max( countAB(s, i)
for i in range(len(s)) ) )
К.Ю. Поляков, 2024
http://kpolyakov.spb.ru

80.

Структуры данных в Python и их применение для решении задач ЕГЭ
80
24. Демо-2021
Текстовый файл состоит из заглавных букв
латинского алфавита. Определите максимальное
количество идущих подряд символов, среди
которых каждые два соседних различны.
К.Ю. Поляков, 2024
http://kpolyakov.spb.ru

81.

Структуры данных в Python и их применение для решении задач ЕГЭ
81
24. Решение
curLen = maxLen = 0
prev = '*'
for c in s:
if c != prev:
curLen += 1
maxLen = max( curLen, maxLen )
else:
curLen = 1 # началась новая цепочка
prev = c
print( maxLen )
К.Ю. Поляков, 2024
http://kpolyakov.spb.ru

82.

Структуры данных в Python и их применение для решении задач ЕГЭ
82
24. Решение через замены
for x in set(s):
while x+x in s:
s = s.replace( x+x, f"{x} {x}" )
print( max( len(part)
for part in s.split() ) )
?
Почему while?
К.Ю. Поляков, 2024
XXX X XX
X XX X X X
http://kpolyakov.spb.ru

83.

Структуры данных в Python и их применение для решении задач ЕГЭ
83
24. Демо-2023
Текстовый файл состоит из символов
A, C, D, F, O.
Определите максимальное количество идущих
подряд пар символов вида
согласная + гласная
К.Ю. Поляков, 2024
http://kpolyakov.spb.ru

84.

Структуры данных в Python и их применение для решении задач ЕГЭ
84
24. Решение
curLen, maxLen = 0, 0
for c in s:
if c in "CDF" and curLen % 2 == 0 or \
c in "AO" and curLen % 2 == 1:
curLen += 1
maxLen = max( curLen, maxLen )
else:
curLen = 0
print( maxLen // 2 )
считаем
пары
К.Ю. Поляков, 2024
http://kpolyakov.spb.ru

85.

Структуры данных в Python и их применение для решении задач ЕГЭ
85
24. Решение через замены
from itertools import product
for x in product("CDF", "AO"):
s = s.replace( x[0]+x[1], "*" )
for x in set(s)-{'*'}:
s = s.replace( x, " " )
print( max( len(part)
for part in s.split() ) )
К.Ю. Поляков, 2024
http://kpolyakov.spb.ru

86.

Структуры данных в
Python и их применение
для решении задач ЕГЭ
Задача 26
Сортировка
К.Ю. Поляков, 2024
http://kpolyakov.spb.ru

87.

Структуры данных в Python и их применение для решении задач ЕГЭ
87
26. Демо-2022
На диске нужно сохранить файлы разного размера.
Файл 26.txt. Первая строка:
V – размер свободного места на диске
N – количество файлов
В следующих N строках – размеры файлов.
Найдите:
1) наибольшее число файлов, которые могут быть
сохранены на диске;
2) максимальный размер файла, который может быть
при этом сохранён на диске.
К.Ю. Поляков, 2024
http://kpolyakov.spb.ru

88.

Структуры данных в Python и их применение для решении задач ЕГЭ
88
Чтение данных – менеджер контекста
with open("26.txt") as F:
V, N = map( int, F.readline().split() )
data = []
for i in range(N):
data.append( int(F.readline()) )
не нужно вызывать .close()
К.Ю. Поляков, 2024
http://kpolyakov.spb.ru

89.

Структуры данных в Python и их применение для решении задач ЕГЭ
89
Чтение данных – генератор списка
with open("26.txt") as F:
V, N = map( int, F.readline().split() )
data = [ int(F.readline())
for _ in range(N) ]
with open("26.txt") as F:
V, N = map( int, F.readline().split() )
data = [ int(s) for s in F ]
читаются все строки
V, N, *data = map( int,
open("26.txt").read().split() )
Автор: А. Богданов
К.Ю. Поляков, 2024
http://kpolyakov.spb.ru

90.

Структуры данных в Python и их применение для решении задач ЕГЭ
90
Демо-2022: количество файлов
data.sort()
# начнём с наименьшего
количество
добавленных
общий
объём (≤ V)
помещается?
count = total = 0
while total+data[count] <= V:
total += data[count]
нельзя
переставлять!
count += 1
print( count )
К.Ю. Поляков, 2024
http://kpolyakov.spb.ru

91.

Структуры данных в Python и их применение для решении задач ЕГЭ
91
Демо-2022: максимальный размер файла
# вычитаем размер последнего взятого
total -= data[count-1]
# подходящие из оставшихся
candidates = [ x for x in data[count-1:]
if total+x <= V ]
print( max(candidates) )
# или
print( candidates[-1] )
К.Ю. Поляков, 2024
http://kpolyakov.spb.ru

92.

Структуры данных в Python и их применение для решении задач ЕГЭ
92
26. Демо-2023
Кубические коробки вкладываются друг в друга, если
длины их сторон различаются не менее, чем на 3.
Файл 26.txt. Первая строка:
N – количество коробок
В следующих N строках – длины сторон коробок.
Найдите:
1) наибольшее число коробок, которые можно вложить
друг в друга;
2) максимальный размер минимальной коробки в такой
пачке.
!
Начинать с самой большой коробки!
К.Ю. Поляков, 2024
http://kpolyakov.spb.ru

93.

Структуры данных в Python и их применение для решении задач ЕГЭ
93
Чтение и подготовка данных
with open("26.txt") as F:
N = int( F.readline() )
data = [ int(s) for s in F ]
# сортировка по убыванию
data.sort( reverse=True )
К.Ю. Поляков, 2024
http://kpolyakov.spb.ru

94.

Структуры данных в Python и их применение для решении задач ЕГЭ
94
Решение
count = 1
# взяли самую большую
last = 0
# последняя выбранная
i = 1
# эту проверяем
while i < N:
if data[i] <= data[last]-3:
count += 1
last = i
i += 1
print( count, data[last] )
К.Ю. Поляков, 2024
http://kpolyakov.spb.ru

95.

Структуры данных в Python и их применение для решении задач ЕГЭ
95
Решение (цикл for)
count = 1
# взяли самую большую
last = 0
# последняя выбранная
for i in range(1, N):
if data[i] <= data[last]-3:
count += 1
last = i
print( count, data[last] )
К.Ю. Поляков, 2024
http://kpolyakov.spb.ru

96.

Структуры данных в Python и их применение для решении задач ЕГЭ
96
26. Демо-2024 (конференц-зал)
Заявки на провередение мероприятий в конференц-зале.
Файл 26.txt. Первая строка:
N – количество заявок на проведение мероприятий
В следующих N строках – время начала и окончания
каждого мероприятия.
Найдите:
1) максимальное количество мероприятий, которые
можно провести;
2) максимальный перерыв между двумя последними
мероприятиями.
К.Ю. Поляков, 2024
http://kpolyakov.spb.ru

97.

Структуры данных в Python и их применение для решении задач ЕГЭ
97
Чтение и подготовка данных
with open("26.txt") as F:
N = int( F.readline() )
data = []
for s in F:
t0, t1 = map( int, s.split() )
data.append( (t0, t1) ) кортеж
!
Сортировать по времени окончания!
data.sort( key = lambda p: p[1] )
лямбда-функция
К.Ю. Поляков, 2024
http://kpolyakov.spb.ru

98.

Структуры данных в Python и их применение для решении задач ЕГЭ
98
Решение
count = 1
# взяли самое первое
tFree = data[0][1]
# время окончания
for i in range(1, N):
t0, t1 = data[i] # распаковка кортежа
if t0 >= tFree:
count += 1
tFree = t1
print( count, tFree )
первый ответ
К.Ю. Поляков, 2024
http://kpolyakov.spb.ru

99.

Структуры данных в Python и их применение для решении задач ЕГЭ
99
Второй вопрос
предпоследнее
последнее
время
tPrev
К.Ю. Поляков, 2024
второй ответ
http://kpolyakov.spb.ru

100.

Структуры данных в Python и их применение для решении задач ЕГЭ
100
Решение (дополнение)
count = 1
# взяли самое первое
tFree = data[0][1]
# время окончания
for i in range(1, N):
t0, t1 = data[i] # распаковка кортежа
if t0 >= tFree:
count += 1
tPrev = tFree
время начала
tFree = t1
lastStart = [ d[0] for d in data
if d[0] > tPrev ]
print( max(lastStart) - tPrev )
К.Ю. Поляков, 2024
http://kpolyakov.spb.ru

101.

Структуры данных в Python и их применение для решении задач ЕГЭ
101
26. Пакеты с углём
(А. Кабанов) Пакеты с углём различного веса и стоимости.
Отбираются K пакетов с самой низкой ценой угля за
единицу веса; при равной стоимости за единицу веса
выбираются пакеты с большим весом.
Первая строка:
N, K – количество пакетов и сколько нужно отобрать
В следующих N строках – вес и стоимость пакета
Найдите:
1) суммарный вес угля в отправленных пакетах
2) стоимость самого тяжёлого отправленного пакета.
К.Ю. Поляков, 2024
http://kpolyakov.spb.ru

102.

Структуры данных в Python и их применение для решении задач ЕГЭ
102
Чтение данных
with open("26.txt") as F:
N, K = map( int, F.readline().split() )
data = []
for i in range(N):
weight, price =
map( int, F.readline().split() )
data.append( (weight, price) )
кортеж
(или список)
[(49, 686), (68, 1088), (78, 1794), ...]
К.Ю. Поляков, 2024
http://kpolyakov.spb.ru

103.

Структуры данных в Python и их применение для решении задач ЕГЭ
103
Сортировка
… с самой низкой ценой угля за единицу веса; при
равной стоимости за единицу веса выбираются
пакеты с большим весом
Как отсортирует?
data.sort()
?
Элементы: (weight, price)
сначала
по весу
потом
по цене
x[0]
x[1]
(weight, price)
data.sort( key=lambda x: (x[1]/x[0], -x[0]) )
по удельной
стоимости
К.Ю. Поляков, 2024
потом по
убыванию
веса
http://kpolyakov.spb.ru

104.

Структуры данных в Python и их применение для решении задач ЕГЭ
104
Решение (подробно)
data = data[:K]
# первые K пакетов
суммарный вес угля в отправленных пакетах
weights = ( x[0] for x in data )
print( sum(weights) )
стоимость самого тяжёлого отправленного пакета
heavy = max(data)
print( heavy[1] )
цена
К.Ю. Поляков, 2024
# (weight, price)
сначала
по весу
потом
по цене
http://kpolyakov.spb.ru

105.

Структуры данных в Python и их применение для решении задач ЕГЭ
105
Решение (кратко)
data = data[:K]
print( sum( weight
for weight, price in data ) )
print( max(data)[1] )
К.Ю. Поляков, 2024
http://kpolyakov.spb.ru

106.

Структуры данных в Python и их применение для решении задач ЕГЭ
106
Конец фильма
ПОЛЯКОВ Константин Юрьевич
д. т. н., учитель информатики
г. Санкт-Петербург
[email protected]
К.Ю. Поляков, 2024
http://kpolyakov.spb.ru