1451.md (16144B)
1 Source: https://codeforces.com/blog/entry/84885 2 3 [1451A - Subtract or Divide](/contest/1451/problem/A "Codeforces Round 685 (Div. 2)") 4 5 **Tutorial** 6 7 Tutorial is loading... 8 9 **Code (C++)** 10 11 ``` 12 #include <bits/stdc++.h> 13 using namespace std; 14 15 int32_t main() { 16 ios::sync_with_stdio(0); cin.tie(0); 17 int t, n; 18 cin >> t; 19 while(t--) { 20 cin >> n; 21 cout << (n <= 3? n-1 : 2 + (n&1)) << '\n'; 22 } 23 return 0; 24 } 25 ``` 26 27 **Code (Java)** 28 29 ``` 30 import java.util.*; 31 import java.util.ArrayList; 32 public class Main { 33 public static void main(String args[]) 34 { 35 Scanner sc = new Scanner(System.in); 36 int t = sc.nextInt(); 37 for(int i = 0; i < t; i++) 38 { 39 int n = sc.nextInt(); 40 System.out.println(Math.min(2 + (n & 1), n - 1)); 41 } 42 } 43 } 44 ``` 45 46 Idea by [ridbit10](/profile/ridbit10 "Expert ridbit10") 47 48 [1451B - Non-Substring Subsequence](/contest/1451/problem/B "Codeforces Round 685 (Div. 2)") 49 50 **Tutorial** 51 52 Tutorial is loading... 53 54 **Code (C++)** 55 56 ``` 57 #include <bits/stdc++.h> 58 using namespace std; 59 60 int32_t main() { 61 ios::sync_with_stdio(0); cin.tie(0); 62 int t; 63 cin >> t; 64 while(t--) { 65 int i, n, Q; string s; 66 cin >> n >> Q >> s; 67 while(Q--) { 68 int l, r; cin >> l >> r; --l; --r; 69 bool bad = true; 70 for(i = 0; i < l and bad; i++) 71 if(s[i] == s[l]) bad = false; 72 for(i = r+1; i < n and bad; i++) 73 if(s[i] == s[r]) bad = false; 74 cout << (bad? "NO" : "YES") << '\n'; 75 } 76 } 77 return 0; 78 } 79 ``` 80 81 **Code (Java)** 82 83 ``` 84 import java.io.*; 85 import java.util.*; 86 public class Main { 87 public static void main(String args[]) throws IOException 88 { 89 BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); 90 int t = Integer.parseInt(br.readLine()); 91 for(int cases = 0; cases < t; cases++) 92 { 93 StringTokenizer st = new StringTokenizer(br.readLine()); 94 int n = Integer.parseInt(st.nextToken()); 95 int q = Integer.parseInt(st.nextToken()); 96 String s = br.readLine(); 97 int fi[] = new int[2]; 98 int la[] = new int[2]; 99 for(int j = 0; j < 2; j++) 100 { 101 fi[j] = 2000000000; 102 la[j] = -1; 103 } 104 for(int i = 0; i < s.length(); i++) 105 { 106 int cur = (s.charAt(i) - '0'); 107 fi[cur] = Math.min(fi[cur], i); 108 la[cur] = i; 109 } 110 for(int i = 0; i < q; i++) 111 { 112 st = new StringTokenizer(br.readLine()); 113 int l = Integer.parseInt(st.nextToken()) - 1; 114 int r = Integer.parseInt(st.nextToken()) - 1; 115 int curl = (s.charAt(l) - '0'); 116 int curr = (s.charAt(r) - '0'); 117 if(fi[curl] < l || la[curr] > r) 118 System.out.println("YES\n"); 119 else 120 System.out.println("NO\n"); 121 } 122 } 123 } 124 } 125 ``` 126 127 Idea by [the_hyp0cr1t3](/profile/the_hyp0cr1t3 "Candidate Master the_hyp0cr1t3") 128 129 [1451C - String Equality](/contest/1451/problem/C "Codeforces Round 685 (Div. 2)") 130 131 **Tutorial** 132 133 Tutorial is loading... 134 135 **Code (C++)** 136 137 ``` 138 #include <bits/stdc++.h> 139 using namespace std; 140 141 int32_t main() { 142 ios::sync_with_stdio(0); cin.tie(0); 143 int t; 144 cin >> t; 145 while(t--) { 146 int i, n, k; string a, b; 147 cin >> n >> k >> a >> b; 148 array<int, 27> have{}, need{}; 149 for(auto& c: a) 150 have[c-'a']++; 151 for(auto& c: b) 152 need[c-'a']++; 153 154 bool bad = false; 155 for(i = 0; i < 26; i++) { 156 if(have[i] < need[i] || (have[i] -= need[i]) % k) 157 bad = true; 158 have[i+1] += have[i]; 159 } 160 cout << (bad? "No" : "Yes") << '\n'; 161 } 162 return 0; 163 } 164 ``` 165 166 **Code (Java)** 167 168 ``` 169 import java.util.*; 170 import java.util.ArrayList; 171 public class Main { 172 public static void main(String args[]) 173 { 174 Scanner sc = new Scanner(System.in); 175 int t = sc.nextInt(); 176 for(int cases = 0; cases < t; cases++) 177 { 178 int n = sc.nextInt(); 179 int k = sc.nextInt(); 180 sc.nextLine(); 181 String a = sc.nextLine(); 182 String b = sc.nextLine(); 183 int have[] = new int[27]; 184 int need[] = new int[27]; 185 for(int i = 0; i < n; i++) 186 { 187 have[a.charAt(i) - 'a']++; 188 need[b.charAt(i) - 'a']++; 189 } 190 boolean bad = false; 191 for(int j = 25; j >= 0; j--) 192 { 193 have[j] += have[j + 1]; 194 need[j] += need[j + 1]; 195 if(have[j] > need[j] || (need[j] - have[j]) % k != 0) 196 bad = true; 197 } 198 if(bad) 199 System.out.println("No"); 200 else 201 System.out.println("Yes"); 202 } 203 } 204 } 205 ``` 206 207 Idea by [Ashishgup](/profile/Ashishgup "Grandmaster Ashishgup") 208 209 [1451D - Circle Game](/contest/1451/problem/D "Codeforces Round 685 (Div. 2)") 210 211 **Tutorial** 212 213 Tutorial is loading... 214 215 **Code (C++)** 216 217 ``` 218 #include <bits/stdc++.h> 219 using namespace std; 220 221 int32_t main() { 222 ios::sync_with_stdio(0); cin.tie(0); 223 int t; 224 cin >> t; 225 while(t--) { 226 int64_t d, k; 227 cin >> d >> k; 228 int64_t x = 0, y = 0; 229 while(true) { 230 if(x <= y && (x + k) * (x + k) + y * y <= d * d) 231 x += k; 232 else if(x > y && (y + k) * (y + k) + x * x <= d * d) 233 y += k; 234 else 235 break; 236 } 237 if(x == y) 238 cout << "Utkarsh" << endl; 239 else 240 cout << "Ashish" << endl; 241 } 242 return 0; 243 } 244 ``` 245 246 **Code (Java)** 247 248 ``` 249 import java.util.*; 250 import java.util.ArrayList; 251 public class Main { 252 public static boolean is_within(long x, long y, long dsq, long k) 253 { 254 return dsq - k * k * x * x - k * k * y * y >= 0; 255 } 256 public static void main(String args[]) 257 { 258 Scanner sc = new Scanner(System.in); 259 int t = sc.nextInt(); 260 for(int cases = 0; cases < t; cases++) 261 { 262 int d = sc.nextInt(); 263 long dsq = ((long) d) * d; 264 int k = sc.nextInt(); 265 int cur = 0; 266 while(is_within(cur + 1, cur + 1, dsq, k)) 267 cur++; 268 if(is_within(cur + 1, cur, dsq, k)) 269 System.out.println("Ashish"); 270 else 271 System.out.println("Utkarsh"); 272 } 273 } 274 } 275 ``` 276 277 Idea by [Utkarsh.25dec](/profile/Utkarsh.25dec "Master Utkarsh.25dec") 278 279 [1451E1 - Bitwise Queries (Easy Version)](/contest/1451/problem/E1 "Codeforces Round 685 (Div. 2)") 280 281 **Tutorial** 282 283 Tutorial is loading... 284 285 **Code (C++)** 286 287 ``` 288 #include <bits/stdc++.h> 289 #define int long long 290 using pii=std::pair<int,int>; 291 using namespace std; 292 293 const int maxn = (1ll << 16) + 5, minn = 4, maxncheck = (1ll << 16); 294 295 int n, xorvals[maxn], ans[maxn]; 296 297 void andqueries(string s, int& dest) 298 { 299 cout << s << endl; 300 cout.flush(); 301 cin >> dest; 302 if(dest == -1) 303 exit(0); 304 return; 305 } 306 307 int32_t main() 308 { 309 cin >> n; 310 assert(n >= minn && n <= maxncheck && __builtin_popcount(n) == 1); 311 for(int i = 2; i <= n; i++) 312 { 313 cout << "XOR 1 " << i << endl; 314 cout.flush(); 315 cin >> xorvals[i]; 316 if(xorvals[i] == -1) 317 return 0; 318 } 319 int xor12 = xorvals[2], xor13 = xorvals[3], xor23 = xorvals[2] ^ xorvals[3]; 320 int and12, and13, and23; 321 andqueries("AND 1 2", and12); 322 andqueries("AND 1 3", and13); 323 andqueries("AND 2 3", and23); 324 int x = xor12 + 2 * and12; 325 int y = xor13 + 2 * and13; 326 int z = xor23 + 2 * and23; 327 assert((x + y - z) % 2 == 0); 328 ans[1] = (x + y - z) / 2; 329 for(int i = 2; i <= n; i++) 330 ans[i] = (xorvals[i] ^ ans[1]); 331 cout << "! "; 332 for(int i = 1; i <= n; i++) 333 cout << ans[i] << " "; 334 cout << endl; 335 cout.flush(); 336 return 0; 337 } 338 ``` 339 340 **Code (Java)** 341 342 ``` 343 import java.util.Scanner; 344 345 public class Main { 346 public static int queries(String s, Scanner sc) 347 { 348 System.out.println(s); 349 System.out.flush(); 350 int x = sc.nextInt(); 351 if(x == -1) 352 System.exit(0); 353 return x; 354 } 355 public static void main(String args[]) 356 { 357 Scanner sc = new Scanner(System.in); 358 int n = sc.nextInt(); 359 int xorvals[] = new int[n + 1]; 360 int ans[] = new int[n + 1]; 361 for(int i = 2; i <= n; i++) 362 xorvals[i] = queries("XOR 1 " + i, sc); 363 int xor12 = xorvals[2], xor13 = xorvals[3], xor23 = xorvals[2] ^ xorvals[3]; 364 int and12, and13, and23; 365 and12 = queries("AND 1 2", sc); 366 and13 = queries("AND 1 3", sc); 367 and23 = queries("AND 2 3", sc); 368 int x = xor12 + 2 * and12; 369 int y = xor13 + 2 * and13; 370 int z = xor23 + 2 * and23; 371 assert((x + y - z) % 2 == 0); 372 ans[1] = (x + y - z) / 2; 373 for(int i = 2; i <= n; i++) 374 ans[i] = (xorvals[i] ^ ans[1]); 375 System.out.print("! "); 376 for(int i = 1; i <= n; i++) 377 System.out.print(ans[i] + " "); 378 System.out.println(); 379 System.out.flush(); 380 } 381 } 382 ``` 383 384 Idea by [Ashishgup](/profile/Ashishgup "Grandmaster Ashishgup") and [ridbit10](/profile/ridbit10 "Expert ridbit10") 385 386 [1451E2 - Bitwise Queries (Hard Version)](/contest/1451/problem/E2 "Codeforces Round 685 (Div. 2)") 387 388 **Tutorial** 389 390 Tutorial is loading... 391 392 **Code (C++)** 393 394 ``` 395 #include <bits/stdc++.h> 396 #define int long long 397 using pii=std::pair<int,int>; 398 using namespace std; 399 400 const int maxn = (1ll << 16) + 5, minn = 4, maxncheck = (1ll << 16); 401 402 int n, xorvals[maxn], ans[maxn]; 403 vector<int> pos[maxn]; 404 405 int queries(string s, int i, int j) 406 { 407 cout << s << " " << i << " " << j << endl; 408 cout.flush(); 409 int dest; 410 cin >> dest; 411 if(dest == -1) 412 exit(0); 413 return dest; 414 } 415 416 int32_t main() 417 { 418 cin >> n; 419 assert(n >= minn && n <= maxncheck && __builtin_popcount(n) == 1); 420 xorvals[1] = 0; 421 pos[0].push_back(1); 422 for(int i = 2; i <= n; i++) 423 { 424 xorvals[i] = queries("XOR", 1, i); 425 pos[xorvals[i]].push_back(i); 426 } 427 int a = 1, b = -1, c = -1; 428 int same = -1; 429 for(int i = 0; i < n; i++) 430 if(pos[i].size() > 1) 431 { 432 b = pos[i][0]; 433 c = pos[i][1]; 434 same = i; 435 } 436 if(same == -1) 437 { 438 // If a_b ^ a_c == n - 1, then a_b & a_c = 0 439 for(int i = 2; i <= 3; i++) 440 for(int j = i + 1; j <= n; j++) 441 if((xorvals[i] ^ xorvals[j]) == n - 1) 442 { 443 b = i; 444 c = j; 445 } 446 int xorab = xorvals[a] ^ xorvals[b], xorac = xorvals[a] ^ xorvals[c], xorbc = xorvals[b] ^ xorvals[c]; 447 int andab = queries("AND", a, b); 448 int andac = queries("AND", a, c); 449 int andbc = 0; 450 int x = xorab + 2 * andab; 451 int y = xorac + 2 * andac; 452 int z = xorbc + 2 * andbc; 453 assert((x + y - z) % 2 == 0); 454 ans[a] = (x + y - z) / 2; 455 } 456 else 457 { 458 // if a_1 ^ a_b == a_1 ^ a_c, then a_b = a_c = (a_b & a_c) 459 ans[b] = queries("AND", b, c); 460 ans[1] = xorvals[b] ^ ans[b]; 461 } 462 for(int i = 2; i <= n; i++) 463 ans[i] = (xorvals[i] ^ ans[1]); 464 cout << "! "; 465 for(int i = 1; i <= n; i++) 466 cout << ans[i] << " "; 467 cout << endl; 468 cout.flush(); 469 return 0; 470 } 471 ``` 472 473 **Code (Java)** 474 475 ``` 476 import java.util.*; 477 import java.util.ArrayList; 478 public class Main { 479 public static int queries(String s, int i, int j, Scanner sc) 480 { 481 System.out.println(s + " " + i + " " + j); 482 System.out.flush(); 483 int x = sc.nextInt(); 484 if(x == -1) 485 System.exit(0); 486 return x; 487 } 488 public static void main(String args[]) 489 { 490 Scanner sc = new Scanner(System.in); 491 int n = sc.nextInt(); 492 ArrayList<Integer> pos[] = new ArrayList[n + 1]; 493 for(int i = 0; i <= n; i++) 494 pos[i] = new ArrayList<Integer>(); 495 int xorvals[] = new int[n + 1]; 496 int ans[] = new int[n + 1]; 497 xorvals[1] = 0; 498 pos[0].add(1); 499 for(int i = 2; i <= n; i++) 500 { 501 xorvals[i] = queries("XOR", 1, i, sc); 502 pos[xorvals[i]].add(i); 503 } 504 int a = 1, b = -1, c = -1; 505 int same = -1; 506 for(int i = 0; i < n; i++) 507 if(pos[i].size() > 1) 508 { 509 b = pos[i].get(0); 510 c = pos[i].get(1); 511 same = i; 512 } 513 if(same == -1) 514 { 515 // If a_b ^ a_c == n - 1, then a_b & a_c = 0 516 for(int i = 2; i <= 3; i++) 517 for(int j = i + 1; j <= n; j++) 518 if((xorvals[i] ^ xorvals[j]) == n - 1) 519 { 520 b = i; 521 c = j; 522 } 523 assert(b != -1 && c != -1); 524 int xorab = xorvals[a] ^ xorvals[b], xorac = xorvals[a] ^ xorvals[c], xorbc = xorvals[b] ^ xorvals[c]; 525 int andab = queries("AND", a, b, sc); 526 int andac = queries("AND", a, c, sc); 527 int andbc = 0; 528 int x = xorab + 2 * andab; 529 int y = xorac + 2 * andac; 530 int z = xorbc + 2 * andbc; 531 assert((x + y - z) % 2 == 0); 532 ans[a] = (x + y - z) / 2; 533 } 534 else 535 { 536 // if a_1 ^ a_b == a_1 ^ a_c, then a_b = a_c = (a_b & a_c) 537 ans[b] = queries("AND", b, c, sc); 538 ans[1] = xorvals[b] ^ ans[b]; 539 } 540 for(int i = 2; i <= n; i++) 541 ans[i] = (xorvals[i] ^ ans[1]); 542 System.out.print("! "); 543 for(int i = 1; i <= n; i++) 544 System.out.print(ans[i] + " "); 545 System.out.println(); 546 System.out.flush(); 547 } 548 } 549 ``` 550 551 Idea by [FastestFinger](/profile/FastestFinger "Master FastestFinger"), [Ashishgup](/profile/Ashishgup "Grandmaster Ashishgup") and [ridbit10](/profile/ridbit10 "Expert ridbit10") 552 553 [1451F - Nullify The Matrix](/contest/1451/problem/F "Codeforces Round 685 (Div. 2)") 554 555 **Tutorial** 556 557 Tutorial is loading... 558 559 **Code (C++)** 560 561 ``` 562 #include <bits/stdc++.h> 563 using namespace std; 564 565 #define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); 566 #define endl "\n" 567 #define int long long 568 569 const int N = 105; 570 571 int n, m; 572 int a[N][N], xorsum[2 * N]; 573 574 int32_t main() 575 { 576 IOS; 577 int t; 578 cin >> t; 579 while(t--) 580 { 581 memset(xorsum, 0, sizeof(xorsum)); 582 cin >> n >> m; 583 for(int i = 1; i <= n; i++) 584 { 585 for(int j = 1; j <= m; j++) 586 { 587 cin >> a[i][j]; 588 xorsum[i + j] ^= a[i][j]; 589 } 590 } 591 int flag = 1; 592 for(int i = 1; i <= n + m; i++) 593 flag &= (xorsum[i] == 0); 594 if(!flag) 595 cout << "Ashish" << endl; 596 else 597 cout << "Jeel" << endl; 598 } 599 return 0; 600 } 601 ``` 602 603 **Code (Java)** 604 605 ``` 606 import java.util.*; 607 608 public class NullifyTheMatrix { 609 public static void main(String[] args) { 610 Scanner sc = new Scanner(System.in); 611 int t = sc.nextInt(); 612 613 for(int x = 0; x < t; ++x) { 614 int n = sc.nextInt(); 615 int m = sc.nextInt(); 616 617 int mat[][] = new int[n][m]; 618 for(int i = 0; i < n; ++i) { 619 for(int j = 0; j < m; ++j) 620 mat[i][j] = sc.nextInt(); 621 } 622 623 int xors[] = new int[n + m - 1]; 624 for(int i = 0; i < n; ++i) { 625 for(int j = 0; j < m; ++j) 626 xors[i + j] ^= mat[i][j]; 627 } 628 629 int flag = 0; 630 for(int xor : xors) { 631 flag |= xor != 0 ? 1 : 0; 632 } 633 634 if(flag == 1) 635 System.out.println("Ashish"); 636 else 637 System.out.println("Jeel"); 638 } 639 } 640 } 641 ``` 642 643 Idea by [Jeel_Vaishnav](/profile/Jeel_Vaishnav "Grandmaster Jeel_Vaishnav")