2234.md (19919B)
1 Source: https://codeforces.com/blog/entry/154319 2 3 Thank you for participating in our round! We hope you enjoyed the problems. 4 5 [2234A - Euclid, Sequence and Two Numbers](/contest/2234/problem/A "Codeforces Round 1102 (Div. 2)") 6 7 Idea: [FairyWinx](/profile/FairyWinx "Grandmaster FairyWinx") 8 9 **Hint 1** 10 11 Note that $(a_i \bmod a_{i + 1}) \lt a_{i + 1}$. 12 13 **Hint 2** 14 15 $a_{i + 2} = (a_i \bmod a_{i + 1}) \lt a_{i + 1}$ and $a_2 \le a_1$ mean that the sequence $a$ must be non-increasing. On the other hand, there is only one permutation of the sequence $b$ that can be non-increasing. 16 17 **Solution** 18 19 Tutorial is loading... 20 21 **Code (Python)** 22 23 ``` 24 t = int(input()) 25 for tt in range(t): 26 n = int(input()) 27 a = list(map(int, input().split())) 28 a.sort() 29 a = a[::-1] 30 valid = True 31 for i in range(2, n): 32 if a[i] != a[i - 2] % a[i - 1]: 33 print(-1) 34 valid = False 35 break 36 if valid: 37 print(a[0], a[1]) 38 ``` 39 40 **Code (C++)** 41 42 ``` 43 #include <iostream> 44 #include <vector> 45 #include <algorithm> 46 47 using namespace std; 48 49 void solve() { 50 int n; 51 cin >> n; 52 vector<int> b(n); 53 for (int i = 0; i < n; i++) { 54 cin >> b[i]; 55 } 56 sort(b.rbegin(), b.rend()); 57 bool ok = true; 58 for (int i = 0; i < n - 2; i++) { 59 if (b[i + 2] != b[i] % b[i + 1]) { 60 ok = false; 61 break; 62 } 63 } 64 if (ok) { 65 cout << b[0] << " " << b[1] << "\n"; 66 } else { 67 cout << -1 << "\n"; 68 } 69 } 70 71 int main() { 72 int t; 73 cin >> t; 74 75 while (t--) { 76 solve(); 77 } 78 } 79 ``` 80 81 **Rate the problem** 82 83 Amazing 84 85 Good 86 87 Ok 88 89 Bad 90 91 Terrible 92 93 [2234B - Palindrome, Twelve and Two Terms](/contest/2234/problem/B "Codeforces Round 1102 (Div. 2)") 94 95 Idea: [Fakewave](/profile/Fakewave "Master Fakewave") 96 97 **Solution** 98 99 Tutorial is loading... 100 101 **Code (Python)** 102 103 ``` 104 tt = int(input()) 105 for tc in range(tt): 106 n = int(input()) 107 if n == 10: 108 print(-1) 109 elif n % 12 == 10: 110 print(22, n - 22) 111 else: 112 print(n % 12, n - (n % 12)) 113 ``` 114 115 **Code (C++)** 116 117 ``` 118 #include <bits/stdc++.h> 119 120 using namespace std; 121 122 void solve() { 123 long long n; 124 cin >> n; 125 if (n == 10) { 126 cout << "-1\n"; 127 } else if (n % 12 == 10) { 128 cout << "22 " << n - 22 << "\n"; 129 } else { 130 cout << n % 12 << " " << n - (n % 12) << "\n"; 131 } 132 } 133 134 int main() { 135 ios_base::sync_with_stdio(0); cin.tie(0); 136 137 int t; 138 cin >> t; 139 while (t--) { 140 solve(); 141 } 142 } 143 ``` 144 145 **Rate the problem** 146 147 Amazing 148 149 Good 150 151 Ok 152 153 Bad 154 155 Terrible 156 157 [2234C - Vessels, Heights and Two Versions (Easy Version)](/contest/2234/problem/C "Codeforces Round 1102 (Div. 2)") 158 159 Idea: [yanb0](/profile/yanb0 "Candidate Master yanb0") 160 161 **Hint** 162 163 Intuitively, the farther a vessel from the empty one, the more water there can be. Fix the empty vessel and try to explicitly find the formula for the maximum possible water height in each of the other vessels. 164 165 **Solution** 166 167 Tutorial is loading... 168 169 **Code (Python)** 170 171 ``` 172 t = int(input()) 173 for tc in range(t): 174 n = int(input()) 175 h = list(map(int, input().split())) 176 ans = [] 177 for s in range(n): 178 w1 = [0] * n 179 w2 = [0] * n 180 for i in range(1, n): 181 w1[(s + i) % n] = max(w1[(s + i - 1) % n], h[(s + i - 1) % n]) 182 for i in range(1, n): 183 w2[(s + n - i) % n] = max(w2[(s + n - i + 1) % n], h[(s + n - i) % n]) 184 w = [min(w1[i], w2[i]) for i in range(n)] 185 ans.append(sum(w)) 186 print(*ans) 187 ``` 188 189 **Code (C++)** 190 191 ``` 192 #include <bits/stdc++.h> 193 194 using namespace std; 195 196 void solve() { 197 int n; 198 cin >> n; 199 vector<int> h(n); 200 for (int i = 0; i < n; i++) cin >> h[i]; 201 202 for (int s = 0; s < n; s++) { 203 vector<int> w1(n), w2(n), w(n); 204 for (int i = 1; i < n; i++) { 205 w1[(s + i) % n] = max(w1[(s + i - 1) % n], h[(s + i - 1) % n]); 206 } 207 for (int i = 1; i < n; i++) { 208 w2[(s + n - i) % n] = max(w2[(s + n - i + 1) % n], h[(s + n - i) % n]); 209 } 210 for (int i = 0; i < n; i++) { 211 w[i] = min(w1[i], w2[i]); 212 } 213 cout << accumulate(w.begin(), w.end(), 0ll) << " "; 214 } 215 cout << "\n"; 216 } 217 218 signed main() { 219 ios_base::sync_with_stdio(0); cin.tie(0); 220 221 int t; 222 cin >> t; 223 while (t--) { 224 solve(); 225 } 226 } 227 ``` 228 229 **Rate the problem** 230 231 Amazing 232 233 Good 234 235 Ok 236 237 Bad 238 239 Terrible 240 241 [2234D - XOR, Expression and Two Binary Numbers](/contest/2234/problem/D "Codeforces Round 1102 (Div. 2)") 242 243 Idea: [Fakewave](/profile/Fakewave "Master Fakewave") 244 245 **Hint 1.1** 246 247 Let $A = a_1$, $B = a_{2^k + 1}$, $C = A \oplus B$. 248 249 Try to write out some values of $a$, for example, for $k = 3$. 250 251 **Hint 1.2** 252 253 $A \oplus B = C$, $B \oplus C = A$, $C \oplus A = B$. 254 255 **Hint 1.3** 256 257 Let's see how $a$ changes step by step: 258 259 * `a = [A, ?, ?, ?, ?, ?, ?, ?, B]`; 260 * `a = [A, ?, ?, ?, C, ?, ?, ?, B]`; 261 * `a = [A, ?, B, ?, C, ?, A, ?, B]`; 262 * `a = [A, C, B, A, C, B, A, C, B]`. 263 264 Try to notice and prove a pattern. 265 266 **Solution 1** 267 268 Tutorial is loading... 269 270 **Code (C++) of Solution 1** 271 272 ``` 273 #include <bits/stdc++.h> 274 275 using namespace std; 276 277 void solve() { 278 int n, k; 279 cin >> n >> k; 280 vector<int> a(n), b(n); 281 char g; 282 for (int i = 0; i < n; ++i) { 283 cin >> g; 284 a[i] = g - '0'; 285 } 286 for (int i = 0; i < n; ++i) { 287 cin >> g; 288 b[i] = g - '0'; 289 } 290 vector<int> c(4); 291 for (int i = 0; i < n; ++i) { 292 int x = 2 * a[i] + b[i]; 293 c[x]++; 294 } 295 296 if (k % 2) { 297 long long p = 0, q = 0, r = 0; 298 p = c[0] + c[1]; 299 q = c[0] + c[3]; 300 r = c[0] + c[2]; 301 cout << (((1ll << k) + 1) / 3) * (p * (n-p) + q * (n - q) + r * (n - r)) << "\n"; 302 } else { 303 long long p = 0, q = 0, r = 0; 304 p = c[0] + c[1]; 305 q = c[0] + c[2]; 306 r = c[0] + c[3]; 307 cout << (((1ll << k) + 1) / 3) * (p * (n-p) + q * (n - q) + r * (n - r)) + p * (n - p) + q * (n - q) << "\n"; 308 } 309 } 310 311 signed main() { 312 ios_base::sync_with_stdio(false); 313 cin.tie(nullptr); 314 int t; 315 cin >> t; 316 while (t--) { 317 solve(); 318 } 319 } 320 ``` 321 322 **Hint 2.1** 323 324 There is a rather straightforward solution that works in $\mathcal{O}(nk \log k)$. 325 326 **Hint 2.2** 327 328 Read the first two hints for Solution 1. Prove that each $a_i \in [A, B, C]$. 329 330 **Hint 2.3** 331 332 For every pair of bits $(x, y)$, count the number of positions $h$ for which the $h$-th bits of $a_1$ and $a_{2^k+1}$ are $x$ and $y$ respectively. Continue recursively. 333 334 **Hint 2.4** 335 336 Use caching. 337 338 **Solution 2** 339 340 Let the answer for the problem where $a_1 = A$, $a_{2^k+1} = B$ and $k = l$ be $F(l, A, B)$. 341 342 Then, as we write a value $A \oplus B$ in the middle of the array on the first step and then continue recursively, like for $k = l - 1$, $F(l, A, B) = F(l - 1, A, A \oplus B) + F(l - 1, A \oplus B, B) - [\text{product of the } 0 \text{ and } 1 \text{ bit counts for } A \oplus B]$. 343 344 Referring to the proof in Solution 1 that each $a_i \in [A, B, C]$, for each $l$ the function's value must be calculated for different pairs of $(A, B)$ at most $6$ times, thus, if we use a map for caching the answer of $F$, we will make not more than $6k$ calls to it, which makes the time complexity $\mathcal{O}(n + k \log k)$. 345 346 **Code (C++) of Solution 2** 347 348 ``` 349 #include <bits/stdc++.h> 350 351 using namespace std; 352 #define int long long 353 354 int n, k, a, b, c; 355 string p, q, r; 356 357 int get(string &s) { 358 int a = 0, b = 0; 359 for (char c : s) 360 if (c == '0') a++; 361 else b++; 362 return a * b; 363 } 364 365 map<array<int, 4>, int> mp; 366 367 int solve(int l, int a, int b, int c) { 368 array<int, 4> t = {l, a, b, c}; 369 if (mp.find(t) == mp.end()) { 370 if (l == 0) mp[t] = a + b; 371 else mp[t] = solve(l - 1, c, a, b) + solve(l - 1, b, c, a) - c; 372 } 373 return mp[t]; 374 } 375 376 void test_case() { 377 cin >> n >> k >> p >> q; 378 r.clear(); 379 for (int i = 0; i < n; i++) 380 r.push_back('0' + ((p[i] - '0') ^ (q[i] - '0'))); 381 a = get(p); 382 b = get(q); 383 c = get(r); 384 mp.clear(); 385 cout << solve(k, a, b, c) << '\n'; 386 } 387 388 int32_t main() { 389 ios::sync_with_stdio(0); cin.tie(0); 390 int t; cin >> t; 391 while (t--) test_case(); 392 } 393 ``` 394 395 **Rate the problem** 396 397 Amazing 398 399 Good 400 401 Ok 402 403 Bad 404 405 Terrible 406 407 [2234E - Vlad, Misha and Two Arrays](/contest/2234/problem/E "Codeforces Round 1102 (Div. 2)") 408 409 Idea: [Fakewave](/profile/Fakewave "Master Fakewave") 410 411 **Hint 1.1** 412 413 Looking only at the array $a$, how to deduce the index $i$ for which $p_i = 1$, i.e. the minimum of $p$? 414 415 **Hint 1.2** 416 417 Try to come up with a recursive solution that works in $\mathcal{O}(n^2)$. 418 419 **Solution 1 (yanb0)** 420 421 Tutorial is loading... 422 423 **Code (C++)** 424 425 ``` 426 #include <bits/stdc++.h> 427 428 #define int long long 429 430 using namespace std; 431 432 const int Mod = 1e9 + 7, Max = 5e5 + 10; 433 434 vector<int> fact(Max), ifact(Max); 435 436 int binpow(int b, int p) { 437 if (p == 0) return 1; 438 if (p % 2 == 0) return binpow((b * b) % Mod, p / 2); 439 return (binpow(b, p - 1) * b) % Mod; 440 } 441 442 int C(int n, int k) { 443 return (fact[n] * ((ifact[k] * ifact[n - k]) % Mod)) % Mod; 444 } 445 446 int rec(int l, int r, vector<int> &b) { 447 if (r < l) { 448 return 1; 449 } 450 if (l == r) { 451 return (b[l] == 1 ? 1 : 0); 452 } 453 for (int d = 0; d < r - l + 1; d++) { 454 int i = d + l; 455 if ((i - l + 1) * (r - i + 1) == b[i]) { 456 return (((rec(l, i - 1, b) * rec(i + 1, r, b)) % Mod) * C(r - l, i - l)) % Mod; 457 } 458 i = r - d; 459 if ((i - l + 1) * (r - i + 1) == b[i]) { 460 return (((rec(l, i - 1, b) * rec(i + 1, r, b)) % Mod) * C(r - l, i - l)) % Mod; 461 } 462 } 463 return 0; 464 } 465 466 void solve() { 467 int n; 468 cin >> n; 469 vector<int> b(n); 470 for (int i = 0; i < n; i++) cin >> b[i]; 471 472 int s = accumulate(b.begin(), b.end(), 0ll); 473 if (s != n * (n + 1) / 2) { 474 cout << "0\n"; 475 return; 476 } 477 478 cout << rec(0, n - 1, b) << "\n"; 479 } 480 481 signed main() { 482 ios_base::sync_with_stdio(0); cin.tie(0); 483 484 fact[0] = 1; 485 for (int i = 1; i < Max; i++) { 486 fact[i] = (fact[i - 1] * i) % Mod; 487 } 488 for (int i = 0; i < Max; i++) { 489 ifact[i] = binpow(fact[i], Mod - 2); 490 } 491 492 int t; 493 cin >> t; 494 while (t--) { 495 solve(); 496 } 497 } 498 ``` 499 500 **Solution 2 (_Crimson_)** 501 502 Will be added soon. 503 504 **Rate the problem** 505 506 Amazing 507 508 Good 509 510 Ok 511 512 Bad 513 514 Terrible 515 516 [2234F - Vessels, Heights and Two Versions (Hard Version)](/contest/2234/problem/F "Codeforces Round 1102 (Div. 2)") 517 518 Idea: [yanb0](/profile/yanb0 "Candidate Master yanb0") 519 520 **Hint 1** 521 522 Read the solution of C. Try to calculate the answer when the empty vessel is vessel $1$, then somehow change it quickly when moving the empty vessel to be vessel $2$, $3$, etc. 523 524 **Hint 2** 525 526 Consider the highest vessel connection. 527 528 **Hint 3** 529 530 You do not need any advanced data structures. Use a stack. 531 532 **Solution** 533 534 Tutorial is loading... 535 536 **Code (Python)** 537 538 ``` 539 INF = float("inf") 540 541 tt = int(input()) 542 for tc in range(tt): 543 n = int(input()) 544 h = list(map(int, input().split())) 545 t = 0 546 for i in range(n): 547 if h[i] > h[t]: 548 t = i 549 550 ls = [0 for i in range(n)] 551 rs = [0 for i in range(n)] 552 553 sm = [(INF, 0)] 554 for ti in range(1, n): 555 i = (ti + t) % n 556 s = ls[i] + h[i] 557 c = 1 558 while sm[-1][0] <= h[i]: 559 s += sm[-1][1] * (h[i] - sm[-1][0]) 560 c += sm[-1][1] 561 sm.pop() 562 sm.append((h[i], c)) 563 ls[(i + 1) % n] = s 564 565 sm = [(INF, 0)] 566 for ti in range(1, n): 567 i = (t + n - ti) % n 568 s = rs[(i + 1) % n] + h[i] 569 c = 1 570 while sm[-1][0] <= h[i]: 571 s += sm[-1][1] * (h[i] - sm[-1][0]) 572 c += sm[-1][1] 573 sm.pop() 574 sm.append((h[i], c)) 575 rs[i] = s 576 577 ans = [ls[i] + rs[i] for i in range(n)] 578 print(*ans) 579 ``` 580 581 **Code (C++)** 582 583 ``` 584 #include <bits/stdc++.h> 585 586 #define int long long 587 588 using namespace std; 589 590 using pii = pair<int, int>; 591 592 void solve() { 593 int n; 594 cin >> n; 595 vector<int> h(n); 596 for (int i = 0; i < n; i++) cin >> h[i]; 597 int t = max_element(h.begin(), h.end()) - h.begin(); 598 599 vector<int> ls(n), rs(n); 600 601 stack<pii> sm; 602 sm.push({1e18, 0}); 603 for (int ti = 1; ti < n; ti++) { 604 int i = (ti + t) % n; 605 int s = ls[i] + h[i], c = 1; 606 while (sm.top().first <= h[i]) { 607 s += sm.top().second * (h[i] - sm.top().first); 608 c += sm.top().second; 609 sm.pop(); 610 } 611 sm.push({h[i], c}); 612 ls[(i + 1) % n] = s; 613 } 614 615 sm = stack<pii>(); 616 sm.push({1e18, 0}); 617 for (int ti = 1; ti < n; ti++) { 618 int i = (t + n - ti) % n; 619 int s = rs[(i + 1) % n] + h[i], c = 1; 620 while (sm.top().first <= h[i]) { 621 s += sm.top().second * (h[i] - sm.top().first); 622 c += sm.top().second; 623 sm.pop(); 624 } 625 sm.push({h[i], c}); 626 rs[i] = s; 627 } 628 629 for (int i = 0; i < n; i++) { 630 cout << ls[i] + rs[i] << " "; 631 } 632 cout << "\n"; 633 } 634 635 signed main() { 636 ios_base::sync_with_stdio(0); cin.tie(0); 637 638 int t; 639 cin >> t; 640 while (t--) { 641 solve(); 642 } 643 } 644 ``` 645 646 **Rate the problem** 647 648 Amazing 649 650 Good 651 652 Ok 653 654 Bad 655 656 Terrible 657 658 [2234G - Stripe, Token and Two Players](/contest/2234/problem/G "Codeforces Round 1102 (Div. 2)") 659 660 Idea: [yanb0](/profile/yanb0 "Candidate Master yanb0") 661 662 **Hint 1** 663 664 Think of a $\mathcal{O}(n^3)$ solution. 665 666 **Answer to Hint 1** 667 668 DP. For each pair $(cell, strength)$ you can find whether the player that makes the move from the position wins if the game is played optimally. 669 670 **Hint 2** 671 672 There are not many losing positions in this game. Why? 673 674 **Answer to Hint 2** 675 676 The number of losing positions $(i, k)$ for a fixed $k$ with $i \le n$ is no more than $\big\lceil \frac{n}{k + 1} \big\rceil$, since if position $(i, k)$ is a losing position, then all positions $(i + 1, k), (i + 2, k), \ldots, (i + k, k)$ must be winning if they exist. Then the total number of losing positions $(i, k)$ with $i \le n$ is no more than $\mathcal{O}(n \log n)$. 677 678 **Hint 3** 679 680 Try to iterate over cell number $i$ from $n$ to $1$ and explicitly find all losing positions. 681 682 **Hint 4** 683 684 You need to think of a data structure to optimize the solution to $\mathcal{O}(n \log^2 n)$. 685 686 **Solution** 687 688 We'll denote the state of the game where a chip is on cell $i$ and has strength $k$ before using bonuses as $(i, k)$. We need to determine whether position $(1, 1)$ is a winning position. 689 690 Note that the number of losing positions $(i, k)$ for a fixed $k$ with $i \le n$ is no more than $\big\lceil \frac{n}{k + 1} \big\rceil$, since if position $(i, k)$ is a losing position, then all positions $(i + 1, k), (i + 2, k), \ldots, (i + k, k)$ must be winning if they exist. Then the total number of losing positions $(i, k)$ with $i \le n$ is no more than $\mathcal{O}(n \log n)$. 691 692 We will iterate over cell number $i$ from $n$ to $1$ and explicitly find all losing positions. 693 694 Let's maintain a set $S$ containing all $k$ for which there is no losing position $(j, k)$, where $i \lt j \le i + k$. This can be done using a priority queue, adding the event "no more losing positions with strength $k$ on the interval $[i + 1, i + k]$" to position $i - k - 1$ when position $(i, k)$ is losing. (Also, this event addition is done initially for positions $(n + 1, 0), (n + 1, 1), \ldots, (n + 1, n)$, since they are all losing positions, and the strength can be limited to being not more than $n$ without changing the game.) The total number of such events added to the queue will be no more than $\mathcal{O}(n \log n)$ (based on the number of losing positions), which means there will be no more than $\mathcal{O}(n \log n)$ queries to the queue, since in each cell we will only read and delete events related to it. Note that only when we read such an event do we add one element to $S$, and the number of additions to $S$ is also no more than $\mathcal{O}(n \log n)$. 695 696 We will find losing positions for cell $i$ as follows: a position $(i, k)$ is a losing position if and only if, for all $0 \le d \le a_i$, there are no losing positions among positions $(j, k + d)$ for $j \in [i + 1, i + k + d]$, i.e., if and only if $S$ contains all $k, k + 1, \ldots, k + a_i$. To quickly find such $k$, we use the following data structure (we will call it a *block container*): 697 698 There is a set $s$ of natural numbers, initially empty. All numbers in $s$ will be on the interval $[1, n]$, and all operations are guaranteed to be valid (for example, a number already contained in $s$ will not be asked to be added there). A block container can: 699 700 * add a number $x$ to $s$ in $\mathcal{O}(\log n)$; 701 * find the length of the longest segment of consecutive numbers in $s$ in $\mathcal{O}(1)$; 702 * find any longest segment of consecutive numbers in $s$ and remove its smallest element from $s$ in $\mathcal{O}(\log n)$. 703 704 **How to implement a block container** 705 706 If written in C++, a container of blocks can be implemented, for example, using two `std::set`s storing the same set of blocks (segments) of consecutive numbers in $s$ (numbers adjacent to the edges of a block must not be in $s$; for example, for $s = {1, 5, 3, 2, 6}$, the set of blocks will be ${[1, 3], [5, 6]}$). The first `std::set` will sort the blocks by their left boundary, and the second by length. 707 708 * When adding a number $x$ to $s$, the container adds a new block $[x, x]$, and then, using the first `std::set`, it finds whether some segments need to be merged with the new one (i.e., whether there are two blocks whose boundaries are adjacent numbers), and, if so, merges them. The container merges segments by removing the old pair of segments from both `std::set`s and adding the merged segment back to each `std::set`. 709 * To find the longest segment, the container simply accesses the second `std::set`. 710 * To remove the left element of the segment found above, the container removes the segment from both `std::set`s, increments its left bound by $1$, and, if the segment is still non-empty, adds it back to each `std::set`. 711 712 The code can be written similarly in other languages, if there's a built-in `set` that supports custom sorting and finding the smallest element. Alternatively, a segment tree can be written on a boolean array of length $n$, reflecting the presence/absence ($1$/$0$) of numbers in $s$, storing at a node the boundaries of the longest subsegment of the segment of the node consisting of consecutive 1s. 713 714 Now, let's show how to quickly find the required $k$. We'll store $S$ in a container of blocks. If the length of some block in $S$ is greater than $a_i$ and equals $l + a_i$, the $l$ smallest elements of this block will be losing strengths for cell $i$ — this determines all losing strengths for cell $i$ and only them. Then let's simply remove the smallest element of the longest block while its length is greater than $a_i$ — obviously, and all the removed numbers will be all the losing strengths for cell $i$. The number of requests to the block container for finding and removing when considering cell $i$ is then $1$ more than the number of losing positions $(i, k)$, that is, in total over all cells, no more than $\mathcal{O}(n \log n)$. The number of requests to the block container for adding, as we showed earlier, is also not more than $\mathcal{O}(n \log n)$. 715 716 That is, for each cell, we first process the events coming from the priority queue, load the new elements into the $S$ block container, then find the losing positions, and finally add new events for the next cells to the priority queue. This means we get every losing position in the process; all that remains is to check whether position $(1, 1)$ is a losing position. 717 718 This results in $\mathcal{O}(n \log^2 n)$ for requests to the priority queue, $\mathcal{O}(n \log^2 n)$ for requests to the block container, and a total asymptotic complexity of $\mathcal{O}(n \log^2 n)$. 719 720 **Rate the problem** 721 722 Amazing 723 724 Good 725 726 Ok 727 728 Bad 729 730 Terrible