Имя: Пароль:
IT
 
Задача про дома и дождь
, ,
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
(114) Max - это L из (85)
https://i.imgur.com/aSe7nTq.png

(115) Да, к любому
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

X0000
X000X
X0X0X
X0X0X
XXX0X

Домики нарисовали, осталось заполнить водой

X0000
X111X
X1X1X
X1X1X
XXX1X

И посчитать кол-во 1
179 Garykom
 
гуру
28.05.20
15:03
Приколы возникают что надо эмулировать стекание воды
Например если

X00000
X000X0
X0X0X0
X0X0X0
XXX0XX

То заполнение будет только внутри домов, снаружи вода "стечет"

X00000
X111X0
X1X1X0
X1X1X0
XXX1XX
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
Короче клеточный автомат банальный
Проблемы невозможно решaть нa том же уровне компетентности, нa котором они возникaют. Альберт Эйнштейн