Выход из колеса Сансары, экстремизм и немного зелёнки — разбор задач из буклета GridGain на конференции Joker 2018

*Назвав на нашем стенде автора цитаты и произведение, можно было сразу получить подарок. Конечно, это Юрий Хой (Клинских), «Сектор газа» и трек «Бомж»

Согласно изначальному условию, т.к. периодичность приговоров имеет показательное распределение, то до введения робота и после мы имеем следующие выражения для оценки вероятности того, что вынесли приговор за время ≤ t:

где — это неизвестные параметры, задающие частоту вынесения приговоров, t — параметр времени, по условию выходит что:

Из этих уравнений очень легко выражаются параметры

Из предположения, что число приговоров и число мемасиков имеют линейную зависимость, можно заключить, что отношение как раз и дает искомую величину:

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

Тогда мы отметем варианты, использующие Map<Integer, Integer>, и заметим, что моду удобнее всего искать в отсортированном массиве: если значение повторяется, все дубликаты находятся рядом. Мы отсортируем массив и за один проход (и две переменные) найдем значение с максимальным количеством повторов.

Теперь заметим что:

1) Отсортировать значения можно рекурсивно.

    // Expectation: if there are more than one mode, we are free to return any of them.
    // 2,2,3,3,4,4 has 3 modes : 2,3,4. I expect that 3 is correct answer.
    public static int mode (int a, int b, int c, int d, int e, int f){
        // If arguments are not sorted, let's sort them with bubble sort :)
        if (a > b)
            return mode(b,a,c,d,e,f);
        if (b > c)
            return mode(a,c,b,d,e,f);
        if (c > d)
            return mode(a,b,d,c,e,f);
        if (d > e)
            return mode(a,b,c,e,d,f);
        if (e > f)
            return mode(a,b,c,d,f,e);

2) У нас всего 6 отсортированных значений.
3) Если значение повторяется 3 раза (половина всех значений) — это уже мода!
3.1) Если нет, но есть 2 повторения — тогда это мода!
3.2) Если нет повторяющихся значений, то любое значение является модой.

  
        // Check for mode with 3+ repeats. 3 repeats is enough to say value is a mode (3 is half of 6).
        // Since args are sorted, a == b && b == c is the same as a == c;
        if (a == c)
            return a;
        if (b == d)
            return b;
        if (c == e)
            return c;
        if (d == f)
            return d;

        // Check for 2 repeats.
        if (a == b)
            return a;
        if (b == c)
            return b;
        if (c == d)
            return c;
        if (d == e)
            return d;
        if (e == f)
            return e;

        return f;
       }

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

Для начала отберем среди конечных значений для цветов только те, что строго меньше 0xFF, ибо, по условию, для значения 0xFF мы можем дать только нижнюю границу употребленного усилителя цвета. Это значения 0xF0, 0x6B и 0xFE. Получаем следующие уравнения:

или

Здесь k — коэффициент действия красных таблеток, , — количество употребленных усилителей (таблетки измеряем в штуках, зеленку — в миллилитрах) соответствующего цвета соответствующим потребителем. Далее, мы знаем, что второй съел на 54 больше красных таблеток, чем первый синих, тут все просто:

Еще одно уравнение получается из условия на соотношение между количеством таблеток и миллилитрами зеленки:

Также имеем из соотношения между красными и синими таблетками:

Кроме того, мы знаем, что зеленки было сколько-то раз по 20мл:

, где z — целое неотрицательное.

Из предположения, что k целое и таблетки едятся целиком (зеленку можно пить как угодно), единственный ответ, который подходит следующий:

Его можно получить довольно просто, например, способом, описанным далее.
Мы имеем соотношение . Единственные разложения числа 39 на два множителя это {1, 39}, {3, 13}. Таким образом, k может принимать значения только из множества {1, 3, 13, 39}. Попробуем значение «3».

Но при этом должно быть кратно 20, что не выполняется для значения (79.5 + 3).

Ровно таким же образом отсеиваются значения «13» и «39». Единственное значение, которое остается для k — это единица. Подставив его, мы не приходим к противоречиям и получаем ответ.

На самом деле, поскольку нигде в задаче не сказано, что коэффициент линейного приращения k красного компонента RGB — целая величина, решений получается целое семейство, *даже* если считать, что зеленку пьют только объемами, кратными 1мл, а таблетки потребляются целиком (что также не оговаривалось отдельно):

n — целое неотрицательное.

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

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