WEBVTT

00:00:31.587 --> 00:00:37.288
Этика и Хедж оказываются
на первом этаже огромной башни.

00:00:37.288 --> 00:00:41.945
Энергетические барьеры отделяют их
от следующей цели —

00:00:41.945 --> 00:00:43.945
Модуля творения.

00:00:52.587 --> 00:00:56.169
Чтобы добраться до него, Этике нужно
использовать три энергетических потока,

00:00:56.169 --> 00:00:57.409
которые поднимут её вверх.

00:00:57.409 --> 00:01:03.359
Как только она сделает шаг вперёд,
таймер начнёт отсчёт 60 секунд.

00:01:07.359 --> 00:01:11.659
В задней части зала расположен
резервуар из невидимых башен,

00:01:11.659 --> 00:01:14.735
между которыми может удерживаться энергия.

00:01:14.735 --> 00:01:18.865
По прошествии минуты
поток энергии обрушится сверху,

00:01:18.865 --> 00:01:21.015
заполняя отсеки один за другим.

00:01:21.015 --> 00:01:25.495
Силовое поле не позволяет энергии
выливаться спереди или сзади.

00:01:25.495 --> 00:01:27.625
В течение 60 спокойных секунд

00:01:27.625 --> 00:01:32.723
Этика и Хедж должны определить,
сколько единиц энергии будет спущено.

00:01:32.723 --> 00:01:34.423
Для каждого из трёх этапов

00:01:34.423 --> 00:01:38.088
они должны вычислить точное количество
энергии, которое заполнит резервуар.

00:01:38.088 --> 00:01:41.938
Если им это удастся,
энергия поднимет их выше.

00:01:41.938 --> 00:01:46.558
Но если они ошибутся,
энергетический лифт выйдет из строя

00:01:46.558 --> 00:01:48.048
и они упадут.

00:01:48.048 --> 00:01:51.348
На стенах висят диаграммы с примерами.

00:01:51.348 --> 00:01:55.618
Такая конфигурация может
удержать 2 единицы энергии,

00:01:55.618 --> 00:02:00.735
а такая удержит 4 — 3 здесь и 1 здесь.

00:02:00.735 --> 00:02:03.275
Такая конфигурация тоже удержит 4,

00:02:03.275 --> 00:02:06.688
потому что энергия
из правого отсека выльется.

00:02:06.688 --> 00:02:08.908
Энергия подаётся сверху таким образом,

00:02:08.908 --> 00:02:13.538
что она выльется только в том случае,
если её ничто не будет удерживать.

00:02:13.538 --> 00:02:18.865
Хедж может за раз сделать видимым один
столбик блоков и подсчитать его высоту,

00:02:18.865 --> 00:02:22.725
но он не может рассмотреть
всю конструкцию целиком.

00:02:22.725 --> 00:02:25.530
Как Этике следует запрограммировать
Хеджа, чтобы рассчитать,

00:02:25.530 --> 00:02:29.340
сколько энергии поместится
в каждый резервуар?

00:02:29.340 --> 00:02:38.805
Приостановите видео,
чтобы найти ответ самостоятельно.

00:02:38.805 --> 00:02:41.635
Один из способов взглянуть
на ситуацию следующий:

00:02:41.635 --> 00:02:44.810
каждая незаполненная клетка удерживает
энергию только в том случае,

00:02:44.810 --> 00:02:48.790
если где-то левее есть стена

00:02:48.790 --> 00:02:51.517
и где-то правее есть стена.

00:02:51.517 --> 00:02:54.552
Но если Хедж будет проверять
эти условия для каждой клетки,

00:02:54.552 --> 00:02:56.322
на это уйдёт очень много времени.

00:02:56.322 --> 00:03:01.185
Что, если он будет одновременно
рассматривать весь столбик блоков?

00:03:01.185 --> 00:03:05.025
Например, сколько единиц энергии
может удержать эта конфигурация?

00:03:05.025 --> 00:03:10.389
Приостановите видео,
чтобы найти ответ самостоятельно.

00:03:10.389 --> 00:03:13.759
Давайте проанализируем задачу,
рассмотрев наш пример.

00:03:13.759 --> 00:03:15.914
Здесь 5 столбиков блоков.

00:03:15.914 --> 00:03:20.484
Крайний левый не может удерживать энергию,
потому что он самый высокий.

00:03:20.484 --> 00:03:23.118
Второй может уместить 3 единицы,

00:03:23.118 --> 00:03:27.244
потому что они будут удерживаться
этими двумя столбиками из 4-х блоков.

00:03:27.244 --> 00:03:32.186
Мы получаем 3 единицы,
взяв высоту верхнего предела 4

00:03:32.186 --> 00:03:36.346
и отняв высоту данного столбика,
то есть 4 минус 1.

00:03:36.346 --> 00:03:41.808
Третий столбик такой же:
4 слева и 4 справа, а высота — 3,

00:03:41.808 --> 00:03:46.537
то есть 4 минус 3 равно 1 отсеку.

00:03:46.537 --> 00:03:50.957
У четвёртого и пятого столбика
справа нет столбиков, которые выше их,

00:03:50.957 --> 00:03:53.427
поэтому они не будут удерживать энергию.

00:03:53.427 --> 00:03:57.245
На основе этой идеи
можно создать алгоритм.

00:03:57.245 --> 00:04:01.025
Взяв один столбик за точку отсчёта,

00:04:01.025 --> 00:04:05.436
Хедж может двигаться влево, чтобы найти
высоту самого высокого столбика,

00:04:05.436 --> 00:04:08.156
а затем сделать то же самое,
двигаясь вправо,

00:04:08.156 --> 00:04:12.833
и выбрать меньшее из этих значений
как высоту, которой достигнет энергия.

00:04:12.833 --> 00:04:15.963
Если результат выше
взятого за основу столбика,

00:04:15.963 --> 00:04:18.537
вычтите из него высоту исходного столбика.

00:04:18.537 --> 00:04:23.634
Результатом будет количество отсеков
этого столбика, где энергия удержится.

00:04:23.634 --> 00:04:27.194
Если же он равен или ниже
взятого за основу столбика,

00:04:27.194 --> 00:04:29.397
энергия выльется.

00:04:29.397 --> 00:04:32.917
Хедж может применить алгоритм
ко всему резервуару с помощью цикла,

00:04:32.917 --> 00:04:38.662
который начинается с крайнего левого
столбика и двигается по столбикам вправо.

00:04:38.662 --> 00:04:43.671
Он выполнит одни и те же шаги для каждого
столбика: найдёт самый высокий слева,

00:04:43.671 --> 00:04:47.231
самый высокий справа;
возьмёт меньшее из этих значений,

00:04:47.231 --> 00:04:49.318
вычтет из него высоту исходного столбика

00:04:49.318 --> 00:04:53.178
и увеличит общий итог,
если это положительное число.

00:04:53.178 --> 00:04:56.848
Цикл повторится столько раз,
сколько у нас столбиков.

00:04:56.848 --> 00:05:00.798
Это поможет достичь цели, но на большой
резервуар уйдёт много времени.

00:05:00.798 --> 00:05:05.328
Для каждого шага Хедж должен повторить
движение влево и вправо.

00:05:05.328 --> 00:05:10.280
Если у нас N столбиков, ему придётся
рассмотреть N столбиков N раз.

00:05:10.280 --> 00:05:12.260
Есть ли более быстрый способ?

00:05:12.260 --> 00:05:15.608
Вот один способ сэкономить время:
прежде чем что-либо делать,

00:05:15.608 --> 00:05:17.468
Хедж может начать слева

00:05:17.468 --> 00:05:21.338
и фиксировать самый высокий
столбик по нарастающей.

00:05:21.338 --> 00:05:25.098
Здесь это будет 2, тут тоже 2,
потому что первый столбик был выше,

00:05:25.098 --> 00:05:27.848
затем 4, 4, 4.

00:05:27.848 --> 00:05:30.628
Затем он может найти самый
высокий столбик справа,

00:05:30.628 --> 00:05:36.882
выполнив то же самое
справа налево: 1, 3, 4, 4, 4.

00:05:36.882 --> 00:05:40.722
В итоге у него в памяти
будет вот такая таблица.

00:05:40.722 --> 00:05:44.822
Теперь Хедж может пройти по столбикам
ещё один раз, чтобы подсчитать,

00:05:44.822 --> 00:05:50.001
сколько энергии будет над каждым из них,
с помощью того же уравнения:

00:05:50.001 --> 00:05:53.638
меньшее из сохранённых
значений слева и справа

00:05:53.638 --> 00:05:56.708
минус высота текущего столбика.

00:05:56.708 --> 00:06:02.293
Вместо рассмотрения N столбиков N раз
он рассмотрит N столбиков всего 3 раза;

00:06:02.293 --> 00:06:04.573
это называется линейным временем.

00:06:04.573 --> 00:06:07.814
Есть способы ещё более
оптимизировать это решение,

00:06:07.814 --> 00:06:10.564
но нашим героям этого достаточно.

00:06:10.564 --> 00:06:12.334
Этика и Хедж сплочённо работают.

00:06:14.992 --> 00:06:18.836
Первый поток совсем не сложный,
и они поднимаются на следующий уровень.

00:06:21.573 --> 00:06:23.583
Второй немного сложнее.

00:06:33.051 --> 00:06:36.911
Третий — самый большой,
с дюжинами столбиков.

00:06:36.911 --> 00:06:41.344
Отсчёт таймера приближается к нулю,
но программа Этики работает быстро.

00:06:41.344 --> 00:06:44.308
Она вовремя поворачивает руль
в нужное положение,

00:06:49.015 --> 00:06:51.935
и энергия поднимает их к Модулю творения.

00:06:55.640 --> 00:07:01.067
Как и первый артефакт,
он отображает сцену из прошлого.

00:07:01.067 --> 00:07:03.187
Мировая машина всё изменила,

00:07:03.187 --> 00:07:06.856
и Этике, которая была главным
инженером по робототехнике,

00:07:06.856 --> 00:07:08.826
это совсем не понравилось.

00:07:08.826 --> 00:07:11.966
Когда возвели Брэдбарьер и люди
не могли выбраться за его пределы,

00:07:11.966 --> 00:07:14.586
она поняла, что что-то не так.

00:07:14.586 --> 00:07:16.676
Поэтому она создала три артефакта,

00:07:16.676 --> 00:07:21.221
которые могли восстановить силу,
творчество и память людей,

00:07:21.221 --> 00:07:23.661
и тайно доставила их в три сообщества.

00:07:23.661 --> 00:07:26.679
Но прежде чем она смогла рассказать людям,
как ими пользоваться,

00:07:26.679 --> 00:07:29.959
правительство узнало об этой попытке
и приказало роботам арестовать её

00:07:29.959 --> 00:07:31.889
и других программистов.

00:07:31.889 --> 00:07:35.209
Последним, что она создала
с помощью мировой машины,

00:07:35.209 --> 00:07:39.662
был робот, который сможет защитить
древнее устройство от невежества,

00:07:39.662 --> 00:07:42.329
спрятав его в огромном лабиринте.

00:07:42.329 --> 00:07:44.743
Она назвала его Хедж.

00:07:51.801 --> 00:07:55.631
Внезапно энергетический лифт начинает
мигать, а затем полностью угасает.