1332.md (9037B)
1 Source: https://codeforces.com/blog/entry/75432 2 3 Hope you enjoy those tasks! 4 5 [1332A - Exercising Walk](/contest/1332/problem/A "Codeforces Round 630 (Div. 2)") 6 7 **Tutorial** 8 9 Tutorial is loading... 10 11 **Solution (python by pikmike)** 12 13 ``` 14 t = int(input()) 15 for _ in range(t): 16 a, b, c, d = map(int, input().split()) 17 x, y, x1, y1, x2, y2 = map(int, input().split()) 18 x += b - a 19 y += d - c 20 if a + b > 0 and x1 == x2: 21 print("No") 22 elif c + d > 0 and y1 == y2: 23 print("No") 24 elif x1 <= x <= x2 and y1 <= y <= y2: 25 print("Yes") 26 else: 27 print("No") 28 ``` 29 30 **Solution (C++)** 31 32 ``` 33 #include<bits/stdc++.h> 34 using namespace std; 35 36 int a,b,c,d,x,y,x1,y1,x2,y2,xx,yy; 37 38 int main(){ 39 int t; 40 cin>>t; 41 while (t--){ 42 cin>>a>>b>>c>>d; 43 cin>>x>>y>>x1>>y1>>x2>>y2; 44 xx=x,yy=y; 45 x+=-a+b, y+=-c+d; 46 if (x>=x1&&x<=x2&&y>=y1&&y<=y2&&(x2>x1||a+b==0)&&(y2>y1||c+d==0)){ 47 cout<<"Yes\n"; 48 } 49 else{ 50 cout<<"No\n"; 51 } 52 } 53 return 0; 54 } 55 ``` 56 57 [1332B - Composite Coloring](/contest/1332/problem/B "Codeforces Round 630 (Div. 2)") 58 59 **Tutorial** 60 61 Tutorial is loading... 62 63 **Solution (python by pikmike)** 64 65 ``` 66 from math import gcd 67 68 def getprime(x): 69 for i in range(2, x): 70 if x % i == 0: 71 return i 72 return -1 73 74 primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31] 75 76 t = int(input()) 77 for _ in range(t): 78 n = int(input()) 79 a = [int(x) for x in input().split()] 80 used = [False for i in range(11)] 81 clr = [] 82 for i in range(n): 83 x = primes.index(getprime(a[i])) 84 used[x] = True 85 clr.append(x) 86 cnt = 0 87 num = [] 88 for i in range(11): 89 num.append(cnt) 90 if used[i]: 91 cnt += 1 92 print(cnt) 93 for i in range(n): 94 x = primes.index(getprime(a[i])) 95 print(num[x] + 1, end = " ") 96 print() 97 ``` 98 99 **Solution (C++)** 100 101 ``` 102 #include<bits/stdc++.h> 103 using namespace std; 104 105 int n,t; 106 vector<int> ans[1007]; 107 int res[1007]; 108 int main(){ 109 ios::sync_with_stdio(false); 110 cin.tie(0), cout.tie(0); 111 auto f=[&](int u){ 112 for (int i=2;i<=u;++i){ 113 if (u%i==0) return i; 114 } 115 }; 116 cin>>t; 117 while (t--){ 118 cin>>n; 119 for (int i=1;i<=1000;++i) ans[i].clear(); 120 for (int i=1;i<=n;++i){ 121 int u; 122 cin>>u; ans[f(u)].push_back(i); 123 } 124 int ret=0; 125 for (int i=1;i<=1000;++i){ 126 if (ans[i].size()){ 127 ++ret; 128 for (auto c:ans[i]){ 129 res[c]=ret; 130 } 131 } 132 } 133 cout<<ret<<"\n"; 134 for (int i=1;i<=n;++i){ 135 cout<<res[i]<<" "; 136 } 137 cout<<"\n"; 138 } 139 return 0; 140 } 141 ``` 142 143 [1332C - K-Complete Word](/contest/1332/problem/C "Codeforces Round 630 (Div. 2)") 144 145 **Tutorial** 146 147 Tutorial is loading... 148 149 **Solution(python by pikmike)** 150 151 ``` 152 from sys import stdin 153 154 t = int(stdin.readline()) 155 for _ in range(t): 156 n, k = map(int, stdin.readline().split()) 157 s = stdin.readline() 158 cnt = [[0 for i in range(26)] for j in range((k + 1) // 2)] 159 for i in range(n): 160 cnt[min(i % k, k - i % k - 1)][ord(s[i]) - ord('a')] += 1 161 ans = 0 162 for i in range(k // 2): 163 ans += 2 * n // k - max(cnt[i]) 164 if k % 2 == 1: 165 ans += n // k - max(cnt[k // 2]) 166 print(ans) 167 ``` 168 169 **Solution(C++)** 170 171 ``` 172 #include<bits/stdc++.h> 173 using namespace std; 174 175 const int maxn=200007; 176 177 int n,k,ans=0; 178 int cnt[maxn][26]; 179 string s; 180 181 int differ(int u,int v){ 182 int ret=0,mx=0; 183 for (int j=0;j<26;++j){ 184 ret+=cnt[u][j]+cnt[v][j]; 185 mx=max(mx,cnt[u][j]+cnt[v][j]); 186 } 187 return ret-mx; 188 } 189 190 int main(){ 191 int t; 192 cin>>t; 193 while (t--){ 194 cin>>n>>k>>s; 195 for (int i=0;i<k;++i){ 196 for (int j=0;j<26;++j){ 197 cnt[i][j]=0; 198 } 199 } 200 for (int i=0;i<n;++i){ 201 cnt[i%k][s[i]-'a']++; 202 } 203 int ans=0; 204 for (int i=0;i<k;++i){ 205 ans+=differ(i,k-1-i); 206 } 207 cout<<ans/2<<"\n"; 208 } 209 return 0; 210 } 211 ``` 212 213 [1332D - Walk on Matrix](/contest/1332/problem/D "Codeforces Round 630 (Div. 2)") 214 215 **Tutorial** 216 217 Tutorial is loading... 218 219 **Solution(python by pikmike)** 220 221 ``` 222 k = int(input()) 223 x = 2**17 224 print(2, 3) 225 print(x^k, x, 0) 226 print(k, x^k, k) 227 ``` 228 229 [1332E - Height All the Same](/contest/1332/problem/E "Codeforces Round 630 (Div. 2)") 230 231 **Tutorial** 232 233 Tutorial is loading... 234 235 **Solution 1(python by pikmike)** 236 237 ``` 238 MOD = 998244353 239 240 n, m, l, r = map(int, input().split()) 241 if n * m % 2 == 1: 242 print(pow(r - l + 1, n * m, MOD)) 243 elif (r - l + 1) % 2 == 0: 244 print(pow(r - l + 1, n * m, MOD) * (MOD + 1) // 2 % MOD) 245 else: 246 print((pow(r - l + 1, n * m, MOD) + 1) * (MOD + 1) // 2 % MOD) 247 ``` 248 249 **Solution 2(python by pikmike)** 250 251 ``` 252 MOD = 998244353 253 254 n, m, l, r = map(int, input().split()) 255 if n * m % 2 == 1: 256 print(pow(r - l + 1, n * m, MOD)) 257 else: 258 e = r // 2 - (l - 1) // 2 259 o = (r - l + 1) - e 260 print((pow(e + o, n * m, MOD) + pow(e - o, n * m, MOD)) * (MOD + 1) // 2 % MOD) 261 ``` 262 263 [1332F - Independent Set](/contest/1332/problem/F "Codeforces Round 630 (Div. 2)") 264 265 **Tutorial** 266 267 Tutorial is loading... 268 269 **Solution(C++)** 270 271 ``` 272 #include<bits/stdc++.h> 273 #define int long long 274 #define ULL unsigned long long 275 #define F first 276 #define S second 277 #define pb push_back 278 #define rep(i,n) for(int i=0;i<(int)(n);++i) 279 #define rep1(i,n) for(int i=1;i<=(int)(n);++i) 280 #define range(a) a.begin(), a.end() 281 #define PI pair<int,int> 282 #define VI vector<int> 283 #define debug cout<<"potxdy"<<endl; 284 using namespace std; 285 286 typedef long long ll; 287 288 mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); 289 290 const int maxn=300007; 291 const int mod=998244353; 292 293 int n,dp[maxn][2],f[maxn]; 294 VI vec[maxn]; 295 296 int mult(int u,int v){ 297 u=(u%mod+mod)%mod, v=(v%mod+mod)%mod; 298 return 1ll*u*v%mod; 299 } 300 301 void dfs(int u,int p){ 302 dp[u][0]=dp[u][1]=f[u]=1; 303 for (auto c:vec[u]){ 304 if (c==p) continue; 305 dfs(c,u); 306 dp[u][0]=mult(dp[u][0],2*dp[c][0]+2*dp[c][1]-f[c]); 307 dp[u][1]=mult(dp[u][1],dp[c][1]+2*dp[c][0]-f[c]); 308 f[u]=mult(f[u],dp[c][0]+dp[c][1]-f[c]); 309 } 310 } 311 312 #undef int 313 int main(){ 314 ios::sync_with_stdio(false); 315 cin.tie(0), cout.tie(0); 316 cin>>n; 317 for (int i=1;i<n;++i){ 318 int u,v; 319 cin>>u>>v; 320 vec[u].pb(v), vec[v].pb(u); 321 } 322 dfs(1,0); 323 cout<<(dp[1][0]+dp[1][1]-f[1]-1+2*mod)%mod<<endl; 324 return 0; 325 } 326 ``` 327 328 [1332G - No Monotone Triples](/contest/1332/problem/G "Codeforces Round 630 (Div. 2)") 329 330 Contributor of idea of the solution: [awoo](/profile/awoo "Master awoo") 331 332 **Tutorial** 333 334 Tutorial is loading... 335 336 **Solution (C++)** 337 338 ``` 339 #include<bits/stdc++.h> 340 341 using namespace std; 342 343 const int maxn=200007; 344 int n,q,a[maxn],b[maxn],c[maxn],t[maxn],sum[maxn]; 345 int st1[maxn],st2[maxn],p1,p2,r1,r2,s1,s2; 346 int ans1[maxn][4],ans2[maxn][4]; 347 set<int> s; 348 349 bool cmp1(int u,int v){ 350 return a[u]<a[v]; 351 } 352 353 bool cmp2(int u,int v){ 354 return a[u]>a[v]; 355 } 356 357 int main(){ 358 ios::sync_with_stdio(false); 359 cin.tie(0), cout.tie(0); 360 cin>>n>>q; 361 for (int i=1;i<=n;++i){ 362 cin>>a[i]; 363 } 364 p1=p2=r1=r2=0; 365 s.insert(n+1); 366 for (int i=n;i>0;--i){ 367 while (p1){ 368 int u=st1[p1]; 369 if (a[u]>a[i]){ 370 t[u]--; 371 if (!t[u]) s.insert(u); 372 p1--; 373 r1=0; 374 } 375 else{ 376 break; 377 } 378 } 379 while (p2){ 380 int u=st2[p2]; 381 if (a[u]<a[i]){ 382 t[u]--; 383 if (!t[u]) s.insert(u); 384 p2--; 385 r2=0; 386 } 387 else{ 388 break; 389 } 390 } 391 s1=lower_bound(st1+1,st1+p1+1,i,cmp1)-st1-1, s2=lower_bound(st2+1,st2+p2+1,i,cmp2)-st2-1; 392 b[i]=i+max(r1,r2)+1; 393 ans1[i][0]=i, ans1[i][1]=b[i]-1, ans1[i][2]=b[i]; 394 if (s1&&s2){ 395 c[i]=*s.lower_bound(max(st1[s1],st2[s2])); 396 if (c[i]<=n){ 397 int u=lower_bound(st1+1,st1+p1+1,c[i],greater<int>())-st1,v=lower_bound(st2+1,st2+p2+1,c[i],greater<int>())-st2; 398 ans2[i][0]=i, ans2[i][1]=min(st1[u],st2[v]), ans2[i][2]=max(st1[u],st2[v]), ans2[i][3]=c[i]; 399 } 400 } 401 else{ 402 c[i]=n+1; 403 } 404 st1[++p1]=i; 405 st2[++p2]=i; 406 r1++, r2++; 407 t[i]+=2; 408 if (i<n&&b[i]>b[i+1]){ 409 b[i]=b[i+1]; 410 for (int j=0;j<3;++j){ 411 ans1[i][j]=ans1[i+1][j]; 412 } 413 } 414 if (i<n&&c[i]>c[i+1]){ 415 c[i]=c[i+1]; 416 for (int j=0;j<4;++j){ 417 ans2[i][j]=ans2[i+1][j]; 418 } 419 } 420 } 421 while (q--){ 422 int l,r; 423 cin>>l>>r; 424 if (r>=c[l]){ 425 cout<<"4\n"; 426 for (int j=0;j<4;++j){ 427 cout<<ans2[l][j]<<" "; 428 } 429 cout<<"\n"; 430 } 431 else{ 432 if (r>=b[l]){ 433 cout<<"3\n"; 434 for (int j=0;j<3;++j){ 435 cout<<ans1[l][j]<<" "; 436 } 437 cout<<"\n"; 438 } 439 else{ 440 cout<<"0\n\n"; 441 } 442 } 443 } 444 return 0; 445 } 446 ```