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

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

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

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

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

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

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

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

0:01:14.735,0:01:18.865
По прошествии минуты[br]поток энергии обрушится сверху,

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

0:01:21.015,0:01:25.495
Силовое поле не позволяет энергии[br]выливаться спереди или сзади.

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

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

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

0:01:34.423,0:01:38.088
они должны вычислить точное количество[br]энергии, которое заполнит резервуар.

0:01:38.088,0:01:41.938
Если им это удастся,[br]энергия поднимет их выше.

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

0:01:46.558,0:01:48.048
и они упадут.

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

0:01:51.348,0:01:55.618
Такая конфигурация может[br]удержать 2 единицы энергии,

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

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

0:02:03.275,0:02:06.688
потому что энергия[br]из правого отсека выльется.

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

0:02:08.908,0:02:13.538
что она выльется только в том случае,[br]если её ничто не будет удерживать.

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

0:02:18.865,0:02:22.725
но он не может рассмотреть[br]всю конструкцию целиком.

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

0:02:25.530,0:02:29.340
сколько энергии поместится[br]в каждый резервуар?

0:02:29.340,0:02:38.805
Приостановите видео,[br]чтобы найти ответ самостоятельно.

0:02:38.805,0:02:41.635
Один из способов взглянуть[br]на ситуацию следующий:

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

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

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

0:02:51.517,0:02:54.552
Но если Хедж будет проверять[br]эти условия для каждой клетки,

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

0:02:56.322,0:03:01.185
Что, если он будет одновременно[br]рассматривать весь столбик блоков?

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

0:03:05.025,0:03:10.389
Приостановите видео,[br]чтобы найти ответ самостоятельно.

0:03:10.389,0:03:13.759
Давайте проанализируем задачу,[br]рассмотрев наш пример.

0:03:13.759,0:03:15.914
Здесь 5 столбиков блоков.

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

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

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

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

0:03:32.186,0:03:36.346
и отняв высоту данного столбика,[br]то есть 4 минус 1.

0:03:36.346,0:03:41.808
Третий столбик такой же:[br]4 слева и 4 справа, а высота — 3,

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

0:03:46.537,0:03:50.957
У четвёртого и пятого столбика[br]справа нет столбиков, которые выше их,

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

0:03:53.427,0:03:57.245
На основе этой идеи[br]можно создать алгоритм.

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

0:04:01.025,0:04:05.436
Хедж может двигаться влево, чтобы найти[br]высоту самого высокого столбика,

0:04:05.436,0:04:08.156
а затем сделать то же самое,[br]двигаясь вправо,

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

0:04:12.833,0:04:15.963
Если результат выше[br]взятого за основу столбика,

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

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

0:04:23.634,0:04:27.194
Если же он равен или ниже[br]взятого за основу столбика,

0:04:27.194,0:04:29.397
энергия выльется.

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

0:04:32.917,0:04:38.662
который начинается с крайнего левого[br]столбика и двигается по столбикам вправо.

0:04:38.662,0:04:43.671
Он выполнит одни и те же шаги для каждого[br]столбика: найдёт самый высокий слева,

0:04:43.671,0:04:47.231
самый высокий справа;[br]возьмёт меньшее из этих значений,

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

0:04:49.318,0:04:53.178
и увеличит общий итог,[br]если это положительное число.

0:04:53.178,0:04:56.848
Цикл повторится столько раз,[br]сколько у нас столбиков.

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

0:05:00.798,0:05:05.328
Для каждого шага Хедж должен повторить[br]движение влево и вправо.

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

0:05:10.280,0:05:12.260
Есть ли более быстрый способ?

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

0:05:15.608,0:05:17.468
Хедж может начать слева

0:05:17.468,0:05:21.338
и фиксировать самый высокий[br]столбик по нарастающей.

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

0:05:25.098,0:05:27.848
затем 4, 4, 4.

0:05:27.848,0:05:30.628
Затем он может найти самый[br]высокий столбик справа,

0:05:30.628,0:05:36.882
выполнив то же самое[br]справа налево: 1, 3, 4, 4, 4.

0:05:36.882,0:05:40.722
В итоге у него в памяти[br]будет вот такая таблица.

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

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

0:05:50.001,0:05:53.638
меньшее из сохранённых[br]значений слева и справа

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

0:05:56.708,0:06:02.293
Вместо рассмотрения N столбиков N раз[br]он рассмотрит N столбиков всего 3 раза;

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

0:06:04.573,0:06:07.814
Есть способы ещё более[br]оптимизировать это решение,

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

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

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

0:06:21.573,0:06:23.583
Второй немного сложнее.

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

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

0:06:41.344,0:06:44.308
Она вовремя поворачивает руль[br]в нужное положение,

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

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

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

0:07:03.187,0:07:06.856
и Этике, которая была главным[br]инженером по робототехнике,

0:07:06.856,0:07:08.826
это совсем не понравилось.

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

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

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

0:07:16.676,0:07:21.221
которые могли восстановить силу,[br]творчество и память людей,

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

0:07:23.661,0:07:26.679
Но прежде чем она смогла рассказать людям,[br]как ими пользоваться,

0:07:26.679,0:07:29.959
правительство узнало об этой попытке[br]и приказало роботам арестовать её

0:07:29.959,0:07:31.889
и других программистов.

0:07:31.889,0:07:35.209
Последним, что она создала[br]с помощью мировой машины,

0:07:35.209,0:07:39.662
был робот, который сможет защитить[br]древнее устройство от невежества,

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

0:07:42.329,0:07:44.743
Она назвала его Хедж.

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