|
Задача про дома и дождь | ☑ | ||
---|---|---|---|---|
0
DTX 4th
26.05.20
✎
16:50
|
Есть массив чисел. Каждое число - это высота дома, например:
https://i.imgur.com/OOwGCLS.png Это для массива 5 1 3 0 4. Пошёл дождь и пространство между домами заполнилось водой. Нужно посчитать объём воды, которая скопилась между домами. Вот так вода заполнит исходный пример: https://i.imgur.com/fOXWNTH.png |
|||
91
seevkik
26.05.20
✎
19:12
|
Можно без нахождения максимума сделать цикл в цикле пока они не встретятся, чутка дешевле выйдет, только надо определять переменную которая показывает какая сторона выше на данной итерации
|
|||
92
RomanYS
26.05.20
✎
19:12
|
(85) красиво
|
|||
93
Cyberhawk
26.05.20
✎
19:14
|
(92) Но два прохода
|
|||
94
PR
26.05.20
✎
19:15
|
(85) Прикольно, да
Можно, кстати, даже в один цикл сделать :)) |
|||
95
seevkik
26.05.20
✎
19:16
|
(93) два не полных прохода, это в счёт?
|
|||
96
Ненавижу 1С
гуру
26.05.20
✎
19:17
|
(85) по-твоему там только две лужи воды образуется? это не так
|
|||
97
Cyberhawk
26.05.20
✎
19:19
|
(95) Почему неполных - максимум чтоб найти это один проход, далее с двух сторон накопить пустоту - вот и второй проход
|
|||
98
seevkik
26.05.20
✎
19:19
|
(97) упс) а если (91) ?
|
|||
99
PR
26.05.20
✎
19:20
|
(98) Цикл в цикле - это больше двух
|
|||
100
DTX 4th
26.05.20
✎
19:21
|
(88) с++
(89) Да ладно, все понятно же Код сложнее читать (90) На js не проще такие поделки писать?) Я codepen.io пользую (92) Я тоже порадовался, что еще что-то могу) (93) O(N). Остальное не важно) (94) Как? (96) Не понял вопроса. (98) Похоже на изврат) Но давай код :) |
|||
101
seevkik
26.05.20
✎
19:21
|
(99) ну так количества итераций не будет больше количества элементов
|
|||
102
Ненавижу 1С
гуру
26.05.20
✎
19:22
|
(54) а если..., все написано в (30) и смотри (90)
|
|||
103
PR
26.05.20
✎
19:23
|
(100) А, не, не получается
|
|||
104
Ненавижу 1С
гуру
26.05.20
✎
19:24
|
(100) или я не понял решения в (85) или из него следует, что считается объем двух резервуаров только - до максимума и после
|
|||
105
mistеr
26.05.20
✎
19:25
|
(104) Аналогично
|
|||
106
mistеr
26.05.20
✎
19:26
|
(87) Вроде правильно считает.
Только зачем СписокЗначений, когда есть массив? |
|||
107
PR
26.05.20
✎
19:27
|
(104) Не понял
|
|||
108
Cyberhawk
26.05.20
✎
19:28
|
Так (85) походу работает, только если максимум один, так?
|
|||
109
PR
26.05.20
✎
19:29
|
(106) Как ты сделаешь реквизит формы типа Массив?
|
|||
110
PR
26.05.20
✎
19:29
|
(108) Нет
|
|||
111
seevkik
26.05.20
✎
19:30
|
(108) поэтому нужно определить идентификатор максимума, а не значение
|
|||
112
DTX 4th
26.05.20
✎
19:30
|
(102) Какая сложность получается в (90)?
(104)(105) Ну так по сути самый большой дом разбивает все дома на два резервуара. (108) Не, их может быть несколько. Главное чтобы слева и справа шли к одному и тому же. Ну и вот для наглядности мб кому пригодится: https://i.imgur.com/IrkfjRV.png |
|||
113
seevkik
26.05.20
✎
19:32
|
(100) Блин, код получается суперговнокодом, типа
"если левыйбольше тогда правый = массив[правыйитератор] иначе Левый = массив[левыйитератор]" Не получается сейчас думать, но общая идея такая Находим этажи слева, в том же коде находим этажи справа, сравниваем какой больше и идём с меньшего к большему попутно считая сколько воды заполняем, если представить визуально - поднятие линейки вверх с отметкой заполненности |
|||
114
Ненавижу 1С
гуру
26.05.20
✎
19:33
|
112) резрвуаров может и пять получиться в итоге
|
|||
115
Cyberhawk
26.05.20
✎
19:33
|
"их может быть несколько. Главное чтобы слева и справа шли к одному и тому же" // А к какому идти тогда, если их несколько одинаковых, к любому?
|
|||
116
DTX 4th
26.05.20
✎
19:34
|
||||
117
seevkik
26.05.20
✎
19:35
|
(115) (111)
|
|||
118
DTX 4th
26.05.20
✎
19:35
|
(115) Вот для двух:
https://i.imgur.com/rUAhwWx.png |
|||
119
Cyberhawk
26.05.20
✎
19:35
|
(116) А чем тогда M и L отличаются?
|
|||
120
Ненавижу 1С
гуру
26.05.20
✎
19:35
|
(112) в (90) сложность O(N)
|
|||
121
Cyberhawk
26.05.20
✎
19:36
|
А, L это локальный максимум текущего шага, изначально равен высоте дома первого шага
|
|||
122
PR
26.05.20
✎
19:37
|
(112) Эээ, нихрена не на два
3 0 3 0 5 0 3 0 3 Сколько резервуаров? https://yadi.sk/i/mTv1DEDdHsjeIg |
|||
123
seevkik
26.05.20
✎
19:39
|
(122) два с одинаковой высотой разделенные максимумом с высотой 5
|
|||
124
PR
26.05.20
✎
19:40
|
(123) Че?
|
|||
125
PR
26.05.20
✎
19:41
|
+(124) Так-то вроде 4, я даже раскрасил же
|
|||
126
seevkik
26.05.20
✎
19:41
|
(122) ну, суть в том, что расчета фактически происходит два - слева и справа, а не в том, что там фактически 4 резервуара)
одумайте мысль в (113) плз |
|||
127
RomanYS
26.05.20
✎
19:41
|
(122) Это уже терминология, что называть "резервуаром". По факту в (85) корректное решение и единственное подходящее под ограничения (55).
Пусть будет две "области" |
|||
128
seevkik
26.05.20
✎
19:42
|
Додумайте* (126)
|
|||
129
Ненавижу 1С
гуру
26.05.20
✎
19:42
|
(122) вот и я также думаю
я вообще могу этих луж нарисовать, они все будут умньшаться по уровню от максимума влево и вправо https://cdn1.radikalno.ru/uploads/2020/5/26/fd20b06a3b533fd96b638e94719522e3-full.png |
|||
130
PR
26.05.20
✎
19:42
|
(126) Слова резервуар и расчет для тебя синонимы?
|
|||
131
seevkik
26.05.20
✎
19:43
|
(127) да, две "области" самая верная терминология)
|
|||
132
DTX 4th
26.05.20
✎
19:44
|
(120) Не похоже.
Берем [5,4,3,2,1] (большую убывающую лесенку) Далее: Выбираем самый левый дом за базовый. Ищем следующий базовый от текущего базового как: - первый слева направо, выше текущего - если таковых нет: то крайний справа из тех, что с максимальной высотой На втором пункте много побегать придется, не? (130)(129) Вы о разном. Сначала PR не понял (104) в (107), а теперь топит за (104) :) Касательно (104), глянь 116. Должно стать понятнее) |
|||
133
RomanYS
26.05.20
✎
19:44
|
(129) Не важно сколько луж/дыр/резервуаров. Важно, что проход от краев к одному из максимумов позволяет избавиться от необходимости использовать допмассивы
|
|||
134
seevkik
26.05.20
✎
19:45
|
(130) может не будем углубляться, это не относится к теме, тут ошибочка вышла, верно
|
|||
135
Ненавижу 1С
гуру
26.05.20
✎
19:46
|
(127) категорически не согласен
во-первых резервуаров с разными уровнями может быть больше, см рисунок (129) во-вторых мое решение в (90) вполне O(n) и с доп памятью O(1) |
|||
136
RomanYS
26.05.20
✎
19:47
|
(135) вложенный цикл, не может там быть O(N)
|
|||
137
PR
26.05.20
✎
19:48
|
(129) Да блин, не тупи, в (85) все верно, просто он скудно описал мысль
Ищешь номер максимально высокого дома (любого, если их несколько) Потом слева и справа идешь к этому максимуму с шагом один дом и смотришь, сколько воды умещается между текущим домом и следующим При этом в расчете берешь высоту дома, максимальную в твоем проходе (отдельно для левого, отдельно для правого) |
|||
138
Ненавижу 1С
гуру
26.05.20
✎
19:48
|
(136) а ты так определяешь? а что итератор внешнего цикла двигается только внутренним ничего не говорит?
|
|||
139
Ненавижу 1С
гуру
26.05.20
✎
19:49
|
(137) а потом запоминаем следующий максимальный и т.д., этого в (85) не было написано
|
|||
140
PR
26.05.20
✎
19:50
|
(132) Гражданин, о чем вы?
В (107) я сказал, что Ненавижу 1С в (104) не понял |
|||
141
PR
26.05.20
✎
19:51
|
(135) Слушай, не гунди, в (85), похоже, оптимальный вариант :))
|
|||
142
DTX 4th
26.05.20
✎
19:52
|
(139) Как не было?
Вот же: >Идем слева, запоминая высоту самого высокого дома - L читать как "запоминая высоту самого высокого встретившегося дома" (135) Ты на (132) не ответил. |
|||
143
PR
26.05.20
✎
19:53
|
(139) Я же и говорю, скудно написал, с предполагаемыми домысливаниями
|
|||
144
Ненавижу 1С
гуру
26.05.20
✎
19:54
|
(143) тогда я и в (30) написал решение )))
(142) на что я не ответил? |
|||
145
RomanYS
26.05.20
✎
19:55
|
(138) Это просто "извращение" с учетом возврата ( var nextBased = based;...based = nextBased;) по сути это обычный вложенный цикл и сложность скорее всего О(N^2), как бы хитро ты его не обходил :). 100% выше O(N)
|
|||
146
PR
26.05.20
✎
19:56
|
(144) То, что ты в (30) написал, даже с поллитрой никто не разберет, особенно последнее "А потом просто решаем задачу"
|
|||
147
seevkik
26.05.20
✎
19:58
|
Так, в одну итерацию кто-нибудь придумал?
Вот так получается (113) ? |
|||
148
Ненавижу 1С
гуру
26.05.20
✎
19:59
|
Ладно, убедили, еще подумаю
|
|||
149
Ненавижу 1С
гуру
26.05.20
✎
20:00
|
(146) нет там таких слов, ну посчитать объем всегда можно
|
|||
150
DTX 4th
26.05.20
✎
20:01
|
Смотрите, какой я молодец, переписал (90) на js :)
https://codepen.io/DTX/pen/rNOgOqN?editors=1011 И даже подсчет итераций сделал :) "Elems: 40. Iterations: 780" "Elems: 80. Iterations: 3160" Не тянет на О(N) |
|||
151
rphosts
26.05.20
✎
20:05
|
(150) растёт быстрее чем О(N), так что ...
|
|||
152
RomanYS
26.05.20
✎
20:10
|
(150) О(N^2) как и предполагалось в (145). Запусти ещё пару раз для пущей убедительности)
|
|||
153
DTX 4th
26.05.20
✎
20:14
|
(152) Так там же (150) прям в браузере можно код менять, он сразу и выполнится) Удобно, попробуйте
Не понимаю, как кто-то тут на 1С прогают такие вещи) 0 "Elems: 1000. Iterations: 499500" 0 "Elems: 2000. Iterations: 1999000" Ровно O(n2) Я в (132) это и имел в виду. Но если развернуть массив, будет O(N) 0 "Elems: 1000. Iterations: 999" 0 "Elems: 2000. Iterations: 1999" |
|||
154
DTX 4th
26.05.20
✎
20:15
|
Или это не O(N^2)? Че-т я запутался
|
|||
155
seevkik
26.05.20
✎
20:25
|
(154) нарисуй график и посмотри
|
|||
156
DTX 4th
26.05.20
✎
20:29
|
(155) Подтверждаю, O(n^2)
(2n)^2/n^2 = 4 чудеса |
|||
157
Ненавижу 1С
гуру
26.05.20
✎
21:21
|
Все равно я не понимаю, где тот алгоритм, который за O(N) решает
вот автор говорит, потом ищем максимум справа/слева от масимума, но потом его еще и еще надо искать ведь получаются те же O(N^2) вот для подобных случаев: https://cdn1.radikalno.ru/uploads/2020/5/26/ae38d6d3dc59165b2a3ebffc4e303b5c-full.png |
|||
158
Ненавижу 1С
гуру
26.05.20
✎
21:33
|
нашел, спасибо за задачу, вообще огонь решение:
https://tproger.ru/problems/water-accumulated-in-puddles-between-walls/ |
|||
159
Asmody
26.05.20
✎
21:47
|
(158) мне кажется, что приведенное там решение "в один проход" не сработает для случая 2 и более "стаканов"
|
|||
160
Asmody
26.05.20
✎
21:49
|
я мееедленно запускаю IDEA...
|
|||
161
Ненавижу 1С
гуру
26.05.20
✎
21:53
|
(159) да нет, сработает
как всегда всё просто, уровни стаканов все время поднимаются к максимуму |
|||
162
Asmody
26.05.20
✎
22:26
|
надо же - работает!
|
|||
163
Asmody
26.05.20
✎
22:27
|
2 строчки поменять - и можно получить массив заполнения воды.
|
|||
164
Bigbro
27.05.20
✎
04:16
|
(158) а если несколько локальных экстремумов?
32172312 когда у нас не один стакан с неровным дном а конфигурация разбивается на несколько стаканов с отбитым краем. и тоже неровным дном. |
|||
165
seevkik
27.05.20
✎
08:29
|
(157) и ничем не отличается от предложенных мной
|
|||
166
fisher
27.05.20
✎
09:24
|
(157)(158) В (85) же было.
|
|||
167
dezss
27.05.20
✎
09:25
|
(51) Я проверил. Работает.
А тут форум 1с-ников, а не js-ников. Да, это не самый оптимальный вариант. Просто на скорую руку набросал. |
|||
168
fisher
27.05.20
✎
09:35
|
(0) Если до (85) как говоришь сам за 15 минут догадался, то респект.
|
|||
169
fisher
27.05.20
✎
09:39
|
(91) Без нахождения максимума за один проход не получится.
|
|||
170
fisher
27.05.20
✎
09:44
|
Но вообще все эти задачки на собеседованиях если на джуна - я еще могу понять. А на мидла - уже как-то странно.
|
|||
171
seevkik
27.05.20
✎
16:55
|
(169) встречайте говнокод, особо не старался, но полчаса или больше убил. Привет, карантин)
Массив = Новый Массив; Массив.Добавить(1); Массив.Добавить(0); Массив.Добавить(5); Массив.Добавить(5); Массив.Добавить(0); Массив.Добавить(1); Массив.Добавить(17); Массив.Добавить(0); Массив.Добавить(3); Массив.Добавить(1); Массив.Добавить(0); Массив.Добавить(3); Массив.Добавить(1); Массив.Добавить(1); Массив.Добавить(0); ВсегоВоды = 0; Встретились = Ложь; ЛевыйКрайПорядок = 0; ЛевыйКрай = Массив[ЛевыйКрайПорядок]; ЛевыйИтератор = ЛевыйКрайПорядок; ПройденоСлева = 0; ПройденоЭтажейСлева = 0; ПравыйКрайПорядок = Массив.Количество()-1; ПравыйКрай = Массив[ПравыйКрайПорядок]; ПравыйИтератор = ПравыйКрайПорядок; ПройденоСправа = 0; ПройденоЭтажейСправа = 0; КрайИзменится = Ложь; КоличествоЭлементовМассива = Массив.Количество(); Пока Не Встретились Цикл //Шаг вперед ТипШага = ?(ЛевыйКрай>ПравыйКрай,"Справа","Слева"); Если ТипШага = "Слева" Тогда ЛевыйИтератор = ЛевыйИтератор + 1; ПройденоСлева = ПройденоСлева +1; Если Массив[ЛевыйИтератор] > ПравыйКрай ИЛИ Массив[ЛевыйИтератор] > ЛевыйКрай Тогда КрайИзменится = Истина; ПройденоЭтажейСлева = ПройденоЭтажейСлева; Иначе КрайИзменится = Ложь; ПройденоЭтажейСлева = ПройденоЭтажейСлева + Массив[ЛевыйИтератор]; КонецЕсли; Иначе ПравыйИтератор = ПравыйИтератор - 1; ПройденоСправа = ПройденоСправа + 1; Если Массив[ПравыйИтератор] > ЛевыйКрай ИЛИ Массив[ПравыйИтератор] > ПравыйКрай Тогда КрайИзменится = Истина; ПройденоЭтажейСправа = ПройденоЭтажейСправа; Иначе КрайИзменится = Ложь; ПройденоЭтажейСправа = ПройденоЭтажейСправа + Массив[ПравыйИтератор]; КонецЕсли; КонецЕсли; //Расчет воды Если КрайИзменится Тогда Если ТипШага = "Слева" Тогда ВсегоВоды = ВсегоВоды + (ПройденоСлева-1)*ЛевыйКрай - ПройденоЭтажейСлева; ЛевыйКрай = Массив[ЛевыйИтератор]; ЛевыйКрайПорядок = ЛевыйИтератор; ПройденоСлева = 0; ПройденоЭтажейСлева = 0; Иначе ВсегоВоды = ВсегоВоды + (ПройденоСправа-1)*ПравыйКрай - ПройденоЭтажейСправа; ПравыйКрай = Массив[ПравыйИтератор]; ПравыйКрайПорядок = ПравыйИтератор; ПройденоСправа = 0; ПройденоЭтажейСправа = 0; КонецЕсли КонецЕсли; Если ЛевыйИтератор+1 = ПравыйИтератор Тогда Встретились = Истина; КонецЕсли; КонецЦикла; //Загрушка Левого и Правого итератора - последнего стакана КоличествоИтерацийЗагрушки = ПравыйКрайПорядок-ЛевыйКрайПорядок-1; КоличествоЭтажей = 0; Для Счетчик = (ЛевыйКрайПорядок+1) По ЛевыйКрайПорядок+КоличествоИтерацийЗагрушки Цикл КоличествоЭтажей = КоличествоЭтажей + Массив[Счетчик]; //КоличествоИтерацийЗагрушки = КоличествоИтерацийЗагрушки + 1; КонецЦикла; ВсегоВоды = ВсегоВоды + Мин(ПравыйКрай,ЛевыйКрай) * КоличествоИтерацийЗагрушки - КоличествоЭтажей; Сообщить(ВсегоВоды); |
|||
172
fisher
27.05.20
✎
17:49
|
(171) Как работает - пока до конца не понял (что за случай в конце обрабатывается). Но работает вроде как заявлено. Так что респект.
|
|||
173
seevkik
27.05.20
✎
18:20
|
(172) основная идея - шагать вперёд с двух сторон от максимума до следующего максимума и рассчитывать сколько лезет в кусок между этим отрезком, триггер - переменная КрайИзменится как знак того, что надо рассчитать кусок от предыдущего максимума до следующего, загвоздка в том, что в последней итерации край не меняется, они просто встречаются и последний стакан остаётся не рассчитанным
Заглушка рассчитывает промежуток между последним стаканом(или первым, если он один) Хмм, только заметил опечатку "загрушка") |
|||
174
Ненавижу 1С
гуру
27.05.20
✎
18:23
|
(173) от одного локального максимума, до другого как оказалось неверное решение
|
|||
175
seevkik
27.05.20
✎
18:30
|
Но и это (171) решение не идеальное, как максимум, она может также пройтись два раза по циклу - в том случае, если стакан в итоге один, не могу додумать механизм как все сделать в одном цикле)
Хотя, пока писал этот коммент понял, что последний цикл всего лишь считает количество этажей внутри стакана, а они определены как переменные "пройденоэтажейсправа" и "пройденоэтажейслева", тогда можно не бегать последний раз по циклу, может в основном теле надо поиграться с итераторами, но работать будет |
|||
176
fisher
28.05.20
✎
10:16
|
(174) Мне тоже казалось, что неверное. Но (171) проходит тесты. Появится время - разберусь в чем фишка.
|
|||
177
DomovoiAtakue
28.05.20
✎
14:03
|
Массив = Новый Массив;
Массив.Добавить(1); Массив.Добавить(0); Массив.Добавить(5); Массив.Добавить(5); Массив.Добавить(0); Массив.Добавить(1); Массив.Добавить(17); Массив.Добавить(0); Массив.Добавить(3); Массив.Добавить(1); Массив.Добавить(0); Массив.Добавить(3); Массив.Добавить(1); Массив.Добавить(1); Массив.Добавить(0); ВсегоВоды = 0; ПерваяГраница = 0; ПерваяПоз = 0; к=0; Пока к<=Массив.Количество()-1 Цикл Если ПерваяГраница<=Массив[к] Тогда ПерваяГраница = Массив[к]; ПерваяПоз = к; Иначе МаксВысота = Массив[к]; ПозМаксВысоты = к; СчитатьПоМаксВысоте = Истина; Для н=к+1 По Массив.Количество()-1 Цикл Если ПерваяГраница<=Массив[н] Тогда Предел = Мин(ПерваяГраница,Массив[н]); Для р=ПерваяПоз+1 По н-1 Цикл ВсегоВоды = ВсегоВоды+(Предел-Массив[р]); КонецЦикла; ПерваяГраница = Массив[н]; ПерваяПоз = н; к = ПерваяПоз; СчитатьПоМаксВысоте = Ложь; Прервать; Иначе Если Массив[н]>МаксВысота Тогда МаксВысота = Массив[н]; ПозМаксВысоты = н; КонецЕсли; КонецЕсли; КонецЦикла; Если СчитатьПоМаксВысоте Тогда Предел = Мин(ПерваяГраница,МаксВысота); Для р=ПерваяПоз+1 По ПозМаксВысоты-1 Цикл ВсегоВоды = ВсегоВоды+(Предел-Массив[р]); КонецЦикла; ПерваяГраница = МаксВысота; ПерваяПоз = ПозМаксВысоты; к = ПерваяПоз; КонецЕсли; КонецЕсли; к=к+1; КонецЦикла; Сообщить(ВсегоВоды); |
|||
178
Garykom
гуру
28.05.20
✎
15:00
|
(0) Интересная задачка.
Проще всего решается через заполнение двухмерного массива, так сказать методом эмуляции. Для 5 1 3 0 4 массив будет 5х5
Домики нарисовали, осталось заполнить водой
И посчитать кол-во 1 |
|||
179
Garykom
гуру
28.05.20
✎
15:03
|
Приколы возникают что надо эмулировать стекание воды
Например если
То заполнение будет только внутри домов, снаружи вода "стечет"
|
|||
180
fisher
28.05.20
✎
15:03
|
(178) И в каком месте упрощение? Каков будет алгоритм "эмуляции заполнения"?
|
|||
181
fisher
28.05.20
✎
15:05
|
А, типа пробегаться каждый раз по горизонталям?
|
|||
182
Garykom
гуру
28.05.20
✎
15:06
|
(180) Итерационный добавляем во все нижние клетки 0 воду и эмулируем набор воды с вытеснением-стеканием.
Как только несколько циклов картинка не меняется - все заполнилось. |
|||
183
Garykom
гуру
28.05.20
✎
15:06
|
(182)+ Хотя еще проще, все клетки 0 заполняем 1 и далее алгоритм стекания, стенки считаем что прозрачны
|
|||
184
fisher
28.05.20
✎
15:10
|
(182) Предлагаю упростить до реальной физической модели на дифурах. Будет частный случай от стекания воды в риал-тайме.
"Тем самым сведя задачу к предыдущей" (с) |
|||
185
Garykom
гуру
28.05.20
✎
15:12
|
(184) Зачем дифуры когда можно молекулы эмулировать с броуновским движением ))
|
|||
186
fisher
28.05.20
✎
15:13
|
(185) 1С тормозить начнет
|
|||
187
Йохохо
28.05.20
✎
15:13
|
(185) точно, там будет лагранжиан второго рода, а это урчп, что не диффуры
|
|||
188
Garykom
гуру
28.05.20
✎
15:16
|
(186) По условиям задачи молекулы очень крупные размером с этаж дома ))
|
|||
189
fisher
28.05.20
✎
15:18
|
Броуновское движение этажей дома - это страшно.
|
|||
190
Garykom
гуру
28.05.20
✎
15:18
|
Короче клеточный автомат банальный
|
Форум | Правила | Описание | Объявления | Секции | Поиск | Книга знаний | Вики-миста |