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 ```