AlexanderBolshakov's blog

By AlexanderBolshakov, 13 years ago, translation, In English
A-div2:
First, we need to calculate n - 10 (because the queen of spades costs 10 points). If the difference stands in the [1;9] segment or is equal to 11, then the answer will be 4, because there are 4 cards for each cost. If the difference is 10, then the answer will be 15, i.e. 4 tens, 4 jacks, 3 queens (the queen of spades has been extracted from the pack) and 4 kings. And it's obvious that in all other cases the answer will be 0.

B-div2/A-div1:
We need to use the following recurrence relation: count[i] = count[i - 1] + 1 + (answers[i] - 1) * i, and remember that count[1] = answers[1]. The answers[i] array contains the count of answers for the i-th question, count[i] - count of clicks that you need to answer the i-th question.
Explanation of the formula:
To answer the first question, we need to brute-force all of the answers to it. To answer the i-th question, we need to answer the (i-1)-th question and then brute-force the answers to the i-th. For the first try, we need only 1 click, for all other - i clicks (because we start answering from the very beginning).

C-div2/B-div1:
We need to check the graph for connectivity and count loops in it using DFS. If the graph is connective and has only one loop - it is Cthulhu, if not - it isn't Cthulhu (C.O.).

D-div2/C-div1:
Основная часть данной задачи - найти закономерность заполнения ячеек патронами. Найдем эту закономерность по индукции. Если патрон один - его можно поместить куда угодно, но т.к. нам нужна лексикографически минимальная строка, поместим его в самую правую ячейку. Теперь разберем случай с большим количеством патронов. Когда у нас один патрон находится в крайней правой ячейке, ячейки с той же четностью оказываются для нас проигрышными, а остальные - соответственно, выигрышными. Т.о. по идее, мы должны заполнять заведомо проигрышные ячейки справа налево, а после их заполнения заполнять справа налево и выигрышные ячейки. Но... это верно лишь для четного количества ячеек. Для нечетного количества ячеек второй патрон выгоднее посылать в предпоследнюю ячейку (т.к. количество выигрышных ячеек все равно не изменится, но зато при лексикографическом сравнении такая строка будет меньше). Далее заполняем аналогично с четным количеством ячеек.

E-div2/D-div1:
Считываем все запросы и сортируем их по b. Далее используем ДП для всех запросов с b < 500 (для запоминания ответов нам хватит одномерного массива размера n), а остальные вычисляем наивным алгоритмом. За объяснение того, зачем следует выполнять сортировку, спасибо Александру Миланину (Milanin).

E-div1:
Эту задачу я пока не решил :).

Full text and comments »

  • Vote: I like it
  • +27
  • Vote: I do not like it