Competitive Programming Solutions

793A - Oleg And Shares

31 Dec 2020 — Tags: math,implementation — URL

Let’s say that after some number of operations, all numbers become $x$. Note that $x$ has to be $\min(a_1, a_2,… a_n)$, because it would be suboptimal otherwise.

So, if all numbers can reach $x$ by decrementing by $k$, then it should be possible.

Time complexity: $O(n)$

Memory complexity: $O(n)$

Click to show code.

 

using namespace std;
using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
ll solve(vi a, int k)
{
    int mv = *min_element(begin(a), end(a));
    ll ans = 0;
    for (auto x : a)
    {
        if ((x - mv) % k)
            return -1;
        ans += (x - mv) / k;
    }
    return ans;
}
int main(void)
{
    ios::sync_with_stdio(false), cin.tie(NULL);
    int n, k;
    cin >> n >> k;
    vi a(n);
    for (auto &x : a)
        cin >> x;
    cout << solve(a, k) << endl;
    return 0;
}

Related posts