1670.md (16688B)
1 Source: https://codeforces.com/blog/entry/102579 2 3 Here is the editorial. Please provide your feedback on each problem so that we can improve upon them the next time. 4 5 ### [1670A - Профессор Слим](/contest/1670/problem/A "Codeforces Round 788 (Div. 2)") 6 7 **Tutorial** 8 9 Tutorial is loading... 10 11 **Solution** 12 13 ``` 14 import java.io.*; 15 import java.util.StringTokenizer; 16 17 public class A { 18 public static void main(String[] args) throws IOException { 19 Scanner sc = new Scanner(System.in); 20 PrintWriter pw = new PrintWriter(System.out); 21 int tc = sc.nextInt(); 22 for (int test = 1; test <= tc; test++) { 23 int n = sc.nextInt(); 24 int[] arr = new int[n]; 25 for (int i = 0; i < n; i++) 26 arr[i] = sc.nextInt(); 27 int i = 0, j = 0; 28 while (i < n) { 29 if (arr[i] < 0) { 30 arr[j++] *= -1; 31 arr[i] *= -1; 32 } 33 i++; 34 } 35 if (isSorted(arr)) { 36 pw.println("YES"); 37 } else 38 pw.println("NO"); 39 } 40 pw.flush(); 41 } 42 43 private static boolean isSorted(int[] arr) { 44 for (int i = 1; i < arr.length; i++) 45 if (arr[i] < arr[i - 1]) 46 return false; 47 return true; 48 } 49 50 static class Scanner { 51 BufferedReader br; 52 StringTokenizer st; 53 54 public Scanner(InputStream s) { 55 br = new BufferedReader(new InputStreamReader(s)); 56 } 57 58 public Scanner(FileReader f) { 59 br = new BufferedReader(f); 60 } 61 62 public String next() throws IOException { 63 while (st == null || !st.hasMoreTokens()) 64 st = new StringTokenizer(br.readLine()); 65 return st.nextToken(); 66 } 67 68 public int nextInt() throws IOException { 69 return Integer.parseInt(next()); 70 } 71 72 public long nextLong() throws IOException { 73 return Long.parseLong(next()); 74 } 75 76 public double nextDouble() throws IOException { 77 return Double.parseDouble(next()); 78 } 79 80 public int[] nextIntArr(int n) throws IOException { 81 int[] arr = new int[n]; 82 for (int i = 0; i < n; i++) { 83 arr[i] = Integer.parseInt(next()); 84 } 85 return arr; 86 } 87 88 } 89 } 90 ``` 91 92 ### [1670B - Общажные войны](/contest/1670/problem/B "Codeforces Round 788 (Div. 2)") 93 94 **Tutorial** 95 96 Tutorial is loading... 97 98 **Solution** 99 100 ``` 101 import java.io.*; 102 import java.util.StringTokenizer; 103 104 public class B{ 105 106 107 public static void main(String[] args) throws IOException { 108 Scanner sc = new Scanner(System.in); 109 PrintWriter pw = new PrintWriter(System.out); 110 int tests = sc.nextInt(); 111 for (int test = 0; test < tests; test++) { 112 int n = sc.nextInt(); 113 char[] arr = sc.next().toCharArray(); 114 int k = sc.nextInt(); 115 boolean[] special = new boolean[26]; 116 for (int i = 0; i < k; i++) 117 special[sc.next().charAt(0) - 'a'] = true; 118 int idx = -1; 119 for (int i = 0; i < n; i++) 120 if (special[arr[i] - 'a']) 121 idx = i; 122 int max=0; 123 for(int i=idx-1;i>=0;i--){ 124 int j=i; 125 while (j>0&&!special[arr[j]-'a']) 126 j--; 127 max=Math.max(max,i+1-j); 128 i=j; 129 } 130 pw.println(max); 131 } 132 pw.flush(); 133 } 134 135 136 public static class Scanner { 137 StringTokenizer st; 138 BufferedReader br; 139 140 public Scanner(InputStream s) { 141 br = new BufferedReader(new InputStreamReader(s)); 142 } 143 144 public Scanner(String s) throws FileNotFoundException { 145 br = new BufferedReader(new InputStreamReader(new FileInputStream(s))); 146 } 147 148 public String next() throws IOException { 149 while (st == null || !st.hasMoreTokens()) 150 st = new StringTokenizer(br.readLine()); 151 return st.nextToken(); 152 } 153 154 public int nextInt() throws IOException { 155 return Integer.parseInt(next()); 156 } 157 158 public long nextLong() throws IOException { 159 return Long.parseLong(next()); 160 } 161 } 162 } 163 ``` 164 165 ### [1670C - Где пицца?](/contest/1670/problem/C "Codeforces Round 788 (Div. 2)") 166 167 **Tutorial** 168 169 Tutorial is loading... 170 171 **Solution** 172 173 ``` 174 import java.io.*; 175 import java.util.HashSet; 176 import java.util.StringTokenizer; 177 178 public class C{ 179 180 static int mod = (int) 1e9 + 7; 181 182 public static void main(String[] args) throws IOException { 183 Scanner sc = new Scanner(System.in); 184 PrintWriter pw = new PrintWriter(System.out); 185 int tests = sc.nextInt(); 186 for (int test = 0; test < tests; test++) { 187 int n = sc.nextInt(); 188 int[] first = new int[n]; 189 int[] second = new int[n]; 190 int[] third=new int[n]; 191 for (int i = 0; i < n; i++) 192 first[i] = sc.nextInt() - 1; 193 for (int i = 0; i < n; i++) 194 second[i] = sc.nextInt() - 1; 195 for(int i=0;i<n;i++) 196 third[i]= sc.nextInt()-1; 197 UnionFind uf = new UnionFind(n); 198 for (int i = 0; i < n; i++) 199 uf.unionSet(first[i], second[i]); 200 HashSet<Integer> set = new HashSet<>(); 201 for (int i = 0; i < n; i++) 202 set.add(uf.findSet(i)); 203 for(int i=0;i<n;i++){ 204 if(third[i]==-1) 205 continue; 206 set.remove(uf.findSet(third[i])); 207 } 208 int pow = 0; 209 for (int x : set) 210 if (uf.sizeOfSet(x) > 1) 211 pow++; 212 int ans = 1; 213 for (int i = 0; i < pow; i++) 214 ans = (int) ((2L * ans) % mod); 215 pw.println(ans); 216 } 217 pw.flush(); 218 } 219 220 221 222 public static class UnionFind { 223 int[] p, rank, setSize; 224 int numSets; 225 226 public UnionFind(int N) { 227 p = new int[numSets = N]; 228 rank = new int[N]; 229 setSize = new int[N]; 230 for (int i = 0; i < N; i++) { 231 p[i] = i; 232 setSize[i] = 1; 233 } 234 } 235 236 public int findSet(int i) { 237 return p[i] == i ? i : (p[i] = findSet(p[i])); 238 } 239 240 public boolean isSameSet(int i, int j) { 241 return findSet(i) == findSet(j); 242 } 243 244 public void unionSet(int i, int j) { 245 if (isSameSet(i, j)) 246 return; 247 numSets--; 248 int x = findSet(i), y = findSet(j); 249 if (rank[x] > rank[y]) { 250 p[y] = x; 251 setSize[x] += setSize[y]; 252 } else { 253 p[x] = y; 254 setSize[y] += setSize[x]; 255 if (rank[x] == rank[y]) rank[y]++; 256 } 257 } 258 259 public int numDisjointSets() { 260 return numSets; 261 } 262 263 public int sizeOfSet(int i) { 264 return setSize[findSet(i)]; 265 } 266 } 267 268 269 public static class Scanner { 270 StringTokenizer st; 271 BufferedReader br; 272 273 public Scanner(InputStream s) { 274 br = new BufferedReader(new InputStreamReader(s)); 275 } 276 277 public Scanner(String s) throws FileNotFoundException { 278 br = new BufferedReader(new InputStreamReader(new FileInputStream(s))); 279 } 280 281 public String next() throws IOException { 282 while (st == null || !st.hasMoreTokens()) 283 st = new StringTokenizer(br.readLine()); 284 return st.nextToken(); 285 } 286 287 public int nextInt() throws IOException { 288 return Integer.parseInt(next()); 289 } 290 291 public long nextLong() throws IOException { 292 return Long.parseLong(next()); 293 } 294 } 295 } 296 ``` 297 298 ### [1670D - Очень подозрительно](/contest/1670/problem/D "Codeforces Round 788 (Div. 2)") 299 300 **Tutorial** 301 302 Tutorial is loading... 303 304 **Solution** 305 306 ``` 307 import java.util.*; 308 import java.io.*; 309 310 public class D{ 311 public static void main(String[] args) throws Exception { 312 int t=sc.nextInt(); 313 while(t-->0) { 314 pw.println(sol(sc.nextInt())); 315 } 316 pw.close(); 317 } 318 319 public static int sol(int n) { 320 int low=0; 321 int high=(int)1e9; 322 int mid=(low+high)/2; 323 while(low<=high) { 324 if(calc(mid)<n) { 325 low=mid+1; 326 }else { 327 high=mid-1; 328 } 329 mid=(low+high)/2; 330 } 331 return low; 332 } 333 334 public static long calc(long n) { 335 n--; 336 long ans=0; 337 ans=(n/3)*(n/3)*3; 338 for (int i = 0; i <= n % 3; i++) 339 ans += (n / 3) * 2 + i; 340 return ans*2; 341 } 342 343 static class Scanner { 344 StringTokenizer st; 345 BufferedReader br; 346 347 public Scanner(InputStream s) { 348 br = new BufferedReader(new InputStreamReader(s)); 349 } 350 351 public Scanner(FileReader r) { 352 br = new BufferedReader(r); 353 } 354 355 public String next() throws IOException { 356 while (st == null || !st.hasMoreTokens()) 357 st = new StringTokenizer(br.readLine()); 358 return st.nextToken(); 359 } 360 361 public int nextInt() throws IOException { 362 return Integer.parseInt(next()); 363 } 364 365 public long nextLong() throws IOException { 366 return Long.parseLong(next()); 367 } 368 369 public String nextLine() throws IOException { 370 return br.readLine(); 371 } 372 373 public double nextDouble() throws IOException { 374 String x = next(); 375 StringBuilder sb = new StringBuilder("0"); 376 double res = 0, f = 1; 377 boolean dec = false, neg = false; 378 int start = 0; 379 if (x.charAt(0) == '-') { 380 neg = true; 381 start++; 382 } 383 for (int i = start; i < x.length(); i++) 384 if (x.charAt(i) == '.') { 385 res = Long.parseLong(sb.toString()); 386 sb = new StringBuilder("0"); 387 dec = true; 388 } else { 389 sb.append(x.charAt(i)); 390 if (dec) 391 f *= 10; 392 } 393 res += Long.parseLong(sb.toString()) / f; 394 return res * (neg ? -1 : 1); 395 } 396 397 public long[] nextlongArray(int n) throws IOException { 398 long[] a = new long[n]; 399 for (int i = 0; i < n; i++) 400 a[i] = nextLong(); 401 return a; 402 } 403 404 public Long[] nextLongArray(int n) throws IOException { 405 Long[] a = new Long[n]; 406 for (int i = 0; i < n; i++) 407 a[i] = nextLong(); 408 return a; 409 } 410 411 public int[] nextIntArray(int n) throws IOException { 412 int[] a = new int[n]; 413 for (int i = 0; i < n; i++) 414 a[i] = nextInt(); 415 return a; 416 } 417 418 public Integer[] nextIntegerArray(int n) throws IOException { 419 Integer[] a = new Integer[n]; 420 for (int i = 0; i < n; i++) 421 a[i] = nextInt(); 422 return a; 423 } 424 425 public boolean ready() throws IOException { 426 return br.ready(); 427 } 428 429 } 430 431 static Scanner sc = new Scanner(System.in); 432 static PrintWriter pw = new PrintWriter(System.out); 433 } 434 ``` 435 436 ### [1670E - Хемос на дереве](/contest/1670/problem/E "Codeforces Round 788 (Div. 2)") 437 438 **Tutorial** 439 440 Tutorial is loading... 441 442 **Solution** 443 444 ``` 445 import java.util.*; 446 import java.io.*; 447 448 public class E{ 449 static ArrayList<int[]>[] adj; 450 static int[] nodeval, edgeval; 451 static int count, N; 452 453 public static void main(String[] args) throws IOException { 454 Scanner sc = new Scanner(System.in); 455 PrintWriter pw = new PrintWriter(System.out); 456 int t = sc.nextInt(); 457 while(t-->0){ 458 459 int n = sc.nextInt(); 460 N = 1 << n; 461 adj = new ArrayList[N]; 462 for (int i = 0; i < N; i++) 463 adj[i] = new ArrayList<>(); 464 465 for (int i = 0; i < N - 1; i++) { 466 int u = sc.nextInt() - 1; 467 int v = sc.nextInt() - 1; 468 469 adj[u].add(new int[]{v, i}); 470 adj[v].add(new int[]{u, i}); 471 } 472 nodeval = new int[N]; 473 edgeval = new int[N]; 474 nodeval[0] = N; 475 count =0; 476 dfs(0, -1); 477 478 pw.println(1); 479 for (int i = 0; i < N; i++) 480 pw.print(nodeval[i] + " "); 481 pw.println(); 482 for (int i = 0; i < N - 1; i++) 483 pw.print(edgeval[i] + " "); 484 pw.println(); 485 } 486 pw.close(); 487 488 } 489 490 private static void dfs(int u, int p) { 491 492 for (int[] nxt : adj[u]) { 493 int v = nxt[0]; 494 int idx = nxt[1]; 495 if (v == p) 496 continue; 497 count++; 498 edgeval[idx] = count + ((nodeval[u] & N) != 0 ? N : 0); 499 nodeval[v] = count + ((nodeval[u] & N) != 0 ? 0 : N); 500 dfs(v, u); 501 } 502 } 503 504 505 static class Scanner { 506 BufferedReader br; 507 StringTokenizer st; 508 509 public Scanner(InputStream s) { 510 br = new BufferedReader(new InputStreamReader(s)); 511 } 512 513 public Scanner(FileReader f) { 514 br = new BufferedReader(f); 515 } 516 517 public String next() throws IOException { 518 while (st == null || !st.hasMoreTokens()) 519 st = new StringTokenizer(br.readLine()); 520 return st.nextToken(); 521 } 522 523 public int nextInt() throws IOException { 524 return Integer.parseInt(next()); 525 } 526 527 public long nextLong() throws IOException { 528 return Long.parseLong(next()); 529 } 530 531 public double nextDouble() throws IOException { 532 return Double.parseDouble(next()); 533 } 534 535 public int[] nextIntArr(int n) throws IOException { 536 int[] arr = new int[n]; 537 for (int i = 0; i < n; i++) { 538 arr[i] = Integer.parseInt(next()); 539 } 540 return arr; 541 } 542 543 } 544 545 } 546 ``` 547 548 ### [1670F - Джи, видишь?](/contest/1670/problem/F "Codeforces Round 788 (Div. 2)") 549 550 **Tutorial** 551 552 Tutorial is loading... 553 554 **Solution** 555 556 ``` 557 import java.io.*; 558 import java.util.Arrays; 559 import java.util.StringTokenizer; 560 561 public class F { 562 static final int mod = (int) 1e9 + 7; 563 static int n; 564 static long l, r, z; 565 static long[][] memo; 566 static long[][] memo2; 567 568 public static long nCr(int n, int r) { 569 if (r == 0) 570 return 1; 571 if (n == 0) 572 return 0; 573 if (memo[n][r] != -1) 574 return memo[n][r]; 575 return memo[n][r] = (nCr(n - 1, r) + nCr(n - 1, r - 1)) % mod; 576 } 577 578 public static void main(String[] args) throws IOException { 579 Scanner sc = new Scanner(System.in); 580 PrintWriter pw = new PrintWriter(System.out); 581 int tests = 1; 582 memo = new long[1001][1001]; 583 for (long[] x : memo) 584 Arrays.fill(x, -1); 585 for (int test = 0; test < tests; test++) { 586 n = sc.nextInt(); 587 l = sc.nextLong(); 588 r = sc.nextLong(); 589 z = sc.nextLong(); 590 long ans = (compute(r) - compute(l - 1) + mod) % mod; 591 pw.println(ans); 592 } 593 pw.flush(); 594 } 595 596 private static long compute(long val) { 597 memo2 = new long[61][2001]; 598 for (long[] x : memo2) 599 Arrays.fill(x, -1); 600 return dp(60, 0, val); 601 } 602 603 private static long dp(int idx, int rem, long val) { 604 if (rem > 2000) 605 rem = 2000; 606 if (rem < 0) 607 return 0; 608 if (idx == -1) 609 return 1; 610 if (memo2[idx][rem] != -1) 611 return memo2[idx][rem]; 612 long ans = 0; 613 int currentBitXor = (z & 1L << idx)== 0 ? 0 : 1; 614 for (int i = currentBitXor == 1 ? 1 : 0; i <= n; i += 2) { 615 int currentBitSum = (val & 1L << idx) == 0 ? 0 : 1; 616 int nextRem = 2 * (rem + currentBitSum - i); 617 long toAdd = (nCr(n, i) * dp(idx - 1, nextRem, val)) % mod; 618 ans = (ans + toAdd) % mod; 619 } 620 return memo2[idx][rem] = ans; 621 } 622 623 624 public static class Scanner { 625 StringTokenizer st; 626 BufferedReader br; 627 628 public Scanner(InputStream s) { 629 br = new BufferedReader(new InputStreamReader(s)); 630 } 631 632 public Scanner(String s) throws FileNotFoundException { 633 br = new BufferedReader(new InputStreamReader(new FileInputStream(s))); 634 } 635 636 public String next() throws IOException { 637 while (st == null || !st.hasMoreTokens()) 638 st = new StringTokenizer(br.readLine()); 639 return st.nextToken(); 640 } 641 642 public int nextInt() throws IOException { 643 return Integer.parseInt(next()); 644 } 645 646 public long nextLong() throws IOException { 647 return Long.parseLong(next()); 648 } 649 } 650 } 651 ```