---
# System prepended metadata

title: Разбор задач 2014 года

---

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

## [1. Парк аттракционов](https://codeforces.com/group/skz9fIV5Hq/contest/261187/problem/2014_1)
:::spoiler Разбор
:::info
Давайте посчитаем два массива $pref_i$ -- минимальное количество земли, которую надо убрать, чтобы все высоты от $1$-й до $i$-й шли по неубыванию, и $suff_i$ -- минимальное количество земли, которую надо убрать, чтобы все высоты от $i$-й до $n$-й шли по невозрастанию. 

Тогда ответ будет такой: $ans = min(ans, pref_i + suff_i)$ для всех $i$ от $1$ до $n$.

Теперь осталось разобрать, как считать $pref_i$ и $suff_i$.

Давайте введём понятие **ступенек** -- это подряд идущие и одиннаковые по высоте горы, в формате *{высота ступеньки, длина ступеньки}*. Например, во множестве $\{1, 1, 1, 3, 4, 4, 4\}$ ступеньки будут выглядеть так: $\{1, 3\}$, $\{3, 1\}$, $\{4, 3\}$. 

Основная идея заключается в том, что если мы встретили гору, которая ниже предыдущей, то нам всегда выгодно "срезать" все предыдущие горы под уровень нашей текущей горы. 

Давайте поддерживать очередь, в которой будем хранить ступеньки. Будем иттерироваться от $1$ до $n$ и считать $pref_i$. У нас есть 2 случая:
1. Если текущая гора выше предыдущей, мы добавляем очередную ступеньку; 
2. Если текущая гора ниже предыдущей, мы "срезаем" все предыдущие горы, которые выше нашей текущей. Тем сасмым у нас образуется ступенька.

Аналогично считаем $suff_i$. 

Асимптотика: $O(N)$.

:::
:::spoiler Авторское решение (С++)
```cpp
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <math.h>

using namespace std;

int a[100005];
long long f[100005];
long long g[100005];
int q[100005];
int qcount[100005];

int main() {

    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) {
        scanf("%d", &a[i]);
    }

    f[0] = 0;
    int uk = 1;
    q[0] = a[0];
	qcount[0] = 1;
    for (int i = 1; i < n; ++i) {
        f[i] = f[i-1];
		int count = 0;
        while (uk > 0 && a[i] <= q[uk-1]) {
            f[i] += 1ll * (q[uk-1] - a[i]) * qcount[uk-1];
			count += qcount[uk-1];
            --uk;
            }
        q[uk] = a[i];
		qcount[uk] = 1 + count;
        uk++;
    }

    g[n-1] = 0;
    uk = 1;
    q[0] = a[n-1];
	qcount[0] = 1;
    for (int i = n-2; i >= 0; --i) {
        g[i] = g[i+1];
		int count = 0;
        while (uk > 0 && a[i] <= q[uk-1]) {
            g[i] += 1ll * (q[uk-1] - a[i]) * qcount[uk-1];
			count += qcount[uk-1];
            --uk;
            }
        q[uk] = a[i];
		qcount[uk] = 1 + count;
        uk++;
    }

    long long minimum = 1ll<<60;
    int peak = n;
    for (int i = 0; i < n; ++i) {
        if (f[i] + g[i] < minimum) {
            minimum = f[i] + g[i];
            peak = i + 1;
        }
    }

    cout << peak << " " << minimum << endl;

    return 0;
}
```
:::
:::spoiler Код (C++, автор: [Zhdun](https://codeforces.com/profile/Zhdun))
```cpp
#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    int a[n];
    for (auto &to : a) cin >> to;
    vector<pair<int, int>> q;
    long long pref[n];
    pref[0] = 0;
    q.push_back({a[0], 1});
    for (int i = 1; i < n; ++i) {
        pref[i] = pref[i - 1];
        int kol = 0;
        while (q.size() && q[q.size() - 1].first >= a[i]) {
            pref[i] += (long long)(q[q.size() - 1].first - a[i]) * q[q.size() - 1].second;
            kol += q[q.size() - 1].second;
            q.pop_back();
        }
        q.push_back({a[i], kol + 1});
    }
    q.clear();
    long long suf[n];
    suf[n - 1] = 0;
    q.push_back({a[n - 1], 1});
    for (int i = n - 2; i >= 0; --i) {
        suf[i] = suf[i + 1];
        int kol = 0;
        while (q.size() && q[q.size() - 1].first >= a[i]){
            suf[i] += (long long)(q[q.size() - 1].first - a[i]) * q[q.size() - 1].second;
            kol += q[q.size() - 1].second;
            q.pop_back();
        }
        q.push_back({a[i], kol + 1});
    }
    int pos = -1;
    long long mi = 1e18;
    for (int i = 0; i < n; ++i)
        if (pref[i] + suf[i] < mi)
            mi = pref[i] + suf[i], pos = i + 1;
    cout << pos << " " << mi << endl;
    return 0;
}
```
:::

## [2. Красивая задача](https://codeforces.com/group/skz9fIV5Hq/contest/261187/problem/2014_2)
:::spoiler Разбор
:::info
Делаем ровно то, что просят в условии. Находим количество делителей за корень.
Асимптотика: $O(\sqrt{N})$.
:::
:::spoiler Авторское решение (C++)
```cpp
#include <iostream>
#include <algorithm>
#include <math.h>
#include <stdio.h>

using namespace std;

int a[1000005];
int b[1000005];

int main() {
    

    int n, nn;
    cin >> n;
    nn = n;

    int k = 0;
    int d = 2;
    while ((1ll*d)*d <= n) {
        if (n%d == 0) {
            a[k] = d;
            b[k] = 0;
            while (n%d  == 0) {
                n/=d;
                ++b[k];
            }
            ++k;
        }
        if (d == 2) ++d;
        else d += 2;
    }
    if (n > 1) {
        a[k] = n;
        b[k] = 1;
        ++k;
    }

    int m = 1;
    for (int i = 0; i < k; ++i) {
        m *= b[i] + 1;
    }

    if (nn%m == 0)
        cout << "Yes " << (nn/m) << endl;
    else
        cout << "No " << (nn%m) << endl;

    return 0;
}
```
:::
:::spoiler Код (C++, автор: [Adamenko](https://codeforces.com/profile/Adamenko))
```cpp
#include <bits/stdc++.h>
using namespace std;

int main() {
    int a;
    cin >> a;
    int kol = 0;
    int d = 1;
    while (d * d < a) {
        if (a % d == 0) kol += 2;
        d++;
    }
    if (d * d == a) kol++;
    if (a % kol == 0)
        cout << "Yes " << a / kol << endl;
    else cout << "No " << a % kol << endl;
    return 0;
}

```
:::

## [3. Плагиат](https://codeforces.com/group/skz9fIV5Hq/contest/261187/problem/2014_3)
:::spoiler Разбор
:::info
Давайте напишем [НОП](https://ru.m.wikipedia.org/wiki/%D0%9D%D0%B0%D0%B8%D0%B1%D0%BE%D0%BB%D1%8C%D1%88%D0%B0%D1%8F_%D0%BE%D0%B1%D1%89%D0%B0%D1%8F_%D0%BF%D0%BE%D0%B4%D1%81%D1%82%D1%80%D0%BE%D0%BA%D0%B0#:~:text=%D0%9D%D0%B0%D0%B8%D0%B1%D0%BE%D0%BB%D1%8C%D1%88%D0%B0%D1%8F%20%D0%BE%D0%B1%D1%89%D0%B0%D1%8F%20%D0%BF%D0%BE%D0%B4%D1%81%D1%82%D1%80%D0%BE%D0%BA%D0%B0%20%D0%B0%D0%BD%D0%B3%D0%BB.,%D0%B1%D0%BE%D0%BB%D0%B5%D0%B5%20%D1%81%D1%82%D1%80%D0%BE%D0%BA%2C%20%D0%B8%D0%BC%D0%B5%D1%8E%D1%89%D0%B0%D1%8F%20%D0%BC%D0%B0%D0%BA%D1%81%D0%B8%D0%BC%D0%B0%D0%BB%D1%8C%D0%BD%D1%83%D1%8E%20%D0%B4%D0%BB%D0%B8%D0%BD%D1%83). На этом все!
Асимптотика: $O(N^2)$.
:::
:::spoiler Авторское решение (C++)
```cpp
#include <iostream>
#include <stdio.h>
#include <locale>
#include <map>
#include <algorithm>
#include <math.h>
#include <string>
#include <string.h>
#include <vector>

using namespace std;

string olds, news;
map <string, int> dictionary;
map <int, string> bdictionary;
int num = 0, olen, nlen;
vector <int> oldw, neww;

int parce(string s, vector <int> & v) {
    int l = 0;
    string word = "";
    s += ' ';
    for (int i = 0; i < s.length(); ++i){
        if (s[i] == ' ') {
            if (!dictionary.count(word)){
                    ++num;
                    dictionary[word] = num;
                    bdictionary[num] = word;
                }
            v[l] = dictionary[word];
            ++l;
            word = "";
            continue;
        }
        word += s[i];
    }
    return l;
}



int main() {


    getline(cin, olds);
    getline(cin, news);
    oldw.resize(olds.length());
    neww.resize(news.length());
    olen = parce(olds, oldw);
    nlen = parce(news, neww);

    vector < vector <int> > lcs;
    lcs.resize(olen+1);
    for (int i = 0 ; i < olen+1; ++i)
        lcs[i].resize(nlen);

    if (oldw[0] == neww[0]) lcs[0][0] = 1;
    else lcs[0][0] = 0;
    for (int i = 1; i < nlen; ++i)
        if (oldw[0] == neww[i]) lcs[0][i] = lcs[0][i-1] + 1;
        else lcs[0][i] = 0;
    for (int i = 1; i < olen; ++i)
        if (oldw[i] == neww[0]) lcs[i][0] = lcs[i-1][0] + 1;
        else lcs[i][0] = 0;

    for (int i = 1; i < olen; ++i) {
        for (int j = 1; j < nlen; ++j) {
            if (oldw[i] == neww[j]) lcs[i][j] = lcs[i-1][j-1] + 1;
            else lcs[i][j] = 0;
        }
    }

    int maxlen = 0, maxj = 0;
    for (int i = 0; i < olen; ++i) {
        for (int j = 0; j < nlen; ++j) {
            if (lcs[i][j] > maxlen) {
                maxlen = lcs[i][j];
                maxj = j;
            }
        }
    }

    if (maxlen <= nlen/2) {
        cout << "No\n";
        return 0;
    }

    cout << "Yes\n";
    maxj -= maxlen - 1;
    for (int i = maxj; i < maxj + maxlen; ++i)
        cout << bdictionary[neww[i]] << " ";
    cout << endl;
    return 0;
}
```
:::
:::spoiler Код (C++, автор: [BaluconisTima](https://codeforces.com/profile/BaluconisTima))
```cpp
#include <bits/stdc++.h>
using namespace std;

int main() {
    long long n, m;
    string s1, s2;
    getline(cin, s1);
    getline(cin, s2);
    vector<string> s, ss;
    s.push_back("@");
    ss.push_back("!");
    long long j = 0;
    s1 = s1 + ' ';
    s2 = s2 + ' ';
    for (int i = 0; i < int(s1.size()); i++) {
        if (s1[i] == ' ' || i  - 1 == int(s1.size())) {
            s.push_back(s1.substr(j,i - j));
            j = i + 1;
        }
    }
    j = 0;
    for (int i = 0; i < int(s2.size()); i++) {
        if (s2[i] == ' '|| i - 1== int(s2.size())) {
            ss.push_back(s2.substr(j,i - j));
            j = i + 1;
        }
    }
    s1 = "";
    s2 = "";
    n = int(s.size());
    m = int(ss.size());
    pair<long long, long long> p;
    long long ma = 0;
    vector<vector<int>> dp(n, vector<int>(m, 0));
    for (int i = 1; i < n; i++)
        for (int j = 1; j < m; j++) {
            if (s[i] == ss[j])
                dp[i][j] = dp[i-1][j-1] + 1;
            if (dp[i][j] > ma) {
                ma = dp[i][j];
                p = {i, j};
            }
        }
    if (ma > ((m - 1) / 2)) {
        cout << "Yes" << endl;
        ma--;
        p = {p.first - ma, p.second - ma};
        for(int i = 0; i <= ma; i++)
            cout << s[p.first + i] << ' ';
        cout << endl;
    } else cout << "No" << endl;
}
```
:::

## [4. Автомобильный салон](https://codeforces.com/group/skz9fIV5Hq/contest/261187/problem/2014_4)
:::spoiler Разбор
:::info
Давайте **<ins>[отсортируем](https://habr.com/ru/post/335920/)</ins>** уникальные числа и выведем $k$-е.
Асимптотика: $O(N * log(N))$.
:::
:::spoiler Авторское решение (C++)
```cpp
#include <algorithm>
#include <math.h>
#include <iostream>
#include <cstdio>

using namespace std;

bool comp (int i, int j) {
    return i > j;
}

int a[1000005];

int main() {
    int n, k;
    cin >> n >> k;


    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }

    sort(a, a+n, comp);

    if (k == 1) {
        cout << a[0] << endl;
        return 0;
    }

    int t=1;
    for (int i = 1; i < n; ++i) {
        if(a[i] != a[i-1]){
            t++;
            if (t==k){
                cout << a[i] << endl;
                return 0;
            }
        }
    }

    cout << "!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!";
    return 0;
}
```
:::
:::spoiler Код (C++, автор: [gruntov_dima](https://codeforces.com/profile/gruntov_dima))
```cpp
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

typedef tree <int,null_type,greater<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;

int main() {
    vector<string> v1;
    long long n,k;
    cin >> n >> k;
    ordered_set st;
    for (int i = 0; i < n; i++) {
        long long x;
        cin >> x;
        st.insert(x);
    }
    cout << *st.find_by_order(k-1) << endl;
    return 0;
}
```
:::

## [5. Подготовка](https://codeforces.com/group/skz9fIV5Hq/contest/261187/problem/2014_5)
:::spoiler Разбор
:::info
Делаем ровно то, что просят в условии. Это будет работать быстро, так как $N \leq 10^5$.
Асимптотика: $O(N)$. 
:::
:::spoiler Авторское решение (C++)
```cpp
#include <stdio.h>
#include <algorithm>
#include <iostream>

using namespace std;

int main() {


    int n, x, y;
    scanf("%d%d%d", &n, &x, &y);


    int days = 0, solved = 0;
    while (solved < n) {
        solved += x;
        x += y;
        ++days;
    }

    printf("%d\n", days);

    return 0;
}
```
:::
:::spoiler Код (C++, автор: [Zhdun](https://codeforces.com/profile/Zhdun))
```cpp
#include <bits/stdc++.h>
using namespace std;

int main() {
    long long n, x, y;
    cin >> n >> x >> y;
    long long ans = 0;
    long long kol = x;
    while (n > 0) {
        n -= kol;
        kol += y;
        ans++;
    }
    cout << ans << endl;
    return 0;
}
```
:::