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

Вот так вода заполнит исходный пример:
https://i.imgur.com/fOXWNTH.png

Сколько платят?

(1) Похоже на олимпиаду по информатике

Такое дают на собеседовании в яндекс

посто минимум по 2 соседям

Судя по картинке будет 2 плюс бесконечность, в правой дырке всё будет выливаться в канализацию.

(4) Для третьего дома соседи 1 и 0

(5) Для исходного примера ответ 8, как видно на второй картинке

(6) Неправильно. Там справа дырка бездонная.

Ну, я человек простой, тупо пробежаться по массиву отнимая по одному с элемента и за каждый "0" давать по одному "литру" воды в переменную "заполненный объем" не вариант?

(7) Ну так вопрос про то, сколько скопилось, а не сколько было вылито.

(0) Еще тестовые данные есть?
Сейчас попробуем

(8) Не пойму
Сколько будет, если входной массив будет: 1,1,1,0?

(10) Есть решение :)

Ответ 8. Это правильно?

(11)
Функция ноевковчег(сколькоэтажейтыхочешьзалить)
Потрачено равно 0;
С 1 по сколькоэтажейтыхочешьзалить цико
Для каждого элемент из массив цикл
Если элемент =0 тогда
потрачено равно потрачено плюс 1;
Конецесли
Конеццикла
Конеццикла
Возврат потрачено
Конецфункции

Сорян, с телефона

(11) Думаю будет 0.

(11) Пока нет.

(13) ыах, там ещё надо переопределить значения элементов массива, ну или отнимать итератор и поставить условие меньше или равно 0

Прикольная задачка.
Нужно учитывать, что если дальше есть более высокие дома, то над средними более низкими тоже будет вода.

(13) Че-т фигня
Код зависит только от нулей в массиве

(15) Это да. Я к тому, что в (8) ноль не получится.

(16) Решение есть у меня :)

(19) как дал тз так и решил, код рабочий, с оглядкой на (17).
И зависит не от нулей, а от "высоты" зданий

(20) Тогда повторю вопрос. Какой ответ для [1,1,0]?

(21) сколько ты этажей зальешь?

(21) 0

Высота столба воды для каждого "междудомного" промежутка равна минимуму максимальной высоты домов слева и справа.

ИМХО, идти надо с первого этажа, фиксируя значения, когда находишь следующее здание.
Т.е. сперва находим самое высокое здание, а потом цикл с 1 до этой максимальной высоты.

Так, условие именно "между" домами, более понятный пример надо давать
Тогда добавить условие на проверку первого и последнего элемента, если они равно или меньше 0 тогда прервать

(0) Примитивная задача на 5 минут
И не стыдно ведь

Хотя у тебя туманные условия, если будет массив 1 0 5 5 0 1 сколько воды будет потрачено?

(28) Между домами скопится 2. А сколько потрачено - такого вопроса в задаче нет.

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

исследуем интервалы между базовыми домами:
- находим уровень воды и считаем емкость заполнения

1. цикл от первого до следующего не меньшего не включительно
2. просуммировать разницы между первым элементом и текущим
3. последний в цикле назначить первым
4. перейти к п.1

(29) сорян, 1050501, а сейчас 7?

(28) Да. Дурацкая постановка. Словесное описание не соответствует картинке примера. Из картинки следует, что промежутка между вплотную стоящими домами не существует.

(23) Тут утверждают, что код рабочий) Но он 0 не возвращает для этого случая)

(26) Там аж два скрине с примерами)
Условие на И? На ИЛИ?
01010 - 0 вернет?

(27) Я 15 потратил, но был момент, когда думал, что не решу
Кидай решение на pastebin, если так уверен. Как кто решит - даешь ссылку, и мы проверяем :) Там как раз дата создания есть

мне кажется нужно так решать. берешь верхний ряд, первое поле. пытаешься его слить вправо, потом влево
потом 2 поле... потом второй ряд

тьфу...да не сложно же
    Мас = Новый Массив;
    Мас.Добавить(5);
    Мас.Добавить(1);
    Мас.Добавить(3);
    Мас.Добавить(0);
    Мас.Добавить(4);
    
    //Мас.Добавить(1);
    //Мас.Добавить(0);
    //Мас.Добавить(5);
    //Мас.Добавить(0);
    //Мас.Добавить(5);
    //Мас.Добавить(0);
    //Мас.Добавить(1);
    
    ВсегоВоды = 0;
    МаксВысота = 5;
    Для н = 1 по МаксВысота Цикл
        Добавим = 0;
        Перв = Истина;
        Для й = 0 По Мас.Количество()-1 Цикл
            Если Перв И Мас[й] < н Тогда
                Продолжить;
            КонецЕсли;
            Перв = Ложь;
            Если Мас[й] < н Тогда
                Добавим = Добавим + 1;
            Иначе
                ВсегоВоды = ВсегоВоды + Добавим;
                Добавим = 0;
            КонецЕсли;
        КонецЦикла;
    КонецЦикла;
    
    Сообщить(ВсегоВоды);
Ко

можно провести оптимизацию и искать диапазон что не сольется

1. Найти два наибольших числа - это стакан.
2. Воды внутри стакана это вторая высота на расстояние между станками минут что внутри.
3. Внутри стакана нашли. Это стакан разбивает задачу на две аналогичные...

(38) Только дно у стакана может быть не ровным.

(36) Можно даж слегка оптимизировать.
Если макс высота всего одна, то первый цикл по высоте здания, которые идем следующим.

(39) Так минус сумма чисел внутри стакана,но мне кажется можно и одно проходным сделать...
(36) Мне кажется нет определения левой и правой стенки. Без одной из них вода выливается...

(40) задача решается одним циклом
в (36) хотя бы определение МаксВысота - это уже цикл

+(30) оценка времени выполнения O(N^2)

+(43) хотя нет O(N)

(34) слишком грубый пример, кто знал что справа и слева от картинки пустота и между ними не копится вода, не олимпиадник, извиняюсь)

(43) Вижу решение за O(N). За два прохода короче :) Но с доп. памятью.

(34) Ну код я писать не буду ессно, но идея следующая для n домов:
Берем цикл по i от 1 до n - 2, то есть количество дырок в один дом между домами
В нем МаксимальнаяВысотаЛевогоДома = Max(высоты домов от 1 до i) и МаксимальнаяВысотаПравогоДома = Max(высоты домов от i + 2 до n)
В дырку между домом i и домом i + 2 зальется Min(МаксимальнаяВысотаЛевогоДома, МаксимальнаяВысотаПравогоДома) - высота дома i + 1 (то есть дома в дырке)
Если получившееся число отрицательное, то берем вместо него 0
Конец цикла
Все посчитанное в цикле ессно суммируем

(38) Это рекурсия
Нахрен с пляжа

(47) лучше бы код написал, проще воспринимать)

(47) Типа того. И тут либо квадратичное количество итераций, либо два прохода с доп-массивом.
(48) И чо? Рекурсивно тоже можно решить.

(30) Не понимаю
Если будет [1,2,3], как считать?

(31) Тот же вопрос
Для [1,2,3] не получается

(38) Похоже на рабочее
Но сложность, думаю, заоблачаная будет
Но неплохо)

(36) Блин, почему не на js, как проверять то.
Не уверен, что будет работать

(51) ну вот исходя из (30)
базовый [1], следующий базовый [2] следующий [3]
считаем между ними воду: расстояний нет между домами в конкретном примере - получаем 0

Ок, делаем так
Находим максимальный элемент массива, далее берём первый элемент, далее бежим по массиву пока не найдем равное или больше первого элемента или пока не дойдем до максимума, по пути считаем количество этажей и пройденный путь
Если найдем нужный элемент, то умножаем первый на количество пройденного пути и минусуем количество этажей
И делаем такой же цикл, только с конца до максимального элемента

(30) а если высота домов 1 0 5 0 5 0 3 0 1

(46)(47)(50) Неэффективно. Решается за O(N) без доп памяти :)

Да, вижу "если таковых нет: то крайний справа из тех, что с максимальной высотой", сильно конечно)

(55) А вот это уже гораздо интереснее :)

(55) Да похрен

(53) [1,0,2,3]
Макс - 3
Первый элемент - 1
Бежим
Находим 2
Прошли два дома в длину и один этаж?

Как блин это читать.

(59) прошли минус 1, ну ты чего)

(54) а если вводная меняется, то пишите алгоритмы этого чятика сначала.

а я на этой погорел:

Штаб гражданской обороны Тридесятой области решил обновить план спасения на случай ядерной атаки. Известно, что все n селений Тридесятой области находятся вдоль одной прямой дороги. Вдоль дороги также расположены m бомбоубежищ, в которых жители селений могут укрыться на случай ядерной атаки.

Чтобы спасение в случае ядерной тревоги проходило как можно эффективнее, необходимо для каждого селения определить ближайшее к нему бомбоубежище.

в 1000 мс не уложился ((( на питоне

Имеем массив 2 1 3 0 5 0 5 0 3
Максимальный элемент = 2; (его порядковый номер)
ЛевыйВысокий=массив[0];
Заполнено = 0;
Пройдено =0;
С итератор=1 по итератор=максэл цикл
Если ЛевыйВысокий>массив[итератор] тогда
Пройдено=пройдено+1;
Этажей = этажей+массив[итератор];
Иначе
ЛевыйВысокий = массив[итератор];
Заполнено = заполнено+пройдено*левыйвысокий-этажей;
Конецесли
Конеццикла
Ну и такой же, только в обратную сторону

(63) Блин, надо поработать)
Через пару часов выложу решение для (0)

А для (63) я бы решал так:
Сортируем отдельно селенья и убежища.
Берем первое убежище: m1 = m[i] (тут будет индекс убежищ, i = 0 в начале)
И сразу второе: m2 = m[i+1]

Далее цикл по селеньям:
Пока от текущего селения ближе до m2 чем до m1, увеличиваем индекс убежищ (i++)
Выводим: для текущего селения ближайшее убежище - m1
КонецЦикла

переберать массив по этажу.
1 слева дом 1 этаж. проверяем есть вода или нет и прибавляем 1 или 0. 2 дом 1 этаж. и т. д.

Два цикла внешний по этажам. внутренний по домам.

(65) упс, максимальный элемент [4]

Функция РассчитатьОбъемВоды(Дома)
    
    Перем ОбъемВоды, Высота, ЕстьДома, Вода;
    
    ОбъемВоды = 0;
    Высота = 1;
    ЕстьДома = Истина;
    
    Пока ЕстьДома И Высота < 1000 Цикл
        ЕстьДома = Ложь;
        Вода = 0;
        Для Каждого Дом Из Дома Цикл
            Если Дом >= Высота Тогда // тут дом
                ОбъемВоды = ОбъемВоды + ?(ЕстьДома, Вода, 0);  // считаем накопленное
                Вода = 0;  // сливаем воду
                ЕстьДома = Истина;
            Иначе // тут пусто
                Вода = Вода + 1;  // накапливаем воду
            КонецЕсли;
        КонецЦикла;
        Высота = Высота + 1;  // идем на следующий этаж
    КонецЦикла;
    
    Возврат ОбъемВоды
    
КонецФункции

(69) Блин, тупой форматтер.

для массива из (67) получим
2 1 3 0 5 0 5 0 3
0 0 0 1 0 1 0 1 0 =3
0 1 0 1 0 1 0 1 0 =4
0 0 0 1 0 1 0 1 0 =3
0 0 0 0 0 1 0 0 0 =1
0 0 0 0 0 1 0 0 0=1

итого 12

накидал прогу, 2 вложенных цикла
для (0) выводит 8
для 1,0,2,3 = 1
для 1, 0, 5, 0, 5, 0, 3, 0, 1 = 10
для 2, 1, 3, 0, 5, 0, 5, 0, 3 = 12

какие еще тесты прогнать?
думаю оптимизировать немного, чтобы вложенный цикл максимум 2 раза выполнялся для каждой итерации 1го

(72) смотри (55)
Решение O(N) с двумя допмассивами в три прохода на поверхности и здесь уже описано. А вот без доппамяти гораздо интереснее

(69) Че-т не то.
Для [0, 1] и [1, 0], похоже, разные результаты будут

(71) Не понимаю
"проверяем, есть вода или нет"
Как проверяем?

(63) И каковы входные данные?

(74) Одинаковые

(74) сравниваем тек значение с крайними. и проверяем тек значение не дом ли это.

(73) у меня нет доп массивов, только 2 аккумулирующие переменные, основная и промежуточная

И кто мне объяснит, как с доппамятью решать? Пока не пойму, что там хотите хранить

(76) Согласен
Но как это работает, не понимаю)

(77) А если там дырка больше чем один дом?
Тип вот так
3 0 0 2
0 ? ? 0

Как мы для первого дома поймем, есть тут вода или нет?
Видимо, циклом, пока в дом не упремся

Решение понял) Похоже, оно похоже на (47)

(78) но и O(N) нет: "вложенный цикл"

(73) Что-то я не вижу ни одного решения с O(N). А интересно..

(81)
1й проход - собираем нарастающие максимумы слева в массив
2-й - во второй допмассив собираем максимумы справа
3-й - считаем объем

(3) На какую позицию такое дают?

(82) Код нужен. Только по коду можно понять, O(N) там или что.

В общем, вот мое:
Проходим по массиву, получаем максимум - M
Дальше будем идти к этому максимум с двух сторон
Идем слева, запоминая высоту самого высокого дома - L
На каждом шаге добавляем к результату L-h, где h - высота текущего дома

Похоже, ближе всего (53)

Ну и рекурсия мне понравилась со стаканом)

(82) Теперь понял)

(83) Рядовой мидл.

По-моему, там две задачи. Одна попроще, другая посложнее.

Вот попроще, если кому интересно:
Дана карта (матрица),  с 1 и 0.
1 - земля. 0 - вода. Нужно найти площадь самого большого острова. Земля  соединяется только по горизонтали и вертикали

(49) Какой ты, а
Ну на https://yadi.sk/d/AOxrrEm_zz8bDg :))

Код

ТД.Очистить();

МаксимальнаяВысотаДома = 0;

Для А = 0 По Дома.Количество() - 1 Цикл
    
    Если Дома[А].Значение > МаксимальнаяВысотаДома Тогда
        МаксимальнаяВысотаДома = Дома[А].Значение;
    КонецЕсли;
    
КонецЦикла;

КоличествоДомов = Дома.Количество();

ТД.Область(, 1, , КоличествоДомов + 1).ШиринаКолонки = 2;

Для А = 0 По КоличествоДомов - 1 Цикл
    
    Если Дома[А].Значение > 0 Тогда
        ТД.Область(МаксимальнаяВысотаДома - Дома[А].Значение + 2, А + 2, МаксимальнаяВысотаДома + 1, А + 2).ЦветФона = Новый Цвет(0, 0, 0);
    КонецЕсли;
    
КонецЦикла;

ОбъемВоды = 0;
МаксимальнаяВысотаЛевогоДома = 0;

Для А = 0 По КоличествоДомов - 3 Цикл
    
    Если МаксимальнаяВысотаЛевогоДома < Дома[А].Значение Тогда
        МаксимальнаяВысотаЛевогоДома = Дома[А].Значение;
    КонецЕсли;
    
    МаксимальнаяВысотаПравогоДома = 0;
    
    Для Б = А + 2 По КоличествоДомов - 1 Цикл
        
        Если МаксимальнаяВысотаПравогоДома < Дома[Б].Значение Тогда
            МаксимальнаяВысотаПравогоДома = Дома[Б].Значение;
        КонецЕсли;
        
    КонецЦикла;
    
    ОбъемВодыМеждуДомами = Мин(МаксимальнаяВысотаЛевогоДома, МаксимальнаяВысотаПравогоДома) - Дома[А + 1].Значение;
    
    Если ОбъемВодыМеждуДомами > 0 Тогда
        ОбъемВоды = ОбъемВоды + ОбъемВодыМеждуДомами;
        ТД.Область(МаксимальнаяВысотаДома - ОбъемВодыМеждуДомами - Дома[А + 1].Значение + 2, А + 3, МаксимальнаяВысотаДома - Дома[А + 1].Значение + 1, А + 3).ЦветФона = Новый Цвет(0, 0, 255);
    КонецЕсли;
    
КонецЦикла;

ТД.Область(МаксимальнаяВысотаДома + 3, 2).Текст = "Воды: " + ОбъемВоды;


(86) Мидл на какой стек?

(85) Код давай

Моё решение:
https://ideone.com/RP32SG

Можно без нахождения максимума сделать цикл в цикле пока они не встретятся, чутка дешевле выйдет, только надо определять переменную которая показывает какая сторона выше на данной итерации

(85) красиво

(92) Но два прохода

(85) Прикольно, да
Можно, кстати, даже в один цикл сделать :))

(93) два не полных прохода, это в счёт?

(85) по-твоему там только две лужи воды образуется? это не так

(95) Почему неполных - максимум чтоб найти это один проход, далее с двух сторон накопить пустоту - вот и второй проход

(97) упс) а если (91) ?

(98) Цикл в цикле - это больше двух

(88) с++
(89) Да ладно, все понятно же
Код сложнее читать

(90) На js не проще такие поделки писать?) Я codepen.io пользую
(92) Я тоже порадовался, что еще что-то могу)

(93) O(N). Остальное не важно)
(94) Как?

(96) Не понял вопроса.
(98) Похоже на изврат) Но давай код :)

(99) ну так количества итераций не будет больше количества элементов

(54) а если..., все написано в (30) и смотри (90)

(100) А, не, не получается

(100) или я не понял решения в (85) или из него следует, что считается объем двух резервуаров только - до максимума и после

(104) Аналогично

(87) Вроде правильно считает.

Только зачем СписокЗначений, когда есть массив?

(104) Не понял

Так (85) походу работает, только если максимум один, так?

(106) Как ты сделаешь реквизит формы типа Массив?

(108) Нет

(108) поэтому нужно определить идентификатор максимума, а не значение

(102) Какая сложность получается в (90)?

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

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

Ну и вот для наглядности мб кому пригодится:
https://i.imgur.com/IrkfjRV.png

(100) Блин, код получается суперговнокодом, типа
"если левыйбольше тогда правый = массив[правыйитератор] иначе
Левый = массив[левыйитератор]"
Не получается сейчас думать, но общая идея такая
Находим этажи слева, в том же коде находим этажи справа, сравниваем какой больше и идём с меньшего к большему попутно считая сколько воды заполняем, если представить визуально - поднятие линейки вверх с отметкой заполненности

112) резрвуаров может и пять получиться в итоге

"их может быть несколько. Главное чтобы слева и справа шли к одному и тому же" // А к какому идти тогда, если их несколько одинаковых, к любому?

(114) Max - это L из (85)
https://i.imgur.com/aSe7nTq.png

(115) Да, к любому

(115) (111)

(115) Вот для двух:
https://i.imgur.com/rUAhwWx.png

(116) А чем тогда M и L отличаются?

(112) в (90) сложность O(N)

А, L это локальный максимум текущего шага, изначально равен высоте дома первого шага

(112) Эээ, нихрена не на два
3 0 3 0 5 0 3 0 3
Сколько резервуаров?
https://yadi.sk/i/mTv1DEDdHsjeIg

(122) два с одинаковой высотой разделенные максимумом с высотой 5

(123) Че?

+(124) Так-то вроде 4, я даже раскрасил же

(122) ну, суть в том, что расчета фактически происходит два - слева и справа, а не в том, что там фактически 4 резервуара)
одумайте мысль в (113) плз

(122) Это уже терминология, что называть "резервуаром". По факту в (85) корректное решение и единственное подходящее под ограничения (55).
Пусть будет две "области"

Додумайте* (126)

(122) вот и я также думаю
я вообще могу этих луж нарисовать, они все будут умньшаться по уровню от максимума влево и вправо
https://cdn1.radikalno.ru/uploads/2020/5/26/fd20b06a3b533fd96b638e94719522e3-full.png

(126) Слова резервуар и расчет для тебя синонимы?

(127) да, две "области" самая верная терминология)

(120) Не похоже.
Берем [5,4,3,2,1] (большую убывающую лесенку)

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

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

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

Касательно (104), глянь 116. Должно стать понятнее)

(129) Не важно сколько луж/дыр/резервуаров. Важно, что проход от краев к одному из максимумов позволяет избавиться от необходимости использовать допмассивы

(130) может не будем углубляться, это не относится к теме, тут ошибочка вышла, верно

(127) категорически не согласен
во-первых резервуаров с разными уровнями может быть больше, см рисунок (129)
во-вторых мое решение в (90) вполне O(n) и с доп памятью O(1)

(135) вложенный цикл, не может там быть O(N)

(129) Да блин, не тупи, в (85) все верно, просто он скудно описал мысль
Ищешь номер максимально высокого дома (любого, если их несколько)
Потом слева и справа идешь к этому максимуму с шагом один дом и смотришь, сколько воды умещается между текущим домом и следующим
При этом в расчете берешь высоту дома, максимальную в твоем проходе (отдельно для левого, отдельно для правого)

(136) а ты так определяешь? а что итератор внешнего цикла двигается только внутренним ничего не говорит?

(137) а потом запоминаем следующий максимальный и т.д., этого в (85) не было написано

(132) Гражданин, о чем вы?
В (107) я сказал, что Ненавижу 1С в (104) не понял

(135) Слушай, не гунди, в (85), похоже, оптимальный вариант :))

(139) Как не было?
Вот же:
>Идем слева, запоминая высоту самого высокого дома - L

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

(135) Ты на (132) не ответил.

(139) Я же и говорю, скудно написал, с предполагаемыми домысливаниями

(143) тогда я и в (30) написал решение )))
(142) на что я не ответил?

(138) Это просто "извращение" с учетом возврата ( var nextBased = based;...based = nextBased;) по сути это обычный вложенный цикл и сложность скорее всего О(N^2), как бы хитро ты его не обходил :). 100% выше O(N)

(144) То, что ты в (30) написал, даже с поллитрой никто не разберет, особенно последнее "А потом просто решаем задачу"

Так, в одну итерацию кто-нибудь придумал?
Вот так получается (113) ?

Ладно, убедили, еще подумаю

(146) нет там таких слов, ну посчитать объем всегда можно

Смотрите, какой я молодец, переписал (90) на js :)
https://codepen.io/DTX/pen/rNOgOqN?editors=1011

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

"Elems: 40. Iterations: 780"
"Elems: 80. Iterations: 3160"
Не тянет на О(N)

(150) растёт быстрее чем О(N), так что ...

(150) О(N^2) как и предполагалось в (145). Запусти ещё пару раз для пущей убедительности)

(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"

Или это не O(N^2)? Че-т я запутался

(154) нарисуй график и посмотри

(155) Подтверждаю, O(n^2)
(2n)^2/n^2 = 4
чудеса

Все равно я не понимаю, где тот алгоритм, который за O(N) решает
вот автор говорит, потом ищем максимум справа/слева от масимума, но потом его еще и еще надо искать ведь
получаются те же O(N^2)
вот для подобных случаев: https://cdn1.radikalno.ru/uploads/2020/5/26/ae38d6d3dc59165b2a3ebffc4e303b5c-full.png

нашел, спасибо за задачу, вообще огонь решение:

https://tproger.ru/problems/water-accumulated-in-puddles-between-walls/

(158) мне кажется, что приведенное там решение "в один проход" не сработает для случая 2 и более "стаканов"

я мееедленно запускаю IDEA...

(159) да нет, сработает
как всегда всё просто, уровни стаканов все время поднимаются к максимуму

надо же - работает!

2 строчки поменять - и можно получить массив заполнения воды.

(158) а если несколько локальных экстремумов?
32172312
когда у нас не один стакан с неровным дном а конфигурация разбивается на несколько стаканов с отбитым краем. и тоже неровным дном.

(157) и ничем не отличается от предложенных мной

(157)(158) В (85) же было.

(51) Я проверил. Работает.
А тут форум 1с-ников, а не js-ников.
Да, это не самый оптимальный вариант. Просто на скорую руку набросал.

(0) Если до (85) как говоришь сам за 15 минут догадался, то респект.

(91) Без нахождения максимума за один проход не получится.

Но вообще все эти задачки на собеседованиях если на джуна - я еще могу понять. А на мидла - уже как-то странно.

(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;
    КонецЦикла;
    
    ВсегоВоды = ВсегоВоды + Мин(ПравыйКрай,ЛевыйКрай) * КоличествоИтерацийЗагрушки - КоличествоЭтажей;
    
    Сообщить(ВсегоВоды);

(171) Как работает - пока до конца не понял (что за случай в конце обрабатывается). Но работает вроде как заявлено. Так что респект.

(172) основная идея - шагать вперёд с двух сторон от максимума до следующего максимума и рассчитывать сколько лезет в кусок между этим отрезком, триггер - переменная КрайИзменится как знак того, что надо рассчитать кусок от предыдущего максимума до следующего, загвоздка в том, что в последней итерации край не меняется, они просто встречаются и последний стакан остаётся не рассчитанным
Заглушка рассчитывает промежуток между последним стаканом(или первым, если он один)
Хмм, только заметил опечатку "загрушка")

(173) от одного локального максимума, до другого как оказалось неверное решение

Но и это (171) решение не идеальное, как максимум, она может также пройтись два раза по циклу - в том случае, если стакан в итоге один, не могу додумать механизм как все сделать в одном цикле)

Хотя, пока писал этот коммент понял, что последний цикл всего лишь считает количество этажей внутри стакана, а они определены как переменные "пройденоэтажейсправа" и "пройденоэтажейслева", тогда можно не бегать последний раз по циклу, может в основном теле надо поиграться с итераторами, но работать будет

(174) Мне тоже казалось, что неверное. Но (171) проходит тесты. Появится время - разберусь в чем фишка.

Массив = Новый Массив;
    
Массив.Добавить(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;
                
КонецЦикла;
    
Сообщить(ВсегоВоды);

(0) Интересная задачка.
Проще всего решается через заполнение двухмерного массива, так сказать методом эмуляции.

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

X0000
X000X
X0X0X
X0X0X
XXX0X

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

X0000
X111X
X1X1X
X1X1X
XXX1X

И посчитать кол-во 1

Приколы возникают что надо эмулировать стекание воды
Например если

X00000
X000X0
X0X0X0
X0X0X0
XXX0XX

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

X00000
X111X0
X1X1X0
X1X1X0
XXX1XX


(178) И в каком месте упрощение? Каков будет алгоритм "эмуляции заполнения"?

А, типа пробегаться каждый раз по горизонталям?

(180) Итерационный добавляем во все нижние клетки 0 воду и эмулируем набор воды с вытеснением-стеканием.
Как только несколько циклов картинка не меняется - все заполнилось.

(182)+ Хотя еще проще, все клетки 0 заполняем 1 и далее алгоритм стекания, стенки считаем что прозрачны

(182) Предлагаю упростить до реальной физической модели на дифурах. Будет частный случай от стекания воды в риал-тайме.
"Тем самым сведя задачу к предыдущей" (с)

(184) Зачем дифуры когда можно молекулы эмулировать с броуновским движением ))

(185) 1С тормозить начнет

(185) точно, там будет лагранжиан второго рода, а это урчп, что не диффуры

(186) По условиям задачи молекулы очень крупные размером с этаж дома ))

Броуновское движение этажей дома - это страшно.

Короче клеточный автомат банальный