A-div2:
Вычисляем разность n - 10 (т.к. пиковая дама оценивается в 10 очков). Если разность находится в промежутке [1;9] или равна 11, то ответом будет 4, т.к. карт с такими номиналами существует по 4 штуки на номинал. Если разность равна 10, то ответом будет 15, т.е. 4 десятки, 4 вальта, 3 дамы (пиковая дама из колоды извлечена) и 4 короля. Во всех остальных случаях ответ равен нулю (по очевидной причине).
B-div2/A-div1:
Достаточно воспользоваться следующим рекуррентным соотношением: count[i] = count[i - 1] + 1 + (answers[i] - 1) * i, и учесть, что count[1] = answers[1]. Массив answers[i] обозначает количество ответов на i-ый вопрос, count[i] - количество кликов, необходимое для ответа на i-ый вопрос.
Пояснение к формуле:
Чтобы ответить на первый вопрос, нужно перебрать все возможные варианты ответа на него. Чтобы ответить на i-ый вопрос, нужно узнать правильный ответ на (i - 1)-ый вопрос и далее перебрать все ответы на i-ый. Первая попытка делается за 1 клик, последующие - за i кликов (т.к. мы начинаем отвечать сначала).
C-div2/B-div1:
При помощи DFS находим количество циклов в графе и проверяем его на связность. Если граф связный, а цикл один - значит это Ктулху, в противном случае это не Ктулху (К.О.).
D-div2/C-div1:
Основная часть данной задачи - найти закономерность заполнения ячеек патронами. Найдем эту закономерность по индукции. Если патрон один - его можно поместить куда угодно, но т.к. нам нужна лексикографически минимальная строка, поместим его в самую правую ячейку. Теперь разберем случай с большим количеством патронов. Когда у нас один патрон находится в крайней правой ячейке, ячейки с той же четностью оказываются для нас проигрышными, а остальные - соответственно, выигрышными. Т.о. по идее, мы должны заполнять заведомо проигрышные ячейки справа налево, а после их заполнения заполнять справа налево и выигрышные ячейки. Но... это верно лишь для четного количества ячеек. Для нечетного количества ячеек второй патрон выгоднее посылать в предпоследнюю ячейку (т.к. количество выигрышных ячеек все равно не изменится, но зато при лексикографическом сравнении такая строка будет меньше). Далее заполняем аналогично с четным количеством ячеек.
E-div2/D-div1:
Считываем все запросы и сортируем их по b. Далее используем ДП для всех запросов с b < 500 (т.к. запросы у нас отсортированы, для запоминания ответов нам хватит одномерного массива размера n), а остальные вычисляем наивным алгоритмом. За объяснение того, зачем следует выполнять сортировку, спасибо Александру Миланину (Milanin).
E-div1:
Эту задачу я пока не решил :).
Далее используем ДП для всех запросов с b < 500
Вы либо напишите пометку (К.О.), либо распишите, что это за ДП.
По поводу D(div1). Непонятно, зачем разделять запросы на два типа. Реально решение еще проще.
Решение. Посчитаем наивно все запросы. Единственная оптимизация, которую мы сделаем - сгруппируем запросы (a, b) и (a', b), если a mod b == a' mod b. Ясно, например, как посчитать (2,3), (5,3) и (11,3) за n/3 операций без всякой дополнительной памяти, ДП и т.д. Все решение - сортировка запросов.
Доказательство. Чтобы ответить на (a,b) нужно сделать n/b операций. Но т.к. мы сгруппировали модули, то надо обработать не более b таких запросов. Получаем, что за обработку 2n элементов можно выполнить не менее 3 запросов, за 3n - не менее 6, и т.д. Итого время работы - O(n * sqrt(p)).
seems pretty good at this. And that's how I read Russian and Japanese posts.
Запросы так же делятся на два типа: b <= B и b > B. (в моем решении B = 175). Вторые обрабатываем, что называется, втупую, а с первыми поступаем так:
Заметим, что для конкретного b ответ является суммой на отрезке одной из таких последовательностей:
a[0], a[b], a[2b], ...
a[1], a[b+1], a[2b+1], ...
.................................
a[b-1], a[2b-1], a[3b-1], ...
Теперь к каждому такому воображаемому массиву применяем sqrt-декомпозицию. Сохраняем все эти данные в трехмерный массив p, где p[i][j] содержит предпросчитанные суммы одной из указанных выше последовательностей (здесь i = b, а j - это индекс первого элемента в массиве a (от 0 до b-1)).
Каждый массив p[i][j] имеет длину sqrt(n / i), а общее число элементов в p равно sum{i*sqrt(n/i)} = sum{sqrt(ni)} <= B*sqrt(nB) <= 1500000, что прекрасно лезет в память.
TeX-формулы в предпросмотре выглядели настолько ужасно, что решил их не применять
Все когда-то начинают писать в первый раз и вот в этот момент их нужно поддержать. Если есть огрехи -указать, неточности - подправить и направить в нужное русло.
Другое дело что "молодой и горячий" сам "вызывает огонь на себя" тем, что вместо фраз "Спасибо за замечание, учту..." или "А как бы Вы (ты) посоветовали (вал) написать?" и т.д. в ответ пишет "Можно подумать..."
Так что желательно сбросить пар и перейти в более конструктивное русло.
А если кому-то не нравится - так здесь неофициальный разбор, как указано в теме, возьмите и предложите свой. Опять же пользы будет всем, как и автору поста, так и писавшему, да и остальным тоже, особенно тем, кому это интересно
Так что не бойтесь критики и не реагируйте на неё резко - подумайте и попробуйте написать по другому... А потом всё начнёт потихоньку получаться.
Ну так я и написал, что реакция с обеих сторон резковата. Кто-то резковато покритиковал, автор - сразу чуть ли не с обидой в ответ резковато отвечает, что и перешло почти, как Вы правильно заметили, во взаимные наезды.
Если бы все обращали внимание на все резкие слова сказанные в их адрес, это было бы что-то невообразимое.
Поэтому прочли - там где сочли нужным - ответили, а если не сочли нужным отвечать - не ответили. Но в любом случае нужно просто анализировать не только решения, но и сообщения. И задавать себе вопросы, типа "А как бы элегантно написать так, чтобы в следующий раз подобных "наездов" не было?" Это по сути процесс взаимного общения, пусть и дистанционного и разные люди по разным причинам иногда на одну и ту же фразу реагируют по разному. Поэтому и тут нужно каждому учится искусству подобного интернет-общения.
Так же и в реальной жизни: один раз с женой пошутил - рассмеялась, так как хорошее настроение было, а иной раз за подобную шутку можно чуть ли не поварёшкой по лбу получить... :)
А разборы пишите - не стесняйтесь. Это подобно решению задач: как невозможно научиться решать задачи не решая их, так и невозможно научиться толком объяснить решения, не пробуя объяснять их другим.