Вход | Регистрация
    1  2
Информационные технологии :: Математика и алгоритмы

Задача про дома и дождь

Задача про дома и дождь
Я
   DTX 4th
 
26.05.20 - 16:50
Есть массив чисел. Каждое число - это высота дома, например:
https://i.imgur.com/OOwGCLS.png
Это для массива 5 1 3 0 4.
Пошёл дождь и пространство между домами заполнилось водой. Нужно посчитать объём воды, которая скопилась между домами.

Вот так вода заполнит исходный пример:
https://i.imgur.com/fOXWNTH.png
   seevkik
 
101 - 26.05.20 - 19:21
(99) ну так количества итераций не будет больше количества элементов
   Ненавижу 1С
 
102 - 26.05.20 - 19:22
(54) а если..., все написано в (30) и смотри (90)
   PR
 
103 - 26.05.20 - 19:23
(100) А, не, не получается
   Ненавижу 1С
 
104 - 26.05.20 - 19:24
(100) или я не понял решения в (85) или из него следует, что считается объем двух резервуаров только - до максимума и после
   mistеr
 
105 - 26.05.20 - 19:25
(104) Аналогично
   mistеr
 
106 - 26.05.20 - 19:26
(87) Вроде правильно считает.

Только зачем СписокЗначений, когда есть массив?
   PR
 
107 - 26.05.20 - 19:27
(104) Не понял
   Cyberhawk
 
108 - 26.05.20 - 19:28
Так (85) походу работает, только если максимум один, так?
   PR
 
109 - 26.05.20 - 19:29
(106) Как ты сделаешь реквизит формы типа Массив?
   PR
 
110 - 26.05.20 - 19:29
(108) Нет
   seevkik
 
111 - 26.05.20 - 19:30
(108) поэтому нужно определить идентификатор максимума, а не значение
   DTX 4th
 
112 - 26.05.20 - 19:30
(102) Какая сложность получается в (90)?

(104)(105) Ну так по сути самый большой дом разбивает все дома на два резервуара.

(108) Не, их может быть несколько. Главное чтобы слева и справа шли к одному и тому же.

Ну и вот для наглядности мб кому пригодится:
https://i.imgur.com/IrkfjRV.png
   seevkik
 
113 - 26.05.20 - 19:32
(100) Блин, код получается суперговнокодом, типа
"если левыйбольше тогда правый = массив[правыйитератор] иначе
Левый = массив[левыйитератор]"
Не получается сейчас думать, но общая идея такая
Находим этажи слева, в том же коде находим этажи справа, сравниваем какой больше и идём с меньшего к большему попутно считая сколько воды заполняем, если представить визуально - поднятие линейки вверх с отметкой заполненности
   Ненавижу 1С
 
114 - 26.05.20 - 19:33
112) резрвуаров может и пять получиться в итоге
   Cyberhawk
 
115 - 26.05.20 - 19:33
"их может быть несколько. Главное чтобы слева и справа шли к одному и тому же" // А к какому идти тогда, если их несколько одинаковых, к любому?
   DTX 4th
 
116 - 26.05.20 - 19:34
(114) Max - это L из (85)
https://i.imgur.com/aSe7nTq.png

(115) Да, к любому
   seevkik
 
117 - 26.05.20 - 19:35
(115) (111)
   DTX 4th
 
118 - 26.05.20 - 19:35
(115) Вот для двух:
https://i.imgur.com/rUAhwWx.png
   Cyberhawk
 
119 - 26.05.20 - 19:35
(116) А чем тогда M и L отличаются?
   Ненавижу 1С
 
120 - 26.05.20 - 19:35
(112) в (90) сложность O(N)
   Cyberhawk
 
121 - 26.05.20 - 19:36
А, L это локальный максимум текущего шага, изначально равен высоте дома первого шага
   PR
 
122 - 26.05.20 - 19:37
(112) Эээ, нихрена не на два
3 0 3 0 5 0 3 0 3
Сколько резервуаров?
https://yadi.sk/i/mTv1DEDdHsjeIg
   seevkik
 
123 - 26.05.20 - 19:39
(122) два с одинаковой высотой разделенные максимумом с высотой 5
   PR
 
124 - 26.05.20 - 19:40
(123) Че?
   PR
 
125 - 26.05.20 - 19:41
+(124) Так-то вроде 4, я даже раскрасил же
   seevkik
 
126 - 26.05.20 - 19:41
(122) ну, суть в том, что расчета фактически происходит два - слева и справа, а не в том, что там фактически 4 резервуара)
одумайте мысль в (113) плз
   RomanYS
 
127 - 26.05.20 - 19:41
(122) Это уже терминология, что называть "резервуаром". По факту в (85) корректное решение и единственное подходящее под ограничения (55).
Пусть будет две "области"
   seevkik
 
128 - 26.05.20 - 19:42
Додумайте* (126)
   Ненавижу 1С
 
129 - 26.05.20 - 19:42
(122) вот и я также думаю
я вообще могу этих луж нарисовать, они все будут умньшаться по уровню от максимума влево и вправо
https://cdn1.radikalno.ru/uploads/2020/5/26/fd20b06a3b533fd96b638e94719522e3-full.png
   PR
 
130 - 26.05.20 - 19:42
(126) Слова резервуар и расчет для тебя синонимы?
 
 Рекламное место пустует
   seevkik
 
131 - 26.05.20 - 19:43
(127) да, две "области" самая верная терминология)
   DTX 4th
 
132 - 26.05.20 - 19:44
(120) Не похоже.
Берем [5,4,3,2,1] (большую убывающую лесенку)

Далее:
Выбираем самый левый дом за базовый.
Ищем следующий базовый от текущего базового как:
- первый слева направо, выше текущего
- если таковых нет: то крайний справа из тех, что с максимальной высотой

На втором пункте много побегать придется, не?

(130)(129) Вы о разном. Сначала PR не понял (104) в (107), а теперь топит за (104) :)

Касательно (104), глянь 116. Должно стать понятнее)
   RomanYS
 
133 - 26.05.20 - 19:44
(129) Не важно сколько луж/дыр/резервуаров. Важно, что проход от краев к одному из максимумов позволяет избавиться от необходимости использовать допмассивы
   seevkik
 
134 - 26.05.20 - 19:45
(130) может не будем углубляться, это не относится к теме, тут ошибочка вышла, верно
   Ненавижу 1С
 
135 - 26.05.20 - 19:46
(127) категорически не согласен
во-первых резервуаров с разными уровнями может быть больше, см рисунок (129)
во-вторых мое решение в (90) вполне O(n) и с доп памятью O(1)
   RomanYS
 
136 - 26.05.20 - 19:47
(135) вложенный цикл, не может там быть O(N)
   PR
 
137 - 26.05.20 - 19:48
(129) Да блин, не тупи, в (85) все верно, просто он скудно описал мысль
Ищешь номер максимально высокого дома (любого, если их несколько)
Потом слева и справа идешь к этому максимуму с шагом один дом и смотришь, сколько воды умещается между текущим домом и следующим
При этом в расчете берешь высоту дома, максимальную в твоем проходе (отдельно для левого, отдельно для правого)
   Ненавижу 1С
 
138 - 26.05.20 - 19:48
(136) а ты так определяешь? а что итератор внешнего цикла двигается только внутренним ничего не говорит?
   Ненавижу 1С
 
139 - 26.05.20 - 19:49
(137) а потом запоминаем следующий максимальный и т.д., этого в (85) не было написано
   PR
 
140 - 26.05.20 - 19:50
(132) Гражданин, о чем вы?
В (107) я сказал, что Ненавижу 1С в (104) не понял
   PR
 
141 - 26.05.20 - 19:51
(135) Слушай, не гунди, в (85), похоже, оптимальный вариант :))
   DTX 4th
 
142 - 26.05.20 - 19:52
(139) Как не было?
Вот же:
>Идем слева, запоминая высоту самого высокого дома - L

читать как "запоминая высоту самого высокого встретившегося дома"

(135) Ты на (132) не ответил.
   PR
 
143 - 26.05.20 - 19:53
(139) Я же и говорю, скудно написал, с предполагаемыми домысливаниями
   Ненавижу 1С
 
144 - 26.05.20 - 19:54
(143) тогда я и в (30) написал решение )))
(142) на что я не ответил?
   RomanYS
 
145 - 26.05.20 - 19:55
(138) Это просто "извращение" с учетом возврата ( var nextBased = based;...based = nextBased;) по сути это обычный вложенный цикл и сложность скорее всего О(N^2), как бы хитро ты его не обходил :). 100% выше O(N)
   PR
 
146 - 26.05.20 - 19:56
(144) То, что ты в (30) написал, даже с поллитрой никто не разберет, особенно последнее "А потом просто решаем задачу"
   seevkik
 
147 - 26.05.20 - 19:58
Так, в одну итерацию кто-нибудь придумал?
Вот так получается (113) ?
   Ненавижу 1С
 
148 - 26.05.20 - 19:59
Ладно, убедили, еще подумаю
   Ненавижу 1С
 
149 - 26.05.20 - 20:00
(146) нет там таких слов, ну посчитать объем всегда можно
   DTX 4th
 
150 - 26.05.20 - 20:01
Смотрите, какой я молодец, переписал (90) на js :)
https://codepen.io/DTX/pen/rNOgOqN?editors=1011

И даже подсчет итераций сделал :)

"Elems: 40. Iterations: 780"
"Elems: 80. Iterations: 3160"
Не тянет на О(N)
   rphosts
 
151 - 26.05.20 - 20:05
(150) растёт быстрее чем О(N), так что ...
   RomanYS
 
152 - 26.05.20 - 20:10
(150) О(N^2) как и предполагалось в (145). Запусти ещё пару раз для пущей убедительности)
   DTX 4th
 
153 - 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"
   DTX 4th
 
154 - 26.05.20 - 20:15
Или это не O(N^2)? Че-т я запутался
   seevkik
 
155 - 26.05.20 - 20:25
(154) нарисуй график и посмотри
   DTX 4th
 
156 - 26.05.20 - 20:29
(155) Подтверждаю, O(n^2)
(2n)^2/n^2 = 4
чудеса
   Ненавижу 1С
 
157 - 26.05.20 - 21:21
Все равно я не понимаю, где тот алгоритм, который за O(N) решает
вот автор говорит, потом ищем максимум справа/слева от масимума, но потом его еще и еще надо искать ведь
получаются те же O(N^2)
вот для подобных случаев: https://cdn1.radikalno.ru/uploads/2020/5/26/ae38d6d3dc59165b2a3ebffc4e303b5c-full.png
   Ненавижу 1С
 
158 - 26.05.20 - 21:33
нашел, спасибо за задачу, вообще огонь решение:

https://tproger.ru/problems/water-accumulated-in-puddles-between-walls/
   Asmody
 
159 - 26.05.20 - 21:47
(158) мне кажется, что приведенное там решение "в один проход" не сработает для случая 2 и более "стаканов"
   Asmody
 
160 - 26.05.20 - 21:49
я мееедленно запускаю IDEA...
 
 Рекламное место пустует
   Ненавижу 1С
 
161 - 26.05.20 - 21:53
(159) да нет, сработает
как всегда всё просто, уровни стаканов все время поднимаются к максимуму
   Asmody
 
162 - 26.05.20 - 22:26
надо же - работает!
   Asmody
 
163 - 26.05.20 - 22:27
2 строчки поменять - и можно получить массив заполнения воды.
   Bigbro
 
164 - 27.05.20 - 04:16
(158) а если несколько локальных экстремумов?
32172312
когда у нас не один стакан с неровным дном а конфигурация разбивается на несколько стаканов с отбитым краем. и тоже неровным дном.
   seevkik
 
165 - 27.05.20 - 08:29
(157) и ничем не отличается от предложенных мной
   fisher
 
166 - 27.05.20 - 09:24
(157)(158) В (85) же было.
   dezss
 
167 - 27.05.20 - 09:25
(51) Я проверил. Работает.
А тут форум 1с-ников, а не js-ников.
Да, это не самый оптимальный вариант. Просто на скорую руку набросал.
   fisher
 
168 - 27.05.20 - 09:35
(0) Если до (85) как говоришь сам за 15 минут догадался, то респект.
   fisher
 
169 - 27.05.20 - 09:39
(91) Без нахождения максимума за один проход не получится.
   fisher
 
170 - 27.05.20 - 09:44
Но вообще все эти задачки на собеседованиях если на джуна - я еще могу понять. А на мидла - уже как-то странно.
   seevkik
 
171 - 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;
    КонецЦикла;
    
    ВсегоВоды = ВсегоВоды + Мин(ПравыйКрай,ЛевыйКрай) * КоличествоИтерацийЗагрушки - КоличествоЭтажей;
    
    Сообщить(ВсегоВоды);
   fisher
 
172 - 27.05.20 - 17:49
(171) Как работает - пока до конца не понял (что за случай в конце обрабатывается). Но работает вроде как заявлено. Так что респект.
   seevkik
 
173 - 27.05.20 - 18:20
(172) основная идея - шагать вперёд с двух сторон от максимума до следующего максимума и рассчитывать сколько лезет в кусок между этим отрезком, триггер - переменная КрайИзменится как знак того, что надо рассчитать кусок от предыдущего максимума до следующего, загвоздка в том, что в последней итерации край не меняется, они просто встречаются и последний стакан остаётся не рассчитанным
Заглушка рассчитывает промежуток между последним стаканом(или первым, если он один)
Хмм, только заметил опечатку "загрушка")
   Ненавижу 1С
 
174 - 27.05.20 - 18:23
(173) от одного локального максимума, до другого как оказалось неверное решение
   seevkik
 
175 - 27.05.20 - 18:30
Но и это (171) решение не идеальное, как максимум, она может также пройтись два раза по циклу - в том случае, если стакан в итоге один, не могу додумать механизм как все сделать в одном цикле)

Хотя, пока писал этот коммент понял, что последний цикл всего лишь считает количество этажей внутри стакана, а они определены как переменные "пройденоэтажейсправа" и "пройденоэтажейслева", тогда можно не бегать последний раз по циклу, может в основном теле надо поиграться с итераторами, но работать будет
   fisher
 
176 - 28.05.20 - 10:16
(174) Мне тоже казалось, что неверное. Но (171) проходит тесты. Появится время - разберусь в чем фишка.
   DomovoiAtakue
 
177 - 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;
                
КонецЦикла;
    
Сообщить(ВсегоВоды);
   Garykom
 
178 - 28.05.20 - 15:00
(0) Интересная задачка.
Проще всего решается через заполнение двухмерного массива, так сказать методом эмуляции.

Для 5 1 3 0 4 массив будет 5х5
X0000
X000X
X0X0X
X0X0X
XXX0X

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

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

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

   fisher
 
180 - 28.05.20 - 15:03
(178) И в каком месте упрощение? Каков будет алгоритм "эмуляции заполнения"?
   fisher
 
181 - 28.05.20 - 15:05
А, типа пробегаться каждый раз по горизонталям?
   Garykom
 
182 - 28.05.20 - 15:06
(180) Итерационный добавляем во все нижние клетки 0 воду и эмулируем набор воды с вытеснением-стеканием.
Как только несколько циклов картинка не меняется - все заполнилось.
   Garykom
 
183 - 28.05.20 - 15:06
(182)+ Хотя еще проще, все клетки 0 заполняем 1 и далее алгоритм стекания, стенки считаем что прозрачны
   fisher
 
184 - 28.05.20 - 15:10
(182) Предлагаю упростить до реальной физической модели на дифурах. Будет частный случай от стекания воды в риал-тайме.
"Тем самым сведя задачу к предыдущей" (с)
   Garykom
 
185 - 28.05.20 - 15:12
(184) Зачем дифуры когда можно молекулы эмулировать с броуновским движением ))
   fisher
 
186 - 28.05.20 - 15:13
(185) 1С тормозить начнет
   Йохохо
 
187 - 28.05.20 - 15:13
(185) точно, там будет лагранжиан второго рода, а это урчп, что не диффуры
   Garykom
 
188 - 28.05.20 - 15:16
(186) По условиям задачи молекулы очень крупные размером с этаж дома ))
   fisher
 
189 - 28.05.20 - 15:18
Броуновское движение этажей дома - это страшно.
   Garykom
 
190 - 28.05.20 - 15:18
Короче клеточный автомат банальный
  1  2

Список тем форума
Рекламное место пустует  Рекламное место пустует
ВНИМАНИЕ! Если вы потеряли окно ввода сообщения, нажмите Ctrl-F5 или Ctrl-R или кнопку "Обновить" в браузере.