1594.md (11537B)
1 Source: https://codeforces.com/blog/entry/95525 2 3 [1594A - Загадка последовательной суммы](/contest/1594/problem/A "Codeforces Round 747 (Div. 2)") 4 5 **Hint** 6 7 See how $n = 2$ case works. 8 9 **Solution** 10 11 Tutorial is loading... 12 13 **Code (C++)** 14 15 ``` 16 #include <bits/stdc++.h> 17 using namespace std; 18 typedef long long ll; 19 int main(void){ 20 ios_base::sync_with_stdio(0); 21 cin.tie(0); 22 int t; 23 cin>>t; 24 while(t--){ 25 ll n; 26 cin>>n; 27 cout<<-n+1<<" "<<n<<endl; 28 } 29 } 30 ``` 31 32 [1594B - Особые числа](/contest/1594/problem/B "Codeforces Round 747 (Div. 2)") 33 34 **Hint** 35 36 Think of the numbers in base $n$. 37 38 **Solution** 39 40 Tutorial is loading... 41 42 **Code (C++)** 43 44 ``` 45 #include <bits/stdc++.h> 46 using namespace std; 47 typedef long long ll; 48 const ll INF = 1e9+7; 49 const ll MOD = 998244353; 50 typedef pair<ll,ll> ii; 51 #define iii pair<ll,ii> 52 #define f(i,a,b) for(ll i = a;i < b;i++) 53 #define pb push_back 54 #define vll vector<ll> 55 #define F first 56 #define S second 57 #define all(x) (x).begin(), (x).end() 58 int main(void){ 59 ios_base::sync_with_stdio(0); 60 cin.tie(0); 61 int t; 62 cin>>t; 63 while(t--){ 64 ll n,k; 65 cin>>n>>k; 66 ll p = 1; 67 ll ans = 0; 68 f(j,0,31){ 69 if(k & (1<<j)){ 70 ans = (ans + p) % INF; 71 } 72 p *= n; 73 p %= INF; 74 } 75 cout<<ans<<"\n"; 76 } 77 } 78 ``` 79 80 [1594C - Сделай их равными](/contest/1594/problem/C "Codeforces Round 747 (Div. 2)") 81 82 **Hint** 83 84 You need atmost 2 operations. 85 86 **Solution** 87 88 Tutorial is loading... 89 90 **Code (C++)** 91 92 ``` 93 #include <bits/stdc++.h> 94 using namespace std; 95 typedef long long ll; 96 const ll INF = 1e9+7; 97 const ll MOD = 998244353; 98 typedef pair<ll,ll> ii; 99 #define iii pair<ll,ii> 100 #define f(i,a,b) for(int i = a;i < b;i++) 101 #define pb push_back 102 #define vll vector<ll> 103 #define F first 104 #define S second 105 #define all(x) (x).begin(), (x).end() 106 int main(void){ 107 ios_base::sync_with_stdio(0); 108 cin.tie(0); 109 int t; 110 cin>>t; 111 while(t--){ 112 ll n; 113 cin>>n; 114 char c; 115 cin>>c; 116 string s; 117 cin>>s; 118 vector<int>ans; 119 bool ok = true; 120 for(auto x:s){ 121 if(x != c){ 122 ok = false; 123 } 124 } 125 if(!ok){ 126 f(i,1,n+1){ 127 ok = true; 128 f(j,i,n+1){ 129 ok &= (s[j-1] == c); 130 j += i-1; 131 } 132 if(ok){ 133 ans.pb(i); 134 break; 135 } 136 } 137 if(!ok){ 138 ans.pb(n); 139 ans.pb(n-1); 140 } 141 } 142 cout<<ans.size()<<"\n"; 143 for(auto x:ans){ 144 cout<<x<<" "; 145 } 146 cout<<"\n"; 147 } 148 } 149 ``` 150 151 [1594D - Количество предателей](/contest/1594/problem/D "Codeforces Round 747 (Div. 2)") 152 153 **Hint** 154 155 Construct a graph from the comments. 156 157 **Solution** 158 159 Tutorial is loading... 160 161 **Code 1(C++)** 162 163 ``` 164 #include <bits/stdc++.h> 165 using namespace std; 166 typedef long long ll; 167 const ll INF = 1e9+7; 168 const ll MOD = 998244353; 169 typedef pair<ll,ll> ii; 170 #define iii pair<ll,ii> 171 #define f(i,a,b) for(int i = a;i < b;i++) 172 #define pb push_back 173 #define vll vector<ll> 174 #define F first 175 #define S second 176 #define all(x) (x).begin(), (x).end() 177 vector<vector<ii> >adj; 178 int c[2]; 179 int colour[700005]; 180 bool ok; 181 int n; 182 void dfs(int idx){ 183 c[colour[idx]]+= (idx <= n); 184 for(auto x:adj[idx]){ 185 if(colour[x.F] == -1){ 186 colour[x.F] = colour[idx] ^ x.S; 187 dfs(x.F); 188 } 189 else if(colour[x.F] != (colour[idx] ^ x.S)){ 190 ///impossible 191 ok = false; 192 } 193 } 194 } 195 int main(void){ 196 ios_base::sync_with_stdio(0); 197 cin.tie(0); 198 int t; 199 cin>>t; 200 while(t--){ 201 int m; 202 cin>>n>>m; 203 ///n original + m atmost fake nodes 204 adj.assign(n+m+5,vector<ii>()); 205 f(i,0,n+m+5){ 206 colour[i] = -1; 207 } 208 int fake = n+1; 209 f(i,0,m){ 210 int a,b; 211 string c; 212 cin>>a>>b>>c; 213 if(c == "crewmate"){ 214 ///same team 215 adj[a].pb(ii(fake,1)); 216 adj[fake].pb(ii(a,1)); 217 adj[fake].pb(ii(b,1)); 218 adj[b].pb(ii(fake,1)); 219 fake++; 220 } 221 else{ 222 ///different team 223 adj[a].pb(ii(b,1)); 224 adj[b].pb(ii(a,1)); 225 } 226 } 227 int ans = 0; 228 ok = true; 229 f(i,1,n+1){ 230 if(colour[i] == -1){ 231 colour[i] = 0; 232 c[0] = c[1] = 0; 233 dfs(i); 234 ans += max(c[0],c[1]); 235 } 236 } 237 if(!ok){ 238 ans = -1; 239 } 240 cout<<ans<<"\n"; 241 } 242 } 243 ``` 244 245 **Code 2(C++)** 246 247 ``` 248 #include <bits/stdc++.h> 249 using namespace std; 250 typedef long long ll; 251 const ll INF = 1e9+7; 252 const ll MOD = 998244353; 253 typedef pair<ll,ll> ii; 254 #define iii pair<ll,ii> 255 #define f(i,a,b) for(int i = a;i < b;i++) 256 #define pb push_back 257 #define vll vector<ll> 258 #define F first 259 #define S second 260 #define all(x) (x).begin(), (x).end() 261 vector<vector<ii> >adj; 262 int c[2]; 263 int colour[200005]; 264 bool ok; 265 void dfs(int idx){ 266 c[colour[idx]]++; 267 for(auto x:adj[idx]){ 268 if(colour[x.F] == -1){ 269 colour[x.F] = colour[idx] ^ x.S; 270 dfs(x.F); 271 } 272 else if(colour[x.F] != (colour[idx] ^ x.S)){ 273 ///impossible 274 ok = false; 275 } 276 } 277 } 278 int main(void){ 279 ios_base::sync_with_stdio(0); 280 cin.tie(0); 281 int t; 282 cin>>t; 283 while(t--){ 284 int n,m; 285 cin>>n>>m; 286 adj.assign(n+5,vector<ii>()); 287 f(i,0,n+5){ 288 colour[i] = -1; 289 } 290 f(i,0,m){ 291 int a,b; 292 string c; 293 cin>>a>>b>>c; 294 if(c == "crewmate"){ 295 ///same team 296 adj[a].pb(ii(b,0)); 297 adj[b].pb(ii(a,0)); 298 } 299 else{ 300 ///different team 301 adj[a].pb(ii(b,1)); 302 adj[b].pb(ii(a,1)); 303 } 304 } 305 int ans = 0; 306 ok = true; 307 f(i,1,n+1){ 308 if(colour[i] == -1){ 309 colour[i] = 0; 310 c[0] = c[1] = 0; 311 dfs(i); 312 ans += max(c[0],c[1]); 313 } 314 } 315 if(!ok){ 316 ans = -1; 317 } 318 cout<<ans<<"\n"; 319 } 320 } 321 ``` 322 323 [1594E1 - Раскраска кубика Рубика (простая версия)](/contest/1594/problem/E1 "Codeforces Round 747 (Div. 2)") 324 325 **Hint** 326 327 Think of how many colorings there are if you color only the root with one color. 328 329 **Solution** 330 331 Tutorial is loading... 332 333 **Code (C++)** 334 335 ``` 336 #include <bits/stdc++.h> 337 using namespace std; 338 typedef long long ll; 339 const ll INF = 1e9+7; 340 const ll MOD = 998244353; 341 typedef pair<ll,ll> ii; 342 #define iii pair<ii,ll> 343 #define f(i,a,b) for(ll i = a;i < b;i++) 344 #define pb push_back 345 #define vll vector<ll> 346 #define F first 347 #define S second 348 #define all(x) (x).begin(), (x).end() 349 ll power(ll a,ll b,ll mod){ 350 if(b == 0){ 351 return 1; 352 } 353 ll ans = power(a,b/2,mod); 354 ans *= ans; 355 ans %= mod; 356 if(b % 2){ 357 ans *= a; 358 } 359 return ans % mod; 360 } 361 int main(void){ 362 ios_base::sync_with_stdio(0); 363 cin.tie(0); 364 ll k; 365 cin>>k; 366 ll othernodes = (1LL<<k) - 2; 367 ll ans = power(4,othernodes,INF); 368 ans *= 6; 369 ans %= INF; 370 cout<<ans<<"\n"; 371 } 372 ``` 373 374 [1594E2 - Раскраска кубика Рубика (сложная версия)](/contest/1594/problem/E2 "Codeforces Round 747 (Div. 2)") 375 376 **Hint** 377 378 If you have a tree with a root with a fixed color and the others are all not predefined the number of colorings is $4^{nodes-1}$. 379 380 **Solution** 381 382 Tutorial is loading... 383 384 **Code (C++)** 385 386 ``` 387 #include <bits/stdc++.h> 388 using namespace std; 389 typedef long long ll; 390 const ll INF = 1e9+7; 391 const ll MOD = 998244353; 392 typedef pair<ll,ll> ii; 393 #define iii pair<ii,ll> 394 #define f(i,a,b) for(ll i = a;i < b;i++) 395 #define pb push_back 396 #define vll vector<ll> 397 #define F first 398 #define S second 399 #define all(x) (x).begin(), (x).end() 400 ll dp[(60 * 10000) + 5][6]; 401 vll color[6]; 402 vector<vector<int> >adj; 403 map<ll,int>label; 404 ll c[(60 * 10000) + 5]; 405 ll solve(int i,int j){ 406 if(c[i] != -1 && c[i] != j){ 407 return 0; 408 } 409 if(dp[i][j] != -1){ 410 return dp[i][j]; 411 } 412 ll ans = 0; 413 ll sum[2] = {0}; 414 for(auto x:color[j]){ 415 f(j,0,adj[i].size()){ 416 sum[j] += solve(adj[i][j],x); 417 sum[j] %= INF; 418 } 419 } 420 if(adj[i].empty()){ 421 sum[0] = sum[1] = 1; 422 } 423 if((ll)adj[i].size() == 1){ 424 sum[1] = 1; 425 } 426 ans = (sum[0] * sum[1]) % INF; 427 return dp[i][j] = ans; 428 } 429 ll power(ll a,ll b,ll mod){ 430 if(b == 0){ 431 return 1; 432 } 433 ll ans = power(a,b/2,mod); 434 ans *= ans; 435 ans %= mod; 436 if(b % 2){ 437 ans *= a; 438 } 439 return ans % mod; 440 } 441 int main(void){ 442 ios_base::sync_with_stdio(0); 443 cin.tie(0); 444 color[0] = {1,2,4,5}; 445 color[1] = {0,2,3,5}; 446 color[2] = {0,1,3,4}; 447 color[3] = {1,2,4,5}; 448 color[4] = {0,2,3,5}; 449 color[5] = {0,1,3,4}; 450 map<string,ll>mp; 451 mp["white"] = 0; 452 mp["blue"] = 1; 453 mp["red"] = 2; 454 mp["yellow"] = 3; 455 mp["green"] = 4; 456 mp["orange"] = 5; 457 memset(dp,-1,sizeof dp); 458 memset(c,-1,sizeof c); 459 ll k; 460 cin>>k; 461 ll n; 462 cin>>n; 463 ll posoi = (1LL<<k) - 1; 464 int lab = 0; 465 map<ll,int>ar; 466 f(i,0,n){ 467 ll x; 468 cin>>x; 469 string s; 470 cin>>s; 471 ar[x] = mp[s]; 472 ll cur = x; 473 while(cur >= 1 && !label.count(cur)){ 474 label[cur] = lab; 475 lab++; 476 posoi--; 477 cur /= 2; 478 } 479 } 480 adj.assign(lab + 5,vector<int>()); 481 for(auto x:label){ 482 if(ar.count(x.F)){ 483 c[x.S] = ar[x.F]; 484 } 485 if(label.count(x.F * 2)){ 486 adj[x.S].pb(label[x.F * 2]); 487 } 488 if(label.count(x.F * 2 + 1)){ 489 adj[x.S].pb(label[x.F * 2 + 1]); 490 } 491 } 492 ll ans = power(4,posoi,INF); 493 ll sum = 0; 494 f(j,0,6){ 495 sum += solve(label[1],j); 496 sum %= INF; 497 } 498 ans *= sum; 499 ans %= INF; 500 cout<<ans<<"\n"; 501 } 502 ``` 503 504 [1594F - Идеальная ферма](/contest/1594/problem/F "Codeforces Round 747 (Div. 2)") 505 506 **Solution** 507 508 Tutorial is loading... 509 510 **Code (C++)** 511 512 ``` 513 #include <bits/stdc++.h> 514 using namespace std; 515 typedef long long ll; 516 ll INF = 1e9+7; 517 ll MOD = 998244353; 518 typedef pair<ll,ll> ii; 519 #define iii pair<ii,ll> 520 #define f(i,a,b) for(int i = a;i < b;i++) 521 #define pb push_back 522 #define vll vector<ll> 523 #define F first 524 #define S second 525 #define all(x) (x).begin(), (x).end() 526 int main(void){ 527 ios_base::sync_with_stdio(0); 528 cin.tie(0); 529 int t; 530 cin>>t; 531 while(t--){ 532 ll n,k,s; 533 cin>>s>>n>>k; 534 if(s == k){ 535 cout<<"YES\n"; 536 } 537 else if(k > s){ 538 cout<<"NO\n"; 539 } 540 else{ 541 ll posa = s+k; 542 ll l = s-k+1,r = s; 543 ll siz = r - l + 1; 544 ll a = 0,b = 0; 545 ll num = (s / k) * k; 546 b = r - num + 1; 547 a = siz - b; 548 if((s / k) % 2 == 1){ 549 posa -= b; 550 } 551 else{ 552 posa -= a; 553 } 554 if((2 * n + 1) > posa){ 555 cout<<"YES\n"; 556 } 557 else{ 558 cout<<"NO\n"; 559 } 560 } 561 } 562 } 563 ```