Сколько клоунов влезет в Фольксваген?

Думаю, многие знают цирковой номер, в котором из крохотного Volkswagen Beetle ("Запорожец" по-немецки) вылезает вереница клоунов, которой, кажется, нет конца. Невольно задумаешься: как же их туда упаковали? Смоделируем эту ситуацию программно.

Даны два класса на Java:

public class Clown {
    // nothing
}

public class Volkswagen {
    private static final int CAPACITY = 5;
    private Set<Clown> clowns = new HashSet<Clown>();

    public synchronized void add(Clown clown) {
        if (clowns.size() >= CAPACITY) {
            throw new IllegalStateException("I'm full");
        } else {
            clowns.add(clown);
        }
    }

    public synchronized void done() {
        if (clowns.size() == 20) {
            // The goal is to reach this line
            System.out.println("I'm a Volkswagen with 20 clowns!");
        }
    }
}

Нужно написать код, который в конце концов вызовет done() и напечатает указанную строку. Начать можно с чего-то такого (работать, конечно, этот пример не будет):

public class Clowns {
    public static void main(String args[]) {
        Volkswagen vw = new Volkswagen();
        for (int i=0; i<20; i++) {
            vw.add(new Clown());
        }
        vw.done();
    }
}

Несколько ограничений:
0. Нельзя изменять данные Вам файлы Clowns.java и Volkswagen.java.
1. Программа должна работать с включенным SecurityManager'ом (т.е. с опцией -Djava.security.manager). Поэтому воспользоваться reflection'ом, чтобы изменить private поле, не получится.
2. Никакие другие опции JVM использовать нельзя. В частности, нельзя подсовывать JVM свой подхаченный ClassLoader, чтобы подменить стандартную реализацию java.util.HashMap
3. Должна выполниться именно указанная строка указанного класса, а не другая строка каким-то хитрым образом скопированного или унаследованного класса.

В остальном Вы вольны делать всё, что Вашей душе угодно. Можете писать сколь угодно грязный код, даже если за такое в приличном обществе принято бить канделябром отрывать руки.

Оригинал задачи на английском я нашёл здесь.

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

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

Наводнение

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