1
00:00:31,587 --> 00:00:37,288
Этика и Хедж оказываются
на первом этаже огромной башни.

2
00:00:37,288 --> 00:00:41,945
Энергетические барьеры отделяют их
от следующей цели —

3
00:00:41,945 --> 00:00:43,945
Модуля творения.

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

5
00:00:56,169 --> 00:00:57,409
которые поднимут её вверх.

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

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

8
00:01:11,659 --> 00:01:14,735
между которыми может удерживаться энергия.

9
00:01:14,735 --> 00:01:18,865
По прошествии минуты
поток энергии обрушится сверху,

10
00:01:18,865 --> 00:01:21,015
заполняя отсеки один за другим.

11
00:01:21,015 --> 00:01:25,495
Силовое поле не позволяет энергии
выливаться спереди или сзади.

12
00:01:25,495 --> 00:01:27,625
В течение 60 спокойных секунд

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

14
00:01:32,723 --> 00:01:34,423
Для каждого из трёх этапов

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

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

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

18
00:01:46,558 --> 00:01:48,048
и они упадут.

19
00:01:48,048 --> 00:01:51,348
На стенах висят диаграммы с примерами.

20
00:01:51,348 --> 00:01:55,618
Такая конфигурация может
удержать 2 единицы энергии,

21
00:01:55,618 --> 00:02:00,735
а такая удержит 4 — 3 здесь и 1 здесь.

22
00:02:00,735 --> 00:02:03,275
Такая конфигурация тоже удержит 4,

23
00:02:03,275 --> 00:02:06,688
потому что энергия
из правого отсека выльется.

24
00:02:06,688 --> 00:02:08,908
Энергия подаётся сверху таким образом,

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

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

27
00:02:18,865 --> 00:02:22,725
но он не может рассмотреть
всю конструкцию целиком.

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

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

30
00:02:29,340 --> 00:02:38,805
Приостановите видео,
чтобы найти ответ самостоятельно.

31
00:02:38,805 --> 00:02:41,635
Один из способов взглянуть
на ситуацию следующий:

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

33
00:02:44,810 --> 00:02:48,790
если где-то левее есть стена

34
00:02:48,790 --> 00:02:51,517
и где-то правее есть стена.

35
00:02:51,517 --> 00:02:54,552
Но если Хедж будет проверять
эти условия для каждой клетки,

36
00:02:54,552 --> 00:02:56,322
на это уйдёт очень много времени.

37
00:02:56,322 --> 00:03:01,185
Что, если он будет одновременно
рассматривать весь столбик блоков?

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

39
00:03:05,025 --> 00:03:10,389
Приостановите видео,
чтобы найти ответ самостоятельно.

40
00:03:10,389 --> 00:03:13,759
Давайте проанализируем задачу,
рассмотрев наш пример.

41
00:03:13,759 --> 00:03:15,914
Здесь 5 столбиков блоков.

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

43
00:03:20,484 --> 00:03:23,118
Второй может уместить 3 единицы,

44
00:03:23,118 --> 00:03:27,244
потому что они будут удерживаться
этими двумя столбиками из 4-х блоков.

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

46
00:03:32,186 --> 00:03:36,346
и отняв высоту данного столбика,
то есть 4 минус 1.

47
00:03:36,346 --> 00:03:41,808
Третий столбик такой же:
4 слева и 4 справа, а высота — 3,

48
00:03:41,808 --> 00:03:46,537
то есть 4 минус 3 равно 1 отсеку.

49
00:03:46,537 --> 00:03:50,957
У четвёртого и пятого столбика
справа нет столбиков, которые выше их,

50
00:03:50,957 --> 00:03:53,427
поэтому они не будут удерживать энергию.

51
00:03:53,427 --> 00:03:57,245
На основе этой идеи
можно создать алгоритм.

52
00:03:57,245 --> 00:04:01,025
Взяв один столбик за точку отсчёта,

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

54
00:04:05,436 --> 00:04:08,156
а затем сделать то же самое,
двигаясь вправо,

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

56
00:04:12,833 --> 00:04:15,963
Если результат выше
взятого за основу столбика,

57
00:04:15,963 --> 00:04:18,537
вычтите из него высоту исходного столбика.

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

59
00:04:23,634 --> 00:04:27,194
Если же он равен или ниже
взятого за основу столбика,

60
00:04:27,194 --> 00:04:29,397
энергия выльется.

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

62
00:04:32,917 --> 00:04:38,662
который начинается с крайнего левого
столбика и двигается по столбикам вправо.

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

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

65
00:04:47,231 --> 00:04:49,318
вычтет из него высоту исходного столбика

66
00:04:49,318 --> 00:04:53,178
и увеличит общий итог,
если это положительное число.

67
00:04:53,178 --> 00:04:56,848
Цикл повторится столько раз,
сколько у нас столбиков.

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

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

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

71
00:05:10,280 --> 00:05:12,260
Есть ли более быстрый способ?

72
00:05:12,260 --> 00:05:15,608
Вот один способ сэкономить время:
прежде чем что-либо делать,

73
00:05:15,608 --> 00:05:17,468
Хедж может начать слева

74
00:05:17,468 --> 00:05:21,338
и фиксировать самый высокий
столбик по нарастающей.

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

76
00:05:25,098 --> 00:05:27,848
затем 4, 4, 4.

77
00:05:27,848 --> 00:05:30,628
Затем он может найти самый
высокий столбик справа,

78
00:05:30,628 --> 00:05:36,882
выполнив то же самое
справа налево: 1, 3, 4, 4, 4.

79
00:05:36,882 --> 00:05:40,722
В итоге у него в памяти
будет вот такая таблица.

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

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

82
00:05:50,001 --> 00:05:53,638
меньшее из сохранённых
значений слева и справа

83
00:05:53,638 --> 00:05:56,708
минус высота текущего столбика.

84
00:05:56,708 --> 00:06:02,293
Вместо рассмотрения N столбиков N раз
он рассмотрит N столбиков всего 3 раза;

85
00:06:02,293 --> 00:06:04,573
это называется линейным временем.

86
00:06:04,573 --> 00:06:07,814
Есть способы ещё более
оптимизировать это решение,

87
00:06:07,814 --> 00:06:10,564
но нашим героям этого достаточно.

88
00:06:10,564 --> 00:06:12,334
Этика и Хедж сплочённо работают.

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

90
00:06:21,573 --> 00:06:23,583
Второй немного сложнее.

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

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

93
00:06:41,344 --> 00:06:44,308
Она вовремя поворачивает руль
в нужное положение,

94
00:06:49,015 --> 00:06:51,935
и энергия поднимает их к Модулю творения.

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

96
00:07:01,067 --> 00:07:03,187
Мировая машина всё изменила,

97
00:07:03,187 --> 00:07:06,856
и Этике, которая была главным
инженером по робототехнике,

98
00:07:06,856 --> 00:07:08,826
это совсем не понравилось.

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

100
00:07:11,966 --> 00:07:14,586
она поняла, что что-то не так.

101
00:07:14,586 --> 00:07:16,676
Поэтому она создала три артефакта,

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

103
00:07:21,221 --> 00:07:23,661
и тайно доставила их в три сообщества.

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

105
00:07:26,679 --> 00:07:29,959
правительство узнало об этой попытке
и приказало роботам арестовать её

106
00:07:29,959 --> 00:07:31,889
и других программистов.

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

108
00:07:35,209 --> 00:07:39,662
был робот, который сможет защитить
древнее устройство от невежества,

109
00:07:39,662 --> 00:07:42,329
спрятав его в огромном лабиринте.

110
00:07:42,329 --> 00:07:44,743
Она назвала его Хедж.

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