Я правда очень сожалею об ошибках, допущенных в задачах E и F. Не могу больше ничего сказать, так как не хочу оправдывать свои ошибки.
Идея: vovuh
Разбор
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
int t;
cin >> t;
while (t--) {
string x;
cin >> x;
int dig = x[0] - '0' - 1;
int len = x.size();
cout << dig * 10 + len * (len + 1) / 2 << endl;
}
return 0;
}
1433B - Еще одна задача про книжную полку
Идея: vovuh
Разбор
Tutorial is loading...
Решение
#include <bits/stdc++.h>
using namespace std;
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
vector<int> a(n);
for (auto &it : a) cin >> it;
while (a.back() == 0) a.pop_back();
reverse(a.begin(), a.end());
while (a.back() == 0) a.pop_back();
cout << count(a.begin(), a.end(), 0) << endl;
}
return 0;
}
Идея: vovuh
Разбор
Tutorial is loading...
Решение
#include <bits/stdc++.h>
using namespace std;
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
vector<int> a(n);
int mx = 0;
for (auto &it : a) {
cin >> it;
mx = max(mx, it);
}
int idx = -1;
for (int i = 0; i < n; ++i) {
if (a[i] != mx) continue;
if (i > 0 && a[i - 1] != mx) idx = i + 1;
if (i < n - 1 && a[i + 1] != mx) idx = i + 1;
}
cout << idx << endl;
}
return 0;
}
Идея: MikeMirzayanov
Разбор
Tutorial is loading...
Решение
#include <bits/stdc++.h>
using namespace std;
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
vector<int> a(n);
for (auto &it : a) cin >> it;
vector<pair<int, int>> res;
int idx = -1;
for (int i = 1; i < n; ++i) {
if (a[i] != a[0]) {
idx = i;
res.push_back({1, i + 1});
}
}
if (idx == -1) {
cout << "NO" << endl;
continue;
}
for (int i = 1; i < n; ++i) {
if (a[i] == a[0]) {
res.push_back({idx + 1, i + 1});
}
}
cout << "YES" << endl;
for (auto [x, y] : res) cout << x << " " << y << endl;
}
return 0;
}
Идея: MikeMirzayanov
Разбор
Tutorial is loading...
Решение
#include <bits/stdc++.h>
using namespace std;
const int N = 21;
long long f[N];
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
int n;
cin >> n;
f[0] = 1;
for (int i = 1; i < N; ++i) {
f[i] = f[i - 1] * i;
}
long long ans = f[n] / f[n / 2] / f[n / 2];
ans = ans * f[n / 2 - 1];
ans = ans * f[n / 2 - 1];
ans /= 2;
cout << ans << endl;
return 0;
}
1433F - Сумма с нулевым остатком
Идея: MikeMirzayanov
Разбор
Tutorial is loading...
Решение
#include <bits/stdc++.h>
using namespace std;
#define forn(i, n) for (int i = 0; i < int(n); ++i)
const int N = 75;
const int INF = 1e9;
int a[N][N];
int dp[N][N][N][N];
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
int n, m, k;
cin >> n >> m >> k;
forn(i, n) forn(j, m) {
cin >> a[i][j];
}
forn(i, N) forn(j, N) forn(cnt, N) forn(rem, N) dp[i][j][cnt][rem] = -INF;
dp[0][0][0][0] = 0;
forn(i, n) forn(j, m) forn(cnt, m / 2 + 1) forn(rem, k) {
if (dp[i][j][cnt][rem] == -INF) continue;
int ni = (j == m - 1 ? i + 1 : i);
int nj = (j == m - 1 ? 0 : j + 1);
if (i != ni) {
dp[ni][nj][0][rem] = max(dp[ni][nj][0][rem], dp[i][j][cnt][rem]);
} else {
dp[ni][nj][cnt][rem] = max(dp[ni][nj][cnt][rem], dp[i][j][cnt][rem]);
}
if (cnt + 1 <= m / 2) {
int nrem = (rem + a[i][j]) % k;
if (i != ni) {
dp[ni][nj][0][nrem] = max(dp[ni][nj][0][nrem], dp[i][j][cnt][rem] + a[i][j]);
} else {
dp[ni][nj][cnt + 1][nrem] = max(dp[ni][nj][cnt + 1][nrem], dp[i][j][cnt][rem] + a[i][j]);
}
}
}
cout << max(0, dp[n][0][0][0]) << endl;
return 0;
}
1433G - Уменьшение стоимости доставки
Идея: MikeMirzayanov
Разбор
Tutorial is loading...
Решение
#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
int n;
vector<vector<int>> d;
vector<vector<pair<int, int>>> g;
void dijkstra(int s, vector<int> &d) {
d = vector<int>(n, INF);
d[s] = 0;
set<pair<int, int>> st;
st.insert({d[s], s});
while (!st.empty()) {
int v = st.begin()->second;
st.erase(st.begin());
for (auto [to, w] : g[v]) {
if (d[to] > d[v] + w) {
auto it = st.find({d[to], to});
if (it != st.end()) st.erase(it);
d[to] = d[v] + w;
st.insert({d[to], to});
}
}
}
}
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
int m, k;
cin >> n >> m >> k;
g = vector<vector<pair<int, int>>>(n);
for (int i = 0; i < m; ++i) {
int x, y, w;
cin >> x >> y >> w;
--x, --y;
g[x].push_back({y, w});
g[y].push_back({x, w});
}
vector<pair<int, int>> r(k);
for (auto &[a, b] : r) {
cin >> a >> b;
--a, --b;
}
d = vector<vector<int>>(n);
for (int v = 0; v < n; ++v) {
dijkstra(v, d[v]);
}
int ans = INF;
for (int v = 0; v < n; ++v) {
for (auto [to, w] : g[v]) {
int cur = 0;
for (auto [a, b] : r) {
cur += min({d[a][b], d[a][v] + d[to][b], d[a][to] + d[v][b]});
}
ans = min(ans, cur);
}
}
cout << ans << endl;
return 0;
}