Занятие 3.5 Алгоритмы для работы с числами (26)

1. Алгоритмы для работы с числами

2. Суть задания 26

- это задача на обработку набора данных по условию
оптимального выбора.
Чаще всего требуется:
• выбрать объекты по условию;
• уложиться в ограничение;
• получить наилучший результат;
• вывести 2 числа.

3. Суть задания 26

Проверяются:
- понимание условия;
- работа с данными;
- выбор способа решения;
- умение находить оптимальный результат.
Чаще всего используются:
- сортировка;
- жадный подход;
- разделение данных на группы;
- моделирование по условию.

4. Суть задания 26

Типичные модели:
- выбор максимального количества объектов при
ограничении;
- выбор с дополнительным условием;
- задачи на скидки, приоритеты, отбор по категориям;
- задачи на размещение, распределение, занятость
ресурсов.
Главная идея:
Задание 26 — это не одна задача, а набор
повторяющихся схем.

5. Файлы

https://clck.ru/3SmcW4

6. Жадность

7. Задача 1

8. Разбор

Свободное место на диске:
70 МБ
Файлы:
8
3
10
4
5
18
5
15
2
1
9
20
25
Нам необходимо найти максимальное количество файлов,
которое можно сохранить на диск, а также размер максимального файла.

9. Разбор

Свободное место на диске:
70 МБ
Сначала сортируем файлы по возрастанию:
1 2 3 4
5
5
8
9
10
15
18
20
25

10. Разбор

Помещаем файлы на диск, пока есть место:
70 МБ
12 3 4 5 5
8
9
10
15
Сумма сохранённых: 1+2+3+4+5+5+8+9+10+15 = 62 МБ
Количество файлов: 10 (первая часть ответа)
Осталось свободного места: 8МБ
18
20
Оставшиеся файлы не влезут в 8 МБ
25

11. Разбор

Для поиска максимально возможного файла уберём
максимальный отобранный и посмотрим, сможем ли мы поместить больше
70 МБ
12 3 4 5 5
8
9
10
15
Мы уберем последний файл (15).
Свободного места станет: остаток 8 МБ + освобожденные 15 МБ = 23 МБ.
Из оставшихся самый большой файл, который мы можем поместить в 23
МБ – это 20 МБ. Это будет ответом на второй вопрос.
18
20
25

12. Чтение из файла

f = open('26_3.txt’)
Для работы с текстовым файлом используется функция open(). Python не
загружает весь файл в память мгновенно. Он создает файловый объект
(переменную f). Это своеобразный «мост» между программой и файлом на
жестком диске.
Главный принцип чтения файла – курсор. При выполнении open() он ставит
этот курсор в начале файла. При этом любая команда чтения (read,
readline, цикл for), сдвигает этот курсор вперёд.

13. Чтение из файла

Способы чтения:
f.readline() - читает ровно одну строку из файла.
f.read() - считывает весь оставшийся файл целиком в одну гигантскую
текстовую строку. В 26 задании неудобно работать с числами, придется
дополнительно применять метод .split(), чтобы разбить текст на отдельные
элементы.
Цикл for
files = [int(x) for x in f]
Проходит по всем строкам файла
В коде, после шага два, курсор уже стоит на второй строке файла, этот
цикл начинает собирать данные именно оттуда и до самого конца файла.

14. Задача 1

15. Задача 2

16. Задача 3

17. Задача 3

18. Задача 4

19. Разбор

Товары:
31
63
78
421
26
332
523
17
666
10
762
Условия:
Скидка 25% предоставляется на каждый второй товар в списке дороже
50 рублей. Необходимо найти общую стоимость покупки, и стоимость
самого дорогого товара со скидкой.
Общая стоимость товаров со скидкой округляем вверх.
При этом мы находимся на месте жадного продавца, хотим
максимизировать итоговую стоимость

20. Разбор

Товары:
26
31
17
63
10
Откладываем
мелочь. На
них скидка не
работает, но в
общую сумму
(в чек) они
пойдут
78
332
666
421
523
762
Дорогие товары сортируем в порядке
возрастания

21. Разбор

Товары:
26
31
17
63
10
332
666
25%
25%
421
78
63
666
78
Как их хотел бы расположить продавец
421
523
762
25%
523
332
762

22. Разбор

Товары:
26
В коде мы не будем заниматься расстановкой
товаров по позициям, мы логически понимаем,
что можно взять дешёвую половину товара, и
применить к ней скидку.
31
17
10
Скидка даётся на каждый второй товар. Значит,
из 7 дорогих товаров скидку получат ровно 3
(мы делим количество нацело: 7 // 2 = 3)
25%
63
78
332
421
523
666
762
Итоговая стоимость: мелочь(26+31+17+10) + вторая половина дорогих
товаров(421+523+666+762) + первая половина дорогих товаров со
скидкой (63+78+332)*0.75 = 84 + 2372 + (354.75 округляем вверх = 355) =
2811

23. Разбор

Товары:
26
Итоговая стоимость:
мелочь
(26+31+17+10) +
вторая половина дорогих товаров
(421+523+666+762) +
первая половина дорогих товаров со скидкой
(63+78+332)*0.75 =
84 + 2372 + (354.75 округляем вверх = 355) =
2811 – Общая сумма, самый дорогой товар со
скидкой стоит 332 рубля
31
17
10
25%
63
78
332
421
523
666
762

24. Задача 4

25. Задача 5

26. Разбор

Коробки:
40
43
40
30
32
Условия:
Нужно вложить друг в друга как можно больше коробок, при этом
сторона вкладываемой коробки должна быть хотя бы на 3 см меньше,
чем та, в которую вкладываем.

27. Разбор

Коробки:
43
40
40
32
30
Чтобы вложить друг в друга как можно больше коробок, логично начать
собирать матрёшку снаружи внутрь. То есть мы берём самую гигантскую
коробку, и начинаем запихивать в неё всё, что влезет.

28. Разбор

Коробки:
43
40
40
32
30
Мы сортируем коробки по убыванию. Так как если мы будем брать
каждую подходящую коробку по очереди (от больших к меньшим), мы
автоматически выполним второе условие задачи: „сделать самую
маленькую коробку максимально возможной“, потому что берём самый
большой из доступных вариантов.

29. Разбор

Коробки:
40
32
30
Пробуем первое вложение, длина стороны меньше на 3, нам подходит
43
40

30. Разбор

Коробки:
40
30
Следующая (40) не влезает, пробуем четвёртую коробку с длиной 32
43
40
32

31. Разбор

Коробки:
40
30
Пробуем последнюю, 32 – 30 = 2, меньше чем три, не подходит
По итогу у нас:
3 коробки
размер наименьшей коробки - 32
43
40
32

32. Задача 5

33. Задача 6

34. Задача 6

35. Задача 7

36. Задача 7

37. Ответы

1) 568 50
2) 509 31
3) 1612 90
4) 469784 511
5) 2767 51
6) 2172 50
7) 5895 227

38. Индексы, Шаги и Два Указателя

39. Задача 8

40. Задача 8

Товары:
31
63
78
421
26
332
523
17
666
10
762

41. Задача 8

Как покупатель хотел изначально:
26
10
666
11
31
17
421
63
332
78
523
762

42. Задача 8

Как нужно:
762
421
666
332
63
31
26
17
11
10
523
78

43. Задача 8

22262050 33246829

44. Задача 9

45. Задача 9

18456 99999

46. Студенты и lambda

47. lambda

Допустим, у нас есть список студентов:
students = [
(123, 3.4),
(43, 4.4),
(61, 2.4),
(42, 3.4),
(612, 5.0),
(44, 4.1),
(124, 2.3)
]
На первой позиции в строке – ID студента, на второй, средний бал оценок.
Как отсортировать их так, чтобы сначала шли студенты с наивысшим
средним балом, при этом если средние балы равны, то тогда сортируем по
возрастанию ID?

48. lambda

students = [
(123, 3.4),
(43, 4.4),
(61, 2.4),
(42, 3.4),
(612, 5.0),
(44, 4.1),
(124, 2.3)
]
students.sort(key=lambda x: (-x[1], x[0]))

49. Задача 10

50. Задача 10

Сдали
сессию (нет
двоек)
Сортируются по убыванию среднего
балла и возрастанию ID
То есть нам, помимо ID и
оценок,
нужны средний балл и
количество 2, чтобы
отсортировать по ним.
В файле нам дано:
ID 4 оценки
123, 2, 4, 5, 4
Не сдали
сессию
Сортируются по возрастанию
количества двоек и возрастанию ID
Нам нужно так
ID 4 оценки Ср.Б Кол-во 2
123, 2, 4, 5, 4, 3.75, 1

51. Задача 10

Сдали
сессию (нет
двоек)
Не сдали
сессию
25%
Нам нужен ID студента, который
находится в самом конце этих 25
процентов

52. Задача 10

Не сдали
сессию
Для нахождения второй части ответа
перебираем список и ищем первого, у
кого 2 двойки.

53. Задача 10

52326 635

54. Задача 11

55. Задача 11

Русский Математика Информатика Сумма
1. 100 100 100 300
2. 80 80 80 240
3. 75 80 80 235
4. 75 80 80 235
5. 50 60 40 150
6. 50 40 60 150
7. 60 50 40 150

56. Задача 11

Русский Математика Информатика Сумма
1. 100 100 100 300
2. 80 80 80 240
3. 75 80 80 235
4. 75 80 80 235
5. 50 60 40 150
6. 40 50 60 150
7. 60 50 40 150
8. 50 50 49 149
Проходной – 100% проходишь - 235
Полупроходной – зависит от баллов по конкретным предметам - 150

57. Задача 11

Русский Математика Информатика Сумма
1. 100 100 100 300
2. 80 80 80 240
3. 75 80 80 235
4. 75 80 80 235
5. 50 60 40 150
6. 40 50 60 150
7. 60 50 40 150
8. 50 50 49 149
Полупроходной по информатике, чтобы быть зачисленным - 40

58. Задача 11

229 83

59. Задача 12

60. Задача 12

4229 23

61. Матрёшки

62. Задача 13

63. Задача 13

used = [False] * N
boxes
411
311
264
211
189
used
False False False False False False False False False
Пишем цикл while False in used, собирая
матрешки внутри него.
132
17
9
8

64. Задача 13

17 1767

65. Задача 14

66. Задача 14

2326 187

67. Двусторонние очереди

68. Задача 15

69. Задача 15

151
123
15
442
167
13
66
477
31
12
33
88
У продуктов есть срок хранения с
момента изготовления и срок годности с
момента вскрытия упаковки.

70. Задача 15

151
123
5
12
15
442
3
13
167
13
2
15
66
477
5
31
31
12
6
33
33
88
4
66
6
88
1
123
1
151
3
167
2
442
4
477
Сортируем их по возрастанию, не
забывая про нумерацию и тип
срока

71. Задача 15

5
12
3
13
2
15
5
31
6
33
4
66
6
88
1
123
1
151
3
167
2
442
4
477
5
31
12

72. Задача 15

5
12
3
13
2
15
5
31
6
33
4
66
6
88
1
123
3
167
13
1
151
5
31
12
3
167
2
442
4
477

73. Задача 15

5
12
3
13
2
15
5
31
6
33
4
66
6
88
1
2
15
442
123
3
167
13
1
151
5
31
12
3
167
2
442
4
477

74. Задача 15

5
12
3
13
2
15
5
31
6
33
4
66
6
88
1
2
15
442
6
33
88
123
3
167
13
1
151
5
31
12
3
167
2
442
4
477

75. Задача 15

5
12
3
13
2
15
5
31
6
33
4
66
6
88
1
2
15
442
6
33
88
4
66
477
123
3
167
13
1
151
5
31
12
3
167
2
442
4
477

76. Задача 15

5
12
3
13
2
15
5
31
6
33
4
66
6
2
15
442
6
33
88
4
66
477
88
1
151
123
1
123
3
167
13
1
151
5
31
12
3
167
2
442
4
477

77. Задача 15

564 444

78. Задача 16

79. Задача 16

448 515

80. Ряды и места (координаты)

81. Задача 17

82. Задача 17

8631 7311

83. Задача 18

84. Задача 18

10 2786

85. Задача 19

59966 50449

86. Задача 20

26 97586

87. Расписание мероприятий

88. Задача 21

89. Задача 21

1___________________________________________________________200
10 - 150
100 - 110
131 - 170
131 - 180
120 - 130

90. Задача 21

Сортируем по возрастанию времени окончания
1___________________________________________________________200
100 - 110
120 - 130
10 - 150
131 - 170
131 - 180

91. Задача 21

Берём первый
1___________________________________________________________200
100 - 110
120 - 130
10 - 150
131 - 170
131 - 180

92. Задача 21

Смотрим второй, он начинается позже, чем заканчивается первый, значит
подходит.
1___________________________________________________________200
100 - 110
120 - 130
10 - 150
131 - 170
131 - 180

93. Задача 21

Смотрим третий, он начинается позже, чем заканчивается второй?
Нет, значит пропускаем.
1___________________________________________________________200
100 - 110
120 - 130
10 - 150
131 - 170
131 - 180

94. Задача 21

Смотрим четвёртый, он начинается позже, чем заканчивается второй?
Да, значит берём.
1___________________________________________________________200
100 - 110
120 - 130
10 - 150
131 - 170
131 - 180

95. Задача 21

Смотрим пятый, он начинается позже, чем заканчивается 4-ый?
Нет, значит пропускаем.
1___________________________________________________________200
100 - 110
120 - 130
10 - 150
131 - 170
131 - 180
По итогу получилось максимум три мероприятия.

96. Задача 21

Как найти самое мероприятие, которое заканчивается позже всех при том же
максимальном количестве?
1___________________________________________________________200
100 - 110
120 - 130
10 - 150
131 - 170
131 - 180
Убираем последнее мероприятие (зеленое), и ищем мероприятие,
которое начинается
позднее предпоследнего (желтого) и заканчивается позднее всех.
В данном случае это будет фиолетовое.
Мероприятий осталось 3, но время окончания последнего стало 180.

97. Задача 21

16 1345

98. Задача 22

99. Задача 22

17 35

100. Задача 23

101. Задача 23

53 1

102. Камеры хранения

103. Задача 24

104. Задача 24

59 - 60
1
0
30 - 60
61 - 1000
2
40 - 1000
1010 - 1440
0
У нас две камеры хранения и пять пассажиров, у них над головами
время сдачи багажа и освобождения ячейки

105. Задача 24

1
0
30 - 60
2
40 - 1000
59 - 60
61 - 1000
1010 - 1440
0
Сортируем в порядке возрастания времени сдачи, так как они приходят
в этом порядке.

106. Задача 24

Счетчик 1
1
60
30 - 60
2
40 - 1000
59 - 60
61 - 1000
1010 - 1440
0
Приходит первый пассажир, берем его багаж, помечаем камеру хранения
временем освобождения

107. Задача 24

Счетчик 2
1
60
40 - 1000
59 - 60
61 - 1000
1010 - 1440
2 1000
Приходит второй пассажир, у нас есть свободная камера хранения
определяем его багаж туда

108. Задача 24

Счетчик 2
1
60
59 - 60
61 - 1000
1010 - 1440
2 1000
Приходит третий, у него время 59 минут, но наши камеры хранения заняты
до 60 и 1000 минут, он уходит и не оставляет багаж.

109. Задача 24

Счетчик 3
1
60
61 - 1000
1010 - 1440
2 1000
Приходит четвертый, у него время 61 минут, больше 60, значит он сможет
оставить багаж.

110. Задача 24

Счетчик 4
1 1000
1010 - 1440
2 1000
Приходит пятый, у него время 1010 минут, больше 1000, значит он сможет
оставить багаж, по условию он оставляет его в минимальной свободной
камере хранения, то есть в первой.
Ответ тут: 4 (количество обслуженных пассажиров) и 1(номер последней
занятой ячейки)

111. Задача 24

Ловушка с минимальным номером
1 1000
1010 - 1440
1010 - 1440
2 1000
Допустим, приходят два человека, оба последние, у нас две свободных ячейки,
мы их двоих обслуживаем. По условию задачи, мы должны дать минимальный
номер, то есть 1.

112. Задача 24

344 53

113. Задача 25

114. Задача 25

717 19