Idea: Vladosiya
Tutorial
Tutorial is loading...
Solution
def solve():
n, m = map(int, input().split())
x = input()
s = input()
for i in range(6):
if s in x:
print(i)
return
x += x
print(-1)
for _ in range(int(input())):
solve()
Idea: Gornak40
Tutorial
Tutorial is loading...
Solution
for _ in range(int(input())):
a, b, c = sorted(map(int, input().split()))
if a == b and b == c:
print('YES')
elif b % a == 0 and c % a == 0 and (b // a - 1) + (c // a - 1) <= 3:
print('YES')
else:
print('NO')
Idea: myav, MikeMirzayanov, Vladosiya
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
#define all(arr) arr.begin(), arr.end()
using namespace std;
const int MAXN = 1010;
int n;
string A[MAXN];
int solve() {
int ans = 0;
for (int i = 0; i * 2 < n; ++i)
for (int j = 0; j * 2 < n; ++j) {
vector<char> M {A[i][j], A[n - 1 - j][i], A[n - 1 - i][n - 1 - j], A[j][n - 1 - i]};
char c = *max_element(all(M));
for(char e: M)
ans += c - e;
}
return ans;
}
int main() {
int t; cin >> t;
while (t--) {
cin >> n;
for (int i = 0; i < n; ++i)
cin >> A[i];
cout << solve() << endl;
}
}
Idea: myav
Tutorial
Tutorial is loading...
Solution
#include<bits/stdc++.h>
using namespace std;
const int maxv = 1000000;
void add_divs(int x, map<int, int>&divs){
int i = 2;
while(i * i <= x){
while (x % i == 0){
divs[i]++;
x /= i;
}
i++;
}
if(x > 1) divs[x]++;
}
bool solve(){
int n;
cin >> n;
vector<int>a(n);
map<int, int> divs;
for(int i = 0; i < n; i++) {
cin >> a[i];
add_divs(a[i], divs);
}
for(auto e: divs){
if(e.second % n != 0) return false;
}
return true;
}
int main(){
int t;
cin >> t;
while(t--) {
cout << (solve() ? "YES" : "NO") << "\n";
}
}
Idea: MikeMirzayanov
Tutorial
Tutorial is loading...
Solution
def solve():
n = int(input())
a = [int(x) for x in input().split()]
dp = [n + 1] * n
def get(pos):
if pos > n:
return n + 1
if pos == n:
return 0
return dp[pos]
dp[-1] = 1
for i in range(n - 2, -1, -1):
dp[i] = min(dp[i + 1] + 1, get(i + a[i] + 1))
print(dp[0])
for _ in range(int(input())):
solve()
1881F - Minimum Maximum Distance
Idea: senjougaharin
Tutorial
Tutorial is loading...
Solution
#include<bits/stdc++.h>
using namespace std;
int n;
vector<vector<int>> g;
void dfs(int v, int p, vector<int> &d){
if(p != -1) d[v] = d[p] + 1;
for(int u: g[v]){
if(u != p){
dfs(u, v, d);
}
}
}
int main(){
int t;
cin>>t;
while(t--){
int k;
cin>>n>>k;
g.assign(n, vector<int>(0));
vector<int> marked(k);
for(int &e: marked) cin >> e, --e;
for(int i=1;i<n;i++){
int u, v;
cin >> u >> v;
--u, --v;
g[u].push_back(v);
g[v].push_back(u);
}
if(k==1){
cout<<0<<"\n";
continue;
}
vector<int> d1(n);
dfs(marked[0], -1, d1);
int mx = marked[0];
for(int e: marked){
if(d1[e] > d1[mx]) mx = e;
}
vector<int> d2(n);
dfs(mx, -1, d2);
mx = marked[0];
for(int e: marked){
if(d2[e] > d2[mx]) mx = e;
}
cout << (d2[mx] + 1) / 2 << "\n";
}
return 0;
}
1881G - Anya and the Mysterious String
Idea: Gornak40
Tutorial
Tutorial is loading...
Solution
#include <iostream>
#include <string>
#include <set>
#include <cstring>
#define int long long
using namespace std;
const int L = 26;
const int MAXN = 200200;
int n, m;
string s;
set<int> M2, M3;
int fen[MAXN];
void fenadd(int i, int x) {
x = (x % L + L) % L;
for (; i < n; i |= (i + 1))
fen[i] = (fen[i] + x) % L;
}
int fenget(int i) {
int ans = 0;
for (; i >= 0; i = (i & (i + 1)) - 1)
ans = (ans + fen[i]) % L;
return ans;
}
void relax(int l, int r) {
l = max(l, 0LL);
r = min(r, n);
for (int i = l; i + 1 < r; ++i) {
int c1 = fenget(i);
int c2 = fenget(i + 1);
if (c1 == c2) M2.insert(i);
else M2.erase(i);
if (i + 2 >= r) continue;
int c3 = fenget(i + 2);
if (c1 == c3) M3.insert(i);
else M3.erase(i);
}
}
void build() {
M2.clear();
M3.clear();
memset(fen, 0, n * sizeof(int));
fenadd(0, s[0] - 'a');
for (int i = 1; i < n; ++i) {
fenadd(i, s[i] - s[i - 1] + L);
}
for (int i = 0; i + 1 < n; ++i) {
if (s[i] == s[i + 1]) M2.insert(i);
if (i + 2 < n && s[i] == s[i + 2]) M3.insert(i);
}
}
void update(int l, int r, int x) {
fenadd(l, x);
relax(l - 5, l + 5);
fenadd(r, L - x);
relax(r - 5, r + 5);
}
bool query(int l, int r) {
auto it = M2.lower_bound(l);
if (it != M2.end() && *it + 1 < r) return false;
it = M3.lower_bound(l);
if (it != M3.end() && *it + 2 < r) return false;
return true;
}
signed main() {
int t; cin >> t;
while (t--) {
cin >> n >> m >> s;
build();
while (m--) {
int tp, l, r; cin >> tp >> l >> r, --l;
if (tp == 1) {
int x; cin >> x;
update(l, r, x);
} else {
cout << (query(l, r) ? "YES" : "NO") << '\n';
}
}
}
}