1469A - Regular Bracket Sequence
Идея: BledDest
Разбор
Tutorial is loading...
Решение 1 (BledDest)
t = int(input())
for i in range(t):
s = input()
if len(s) % 2 == 0 and s[0] != ')' and s[-1] != '(':
print('YES')
else:
print('NO')
Решение 2 (BledDest)
t = int(input())
for i in range(t):
s = input()
n = len(s)
a = [s[i] for i in range(n)]
cnt = n // 2 - 1
for j in range(n):
if a[j] == '?':
if cnt > 0:
cnt -= 1
a[j] = '('
else:
a[j] = ')'
bal = 0
minbal = 0
for j in range(n):
if a[j] == '(':
bal += 1
else:
bal -= 1
minbal = min(bal, minbal)
print('YES' if bal == 0 and minbal >= 0 else 'NO')
Разбор
Tutorial is loading...
Решение 1 (Ne0n25)
#include <bits/stdc++.h>
using namespace std;
void solve() {
int n;
cin >> n;
vector<int> r(n);
for (int &x : r) cin >> x;
int m;
cin >> m;
vector<int> b(m);
for (int &x : b) cin >> x;
partial_sum(r.begin(), r.end(), r.begin());
partial_sum(b.begin(), b.end(), b.begin());
cout << max(0, *max_element(r.begin(), r.end())) + max(0, *max_element(b.begin(), b.end())) << '\n';
}
int main() {
int t;
cin >> t;
while (t--) solve();
}
Решение 2 (pikmike)
for _ in range(int(input())):
n = int(input())
a = [int(x) for x in input().split()]
m = int(input())
b = [int(x) for x in input().split()]
dp = [[-10**9 for j in range(m + 1)] for i in range(n + 1)]
dp[0][0] = 0
ans = 0
for i in range(n + 1):
for j in range(m + 1):
if i < n:
dp[i + 1][j] = max(dp[i + 1][j], dp[i][j] + a[i])
if j < m:
dp[i][j + 1] = max(dp[i][j + 1], dp[i][j] + b[j])
ans = max(ans, dp[i][j])
print(ans)
Идея: adedalic
Разбор
Tutorial is loading...
Решение (adedalic)
fun main() {
repeat(readLine()!!.toInt()) {
val (n, k) = readLine()!!.split(' ').map { it.toInt() }
val h = readLine()!!.split(' ').map { it.toInt() }
var mn = h[0]
var mx = h[0]
var ok = true
for (i in 1 until n) {
mn = maxOf(mn - k + 1, h[i])
mx = minOf(mx + k - 1, h[i] + k - 1)
if (mn > mx) {
ok = false
break
}
}
if (h[n - 1] !in mn..mx)
ok = false
println(if (ok) "YES" else "NO")
}
}
Идея: adedalic
Разбор
Tutorial is loading...
Решение (adedalic)
#include<bits/stdc++.h>
using namespace std;
#define fore(i, l, r) for(int i = int(l); i < int(r); i++)
#define sz(a) int((a).size())
#define x first
#define y second
typedef long long li;
typedef long double ld;
typedef pair<int, int> pt;
const int INF = int(1e9);
const li INF64 = li(1e18);
const ld EPS = 1e-9;
int n;
inline bool read() {
if(!(cin >> n))
return false;
return true;
}
void calc(int n, vector<pt> &ans) {
if (n == 2)
return;
int y = max(1, (int)sqrt(n) - 1);
while (y < (n + y - 1) / y)
y++;
fore (pos, y + 1, n)
ans.emplace_back(pos, n);
ans.emplace_back(n, y);
ans.emplace_back(n, y);
calc(y, ans);
}
inline void solve() {
vector<pt> ans;
calc(n, ans);
cout << sz(ans) << endl;
for(auto p : ans)
cout << p.first << " " << p.second << '\n';
}
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
int tt = clock();
#endif
ios_base::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cout << fixed << setprecision(15);
int tc; cin >> tc;
while(tc--) {
read();
solve();
#ifdef _DEBUG
cerr << "TIME = " << clock() - tt << endl;
tt = clock();
#endif
}
return 0;
}
Идея: BledDest
Разбор
Tutorial is loading...
Решение (BledDest)
#include<bits/stdc++.h>
using namespace std;
const int N = 1000043;
int q;
char buf[N];
int n, k;
int ceilLog(int x)
{
int y = 0;
while((1 << y) < x)
y++;
return y;
}
int main()
{
scanf("%d", &q);
for(int i = 0; i < q; i++)
{
scanf("%d %d", &n, &k);
scanf("%s", buf);
string s = buf;
int m = min(k, ceilLog(n - k + 2));
vector<int> used(1 << m, 0);
vector<int> next0(n, int(1e9));
if(s[n - 1] == '0')
next0[n - 1] = n - 1;
for(int j = n - 2; j >= 0; j--)
if(s[j] == '0')
next0[j] = j;
else
next0[j] = next0[j + 1];
int d = k - m;
for(int j = 0; j < n - k + 1; j++)
{
if(next0[j] - j < d)
continue;
int cur = 0;
for(int x = j + d; x < j + k; x++)
cur = cur * 2 + (s[x] - '0');
used[((1 << m) - 1) ^ cur] = 1;
}
int ans = -1;
for(int j = 0; j < (1 << m); j++)
if(used[j] == 0)
{
ans = j;
break;
}
if(ans == -1)
puts("NO");
else
{
puts("YES");
string res(d, '0');
string res2;
for(int j = 0; j < m; j++)
{
res2.push_back('0' + (ans % 2));
ans /= 2;
}
reverse(res2.begin(), res2.end());
res += res2;
puts(res.c_str());
}
}
}
Идея: adedalic
Разбор
Tutorial is loading...
Решение (pikmike)
#include <bits/stdc++.h>
#define forn(i, n) for (int i = 0; i < int(n); i++)
using namespace std;
const int INF = 1e9;
int n, k, nn;
vector<long long> t, ps;
void push(int v, int l, int r){
if (l < r - 1){
ps[v * 2] += ps[v];
ps[v * 2 + 1] += ps[v];
}
t[v] += ps[v] * (r - l);
ps[v] = 0;
}
void upd(int v, int l, int r, int L, int R, int val){
push(v, l, r);
if (L >= R)
return;
if (l == L && r == R){
ps[v] = val;
push(v, l, r);
return;
}
int m = (l + r) / 2;
upd(v * 2, l, m, L, min(m, R), val);
upd(v * 2 + 1, m, r, max(m, L), R, val);
t[v] = t[v * 2] + t[v * 2 + 1];
}
long long get(int v, int l, int r, int L, int R){
push(v, l, r);
if (L >= R)
return 0;
if (l == L && r == R)
return t[v];
int m = (l + r) / 2;
long long res = get(v * 2, l, m, L, min(m, R)) + get(v * 2 + 1, m, r, max(m, L), R);
t[v] = t[v * 2] + t[v * 2 + 1];
return res;
}
int trav(int v, int l, int r, int cnt){
push(v, l, r);
if (l == r - 1)
return l;
int m = (l + r) / 2;
push(v * 2, l, m);
push(v * 2 + 1, m, r);
int res = INF;
if (t[v * 2] >= cnt)
res = trav(v * 2, l, m, cnt);
else if (t[v * 2 + 1] >= cnt - t[v * 2])
res = trav(v * 2 + 1, m, r, cnt - t[v * 2]);
t[v] = t[v * 2] + t[v * 2 + 1];
return res;
}
int main() {
scanf("%d%d", &n, &k);
vector<int> a(n);
forn(i, n) scanf("%d", &a[i]);
sort(a.begin(), a.end(), greater<int>());
nn = a[0] + 500;
t.resize(4 * nn);
ps.resize(4 * nn);
upd(1, 0, nn, 0, 1, 1);
int fst = 0;
int ans = INF;
forn(i, n){
while (get(1, 0, nn, 0, fst + 1) == 0) ++fst;
upd(1, 0, nn, fst, fst + 1, -1);
upd(1, 0, nn, fst + 2, fst + 2 + (a[i] - 1) / 2, 1);
upd(1, 0, nn, fst + 2, fst + 2 + a[i] / 2, 1);
ans = min(ans, trav(1, 0, nn, k));
}
printf("%d\n", ans == INF ? -1 : ans);
return 0;
}