Задание 27 // КЕГЭ по информатике 2023

Разбираем задачи со сдвигами областей/пунктов

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

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

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

Тимофей Хирьянов

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

Alex Danov

Андрей Рогов

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

PRO100 EGE

Алексей Ковальчук

Таймкоды
00:00 Приветствие
04:30 Зона доставки перебор
14:05 Зона доставки эффективно
27:10 Зона доставки (кольцо) перебор
34:55 Зона доставки (кольцо) эффективно
44:05 Доставка почты перебор
53:00 Доставка почты эффективно
01:04:15 Доставка почты два указателя
01:20:40 Доставка почты (кольцо) перебор
01:26:30 Доставка почты (кольцо) эффективно
01:35:15 Доставка почты (кольцо) два указателя
01:47:35 Сумма доставки перебор
01:54:50 Сумма доставки эффективно
02:10:35 Сумма доставки (кольцо) перебор
02:16:40 Сумма доставки (кольцо) эффективно
02:32:10 Окончание и напутствия

[nomad]

Афигеть Алексей в футболке!!! Это что то новенькое

[guootsc]

Спасибо большое, вы очень доходчиво и понятно объясняете, крутой контент!👍👍👍

[lorri_i]

44:06
Решение этой задачи через тайм лайн (сводим задачу к предыдущей, где пункт на каждом км):
n = 500
m = 50
b = [[randint(1, 10000), randint(1, 1000)] for _ in range(n)]
l = max([b[i][0] for i in range(len(b))])
a = [0] * (l + 1)

for i in range(n):
km, k = b[i]
c = k // 9 if k % 9 == 0 else k // 9 + 1
a[km] = c
print(a)
mxA = 0
for i in range(l+1):
if a[i] > 0:
s = 0
for j in range(l+1):
if abs(i - j) <= m:
s += a[j]
mxA = max(s, mxA)
print(mxA)

Вот файл Б (костыль не нужен)
l = max([b[i][0] for i in range(len(b))])
a = [0] * (l + 1)

for i in range(n):
km, k = b[i]
c = k // 9 if k % 9 == 0 else k // 9 + 1
a[km] = c

mx = s = sum(a[:2 * m + 1])
for i in range(m+1, l + 1 - m):
s = s - a[i - (m + 1)] + a[i + m]
if a[i] > 0: mx = max(s, mx)
print(mx)

[maxrichard]

а где брать файлики к заданиям со стрима?

[ludmilazvyagina]

Алексей. вопрос по задаче Доставка почты эффективно . Имеем ли мы право писать mx= s = sum(b[:2*m+1]), ведь в общем случае b[m] может быть равно 0 ?

[ludmilazvyagina]

Алексей, в программе Доставка почты(кольцо)два указателя у Вас ошибка, т.к., например, для нулевого почтамта Вы рассматриваете зону доставки только в одну сторону от него. В программе должно быть
for i in range(1, 2*n):
while end + 1 != 2*n and a[end+1][0] - a[i][0] <= m:

[tayagamer]

Алексей, в "Сумма доставки эффективно" не хватает сортировки списка по первому элементу. Программа сработала только потому, что на нулевом пункте был фактически ответ. Можете глянуть, в остальных s мы получаем дикие отрицательные числа. Пункты не отсортированы по километрам, поэтому мы то и дело вычитаем из меньшего большее --> получаем отрицательные значения.
Очевидно это становится при условии с минимальной общей суммой, очень долго пыталась понять, откуда ответы по типу -205118194058883 получаются))

[adamnagoy]

2:23:56 у меня было такое приложение в гугл плей с названием "cheaper", оно еще там, но уже наверное не работает

[hamsandwichhh]

почему в кольцевом варианте задачи с обедами не надо удваивать список для пункта а?

[qusyl]

Я не совсем понял идею с зоной доставки, а именно с if abs(i-j)<=m: s+= a[j].Если, например, расстояние m = 5000, разность (i-j)=2500, где j = 2500, то значит мы можем доставить 2500 сумок?Я просто не могу понять, почему именно так, мы же можем и 3000....

[nomad]

автомагистраль на 1/7 длины экватора)))

[igelsch_di]

Может, я прям жестко туплю, но когда я прочитала условие третьей по счету задачи (дома на автомагистрали, 1:14:52), я изначально подумала, что робот может проходить M километров только в одну сторону, а не M километров влево и потом, вернувшись на почту, ещё М километров вправо от нее. А мы во всех трех решениях считаем, как будто у него заряда хватит на два "захода", хотя одного заряда у него должно по идее хватать только на один заход. Я в голове прикидывала, что для каждого варианта расположения почтамта надо еще сранивать два варианта марщрута робота (робот прошел М км влево или робот прошел М км вправо) и выбирать тот, где робот доставил больше пакетов.
Если решать так, как в видео, то получается, что робот на одной зарядке проходит 2*M км (без учета возвращения с дальних домов на почту), а не М км 🤔 или я не права?

[mnxxx]

спасибо вам большое за веб, реально научился решать эти типы задач. Вы очень доходчиво объясняете :)

[shishan]

В первой задаче на 11:59, у нас роль цеха играет i, а j - это пункт питания, в который мы доставляем из цеха i?
например
i j
1 1
1 2
1 3
1 4
и тд. То есть i - это цех, и из цеха мы доставляем во все пункты питания j на допустимом расстоянии?

[ivanpolyakov]

а почему мы не учли то, что нельзя больше одного неполного контейнера доставлять в первой задачи?