Наводнение (продолжение)

Коллега, который рассказал мне задачу про наводнение, поделился решением, которое требует всего одного прохода по массиву и константной памяти. Подробности под катом.

Наводнение

Дан массив целых положительных чисел, который представляет собой карту высот сложенного из кубиков 1x1 макета местности. Макет полностью погружают под воду, а затем поднимают. При этом часть воды остаётся в углублениях макета, а часть стекает влево или вправо.

Например, массив, местность и оставшаяся вода могли бы выглядеть так:

Напишите функцию, которая принимает на вход массив - карту местности и возвращает одно число - объём оставшейся воды. Желательно, чтобы алгоритм работал за линейное время (от длины массива).

Старая советская задача

Перед Вами картинка. Глядя на неё, ответьте на 9 вопросов:
1. Сколько туристов живет в этом лагере?
2. Когда они сюда приехали: сегодня или несколько дней назад?
3. На чем они сюда приехали?
4. Далеко ли от лагеря до ближайшего селения?
5. Откуда дует ветер: с севера или юга?
6. Какое сейчас время дня?
7. Куда ушел Шура?
8. Кто был вчера дежурным? (Назовите по имени.)
9. Какое сегодня число какого месяца?

Дмитрий Медведев и 1000 бутылок

Дмитрий Медведев готовится к церемонии вступления в должность одного своего друга, которая состоится через 2 месяца. В качестве подарка он подготовил 1000 бутылок дорогого французского вина.

Совершенно случайно он узнал, что в одну из бутылок агенты Госдепа недоброжелатели подмешали споры оранжевой чумы. Тот, кто выпьет отравленного вина из этой бутылки, ровно через 2 месяца станет совершенно оранжевым на всю жизнь, а до этого момента яд никак себя не проявляет. К сожалению, Дмитрий Медведев не знает, какая именно из бутылок отравлена, а найти её по внешнему виду или запаху невозможно.

В распоряжении Дмитрия Медведева есть 10 оппозиционеров подопытных кроликов. Он хочет за оставшиеся до церемонии 2 месяца вычислить отравленную бутылку, а остальные 999 подарить. Что он должен для этого сделать?

10 перчаток

В ящике лежит 5 пар печаток: 3 пары синих и 2 пары зелёных, т.е. всего 10 перчаток. Из ящика наугад достали одну за другой 3 перчатки. Какова вероятность того, что среди них найдётся пара (т.е. левая и правая перчатки одного цвета)?

Эльфийский МММ

Бессмертный эльф Леголас несколько тысяч лет назад вложил 100 золотых монет в инвестиционный фонд "Мордор Может Многое" (МММ) под 5% годовых. Теперь он хочет забрать свои деньги и купить однокомнатное дерево в Лориене.

Владелец МММ, коварный Саурон, поставил следующее условие: Леголас должен правильно назвать первую цифру в сумме на его счету. В противном случае все его деньги навечно останутся в МММ. К сожалению, вклад был открыт так давно, что Леголас совершенно не помнит, сколько лет прошло, и не может просто посчитать сумму на калькуляторе. Возможно, прошла тысяча лет, возможно полторы, возможно и все пять.

Какую цифру должен назвать Леголас, чтобы получить свои деньги с максимальной вероятностью? Считаем, что эльфы пользуются десятичной системой счисления.

Интуитивно, конечно, кажется, что все цифры от 1 до 9 равновероятны, и шансы угадать в любом случае равны 1/9. На самом же деле, Леголас может забрать свой вклад с вероятностью 30%, если назовёт нужную цифру.