Вход | Регистрация
    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
   ДенисЧ
 
1 - 26.05.20 - 16:51
Сколько платят?
   Волшебник
 
Модератор
2 - 26.05.20 - 16:51
(1) Похоже на олимпиаду по информатике
   DTX 4th
 
3 - 26.05.20 - 16:52
Такое дают на собеседовании в яндекс
   Вафель
 
4 - 26.05.20 - 16:52
посто минимум по 2 соседям
   ДенисЧ
 
5 - 26.05.20 - 16:53
Судя по картинке будет 2 плюс бесконечность, в правой дырке всё будет выливаться в канализацию.
   DTX 4th
 
6 - 26.05.20 - 16:55
(4) Для третьего дома соседи 1 и 0

(5) Для исходного примера ответ 8, как видно на второй картинке
   ДенисЧ
 
7 - 26.05.20 - 16:57
(6) Неправильно. Там справа дырка бездонная.
   seevkik
 
8 - 26.05.20 - 17:01
Ну, я человек простой, тупо пробежаться по массиву отнимая по одному с элемента и за каждый "0" давать по одному "литру" воды в переменную "заполненный объем" не вариант?
   dezss
 
9 - 26.05.20 - 17:02
(7) Ну так вопрос про то, сколько скопилось, а не сколько было вылито.
   mistеr
 
10 - 26.05.20 - 17:03
(0) Еще тестовые данные есть?
Сейчас попробуем
   DTX 4th
 
11 - 26.05.20 - 17:05
(8) Не пойму
Сколько будет, если входной массив будет: 1,1,1,0?

(10) Есть решение :)
   Fish
 
12 - 26.05.20 - 17:08
Ответ 8. Это правильно?
   seevkik
 
13 - 26.05.20 - 17:10
(11)
Функция ноевковчег(сколькоэтажейтыхочешьзалить)
Потрачено равно 0;
С 1 по сколькоэтажейтыхочешьзалить цико
Для каждого элемент из массив цикл
Если элемент =0 тогда
потрачено равно потрачено плюс 1;
Конецесли
Конеццикла
Конеццикла
Возврат потрачено
Конецфункции
   seevkik
 
14 - 26.05.20 - 17:10
Сорян, с телефона
   mistеr
 
15 - 26.05.20 - 17:10
(11) Думаю будет 0.
   mistеr
 
16 - 26.05.20 - 17:11
(11) Пока нет.
   seevkik
 
17 - 26.05.20 - 17:12
(13) ыах, там ещё надо переопределить значения элементов массива, ну или отнимать итератор и поставить условие меньше или равно 0
   fisher
 
18 - 26.05.20 - 17:12
Прикольная задачка.
Нужно учитывать, что если дальше есть более высокие дома, то над средними более низкими тоже будет вода.
   DTX 4th
 
19 - 26.05.20 - 17:14
(13) Че-т фигня
Код зависит только от нулей в массиве

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

(16) Решение есть у меня :)
   seevkik
 
20 - 26.05.20 - 17:15
(19) как дал тз так и решил, код рабочий, с оглядкой на (17).
И зависит не от нулей, а от "высоты" зданий
   DTX 4th
 
21 - 26.05.20 - 17:18
(20) Тогда повторю вопрос. Какой ответ для [1,1,0]?
   seevkik
 
22 - 26.05.20 - 17:18
(21) сколько ты этажей зальешь?
   dezss
 
23 - 26.05.20 - 17:19
(21) 0
   fisher
 
24 - 26.05.20 - 17:20
Высота столба воды для каждого "междудомного" промежутка равна минимуму максимальной высоты домов слева и справа.
   dezss
 
25 - 26.05.20 - 17:20
ИМХО, идти надо с первого этажа, фиксируя значения, когда находишь следующее здание.
Т.е. сперва находим самое высокое здание, а потом цикл с 1 до этой максимальной высоты.
   seevkik
 
26 - 26.05.20 - 17:21
Так, условие именно "между" домами, более понятный пример надо давать
Тогда добавить условие на проверку первого и последнего элемента, если они равно или меньше 0 тогда прервать
   PR
 
27 - 26.05.20 - 17:23
(0) Примитивная задача на 5 минут
И не стыдно ведь
   seevkik
 
28 - 26.05.20 - 17:24
Хотя у тебя туманные условия, если будет массив 1 0 5 5 0 1 сколько воды будет потрачено?
   Fish
 
29 - 26.05.20 - 17:25
(28) Между домами скопится 2. А сколько потрачено - такого вопроса в задаче нет.
   Ненавижу 1С
 
30 - 26.05.20 - 17:26
Выбираем самый левый дом за базовый.
Ищем следующий базовый от текущего базового как:
- первый слева направо, выше текущего
- если таковых нет: то крайний справа из тех, что с максимальной высотой

исследуем интервалы между базовыми домами:
- находим уровень воды и считаем емкость заполнения
 
 Рекламное место пустует
   trad
 
31 - 26.05.20 - 17:27
1. цикл от первого до следующего не меньшего не включительно
2. просуммировать разницы между первым элементом и текущим
3. последний в цикле назначить первым
4. перейти к п.1
   seevkik
 
32 - 26.05.20 - 17:27
(29) сорян, 1050501, а сейчас 7?
   fisher
 
33 - 26.05.20 - 17:28
(28) Да. Дурацкая постановка. Словесное описание не соответствует картинке примера. Из картинки следует, что промежутка между вплотную стоящими домами не существует.
   DTX 4th
 
34 - 26.05.20 - 17:28
(23) Тут утверждают, что код рабочий) Но он 0 не возвращает для этого случая)

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

(27) Я 15 потратил, но был момент, когда думал, что не решу
Кидай решение на pastebin, если так уверен. Как кто решит - даешь ссылку, и мы проверяем :) Там как раз дата создания есть
   Вафель
 
35 - 26.05.20 - 17:28
мне кажется нужно так решать. берешь верхний ряд, первое поле. пытаешься его слить вправо, потом влево
потом 2 поле... потом второй ряд
   dezss
 
36 - 26.05.20 - 17:29
тьфу...да не сложно же
    Мас = Новый Массив;
    Мас.Добавить(5);
    Мас.Добавить(1);
    Мас.Добавить(3);
    Мас.Добавить(0);
    Мас.Добавить(4);
    
    //Мас.Добавить(1);
    //Мас.Добавить(0);
    //Мас.Добавить(5);
    //Мас.Добавить(0);
    //Мас.Добавить(5);
    //Мас.Добавить(0);
    //Мас.Добавить(1);
    
    ВсегоВоды = 0;
    МаксВысота = 5;
    Для н = 1 по МаксВысота Цикл
        Добавим = 0;
        Перв = Истина;
        Для й = 0 По Мас.Количество()-1 Цикл
            Если Перв И Мас[й] < н Тогда
                Продолжить;
            КонецЕсли;
            Перв = Ложь;
            Если Мас[й] < н Тогда
                Добавим = Добавим + 1;
            Иначе
                ВсегоВоды = ВсегоВоды + Добавим;
                Добавим = 0;
            КонецЕсли;
        КонецЦикла;
    КонецЦикла;
    
    Сообщить(ВсегоВоды);
Ко
   Вафель
 
37 - 26.05.20 - 17:29
можно провести оптимизацию и искать диапазон что не сольется
   sikuda
 
38 - 26.05.20 - 17:30
1. Найти два наибольших числа - это стакан.
2. Воды внутри стакана это вторая высота на расстояние между станками минут что внутри.
3. Внутри стакана нашли. Это стакан разбивает задачу на две аналогичные...
   dezss
 
39 - 26.05.20 - 17:33
(38) Только дно у стакана может быть не ровным.
   dezss
 
40 - 26.05.20 - 17:34
(36) Можно даж слегка оптимизировать.
Если макс высота всего одна, то первый цикл по высоте здания, которые идем следующим.
   sikuda
 
41 - 26.05.20 - 17:36
(39) Так минус сумма чисел внутри стакана,но мне кажется можно и одно проходным сделать...
(36) Мне кажется нет определения левой и правой стенки. Без одной из них вода выливается...
   trad
 
42 - 26.05.20 - 17:37
(40) задача решается одним циклом
в (36) хотя бы определение МаксВысота - это уже цикл
   Ненавижу 1С
 
43 - 26.05.20 - 17:41
+(30) оценка времени выполнения O(N^2)
   Ненавижу 1С
 
44 - 26.05.20 - 17:42
+(43) хотя нет O(N)
   seevkik
 
45 - 26.05.20 - 17:42
(34) слишком грубый пример, кто знал что справа и слева от картинки пустота и между ними не копится вода, не олимпиадник, извиняюсь)
   fisher
 
46 - 26.05.20 - 17:43
(43) Вижу решение за O(N). За два прохода короче :) Но с доп. памятью.
   PR
 
47 - 26.05.20 - 17:44
(34) Ну код я писать не буду ессно, но идея следующая для n домов:
Берем цикл по i от 1 до n - 2, то есть количество дырок в один дом между домами
В нем МаксимальнаяВысотаЛевогоДома = Max(высоты домов от 1 до i) и МаксимальнаяВысотаПравогоДома = Max(высоты домов от i + 2 до n)
В дырку между домом i и домом i + 2 зальется Min(МаксимальнаяВысотаЛевогоДома, МаксимальнаяВысотаПравогоДома) - высота дома i + 1 (то есть дома в дырке)
Если получившееся число отрицательное, то берем вместо него 0
Конец цикла
Все посчитанное в цикле ессно суммируем
   PR
 
48 - 26.05.20 - 17:46
(38) Это рекурсия
Нахрен с пляжа
   1Снеговик
 
49 - 26.05.20 - 17:47
(47) лучше бы код написал, проще воспринимать)
   fisher
 
50 - 26.05.20 - 17:48
(47) Типа того. И тут либо квадратичное количество итераций, либо два прохода с доп-массивом.
(48) И чо? Рекурсивно тоже можно решить.
   DTX 4th
 
51 - 26.05.20 - 17:49
(30) Не понимаю
Если будет [1,2,3], как считать?

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

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

(36) Блин, почему не на js, как проверять то.
Не уверен, что будет работать
   Ненавижу 1С
 
52 - 26.05.20 - 17:51
(51) ну вот исходя из (30)
базовый [1], следующий базовый [2] следующий [3]
считаем между ними воду: расстояний нет между домами в конкретном примере - получаем 0
   seevkik
 
53 - 26.05.20 - 17:54
Ок, делаем так
Находим максимальный элемент массива, далее берём первый элемент, далее бежим по массиву пока не найдем равное или больше первого элемента или пока не дойдем до максимума, по пути считаем количество этажей и пройденный путь
Если найдем нужный элемент, то умножаем первый на количество пройденного пути и минусуем количество этажей
И делаем такой же цикл, только с конца до максимального элемента
   seevkik
 
54 - 26.05.20 - 17:57
(30) а если высота домов 1 0 5 0 5 0 3 0 1
   DTX 4th
 
55 - 26.05.20 - 17:59
(46)(47)(50) Неэффективно. Решается за O(N) без доп памяти :)
   seevkik
 
56 - 26.05.20 - 18:00
Да, вижу "если таковых нет: то крайний справа из тех, что с максимальной высотой", сильно конечно)
   RomanYS
 
57 - 26.05.20 - 18:03
(55) А вот это уже гораздо интереснее :)
   PR
 
58 - 26.05.20 - 18:05
(55) Да похрен
   DTX 4th
 
59 - 26.05.20 - 18:06
(53) [1,0,2,3]
Макс - 3
Первый элемент - 1
Бежим
Находим 2
Прошли два дома в длину и один этаж?

Как блин это читать.
   seevkik
 
60 - 26.05.20 - 18:08
(59) прошли минус 1, ну ты чего)
 
 Рекламное место пустует
   lodger
 
61 - 26.05.20 - 18:10
(54) а если вводная меняется, то пишите алгоритмы этого чятика сначала.
   mikecool
 
62 - 26.05.20 - 18:12
а я на этой погорел:
   mikecool
 
63 - 26.05.20 - 18:12
Штаб гражданской обороны Тридесятой области решил обновить план спасения на случай ядерной атаки. Известно, что все n селений Тридесятой области находятся вдоль одной прямой дороги. Вдоль дороги также расположены m бомбоубежищ, в которых жители селений могут укрыться на случай ядерной атаки.

Чтобы спасение в случае ядерной тревоги проходило как можно эффективнее, необходимо для каждого селения определить ближайшее к нему бомбоубежище.
   mikecool
 
64 - 26.05.20 - 18:12
в 1000 мс не уложился ((( на питоне
   seevkik
 
65 - 26.05.20 - 18:25
Имеем массив 2 1 3 0 5 0 5 0 3
Максимальный элемент = 2; (его порядковый номер)
ЛевыйВысокий=массив[0];
Заполнено = 0;
Пройдено =0;
С итератор=1 по итератор=максэл цикл
Если ЛевыйВысокий>массив[итератор] тогда
Пройдено=пройдено+1;
Этажей = этажей+массив[итератор];
Иначе
ЛевыйВысокий = массив[итератор];
Заполнено = заполнено+пройдено*левыйвысокий-этажей;
Конецесли
Конеццикла
Ну и такой же, только в обратную сторону
   DTX 4th
 
66 - 26.05.20 - 18:26
(63) Блин, надо поработать)
Через пару часов выложу решение для (0)

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

Далее цикл по селеньям:
Пока от текущего селения ближе до m2 чем до m1, увеличиваем индекс убежищ (i++)
Выводим: для текущего селения ближайшее убежище - m1
КонецЦикла
   Dmitry77
 
67 - 26.05.20 - 18:27
переберать массив по этажу.
1 слева дом 1 этаж. проверяем есть вода или нет и прибавляем 1 или 0. 2 дом 1 этаж. и т. д.

Два цикла внешний по этажам. внутренний по домам.
   seevkik
 
68 - 26.05.20 - 18:27
(65) упс, максимальный элемент [4]
   mistеr
 
69 - 26.05.20 - 18:28
Функция РассчитатьОбъемВоды(Дома)
    
    Перем ОбъемВоды, Высота, ЕстьДома, Вода;
    
    ОбъемВоды = 0;
    Высота = 1;
    ЕстьДома = Истина;
    
    Пока ЕстьДома И Высота < 1000 Цикл
        ЕстьДома = Ложь;
        Вода = 0;
        Для Каждого Дом Из Дома Цикл
            Если Дом >= Высота Тогда // тут дом
                ОбъемВоды = ОбъемВоды + ?(ЕстьДома, Вода, 0);  // считаем накопленное
                Вода = 0;  // сливаем воду
                ЕстьДома = Истина;
            Иначе // тут пусто
                Вода = Вода + 1;  // накапливаем воду
            КонецЕсли;
        КонецЦикла;
        Высота = Высота + 1;  // идем на следующий этаж
    КонецЦикла;
    
    Возврат ОбъемВоды
    
КонецФункции
   mistеr
 
70 - 26.05.20 - 18:29
(69) Блин, тупой форматтер.
   Dmitry77
 
71 - 26.05.20 - 18:32
для массива из (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
   Генератор
 
72 - 26.05.20 - 18:36
накидал прогу, 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го
   RomanYS
 
73 - 26.05.20 - 18:40
(72) смотри (55)
Решение O(N) с двумя допмассивами в три прохода на поверхности и здесь уже описано. А вот без доппамяти гораздо интереснее
   DTX 4th
 
74 - 26.05.20 - 18:41
(69) Че-т не то.
Для [0, 1] и [1, 0], похоже, разные результаты будут

(71) Не понимаю
"проверяем, есть вода или нет"
Как проверяем?
   mistеr
 
75 - 26.05.20 - 18:42
(63) И каковы входные данные?
   mistеr
 
76 - 26.05.20 - 18:43
(74) Одинаковые
   Dmitry77
 
77 - 26.05.20 - 18:45
(74) сравниваем тек значение с крайними. и проверяем тек значение не дом ли это.
   Генератор
 
78 - 26.05.20 - 18:48
(73) у меня нет доп массивов, только 2 аккумулирующие переменные, основная и промежуточная
   DTX 4th
 
79 - 26.05.20 - 18:52
И кто мне объяснит, как с доппамятью решать? Пока не пойму, что там хотите хранить

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

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

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

Решение понял) Похоже, оно похоже на (47)
   RomanYS
 
80 - 26.05.20 - 19:01
(78) но и O(N) нет: "вложенный цикл"
   mistеr
 
81 - 26.05.20 - 19:02
(73) Что-то я не вижу ни одного решения с O(N). А интересно..
   RomanYS
 
82 - 26.05.20 - 19:04
(81)
1й проход - собираем нарастающие максимумы слева в массив
2-й - во второй допмассив собираем максимумы справа
3-й - считаем объем
   Cyberhawk
 
83 - 26.05.20 - 19:06
(3) На какую позицию такое дают?
   mistеr
 
84 - 26.05.20 - 19:06
(82) Код нужен. Только по коду можно понять, O(N) там или что.
   DTX 4th
 
85 - 26.05.20 - 19:07
В общем, вот мое:
Проходим по массиву, получаем максимум - M
Дальше будем идти к этому максимум с двух сторон
Идем слева, запоминая высоту самого высокого дома - L
На каждом шаге добавляем к результату L-h, где h - высота текущего дома

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

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

(82) Теперь понял)
   DTX 4th
 
86 - 26.05.20 - 19:08
(83) Рядовой мидл.

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

Вот попроще, если кому интересно:
Дана карта (матрица),  с 1 и 0.
1 - земля. 0 - вода. Нужно найти площадь самого большого острова. Земля  соединяется только по горизонтали и вертикали
   PR
 
87 - 26.05.20 - 19:09
(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).Текст = "Воды: " + ОбъемВоды;

   Cyberhawk
 
88 - 26.05.20 - 19:10
(86) Мидл на какой стек?
   mistеr
 
89 - 26.05.20 - 19:10
(85) Код давай
   Ненавижу 1С
 
90 - 26.05.20 - 19:10
Моё решение:
https://ideone.com/RP32SG
   seevkik
 
91 - 26.05.20 - 19:12
Можно без нахождения максимума сделать цикл в цикле пока они не встретятся, чутка дешевле выйдет, только надо определять переменную которая показывает какая сторона выше на данной итерации
   RomanYS
 
92 - 26.05.20 - 19:12
(85) красиво
   Cyberhawk
 
93 - 26.05.20 - 19:14
(92) Но два прохода
   PR
 
94 - 26.05.20 - 19:15
(85) Прикольно, да
Можно, кстати, даже в один цикл сделать :))
   seevkik
 
95 - 26.05.20 - 19:16
(93) два не полных прохода, это в счёт?
   Ненавижу 1С
 
96 - 26.05.20 - 19:17
(85) по-твоему там только две лужи воды образуется? это не так
   Cyberhawk
 
97 - 26.05.20 - 19:19
(95) Почему неполных - максимум чтоб найти это один проход, далее с двух сторон накопить пустоту - вот и второй проход
   seevkik
 
98 - 26.05.20 - 19:19
(97) упс) а если (91) ?
   PR
 
99 - 26.05.20 - 19:20
(98) Цикл в цикле - это больше двух
   DTX 4th
 
100 - 26.05.20 - 19:21
(88) с++
(89) Да ладно, все понятно же
Код сложнее читать

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

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

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

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