SpamGPT-4

Автор задачи: Даниил Орешников, разработчики: Константин Бац и Даниил Орешников

Для решения задачи будем анализировать каждое отправленное сообщение. Можно показать, что ответ не превышает число порядка $$$\frac{T^2}{2}$$$, поэтому в первой подгруппе можно было явно просимулировать все выполняемые ботом действия и обработать каждое сообщение отдельно. Такое решение работает за время $$$\mathcal{O}(\text{ответа})$$$, что помещается в ограничения по времени.

Более аккуратная симуляция процесса, работающая за время $$$\mathcal{O}(T)$$$, проходила вторую подгруппу. Заметим, что сообщения не обязательно отличать друг от друга, достаточно просто считать количество отправленных в какой-либо момент сообщений каждым из ботов.

Пусть $$$\mathtt{recv}_1[t]$$$ и $$$\mathtt{recv}_2[t]$$$ — количество сообщений, полученных первым и вторым ботом в момент времени $$$t$$$, соответственно. Тогда достаточно для каждого $$$t$$$, делящегося на $$$a$$$ или $$$b$$$, увеличивать соответствующий $$$\mathtt{recv}$$$ на $$$1$$$. Помимо этого, надо учесть ответы, и для каждого $$$t$$$ увеличить $$$\mathtt{recv}_1[t + 1]$$$ на $$$\mathtt{recv}_2[t]$$$ и наоборот. Перебрав все $$$t$$$ от $$$0$$$ до $$$T$$$ и сложив полученные значения $$$\mathtt{recv}$$$, получим ответ.

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

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

Для третьей подгруппы рассмотрим первый подход. Каждый бот отправляет по новому сообщению каждую секунду, в таком случае в момент времени $$$t$$$ каждый бот получает ответы на все отправленные в момент времени $$$t - 1$$$ сообщения и еще одно новое сообщение. Несложно заметить, что в таком случае в момент времени $$$t$$$ каждый из ботов получает ровно $$$t + 1$$$ сообщение. Осталось просуммировать $$$t + 1$$$ по всем $$$t$$$ от $$$0$$$ до $$$T$$$. Получится сумма арифметической прогрессии, то есть $$$$$$\text{ответ} = \frac{(T + 1)(T + 2)}{2} \text{.}$$$$$$

Для четвертой подгруппы проще рассмотреть второй подход. Поскольку $$$a \le T \le b < 2a$$$, первый бот успеет отправить ровно два сообщения, а второй — не больше двух (в момент времени $$$0$$$, и возможно в момент времени $$$T$$$, если $$$T = b$$$). Для каждого отправленного сообщения легко посчитать, сколько ответов на него получит каждый из ботов. Ответы пересылаются каждую секунду, то есть любой бот получает ответ на свое сообщение каждые две секунды, начиная со следующей после момента отправки.

Таким образом, первый бот на сообщение, отправленное им в момент времени $$$t$$$, получит ровно $$$\left\lfloor\frac{T - t + 1}{2}\right\rfloor$$$ ответов. А второй бот получит это самое сообщение или ответы на него в моменты времени $$$t$$$, $$$t + 2$$$, ..., то есть получит всего $$$\left\lfloor\frac{T - t + 2}{2}\right\rfloor$$$ сообщений, начавшихся с данного. Чтобы получить ответ, осталось просуммировать данные величины для каждого отправленного сообщения, которых не больше четырех.

Полное решение опирается на использованную выше идею. Если первый бот отправляет сообщение в момент времени $$$ka$$$, где $$$k \ge 0$$$ — некоторое целое число, то он сам получит благодаря ему $$$\left\lfloor\frac{T - ka + 1}{2}\right\rfloor$$$ сообщений, а второй получит $$$\left\lfloor\frac{T - ka + 2}{2}\right\rfloor$$$ сообщений. Ответ для первого бота, таким образом, равен $$$$$$\sum\limits_{k=0}^{\left\lfloor\frac{T}{a}\right\rfloor} \left\lfloor\frac{T - ka + 1}{2}\right\rfloor + \sum\limits_{k=0}^{\left\lfloor\frac{T}{b}\right\rfloor} \left\lfloor\frac{T - kb + 2}{2}\right\rfloor \text{,}$$$$$$ а для второго — симметрично наоборот.

Посчитаем каждую сумму отдельно. Заметим, что если бы не было деления на $$$2$$$, получилась бы арифметическа прогрессия с шагом $$$a$$$ или $$$b$$$. Сумму арифметической прогрессии с шагом $$$\small\Delta$$$, начинающейся в числе $$$x$$$ и имеющей $$$q$$$ элементов, можно посчитать по формуле $$$$$$qx + {\small\Delta} \frac{q(q - 1)}{2} \text{.}$$$$$$ Если представить выражение $$$\left\lfloor\frac{r_1}{2} + \frac{r_2}{2} + \ldots + \frac{r_q}{2}\right\rfloor$$$ как $$$\frac{r_1 + r_2 + \ldots + r_q}{2} - \frac{(r_1 \bmod 2) + (r_2 \bmod 2) + \ldots + (r_q \bmod 2)}{2}$$$, то остается только посчитать сумму остатков членов данной прогрессии по модулю $$$2$$$ и вычесть, после чего поделить результат на $$$2$$$.

Для этого достаточно посчитать, сколько членов прогрессии имеют остаток $$$1$$$ по модулю $$$2$$$. Если мы считаем прогрессию из элементов вида $$$T - ka + 1$$$, то в зависимости от четности $$$T$$$ и $$$a$$$ можно за $$$\mathcal{O}(1)$$$ посчитать количество нечетных элементов. Соответственно, теперь мы умеем вычислять сумму прогрессии и сумму остатков ее элементов по модулю $$$2$$$, а значит можем и вычислить исходную сумму за время $$$\mathcal{O}(1)$$$.