codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

1881.md (6269B)


      1 Source: https://codeforces.com/blog/entry/121327
      2 
      3 [1881A - Don't Try to Count](/contest/1881/problem/A "Codeforces Round 903 (Div. 3)")
      4 
      5 Idea: [Vladosiya](/profile/Vladosiya "Expert Vladosiya")
      6 
      7 **Tutorial**
      8 
      9 Tutorial is loading...
     10 
     11 **Solution**
     12 
     13 ```
     14 def solve():
     15     n, m = map(int, input().split())
     16     x = input()
     17     s = input()
     18     for i in range(6):
     19         if s in x:
     20             print(i)
     21             return
     22         x += x
     23     print(-1)
     24 
     25 for _ in range(int(input())):
     26     solve()
     27 ```
     28 
     29 [1881B - Three Threadlets](/contest/1881/problem/B "Codeforces Round 903 (Div. 3)")
     30 
     31 Idea: [Gornak40](/profile/Gornak40 "Expert Gornak40")
     32 
     33 **Tutorial**
     34 
     35 Tutorial is loading...
     36 
     37 **Solution**
     38 
     39 ```
     40 for _ in range(int(input())):
     41     a, b, c = sorted(map(int, input().split()))
     42     if a == b and b == c:
     43         print('YES')
     44     elif b % a == 0 and c % a == 0 and (b // a - 1) + (c // a - 1) <= 3:
     45         print('YES')
     46     else:
     47         print('NO')
     48 ```
     49 
     50 [1881C - Perfect Square](/contest/1881/problem/C "Codeforces Round 903 (Div. 3)")
     51 
     52 Idea: [myav](/profile/myav "Pupil myav"), [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov"), [Vladosiya](/profile/Vladosiya "Expert Vladosiya")
     53 
     54 **Tutorial**
     55 
     56 Tutorial is loading...
     57 
     58 **Solution**
     59 
     60 ```
     61 #include <bits/stdc++.h>
     62 #define all(arr) arr.begin(), arr.end()
     63 
     64 using namespace std;
     65 
     66 const int MAXN = 1010;
     67 
     68 int n;
     69 string A[MAXN];
     70 
     71 int solve() {
     72     int ans = 0;
     73     for (int i = 0; i * 2 < n; ++i)
     74         for (int j = 0; j * 2 < n; ++j) {
     75             vector<char> M {A[i][j], A[n - 1 - j][i], A[n - 1 - i][n - 1 - j], A[j][n - 1 - i]};
     76             char c = *max_element(all(M));
     77             for(char e: M)
     78                 ans += c - e;
     79         }
     80     return ans;
     81 }
     82 
     83 int main() {
     84     int t; cin >> t;
     85     while (t--) {
     86         cin >> n;
     87         for (int i = 0; i < n; ++i)
     88             cin >> A[i];
     89         cout << solve() << endl;
     90     }
     91 }
     92 ```
     93 
     94 [1881D - Divide and Equalize](/contest/1881/problem/D "Codeforces Round 903 (Div. 3)")
     95 
     96 Idea: [myav](/profile/myav "Pupil myav")
     97 
     98 **Tutorial**
     99 
    100 Tutorial is loading...
    101 
    102 **Solution**
    103 
    104 ```
    105 #include<bits/stdc++.h>
    106 using namespace std;
    107 const int maxv = 1000000;
    108 
    109 void add_divs(int x, map<int, int>&divs){
    110     int i = 2;
    111     while(i * i <= x){
    112         while (x % i == 0){
    113             divs[i]++;
    114             x /= i;
    115         }
    116         i++;
    117     }
    118     if(x > 1) divs[x]++;
    119 }
    120 
    121 bool solve(){
    122     int n;
    123     cin >> n;
    124     vector<int>a(n);
    125     map<int, int> divs;
    126     for(int i = 0; i < n; i++) {
    127         cin >> a[i];
    128         add_divs(a[i], divs);
    129     }
    130     for(auto e: divs){
    131         if(e.second % n != 0) return false;
    132     }
    133     return true;
    134 }
    135 
    136 int main(){
    137     int t;
    138     cin >> t;
    139     while(t--) {
    140         cout << (solve() ? "YES" : "NO") << "\n";
    141     }
    142 }
    143 ```
    144 
    145 [1881E - Block Sequence](/contest/1881/problem/E "Codeforces Round 903 (Div. 3)")
    146 
    147 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
    148 
    149 **Tutorial**
    150 
    151 Tutorial is loading...
    152 
    153 **Solution**
    154 
    155 ```
    156 def solve():
    157     n = int(input())
    158     a = [int(x) for x in input().split()]
    159     dp = [n + 1] * n
    160 
    161     def get(pos):
    162         if pos > n:
    163             return n + 1
    164         if pos == n:
    165             return 0
    166         return dp[pos]
    167 
    168     dp[-1] = 1
    169     for i in range(n - 2, -1, -1):
    170         dp[i] = min(dp[i + 1] + 1, get(i + a[i] + 1))
    171     print(dp[0])
    172 
    173 for _ in range(int(input())):
    174     solve()
    175 ```
    176 
    177 [1881F - Minimum Maximum Distance](/contest/1881/problem/F "Codeforces Round 903 (Div. 3)")
    178 
    179 Idea: [ibraevdmitriy](/profile/ibraevdmitriy "Master ibraevdmitriy")
    180 
    181 **Tutorial**
    182 
    183 Tutorial is loading...
    184 
    185 **Solution**
    186 
    187 ```
    188 #include<bits/stdc++.h>
    189 
    190 using namespace std;
    191 
    192 int n;
    193 vector<vector<int>> g;
    194 
    195 void dfs(int v, int p, vector<int> &d){
    196 	if(p != -1) d[v] = d[p] + 1;
    197 	for(int u: g[v]){
    198 		if(u != p){
    199 			dfs(u, v, d);
    200 		}
    201 	}
    202 }
    203 
    204 int main(){
    205     int t;
    206 	cin>>t;
    207 	while(t--){
    208 	    int k;
    209 		cin>>n>>k;
    210 		g.assign(n, vector<int>(0));
    211 		vector<int> marked(k);
    212 		for(int &e: marked) cin >> e, --e;
    213 		for(int i=1;i<n;i++){
    214 			int u, v;
    215 			cin >> u >> v;
    216 			--u, --v;
    217 			g[u].push_back(v);
    218 			g[v].push_back(u);
    219 		}
    220 		if(k==1){
    221 			cout<<0<<"\n";
    222 			continue;
    223 		}
    224 		vector<int> d1(n);
    225 		dfs(marked[0], -1, d1);
    226 		int mx = marked[0];
    227 		for(int e: marked){
    228 		    if(d1[e] > d1[mx]) mx = e;
    229 		}
    230 		vector<int> d2(n);
    231 		dfs(mx, -1, d2);
    232 		mx = marked[0];
    233 		for(int e: marked){
    234 		    if(d2[e] > d2[mx]) mx = e;
    235 		}
    236 		cout << (d2[mx] + 1) / 2 << "\n";
    237 	}
    238 	return 0;
    239 }
    240 ```
    241 
    242 [1881G - Anya and the Mysterious String](/contest/1881/problem/G "Codeforces Round 903 (Div. 3)")
    243 
    244 Idea: [Gornak40](/profile/Gornak40 "Expert Gornak40")
    245 
    246 **Tutorial**
    247 
    248 Tutorial is loading...
    249 
    250 **Solution**
    251 
    252 ```
    253 #include <iostream>
    254 #include <string>
    255 #include <set>
    256 #include <cstring>
    257 #define int long long
    258 
    259 using namespace std;
    260 
    261 const int L = 26;
    262 const int MAXN = 200200;
    263 
    264 int n, m;
    265 string s;
    266 set<int> M2, M3;
    267 int fen[MAXN];
    268 
    269 void fenadd(int i, int x) {
    270 	x = (x % L + L) % L;
    271 	for (; i < n; i |= (i + 1))
    272 		fen[i] = (fen[i] + x) % L;
    273 }
    274 
    275 int fenget(int i) {
    276 	int ans = 0;
    277 	for (; i >= 0; i = (i & (i + 1)) - 1)
    278 		ans = (ans + fen[i]) % L;
    279 	return ans;
    280 }
    281 
    282 void relax(int l, int r) {
    283 	l = max(l, 0LL);
    284 	r = min(r, n);
    285 	for (int i = l; i + 1 < r; ++i) {
    286 		int c1 = fenget(i);
    287 		int c2 = fenget(i + 1);
    288 
    289 		if (c1 == c2) M2.insert(i);
    290 		else M2.erase(i);
    291 
    292 		if (i + 2 >= r) continue;
    293 
    294 		int c3 = fenget(i + 2);
    295 		if (c1 == c3) M3.insert(i);
    296 		else M3.erase(i);
    297 	}
    298 }
    299 
    300 void build() {
    301 	M2.clear();
    302 	M3.clear();
    303 	memset(fen, 0, n * sizeof(int));
    304 	fenadd(0, s[0] - 'a');
    305 	for (int i = 1; i < n; ++i) {
    306 		fenadd(i, s[i] - s[i - 1] + L);
    307 	}
    308 	for (int i = 0; i + 1 < n; ++i) {
    309 		if (s[i] == s[i + 1]) M2.insert(i);
    310 		if (i + 2 < n && s[i] == s[i + 2]) M3.insert(i);
    311 	}
    312 }
    313 
    314 void update(int l, int r, int x) {
    315 	fenadd(l, x);
    316 	relax(l - 5, l + 5);
    317 	fenadd(r, L - x);
    318 	relax(r - 5, r + 5);
    319 }
    320 
    321 bool query(int l, int r) {
    322 	auto it = M2.lower_bound(l);
    323 	if (it != M2.end() && *it + 1 < r) return false;
    324 	it = M3.lower_bound(l);
    325 	if (it != M3.end() && *it + 2 < r) return false;
    326 	return true;
    327 }
    328 
    329 signed main() {
    330 	int t; cin >> t;
    331 	while (t--) {
    332 		cin >> n >> m >> s;
    333 		build();
    334 		while (m--) {
    335 			int tp, l, r; cin >> tp >> l >> r, --l;
    336 			if (tp == 1) {
    337 				int x; cin >> x;
    338 				update(l, r, x);
    339 			} else {
    340 				cout << (query(l, r) ? "YES" : "NO") << '\n';
    341 			}
    342 		}
    343 	}
    344 }
    345 ```