1560.md (6416B)
1 Source: https://codeforces.com/blog/entry/94009 2 3 Ideas: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 4 5 [1560A - Dislike of Threes](/contest/1560/problem/A "Codeforces Round 739 (Div. 3)") 6 7 **Tutorial** 8 9 Tutorial is loading... 10 11 **Solution** 12 13 ``` 14 #include <bits/stdc++.h> 15 16 using namespace std; 17 18 int main() 19 { 20 int t; 21 cin >> t; 22 23 while (t--) 24 { 25 int k; 26 cin >> k; 27 28 for (int i = 1; ; i++) 29 { 30 if (i % 3 == 0 || i % 10 == 3) 31 continue; 32 if (--k == 0) 33 { 34 cout << i << '\n'; 35 break; 36 } 37 } 38 } 39 } 40 ``` 41 42 [1560B - Who's Opposite?](/contest/1560/problem/B "Codeforces Round 739 (Div. 3)") 43 44 **Tutorial** 45 46 Tutorial is loading... 47 48 **Solution** 49 50 ``` 51 #include <bits/stdc++.h> 52 53 using namespace std; 54 55 typedef long long ll; 56 57 int main() 58 { 59 int t; 60 cin >> t; 61 62 while (t--) 63 { 64 ll a, b, c; 65 cin >> a >> b >> c; 66 67 ll n = 2 * abs(a - b); 68 if (a > n || b > n || c > n) 69 cout << -1 << '\n'; 70 else 71 { 72 ll d = n / 2 + c; 73 while (d > n) d -= n; 74 cout << d << '\n'; 75 } 76 } 77 return 0; 78 } 79 ``` 80 81 [1560C - Infinity Table](/contest/1560/problem/C "Codeforces Round 739 (Div. 3)") 82 83 **Tutorial** 84 85 Tutorial is loading... 86 87 **Solution** 88 89 ``` 90 #include <bits/stdc++.h> 91 92 using namespace std; 93 94 int main() 95 { 96 int t; 97 cin >> t; 98 99 while (t--) 100 { 101 int k; 102 cin >> k; 103 104 int a = 1; 105 int x = 1; 106 int i = 1; 107 108 while (k >= x + a) 109 { 110 x += a; 111 a += 2; 112 i += 1; 113 } 114 115 int m = k - x + 1; 116 if (m <= i) 117 cout << m << ' ' << i << '\n'; 118 else 119 cout << i << ' ' << (i - (m - i)) << '\n'; 120 } 121 } 122 ``` 123 124 [1560D - Make a Power of Two](/contest/1560/problem/D "Codeforces Round 739 (Div. 3)") 125 126 **Tutorial** 127 128 Tutorial is loading... 129 130 **Solution** 131 132 ``` 133 #include <bits/stdc++.h> 134 135 using namespace std; 136 137 typedef long long ll; 138 139 const ll P2LIM = (ll)2e18; 140 141 int solve(string s, string t) 142 { 143 int tp = 0; 144 int sp = 0; 145 int taken = 0; 146 147 while (sp < s.length() && tp < t.length()) 148 { 149 if(s[sp] == t[tp]) 150 { 151 taken++; 152 tp++; 153 } 154 sp++; 155 } 156 157 return (int)s.length() - taken + (int)t.length() - taken; 158 } 159 160 vector<string> ts; 161 162 int main() 163 { 164 for (ll p2 = 1; p2 <= P2LIM; p2 *= 2) 165 ts.push_back(to_string(p2)); 166 167 int t; 168 cin >> t; 169 170 while (t--) 171 { 172 string n; 173 cin >> n; 174 175 int ans = n.length() + 1; 176 for (auto p2 : ts) 177 ans = min(ans, solve(n, p2)); 178 cout << ans << '\n'; 179 } 180 181 return 0; 182 } 183 ``` 184 185 [1560E - Polycarp and String Transformation](/contest/1560/problem/E "Codeforces Round 739 (Div. 3)") 186 187 **Tutorial** 188 189 Tutorial is loading... 190 191 **Solution** 192 193 ``` 194 #include <bits/stdc++.h> 195 196 using namespace std; 197 198 int cntsrc[26]; // don't forget to memset it but not cnt 199 int* cnt = cntsrc - 'a'; // so cnt['a'] = cntsrc[0] and so on 200 201 pair<string, string> decrypt(string s) 202 { 203 string order; 204 reverse(s.begin(), s.end()); 205 for (auto c : s) 206 { 207 if (!cnt[c]) 208 order.push_back(c); 209 cnt[c]++; 210 } 211 212 int m = order.length(); 213 int originalLength = 0; 214 for (int i = 0; i < m; i++) 215 originalLength += cnt[order[i]] / (m - i); 216 217 reverse(order.begin(), order.end()); 218 return { string(s.rbegin(), s.rbegin() + originalLength), order }; 219 } 220 221 string encrypt(pair<string, string> p) 222 { 223 string result = p.first; 224 225 for (auto c : p.second) 226 { 227 string temp; 228 for (auto d : p.first) 229 if (d != c) 230 { 231 temp.push_back(d); 232 result.push_back(d); 233 } 234 p.first = temp; 235 } 236 237 return result; 238 } 239 240 int main() 241 { 242 int t; 243 cin >> t; 244 245 while (t--) 246 { 247 memset(cntsrc, 0, sizeof(cntsrc)); 248 string s; 249 cin >> s; 250 251 auto ans = decrypt(s); 252 auto check = encrypt(ans); 253 254 if (check == s) 255 cout << ans.first << ' ' << ans.second << '\n'; 256 else 257 cout << "-1\n"; 258 } 259 260 return 0; 261 } 262 ``` 263 264 [1560F1 - Nearest Beautiful Number (easy version)](/contest/1560/problem/F1 "Codeforces Round 739 (Div. 3)") 265 266 **Tutorial** 267 268 Tutorial is loading... 269 270 **Solution** 271 272 ``` 273 #include <bits/stdc++.h> 274 275 using namespace std; 276 277 string solve1(string n) 278 { 279 string res(n.length(), '9'); 280 for (char c = '8'; c >= '0'; c--) 281 { 282 string t(n.length(), c); 283 if (t >= n) 284 res = t; 285 } 286 287 return res; 288 } 289 290 string solve2(string n) 291 { 292 string res = solve1(n); 293 294 for(char a = '0'; a <= '9'; a++) 295 for (char b = a + 1; b <= '9'; b++) 296 { 297 bool n_ok = true; 298 for (int i = 0; i < n.length(); i++) 299 { 300 if (n[i] < b) 301 { 302 string t = n; 303 if (t[i] < a) t[i] = a; 304 else t[i] = b; 305 for (int j = i + 1; j < n.length(); j++) 306 t[j] = a; 307 if (res > t) 308 res = t; 309 } 310 311 if(n[i] != a && n[i] != b) 312 { 313 n_ok = false; 314 break; 315 } 316 } 317 318 if (n_ok) return n; 319 } 320 321 return res; 322 } 323 324 string solve() 325 { 326 string n; 327 int k; 328 cin >> n >> k; 329 330 if (k == 1) return solve1(n); 331 else return solve2(n); 332 } 333 334 int main() 335 { 336 int t; 337 cin >> t; 338 339 while (t--) 340 cout << solve() << '\n'; 341 342 return 0; 343 } 344 ``` 345 346 [1560F2 - Nearest Beautiful Number (hard version)](/contest/1560/problem/F2 "Codeforces Round 739 (Div. 3)") 347 348 **Tutorial** 349 350 Tutorial is loading... 351 352 **Short solution** 353 354 ``` 355 #include <bits/stdc++.h> 356 357 using namespace std; 358 359 string solve() 360 { 361 string n; 362 int k; 363 cin >> n >> k; 364 365 while (true) 366 { 367 set<char> s; 368 for (auto c : n) s.insert(c); 369 if (s.size() <= k) return n; 370 371 s.clear(); 372 int ptr = 0; 373 for (; ; ptr++) 374 { 375 s.insert(n[ptr]); 376 if (s.size() > k) 377 { 378 while (n[ptr] == '9') 379 ptr--; 380 n[ptr]++; 381 for (int i = ptr + 1; i < n.size(); i++) 382 n[i] = '0'; 383 break; 384 } 385 } 386 } 387 } 388 389 int main() 390 { 391 int t; 392 cin >> t; 393 394 while (t--) 395 cout << solve() << '\n'; 396 397 return 0; 398 } 399 ``` 400 401 **Long solution** 402 403 ``` 404 #include <bits/stdc++.h> 405 406 using namespace std; 407 408 string solveFillingSuffix(string& n, char d, int from) 409 { 410 for (int i = from; i < n.length(); i++) 411 n[i] = d; 412 return n; 413 } 414 415 void decAt(map<char, int>& d, char c) 416 { 417 if (d.count(c)) 418 { 419 d[c]--; 420 if (d[c] == 0) d.erase(c); 421 } 422 } 423 424 string solve() 425 { 426 string n; 427 int k; 428 cin >> n >> k; 429 430 map<char, int> d; 431 int pref = 0; 432 433 while (pref < n.length()) 434 { 435 if (d.count(n[pref])) 436 { 437 d[n[pref++]]++; 438 continue; 439 } 440 if (d.size() == k) break; 441 d[n[pref++]]++; 442 } 443 444 if (pref == n.length()) 445 return n; 446 447 while (true) 448 { 449 if (n[pref] == '9') 450 { 451 decAt(d, n[--pref]); 452 continue; 453 } 454 455 if (d.size() < k) 456 { 457 d[++n[pref]]++; 458 return solveFillingSuffix(n, d.size() < k ? '0' : d.begin()->first, pref + 1); 459 } 460 461 auto it = d.upper_bound(n[pref]); 462 if (it == d.end()) 463 { 464 decAt(d, n[--pref]); 465 continue; 466 } 467 468 n[pref] = it->first; 469 return solveFillingSuffix(n, d.begin()->first, pref + 1); 470 } 471 } 472 473 int main() 474 { 475 int t; 476 cin >> t; 477 478 while (t--) 479 cout << solve() << '\n'; 480 481 return 0; 482 } 483 ```