Наводнение

Дан массив целых положительных чисел, который представляет собой карту высот сложенного из кубиков 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%, если назовёт нужную цифру.

Сумасшедший пассажир

Идёт посадка пассажиров в 100-местный самолёт. У каждого пассажира есть билет, в котором указано его место, и все места проданы (но, конечно, без овербукинга). Однако первый же зашедший в салон пассажир выбрал себе случайным образом одно из 100 мест и разместился на нём.

Следующие 99 пассажиров поступают следующим образом: если место, указанное в билете, свободно, пассажир садится на него. В противном случае (т.е. если назначенное ему место уже занято) пассажир садится на любое из свободных мест случайным образом.

Какова вероятность того, что последний (сотый) пассажир окажется на своём месте?

Дмитрий Медведев и метро

Дмитрий Медведев любит немного развеяться после трудного рабочего дня. Для этого он записался в секцию бадминтона (тренер - МСМК В. Путин) и в кружок занимательной арифметики (преподаватель - д.ф.-м.н. В. Чуров).

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

Известно, что поезда в обоих направлениях следуют с одинаковым интервалом в 2 минуты по чёткому расписанию. Дмитрий Медведев спускается в метро между 18:00 и 18:30, и можно считать, что каждый день это время выбирается случайным образом.

Казалось бы, время между кружком и секцией должно было бы распределяться поровну. Однако через год оказалось, что бадминтоном Дмитрий Медведев занимался в среднем в 3 раза чаще, чем арифметикой. Как такое может быть?