# Разбор задач 2020 года
Если Вы не знали, как решать какую-то задачу, и Вам было лень разбираться в коде на Pascal, то это пост специально для Вас.
:::warning
Убедительная просьба не копировать коды и не пересылать их. Помните -- Вы решаете задачи для себя!
:::

## [1. Неладная фасовка](https://codeforces.com/group/skz9fIV5Hq/contest/306592/problem/A)
:::spoiler Подсказка 1
:::info
Заметим, что во вводе нам дана арифметическая прогрессия; мы можем за $O(1)$ найти стоимость $n$-го подарка: $A_n = A + D(n-1)$. Если же $D=0$ (т.е. стоимость товаров одинаковая), достаточно просто воспользоваться формулой $n=\lfloor \frac{M}{A} \rfloor$.
:::
:::spoiler Подсказка 2
:::info
Сумма первых $n$ членов такой арифметической прогрессии: $S_n = \frac{A + A_n}{2} * n$, или $S_n = \frac{2A + D(n-1)}{2} * n$. Нужно найти последнее целое $n$ такое, чтобы $S_n$ не превышало $M$.
:::
:::spoiler Подсказка 3
:::info
Можно воспользоваться бинарным поиском (т.к. значение $S_n$ возрастает при увеличении $n$) или вывести $n$ из формулы $M = \frac{2A + D(n-1)}{2} * n$. Асимптотика $O(log \hspace{1mm} M)$ или $O(1)$.
:::
:::spoiler Разбор
:::info
Выполнив преобразования формулы $M = \frac{2A + D(n-1)}{2} * n$, получим квадратное уравнение: $Dn^2 + (2A - D)n - 2M = 0$. Дискриминант этого уравнения равен $(2A-D)^2 + 8DM$. Формула $n$: $\lfloor \frac{-(2A-D) + \sqrt{(2A-D)^2 + 8DM}}{2D} \rfloor$.
:::
:::spoiler Код (Python, автор: [Wani4ka](https://codeforces.com/profile/Wani4ka))

import math

a, d, m = map(int, input().split())

def solve():
    if d == 0:
        return m // a
    dis = (a*2-d)**2 + d*m*8
    return math.floor((d - a*2 + math.sqrt(dis)) / (d*2))

print(solve())

:::

## [2. Составной плот](https://codeforces.com/group/skz9fIV5Hq/contest/306592/problem/B)
:::spoiler Разбор
:::info
Давайте воспользуемся бинарным поиском для нахождения максимальной стороны примерно за $O(N \hspace{1mm} log \hspace{1mm} max(A_i))$. В функции проверки мы должны найти количество "подбрёвен", которые мы можем получить из исходных брёвен, и убедиться, что оно не меньше переданной нам стороны.
:::
:::spoiler Код (C++, автор: [Wani4ka](https://codeforces.com/profile/Wani4ka))

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5+7;

int n;
long long a[N];

bool ok(long long side) {
    long long cnt = 0;
    for (int i = 0; i < n; ++i)
        cnt += a[i] / side;
    return cnt >= side;
}

int main() {
    cin >> n;
    for (int i = 0; i < n; ++i)
        cin >> a[i];
    int l = 0, r = N;
    while (l+1 < r) {
        int mid = (l+r)/2;
        if (ok(mid)) l = mid;
        else r = mid;
    }
    cout << l << endl;
    return 0;
}

:::

## [3. Поиск книги](https://codeforces.com/group/skz9fIV5Hq/contest/306592/problem/C)
:::spoiler Разбор
:::info
Сделаем то, о чём сказано в условии.

* Первый массив будет хранить префикс-сумму $B_i$. Условно, $pref_i$ - это последний номер книги, который можно встретить в $i$-м шкафу или ему предшествующих.
* Второй массив будет хранить информацию о самих шкафах, т.е. в $info_i$ хранится номер комнаты и номер $i$-го шкафа.

Ограничения (до $100$ комнат, до $1000$ шкафов в комнате, всего до $10^5$ шкафов) позволяют нам хранить информацию о книгах и шкафах в таком виде.

Теперь, когда нам приходит запрос о местоположении очередной книги, мы при помощи бинарного поиска находим в первом массиве номер шкафа, в котором находится эта книга, и выводим информацию о нём из второго массива.

Асимптотика: $O(K \hspace{1mm} log \hspace{1mm} sum)$ плюс построение за $O(sum)$, где $sum = \sum\limits_{i=1}^N A_i)$.
:::
:::spoiler Код (C++, автор: [Wani4ka](https://codeforces.com/profile/Wani4ka))

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, k;
    cin >> n >> k;
    vector<pair<int, int>> v;
    long long x;
    long long en = 1;
    for (int i = 1; i <= n; ++i) {
        cin >> x;
        for (int j = 1; j <= x; ++j, ++en)
            v.push_back({i, en});
    }
    en = 0;
    vector<long long> pref;
    for (auto to : v) {
        cin >> x;
        en += x;
        pref.push_back(en);
    }
    while (k--) {
        cin >> x;
        int idx = lower_bound(pref.begin(), pref.end(), x) - pref.begin();
        cout << v[idx].first << " " << v[idx].second << endl;
    }
    return 0;
} 

:::

## [4. Рассадка гостей](https://codeforces.com/group/skz9fIV5Hq/contest/306592/problem/D)
:::spoiler Разбор
:::info

Давайте преформулируем задачу на язык олимпиадного программирования:

Вам дано число $N$. Вам нужно вывести множество чисел, сумма которого равна N, а НОК максимален.

Замечания:
1. Легко доказать, что нам всегда выгодно добавлять в множество либо простое число, либо его степень. Это верно, т.к. на очередной операции мы "по-максимуму" умножим наш ответ (НОК).

Давайте напишем динамику $dp_{i,j} = ans$, где $i$ -- параметр суммы чисел из множеста, $j$ -- номер расматриваемого очередного простого числа (или его степень), проще говоря, сколько простых чисел (или их степеней) мы уже рассмотрели, и $ans$ -- максимальный НОК.

Переходы:

1. Пропускаем текущее простое число $dp_{i,j} = dp_{i,j - 1}$;
2. Хотим взять очередное простое число (или его степень) $dp_{i,j} = max(dp_{i,j}, dp_{i - (prost_j)^{st}} * (prost_j)^{st})$;

Не забываем хранить предков!

Самое неприятное в этой задаче было то, что ответ не влезал в long long. Без "длинки", к сожалению, можно было только взять 40 баллов.

:::
:::spoiler Код (Python, автор: [Adamenko](https://codeforces.com/profile/Adamenko))

def array1d(n):
    arr = []
    for i in range(n):
        arr.append(0)
    return arr

def array2d(n, m):
    arr = []
    for i in range(n):
        arr.append(array1d(m))
    return arr


dp = array2d(1000 + 1, 200)
pr = []
prost = array1d(1005)
mac = array2d(1000 + 1, 200)


def output(i, j):
    if i == 0:
        return
    if j < 0:
        i = 0
    output(i - mac[i][j], j-1)
    if mac[i][j]:
        for k in range(2, mac[i][j]+1):
            print(i + k - mac[i][j], end=' ')
        print(i - mac[i][j] + 1, end=' ')


pr.append(0)
for i in range(2, 1001):
    if prost[i] == 0:
        prost[i] = i
        pr.append(i)
    for j in pr:
        if (j * i <= 1000) and (j <= prost[i]):
            prost[i * j] = j
        else:
            break


n = int(input())
for i in range(len(pr)):
    mac[i][0] = i
    if i == 0:
        dp[0][0] = 1
    else:
        dp[0][i] = 1
        dp[i][0] = 0
for i in range(1, n+1):
    for j in range(1, len(pr)):
        dp[i][j] = dp[i][j-1]
        lol = 1
        while lol <= i:
            if dp[i][j] < lol * dp[i-lol][j-1]:
                dp[i][j] = lol * dp[i-lol][j-1]
                mac[i][j] = lol
            lol *= pr[j]
ma = -1
x = -1
y = -1
for i in range(len(pr)):
    if ma < dp[n][i]:
        ma = dp[n][i]
        x = n
        y = i
print(ma)
output(x, y)
print()

:::