Разбор
Tutorial is loading...
Решение
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
string s;
cin >> s;
int index = 0;
int gap = 1;
while (index < n)
cout << s[index], index += gap, gap++;
}
Разбор
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 n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
sort(a.begin(), a.end());
cout << min(a[n - 2] - a[0], a[n - 1] - a[1]) << endl;
return 0;
}
Разбор
Tutorial is loading...
Решение
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n, k;
cin >> n >> k;
map<int, int> ans;
queue<int> q;
for(int i = 0; i <= 30; i++)
if(n & (1 << i))
{
if(i > 0) q.push(1 << i);
ans[1 << i]++;
}
if(int(ans.size()) > k)
{
puts("NO");
return 0;
}
int cnt = ans.size();
while(cnt < k && !q.empty())
{
int z = q.front();
q.pop();
ans[z]--;
ans[z / 2] += 2;
if(z / 2 > 1)
{
q.push(z / 2);
q.push(z / 2);
}
cnt++;
}
if(cnt < k)
{
puts("NO");
return 0;
}
puts("YES");
for(auto x : ans)
for(int i = 0; i < x.second; i++)
printf("%d ", x.first);
puts("");
return 0;
}
Разбор
Tutorial is loading...
Решение
#include <bits/stdc++.h>
using namespace std;
int n;
vector<vector<int>> a;
void check(int l, int r) {
vector<int> ans;
for (int i = 0; i < n; ++i) {
int nxt = -1;
if (a[l][0] == r) {
nxt = a[l][1];
} else if (a[l][1] == r) {
nxt = a[l][0];
} else {
return;
}
ans.push_back(nxt);
l = r;
r = nxt;
}
for (auto it : ans) {
cout << it + 1 << " ";
}
cout << endl;
exit(0);
}
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
cin >> n;
a = vector<vector<int>> (n, vector<int>(2));
for (int i = 0; i < n; ++i) {
cin >> a[i][0] >> a[i][1];
--a[i][0];
--a[i][1];
}
check(0, a[0][0]);
check(0, a[0][1]);
assert(false);
return 0;
}
1095E - Almost Regular Bracket Sequence
Разбор
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 n;
string s;
cin >> n >> s;
string rs(s.rbegin(), s.rend());
for (int i = 0; i < n; ++i) {
if (rs[i] == '(') {
rs[i] = ')';
} else {
rs[i] = '(';
}
}
vector<int> pref(n + 1), suf(n + 1);
vector<bool> okp(n + 1), oks(n + 1);
okp[0] = oks[n] = true;
for (int i = 0; i < n; ++i) {
pref[i + 1] = pref[i] + (s[i] == '(' ? +1 : -1);
okp[i + 1] = okp[i] & (pref[i + 1] >= 0);
suf[n - i - 1] = suf[n - i] + (rs[i] == '(' ? +1 : -1);
oks[n - i - 1] = oks[n - i] & (suf[n - i - 1] >= 0);
}
int ans = 0;
for (int i = 0; i < n; ++i) {
if (!okp[i] || !oks[i + 1]) {
continue;
}
if (s[i] == '(') {
if (pref[i] > 0 && pref[i] - 1 - suf[i + 1] == 0) {
++ans;
}
} else {
if (pref[i] + 1 - suf[i + 1] == 0) {
++ans;
}
}
}
cout << ans << endl;
return 0;
}
Разбор
Tutorial is loading...
Решение
#include<bits/stdc++.h>
using namespace std;
#define x first
#define y second
#define mp make_pair
typedef pair<long long, pair<int, int> > edge;
const int N = 200043;
int p[N];
long long a[N];
int get_leader(int x)
{
return (x == p[x] ? x : (p[x] = get_leader(p[x])));
}
bool merge(int x, int y)
{
x = get_leader(x);
y = get_leader(y);
if(x == y) return false;
p[x] = y;
return true;
}
int main()
{
int n, m;
scanf("%d %d", &n, &m);
for(int i = 0; i < n; i++)
scanf("%lld", &a[i]);
vector<edge> es(m);
for(int i = 0; i < m; i++)
{
scanf("%d %d %lld", &es[i].y.x, &es[i].y.y, &es[i].x);
es[i].y.x--;
es[i].y.y--;
}
int z = min_element(a, a + n) - a;
for(int i = 0; i < n; i++)
if(i != z)
es.push_back(mp(a[i] + a[z], mp(i, z)));
sort(es.begin(), es.end());
long long ans = 0;
for(int i = 0; i < n; i++)
p[i] = i;
for(auto e : es)
if(merge(e.y.x, e.y.y))
ans += e.x;
printf("%lld\n", ans);
return 0;
}