Idea: MikeMirzayanov
Tutorial
Tutorial is loading...
Solution
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;
int main() {
int t;
cin >> t;
for (int it = 0; it < t; ++it) {
int a, b;
cin >> a >> b;
cout << (a == 0 ? 1 : a + 2 * b + 1) << '\n';
}
return 0;
}
Idea: Vladosiya
Tutorial
Tutorial is loading...
Solution
t = int(input())
for _ in range(t):
n = int(input())
a = [int(x) for x in input().split()]
a.sort()
if n == 1:
if a[0] > 1:
print("NO")
else:
print("YES")
continue
if a[-2] + 1 < a[-1]:
print("NO")
else:
print("YES")
Idea: MikeMirzayanov
Tutorial
Tutorial is loading...
Solution
#include<bits/stdc++.h>
using namespace std;
int sz = 26;
void solve(){
string s;
cin >> s;
int m = 0, n = (int)s.size();
vector<bool>prev(sz, false);
for(auto &i : s){
if(prev[i - 'a']){
m += 2;
for(int j = 0; j < sz; j++) prev[j] = false;
}
else prev[i - 'a'] = true;
}
cout << n - m << endl;
}
int main(){
int t;
cin >> t;
while (t--){
solve();
}
}
1660D - Maximum Product Strikes Back
Idea: MisterGu
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
#define forn(i, n) for (int i = 0; i < int(n); i++)
#define sz(v) (int)v.size()
void solve() {
int n; cin >> n;
vector<int> a(n);
forn(i, n)
cin >> a[i];
int ans = 0;
int ap = n, as = 0;
for(int i = 0, l = -1; i <= n; i++) {
if (i == n || a[i] == 0) {
int cnt = 0;
bool neg = false;
int left = -1, right = -1;
int cl = 0, cr = 0;
for (int j = l+1; j < i; j++) {
neg ^= a[j] < 0;
if (a[j] < 0) {
right = j;
cr = 0;
}
if (abs(a[j]) == 2) {
cnt++, cr++;
if (left == -1) cl++;
}
if (a[j] < 0 && left == -1) {
left = j;
}
}
if (neg) {
if (cnt - cl > cnt - cr) {
right = i;
cnt -= cl;
} else {
left = l;
cnt -= cr;
}
} else {
left = l, right = i;
}
if (ans < cnt) {
ans = cnt;
ap = left + 1, as = n - right;
}
l = i;
}
}
cout << ap << ' ' << as << endl;
}
int main() {
int t;
cin >> t;
forn(tt, t) {
solve();
}
}
Idea: MikeMirzayanov
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
#define forn(i, n) for (int i = 0; i < int(n); i++)
#define sz(v) (int)v.size()
#define all(v) v.begin(),v.end()
#define eb emplace_back
const int INF = INT_MAX >> 1;
void solve() {
int n; cin >> n;
int cnt1 = 0;
vector<int> cnt (n, 0);
for (int i = 0; i < n; i++) {
string s; cin >> s;
for (int j = 0, k = (n - i) % n; j < n; j++, k = (k + 1 == n ? 0 : k + 1)) if (s[j] == '1') {
cnt1++;
cnt[k]++;
}
}
int ans = INF;
for (int i = 0; i < sz(cnt); i++) {
ans = min(ans, cnt1 - cnt[i] + (n - cnt[i]));
}
cout << ans << endl;
}
int main() {
int t;
cin >> t;
forn(tt, t) {
solve();
}
}
1660F1 - Promising String (easy version)
Idea: MikeMirzayanov
Tutorial
Tutorial is loading...
Solution
tst = int(input())
for _ in range(tst):
n = int(input())
s = input()
b = [0 for i in range(n+1)]
bal = n
b[0] = bal
ans = 0
for i in range(1,n+1):
if s[i-1] == '+':
bal += 1
else:
bal -= 1
b[i] = bal
for j in range(i):
if b[j] >= b[i] and (b[j] - b[i]) % 3 == 0:
ans += 1
print(ans)
1660F2 - Promising String (hard version)
Idea: MikeMirzayanov
Tutorial
Tutorial is loading...
Solution
tst = int(input())
for _ in range(tst):
n = int(input())
s = input()
f = [0 for i in range(3)]
cur_bal = n
cnt_bal = [0 for i in range(2 * n + 1)]
cnt_bal[cur_bal] += 1
f[cur_bal % 3] += 1
ans = 0
for i in range(n):
#print(f)
#print(cur_bal, ans)
new_bal = cur_bal
if s[i] == '-':
new_bal -= 1
f[new_bal % 3] += cnt_bal[new_bal]
ans += f[new_bal % 3]
cnt_bal[new_bal] += 1
f[new_bal % 3] += 1
else:
f[new_bal % 3] -= cnt_bal[new_bal]
new_bal += 1
ans += f[new_bal % 3]
cnt_bal[new_bal] += 1
f[new_bal % 3] += 1
cur_bal = new_bal
print(ans)