Идея: MikeMirzayanov
Разбор
Tutorial is loading...
Решение
from collections import deque
def solve():
n = int(input())
s = deque(input())
while len(s) > 0 and s[0] == 'W':
s.popleft()
while len(s) > 0 and s[-1] == 'W':
s.pop()
print(len(s))
for _ in range(int(input())):
solve()
Идея: MikeMirzayanov
Разбор
Tutorial is loading...
Решение
def solve():
n = int(input())
a = [int(x) for x in input().split()]
cnt = [0] * 26
s = ''
for i in range(n):
for j in range(26):
if cnt[j] == a[i]:
cnt[j] += 1
s += chr(97 + j)
break
print(s)
for _ in range(int(input())):
solve()
Идея: MikeMirzayanov
Разбор
Tutorial is loading...
Решение
def solve():
n, m, k = map(int, input().split())
a = [int(x) for x in input().split()]
b = [int(x) for x in input().split()]
cnt = [0] * (k + 1)
for e in a:
if e <= k:
cnt[e] |= 1
for e in b:
if e <= k:
cnt[e] |= 2
c = [0] * 4
for e in cnt:
c[e] += 1
if c[1] > k // 2 or c[2] > k // 2 or c[1] + c[2] + c[3] != k:
print("NO")
else:
print("YES")
for _ in range(int(input())):
solve()
Идея: MikeMirzayanov
Разбор
Tutorial is loading...
Решение
def solve():
n = int(input())
a = [int(x) for x in input().split()]
p = [-1] * n
for i in range(1, n):
p[i] = p[i - 1]
if a[i] != a[i - 1]:
p[i] = i - 1
for i in range(int(input())):
l, r = map(int, input().split())
l -= 1
r -= 1
if p[r] < l:
print("-1 -1")
else:
print(p[r] + 1, r + 1)
t = int(input())
for _ in range(t):
solve()
if _ + 1 != t:
print()
Идея: MikeMirzayanov
Разбор
Tutorial is loading...
Решение
def solve():
n, k = map(int, input().split())
l, r = 1, n
ans = [0] * n
for i in range(k):
for j in range(i, n, k):
if i % 2 == 0:
ans[j] = l
l += 1
else:
ans[j] = r
r -= 1
print(*ans)
for _ in range(int(input())):
solve()
Идея: MikeMirzayanov
Разбор
Tutorial is loading...
Решение
#include <bits/stdc++.h>
#define int long long
#define pb emplace_back
#define mp make_pair
#define x first
#define y second
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
typedef long double ld;
typedef long long ll;
using namespace std;
mt19937 rnd(time(nullptr));
const ll inf = 1e18;
const ll M = 998244353;
const ld pi = atan2(0, -1);
const ld eps = 1e-6;
struct dsu{
vector<int> p, lvl;
dsu(int n){
p.resize(n);
iota(p.begin(), p.end(), 0);
lvl.assign(n, 0);
}
int get(int i){
if (p[i] == i) return i;
return p[i] = get(p[i]);
}
bool unite(int a, int b){
a = get(a);
b = get(b);
if(a == b) return false;
if(lvl[a] < lvl[b]) swap(a, b);
p[b] = a;
if(lvl[a] == lvl[b]) lvl[a]++;
return true;
}
};
bool found;
vector<int> ans, path;
void dfs(int v, int p, vector<vector<int>> &g, int f){
path.push_back(v);
if(v == f){
ans = path;
found = true;
return;
}
for(int u: g[v]){
if(u != p) dfs(u, v, g, f);
if (found) return;
}
path.pop_back();
}
void solve(int tc){
int n, m;
cin >> n >> m;
vector<vector<int>> sl(n);
vector<pair<int, pair<int, int>>> edges;
for(int i = 0; i < m; ++i){
int u, v, w;
cin >> u >> v >> w;
--u, --v;
edges.push_back({w, {u, v}});
}
sort(rall(edges));
dsu g(n);
pair<int, int> fin;
int best = INT_MAX;
for(auto e: edges){
if(!g.unite(e.y.x, e.y.y)){
fin = e.y;
best = e.x;
}
else{
sl[e.y.x].push_back(e.y.y);
sl[e.y.y].push_back(e.y.x);
}
}
found = false;
path.resize(0);
dfs(fin.x, -1, sl, fin.y);
cout << best << " " << ans.size() << "\n";
for(int e: ans) cout << e + 1 << " ";
}
bool multi = true;
signed main() {
int t = 1;
if (multi)cin >> t;
for (int i = 1; i <= t; ++i) {
solve(i);
cout << "\n";
}
return 0;
}
Идея: MikeMirzayanov
Разбор
Tutorial is loading...
Решение
#include <bits/stdc++.h>
using namespace std;
#define forn(i, n) for (int i = 0; i < int(n); i++)
int main() {
int t;
cin >> t;
forn(tt, t) {
int n;
cin >> n;
vector<int> a(n);
forn(i, n)
cin >> a[i];
vector<vector<vector<int>>> d(n + 1, vector<vector<int>>(n + 1, vector<int>(n + 1, INT_MAX)));
d[0][0][0] = 0;
forn(i, n)
forn(j, n)
forn(k, n + 1)
if (d[i][j][k] < INT_MAX) {
int ai = a[i];
// Z
{
int ni = i + 1;
int nj = j > 0 ? j + 1 : (k == 0 ? 1 : 0);
int nk = max(0, k - 1);
d[ni][nj][nk] = min(d[ni][nj][nk], d[i][j][k]);
}
// L
{
int ni = i + 1;
int nj = j > 0 ? j + 1 : 0;
if (nj <= ai)
nj = 0;
int nk = max(0, k - 1);
d[ni][nj][nk] = min(d[ni][nj][nk], d[i][j][k] + 1);
}
// R
{
int ni = i + 1;
int nj = j > 0 ? j + 1 : 0;
int nk = max(ai - 1, k - 1);
d[ni][nj][nk] = min(d[ni][nj][nk], d[i][j][k] + 1);
}
}
cout << *min_element(d[n][0].begin(), d[n][0].end()) << endl;
}
}