1476B - Inflation

29 Jan 2021 — Tags: greedy — URL

The problem tells us that for each $i > 0$ we need:

\[\frac{p_i}{psum_{i- 1}} \leq \frac{k}{100}\]

Where $psum_{i}$ is the prefix sum of $p$ up to $i$.

To avoid floating errors, we want the following condition:

\[\frac{100 p_i}{k} \leq psum_{i-1}\]

Furthermore, note that it is always optimal to increment $p_0$, as it will necessarily decrease all inflation rates.

So, for each $i$ we can greedily try to increase $p_0$ until the condition holds.

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 ceil(ll a, ll b) { return (a + b - 1) / b; }
ll solve(vector<ll> p, int k)
{
    int n = p.size();
    ll sum = p.front(), ans = 0;
    for (int i = 1; i < n; ++i)
    {
        ll dif = ceil(100 * p[i], k) - (sum + ans);
        if (dif > 0)
            ans += dif;
        sum += p[i];
    }
    return ans;
}
int main(void)
{
    ios::sync_with_stdio(false), cin.tie(NULL);
    int t;
    cin >> t;
    while (t--)
    {
        int n, k;
        cin >> n >> k;
        vector<ll> p(n);
        for (auto &pi : p)
            cin >> pi;
        cout << solve(p, k) << endl;
    }
    return 0;
}

1476A - K Divisble Sum

29 Jan 2021 — Tags: math — URL

Assume $k \geq n$, otherwise find the smallest multiple of $k$ that matches that condition.

We shall fill the $n$ elements with $floor(k / n)$ and then displace uniformly the remainder over all posible $a_i$. In this way the remainder counts for at most $1$.

Time complexity: $O(1)$

Memory complexity: $O(1)$

Click to show code.

using namespace std;
using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
int ceil(int a, int b) { return (a + b - 1) / b; }
int main(void)
{
    ios::sync_with_stdio(false), cin.tie(NULL);
    int t;
    cin >> t;
    while (t--)
    {
        int n, k;
        cin >> n >> k;
        k *= ceil(n, k);
        cout << k / n + ((k % n) != 0) << endl;
    }
    return 0;
}

yahoo_procon2019_qual_b - Path

28 Jan 2021 — Tags: None

Click to show code.

using namespace std;
int main(void)
{
    int u, v;
    vector<int> deg(5, 0);
    for (int i = 0; i < 3; ++i)
    {
        cin >> u >> v;
        ++deg[u], ++deg[v];
    }
    int ones = 2;
    int evens = 2;
    for (int i = 1; i < 5; ++i)
    {
        if (deg[i] == 1)
            --ones;
        else if (deg[i] % 2 == 0)
            --evens;
    }
    if (ones == 0 and evens == 0)
        cout << "YES" << endl;
    else
        cout << "NO" << endl;
    return 0;
}

tenka_2019_c -

28 Jan 2021 — Tags: None

Click to show code.

using namespace std;
using vi = vector<int>;
int const INF = 1e9;
int main(void)
{
    int n;
    string s;
    vi pw, pb;
    cin >> n >> s;
    s = ' ' + s;
    pw.resize(n + 1, 0), pb.resize(n + 1, 0);
    for (int i = 1; i <= n; ++i)
    {
        pw[i] = pw[i - 1] + (s[i] == '.');
        pb[i] = pb[i - 1] + (s[i] == '#');
    }
    int ans = INF, left, right;
    for (int i = 1; i <= n - 1; ++i)
    {
        left = pb[i], right = (pw[n] - pw[i]);
        ans = min(ans, left + right);
    }
    ans = min({ans, n - pb[n], n - pw[n]});
    cout << ans << endl;
    return 0;
}

rplm - Negative Score

28 Jan 2021 — Tags: None

Click to show code.

using namespace std;
const int NMAX = 1e5 + 11;
const int INF = 1e9 + 11;
int n, seg[4 * NMAX], a[NMAX];
void build(int a[], int v, int tl, int tr)
{
    if (tl == tr)
        seg[v] = a[tl];
    else
    {
        int tm = (tl + tr) / 2;
        build(a, 2 * v, tl, tm);
        build(a, 2 * v + 1, tm + 1, tr);
        seg[v] = min(seg[2 * v], seg[2 * v + 1]);
    }
}
int query(int v, int tl, int tr, int ql, int qr)
{
    if (ql > qr)
        return INF;
    else if (ql == tl and qr == tr)
        return seg[v];
    else
    {
        int tm = (tl + tr) / 2;
        return min(query(2 * v, tl, tm, ql, min(tm, qr)),
                   query(2 * v + 1, tm + 1, tr, max(tm + 1, ql), qr));
    }
}
int main(void)
{
    int t, q, l, r;
    cin >> t;
    for (int tc = 1; tc <= t; ++tc)
    {
        cin >> n >> q;
        for (int i = 0; i < n; ++i)
            cin >> a[i];
        memset(seg, 0, sizeof(seg));
        build(a, 1, 0, n - 1);
        cout << "Scenario #" << tc << ":" << endl;
        while (q--)
        {
            cin >> l >> r;
            if (l > r)
                swap(l, r);
            cout << query(1, 0, n - 1, l - 1, r - 1) << endl;
        }
    }
    return 0;
}

multq3 - Multiples Of 3

28 Jan 2021 — Tags: None

Click to show code.

using namespace std;
using iii = array<int, 3>;
const int NMAX = 1e5 + 11;
int n;
int lazy[4 * NMAX];
iii seg[4 * NMAX];
void lazy_propagate(int v, int tl, int tr, int delta)
{
    iii temp(seg[v]);
    int last = (0 - delta % 3 + 3) % 3;
    for (int i = 0; i < 3; ++i)
    {
        seg[v][i] = temp[last];
        last = (last + 1) % 3;
    }
    if (tl != tr)
    {
        lazy[2 * v] += delta;
        lazy[2 * v + 1] += delta;
    }
    lazy[v] = 0;
}
inline iii merge(iii a, iii b)
{
    return {a[0] + b[0], a[1] + b[1], a[2] + b[2]};
}
void update(int v, int tl, int tr, int ql, int qr, int delta)
{
    if (lazy[v] != 0)
        lazy_propagate(v, tl, tr, lazy[v]);
    if (ql > qr)
        return;
    if (ql == tl and qr == tr)
        lazy_propagate(v, tl, tr, delta);
    else
    {
        int tm = (tl + tr) / 2;
        update(2 * v, tl, tm, ql, min(qr, tm), delta);
        update(2 * v + 1, tm + 1, tr, max(tm + 1, ql), qr, delta);
        seg[v] = merge(seg[2 * v], seg[2 * v + 1]);
    }
}
iii query(int v, int tl, int tr, int ql, int qr)
{
    if (lazy[v] != 0)
        lazy_propagate(v, tl, tr, lazy[v]);
    if (ql > qr)
        return {0, 0, 0};
    if (ql == tl and qr == tr)
        return seg[v];
    else
    {
        int tm = (tl + tr) / 2;
        return merge(query(2 * v, tl, tm, ql, min(tm, qr)),
                     query(2 * v + 1, tm + 1, tr, max(tm + 1, ql), qr));
    }
}
void build(int v, int tl, int tr)
{
    if (tl == tr)
        seg[v] = {1, 0, 0};
    else
    {
        int tm = (tl + tr) / 2;
        build(2 * v, tl, tm);
        build(2 * v + 1, tm + 1, tr);
        seg[v] = merge(seg[2 * v], seg[2 * v + 1]);
    }
}
int main(void)
{
    int q, type, ql, qr;
    cin >> n >> q;
    build(1, 0, n - 1);
    while (q--)
    {
        cin >> type >> ql >> qr;
        if (type == 0)
        {
            update(1, 0, n - 1, ql, qr, +1);
        }
        else
        {
            auto [r0, r1, r2] = query(1, 0, n - 1, ql, qr);
            cout << r0 << endl;
        }
    }
    return 0;
}

minstock - Minimum Stocks

28 Jan 2021 — Tags: None

Click to show code.

using namespace std;
int main(void)
{
    int op, n, price;
    string stock, s;
    set<pair<int, string>> stocks;
    map<string, int> stockprice;
    cin >> n;
    for (int day = 1; day <= n; ++day)
    {
        cin >> op;
        if (op == 1)
        {
            cin >> stock >> price;
            stockprice[stock] = price;
            stocks.insert({price, stock});
        }
        else if (op == 2)
        {
            cin >> stock >> price;
            stocks.erase({stockprice[stock], stock});
            stocks.insert({price, stock});
            stockprice[stock] = price;
        }
        else if (op == 3)
        {
            cin >> s;
            auto [price, stock] = *stocks.begin();
            cout << stock << " " << day << endl;
            stocks.erase(stocks.begin());
        }
    }
    return 0;
}

jsc2019_qual_b - Kleene Inversion

28 Jan 2021 — Tags: None

Click to show code.

using namespace std;
using ll = long long;
using vi = vector<int>;
int const MOD = 1e9 + 7;
inline ll add(ll a, ll b) { return ((a % MOD) + (b % MOD)) % MOD; }
inline ll mult(ll a, ll b) { return ((a % MOD) * (b % MOD)) % MOD; }
int solve(int n, ll k, vi a)
{
    vi l(n, 0), r(n, 0);
    for (int i = 0; i < n; ++i)
    {
        for (int j = i - 1; j >= 0; --j)
        {
            l[i] += (a[j] < a[i]);
        }
        for (int j = i + 1; j < n; ++j)
        {
            r[i] += (a[j] < a[i]);
        }
    }
    ll ans = 0;
    ll sumk = (k * (k + 1)) / 2;
    ll sumk1 = sumk - k;
    for (int i = 0; i < n; ++i)
    {
        ans = add(ans, add(mult(r[i], sumk), mult(l[i], sumk1)));
    }
    return ans;
}
int main(void)
{
    int n, k;
    vi a;
    cin >> n >> k;
    a.resize(n);
    for (auto &ai : a)
        cin >> ai;
    cout << solve(n, k, a) << endl;
    return 0;
}

dp_o - Matching

28 Jan 2021 — Tags: None

Click to show code.

using namespace std;
using vi = vector<int>;
const int NMAX = 21 + 2;
const int MOD = 1e9 + 7;
int n, a[NMAX][NMAX];
int solve(void)
{
    vector<vi> dp(1LL << n, vi(n + 1, 0));
    dp[0][0] = 1;
    for (int mask = 1; mask < (1LL << n); ++mask)
    {
        for (int i = 1; i <= n; ++i)
        {
            if (__builtin_popcount(mask) != i)
                continue;
            for (int j = 1; j <= n; ++j)
            {
                if (((mask >> (j - 1)) & 1LL) and a[i - 1][j - 1])
                {
                    dp[mask][i] =
                        (dp[mask][i] + dp[mask ^ (1LL << (j - 1))][i - 1]) %
                        MOD;
                }
            }
        }
    }
    return dp[(1 << n) - 1][n];
}
int main(void)
{
    ios_base::sync_with_stdio(false), cin.tie(NULL);
    cin >> n;
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j)
            cin >> a[i][j];
    cout << solve() << endl;
    return 0;
}

dpN - Slimes

28 Jan 2021 — Tags: None

Click to show code.

using namespace std;
using ll = long long;
const int NMAX = 4e2 + 11;
int n, a[NMAX];
ll acc[NMAX];
ll dp[NMAX][NMAX];
inline ll sum(int l, int r) { return acc[r] - (l > 0 ? acc[l - 1] : 0); }
ll solve(void)
{
    for (int l = n - 1; l >= 0; --l)
    {
        for (int r = l; r < n; ++r)
        {
            if (l == r)
                dp[l][r] = 0;
            else
            {
                dp[l][r] = LLONG_MAX;
                for (int i = l; i <= r - 1; ++i)
                    dp[l][r] =
                        min(dp[l][r], dp[l][i] + dp[i + 1][r] + sum(l, r));
            }
        }
    }
    return dp[0][n - 1];
}
int main(void)
{
    cin >> n;
    for (int i = 0; i < n; ++i)
    {
        cin >> a[i];
        acc[i] = a[i];
        if (i != 0)
            acc[i] += acc[i - 1];
    }
    cout << solve() << endl;
    return 0;
}

Older Newer

Competitive Programming Solutions