Codeforces 797 (Div.3) Simple Solution

Posted on

Codeforces #797 (Div.3) Simple Solution

Original Problems: https://codeforces.com/contest/1690

A

Try split the problem into three situations: , , . Then it can be solved easily.

Code: 

1
2
3
4
5
6
7
8
9
10
11
void solve()
{
    int n;
    cin >> n;
    if (n % 3 == 0)
        cout << n / 3 << ' ' << n / 3 + 1 << ' ' << n / 3 - 1 << endl;
    else if (n % 3 == 1)
        cout << n / 3 << ' ' << n / 3 + 2 << ' ' << n / 3 - 1 << endl;
    else
        cout << (n + 1) / 3 << ' ' << (n + 1) / 3 + 1 << ' ' << n / 3 - 1 << endl;
}

B

For each pair of pair and , if b equals to zero. have to be subtracted at least b times, but have no limit on how high it goes. If is not zero, but be greater or equal than , also must be equal to the on other pairs where is not zero.

Code: 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
typedef vector<int> vi;
#define yesnosolve cout << (solve() ? "NO" : "YES") << endl

int solve()
{
    int n;
    cin >> n;
    vi a(n), b(n);
    for (int i = 0; i < n; i++)
        cin >> a[i];
    for (int i = 0; i < n; i++)
        cin >> b[i];

    int m = -1;

    for (int i = 0; i < n; i++)
        m = max(a[i] - b[i], m);

    for (int i = 0; i < n; i++)
    {
        if (b[i] == 0)
        {
            if (a[i] > m)
                return 1;
        }
        else
        {
            if (a[i] < b[i] || a[i] - b[i] < m)
                return 1;
        }
    }

    return 0;
}

C

For the first end time , duration is . For other end time , duration is

Code: 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
typedef vector<int> vi;

void solve()
{
    int n;
    cin >> n;
    vi s(n), f(n);
    for (int i = 0; i < n; i++)
        cin >> s[i];
    for (int i = 0; i < n; i++)
        cin >> f[i];

    cout << f[0] - s[0] << ' ';
    for (int i = 1; i < n; i++)
    {
        cout << f[i] - max(s[i], f[i - 1]) << ' ';
    }
    cout << endl;
}

D

Use prefix sum algorithm to determine black strips in a certain region. Iterate through the array and find the minimum value of

Code: 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
const int INF = 2e9;
typedef vector<int> vi;

void solve()
{
    string s;
    int n, m;
    cin >> n >> m;
    cin >> s;
    s = ' ' + s;
    vi p(n + 10), a(n + 10);
    for (int i = 1; i <= n; i++)
        if (s[i] == 'B')
            p[i]++;

    for (int i = 1; i <= n + 1; i++)
        a[i] = a[i - 1] + p[i];

    int mi = INF;
    for (int i = 1; i + m <= n + 1; i++)
        mi = min(mi, m - a[i + m - 1] + a[i - 1]);
    cout << mi << endl;
}

E

  1. Sum the value of each where is integer division for each goods to a value .
  2. Create a new array using the remainder of the last step.
  3. Sort the array and use binary search to find the minimun where .
  4. Add one to and erase both elements and continue.

Code: 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
typedef unsigned long long ull;
typedef vector<int> vi;

void solve()
{
    int n, k;
    cin >> n >> k;
    vi g(n);
    for (int i = 0; i < n; i++)
        cin >> g[i];

    multiset<int> st;

    ull ans = 0;
    for (auto& a : g)
        ans += a / k, st.insert(a % k);

    while (!st.empty())
    {
        auto t = *st.begin();
        st.erase(st.begin());

        auto it = st.lower_bound(k - t);
        if (it != st.end())
            ans++, st.erase(it);
    }

    cout << ans << endl;
}