Да, проблемы с точностью, если в моем решении заменить финальную проверку в бинпоиске изменить с величины потока на количество достижимых вершин, то решение проходит в практисе.

Теперь немного о решении. Есть замечательный алгоритм Гольдберга для поиска подграфа с максимальной средней степенью: http://www.eecs.berkeley.edu/Pubs/TechRpts/1984/CSD-84-171.pdf В нем мы максимизируем sum(edges)/K, в нашем же случае в знаменателе стоит квадратичная функция. Однако оказывается, что такое же решение можно применить и в данном случае.

Будем делать бинпоиск по ответу. Пусть мы хотим проверить значение g. Тогда мы хотим проверить неравенство

sum(a_ij, i,j \in V1) / 2*(K*(200 - K)) < g

если умножить на знаменатель и перегрупировать получаем

sum(a_ij, i,j \in V1) < 398*g*K + K*(K-1)*2*g

квадратичный член в правой части можно внести внутрь суммы, получим

sum(a_ij + 2*g, i,j \in V1) < 398*g*K

ну а дальше осталось применить алгоритм Гольберга, т.е. построить подходящий граф и пустить в нем поток. Если минимальный разрез содержит больше 1 вершины в левой доле, то идем в одну сторону в бинпоиске, иначе — в другую. Конкретные веса ребер можно посмотреть у меня в решении или в оригинальной статье.

Собственно я долго выводил эти выражения, где-то ошибся и в итоге 10 минут подбирал коэффициенты, чтобы прошло тесты :) К сожалению я упустил момент с точностью, буквально исправление одной строки делает решение правильным. Также я не успел написать нормальный поток, так что мое решение проходит в практисе за 1.8 секунды.

Еще многие считали биномиальные коэффициенты в массиве 1000*1000, не предусмотрев что может потребоваться С(100000,х)

Нужно рассматривать счастливые числа (состоящие из цифр 4 и 7), а не только счастливые цифры (т.е. числа 4 и 7).

I completely agree. In my opinion, it's too similar to c++. So basically the only thing you had to do is to figure out how to read data (that turned out to be quite similar to C as well). After that it was just solving trivial problems in a familiar language.

Even though it's my first ULR, for future rounds I'd prefer languages with much weirder syntax (something like APL :) ) or non-imperative paradigm (maybe something functional). In that case participants would have to learn something more than just another few library functions.

Наш алгоритм (команда THIRTEEN) при отсутствии грамотного сопротивления убивает противника за 177 ходов следующим образом:

1. Пробиваем портал в 255 клетке противника обычными attack за 30 ходов
2. Строим тело зомби, который делает help x x 8192 и потом делает copy 0 и вызывает себя же с параметром succ x. Кладем это тело в нашу нулевую клетку
   
3. Если заслать этого зомби с параметром х, то он за один ход нанесет по 16384 урона последовательным 66 клеткам, начиная с клетки х.
4. Засылаем последовательно этого зомби начиная с клеток 0, 66, 132 и 198.

Кроме того, наша штука в меру сил пытается восстанавливать свои части в процессе сборки и пробивает портал снова с помощью dec 0, если противник его оживил. Таким образом, если игрок плохо сопротивлялся, то мы укладываем его за 177 ходов + некоторое время на оживление убитых клеток.

У этой атаки есть один недостаток, рекурсивный зомби проходит только по живым клеткам, у которых от 8192 до 16386 жизни, поэтому применять его как оружие массового добивания не получилось. Поэтому после отработки массированой атаки, мы переключались на логику другого бота, который был скорее оборонительным.

Итог: слабых игроков мы стабильно укладываем за 177, немного сопротивляющиеся выдерживают атаки с несколькими уцелевшими ячейками, которые добивает наш второй бот (гдето за 300-500 ходов). Сильные игроки успевают завалить нашу атаку и после этого обычно выигрывают у нашего второго бота за где-то 100К ходов с небольшим перевесом. Самые сильные игроки похоже придумали что-то еще более быстрое и убивают на с 0 ходов за 200-300.

Это по сути обобщение одного из способов получения формулы для чисел Каталана. Посмотреть это можно например в википедии: http://en.wikipedia.org/wiki/Andr%C3%A9%27s_reflection_method и http://en.wikipedia.org/wiki/Catalan_number (раздел Second Proof)

Во-первых, спасибо авторам за новый интересный формат соревнований, и очень "взламываемые" задачи в этом турнире :)