Задание 27 (Метод частичных сумм) // ЕГЭ по информатике 2022

Разбираем метод частичных сумм, работу с парами тройками и под последовательностями.

За мат, КАПС, политоту, флуд - перманентный бан.

--------------------------------------------------------------------------------------------

Ссылки на каналы других годных преподавателей:
Евгений Джобс

Информатик БУ

Alex Danov

Андрей Рогов

Леонид Шастин

Ботай каждый день, глупый дурачок

Таймкоды
00:00 Приветствие
01:30 Выбор из пары 1
28:20 Выбор из пары 2
47:20 Комбинации троек
01:03:15 Учёт количества чисел
01:23:10 Подмножества пар
01:41:00 Выбранные и не выбранные числа
01:54:25 Максимальная сумма подпоследовательности
02:06:15 Учёт длины подпоследовательности
02:14:25 Максимальная сумма подмножества
02:22:40 Количество подмножеств
02:32:20 Окончание и напутствия

[pgn]

Итак, я написал ЕГЭ на 93 балла. Спасибо большое за Ваш труд. Ваши вебы очень помогли достичь такого уровня. Здорово, что вы понятно объясняете и даёте необычные (непрямые) подходы к решению задач!

[akstis]

Сначала мозг отказывался воспринимать информацию, но после того, как я понял как работают генераторы и сам порешал такого рода задачки, все встало на свои места. Спасибо большое за способ =)

[ПавелВасильев-тн]

Этот веб хорошенько так мне мозги протряс! Спасибо за Ваш труд!

[aufchk]

2:14:12 В этой задаче, я думаю, стоит сортировать не просто по позрастанию первого числа (суммы), а по возрастанию первого и убыванию второго (длины), тк вдруг у нас в файле б попадётся такая ситуация: две максимальные суммы с остатком напр. 17 идут подряд, но у первой длина 7 а у второй 17, по итогу перезапишется после первой вторая и длина не наименьшая. (Двойная сортировка в данном случае: sorted(s, key = lambda t: (t[0], -t[1]))
upd: Хотя в натуральных числах нас это не должно по идее страшить

[TGrod]

Отличный веб. В середине прям тяжко стало, но вроде осилил. Интересная идея решения) Я бы даже сказал гениальная.
И ещё вопрос. Вы в конце сказали, что разобрали ПОЧТИ всё-всё) А что ещё в теории осталось? Самому посмотреть чтобы

[МаксимСлавик-ьд]

Здавствуйте, Алексей! В задаче 02:06:15 при наличии двух подпоследовательностей с разными длинами из-за сортировки sort(s) не возникнет ошибки? Мы ищем минимальные длины, а в строке s = {x[0]%69:x for x in sorted(s)} при наличии нескольких подпоследовательностей с одинаковой суммой и разной длиной сохранится только та, что длиннее. Заранее спасибо)

[.ЗайцевИлья]

В задаче "Учет количество чисел" есть проще решение:

with open("sumtest.txt") as file:
n = int(file.readline())
ans = [ [0, 0, 0] ]
for d in file:
data = list(map(int, d.split()))
ans = [ [a[0]+b, a[1]+int(b%2==0), a[2]+int(b%2!=0)] for a in ans for b in data]
ans = list( {(a[0]%2==0, a[1]>a[2], a[1]==a[2]):a for a in sorted(ans)}.values() )
print(ans)

[friend]

всем, кто это читает, удачииии на инфе! знайте, у вас все получится!!

[forgames]

В третьей задаче есть попроще решение:
1) посчитайте макс. сумму, не учитывая доп. условие. добавляйте к сумме макс. элемент из каждой тройки.
2) посчитайте кол-во элементов кратных 2 и не кратных 2, при этом не надо учитывать выбранные макс. элементы.
3) на основе данных из п.2 делайте вывод: стоит ли уменьшить полученную в п.1 макс. сумму или нет. насколько уменьшить, думаю несложно понять.

[sanisalexandrov]

Почему в последней задаче итерируется с помощью i внутренний и внешний цикл for?Это разве не ошибка?

[llirikh]

Спасибо большое за урок! Алексей, а какие еще идеи решения задач можно изучить? Просто на сайте ФИПИ написано, что задания 26, 27 полностью изменятся. Могут ли попасться задачи на графы?

[Андрей-упв]

1:54:45 в итоге на основной волне 2022 дали новый тип задач с автодорогами?

[bznnhmv]

Скажите, пожалуйста, а когда мы производим группировку целых чисел по остатку (10 задача из домашки) нужно брать остаток по модулю или нет?

[МихаилГолубев-бс]

1:03:15 а это норм то что к этому моменту я самостоятельно чисто решил эту задачу?
n=5
q = [[13, 8], [5, 11], [6, 9], [7, 2], [9, 14]]
s =[[0, 0, 0]]
for i in range(n):
pair = q[i]
s = [[a+b, a0+int(b%2==0), a1+int(b%2==1)] for a, a0, a1 in s for b in pair]
s = {(x[0]%2, x[1]>=x[2]):x for x in sorted(s)}.values()
print(list(s))
mx = 0
for a, a0, a1 in s:
if (a%2==0 and a0>=a1) or (a%2==1 and a1>=a0): mx = max(mx, a)
print(mx)

[Сева-юб]

Здравствуйте. Подобные задания (пункт А) можно решать неэффективным способом? Если да, то можете, пожалуйста, привести примерную программу или передать ее смысл

[СергейКоптев-вщ]

Алексей, 54:32 почему мы не ставим наибольшее число из получившейся тройки на 1 место?

[skhcru]

Я решал задачу 1:03:45 в прошлом году на каком-то пробнике почти таким же способом, как в 37:10 Мне кажется что получится проще, попробуй)
Если такое решение в прошлогоднем стриме, сорян нет пока времени посмотреть, а потом написать забуду)

[shon]

2:32:47 то что мы используем i и в большом цикле и в маленьком нормально?

[МихаилГолубев-бс]

1:00:40 я бы даже лучше написал не a1%2!=0 and a2%2==0, a a1%2!=a2%2

[Мачта]

Попробовал и сделал 48 вот так:
f=open('27-48b.txt')
n=int(f.readline())
s=[[0, 0, 0]]
for i in range(n):
pair=[int(x) for x in f.readline().split()]
s=[[a1+b, a2+(b%2==0), a3+(b%2!=0)] for a1, a2, a3 in s for b in pair]
s={(x[0]%2, 'ch' if x[1]>x[2] else 'nch'):x for x in sorted(s)}.values()
ans=[]
for a, b, c in s:
if a%2==0 and b>c or a%2!=0 and b<c:
ans+=[a]
print(max(ans))
Терь не знаю, норм или нет