# Разбор задач 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;
}
```
:::
Sign in with Wallet
Connect another wallet