Dragon (Editorial)

Пояснення

Позначимо:

• $x$ — кількість S-ніжок

• $y$ — кількість драконів

Отримуємо систему рівнянь:

З першого рівняння виразимо $x$:

Підставляємо у друге рівняння:

Якщо B - S \cdot A = 0, то N = S \cdot K (будь-яке y \geq 1 підходить)

Якщо B - S \cdot A \neq 0, то:

Алгоритм

1. Перебираємо значення $y$ від 1 до нескінченності, поки задовільняється умова задачі

2. Для кожного $y$ обчислюємо x = A - K \cdot y

3. Перевіряємо, що x \geq 1 (має бути хоча б одна S-ніжка)

4. Обчислюємо N = \frac{B - x \cdot S}{y}

5. Перевіряємо, що $N$ ціле і невідʼємне (так, можуть бути дракони без ніг)

6. Виводимо знайдене $N$

Якщо жодне $y$ не дає коректного розв'язку, виводимо $-1$.

Складність за часом: $O(A/K)$

Реалізація

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

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int s, k, a, b;
    cin >> s >> k >> a >> b;

    int y = 1;
    int x = a - k * y;
    while (x >= 1)
    {
        int n = b - x * s;
        if (n >= 0 && n % y == 0)
        {
            cout << n / y << endl;
            return 0;
        }
        ++y;
        x = a - k * y;
    }

    cout << -1 << endl;
}