1493.md (9829B)
1 Source: https://codeforces.com/blog/entry/88422 2 3 [1493A - Anti-knapsack](/contest/1493/problem/A "Codeforces Round 705 (Div. 2)") 4 5 Idea: [AlFlen](/profile/AlFlen "Master AlFlen"), [74TrAkToR](/profile/74TrAkToR "Master 74TrAkToR") 6 7 **Tutorial** 8 9 Tutorial is loading... 10 11 **Solution (74TrAkToR)** 12 13 ``` 14 #include <bits/stdc++.h> 15 16 using namespace std; 17 18 int main() { 19 ios_base::sync_with_stdio(0); 20 cin.tie(0); 21 22 int t, n, k; 23 cin >> t; 24 while (t--) { 25 cin >> n >> k; 26 cout << n - k + k / 2 << '\n'; 27 for (int i = k + 1; i <= n; ++i) cout << i << " "; 28 for (int i = (k + 1) / 2; i < k; ++i) cout << i << " "; 29 cout << '\n'; 30 } 31 32 return 0; 33 } 34 ``` 35 36 [1493B - Planet Lapituletti](/contest/1493/problem/B "Codeforces Round 705 (Div. 2)") 37 38 Idea: [AlFlen](/profile/AlFlen "Master AlFlen") 39 40 **Tutorial** 41 42 Tutorial is loading... 43 44 **Solution (74TrAkToR)** 45 46 ``` 47 #include <bits/stdc++.h> 48 49 using namespace std; 50 51 vector < int > go = {0, 1, 5, -1, -1, 2, -1, -1, 8, -1}; 52 int inf = 1e9 + 7; 53 54 int get(int x) { 55 string s = to_string(x); 56 if ((int)s.size() == 1) s = "0" + s; 57 string answ = ""; 58 for (int i = 1; i >= 0; --i) { 59 if (go[s[i] - '0'] == -1) return inf; 60 answ += char(go[s[i] - '0'] + '0'); 61 } 62 return stoi(answ); 63 } 64 65 string good(int x) { 66 string ans = to_string(x); 67 if (x < 10) { 68 ans = "0" + ans; 69 } 70 return ans; 71 } 72 73 main() { 74 ios_base::sync_with_stdio(0); 75 cin.tie(0); 76 cout.tie(0); 77 int t, h, m, H, M; 78 cin >> t; 79 string s; 80 while (t--) { 81 cin >> h >> m; 82 cin >> s; 83 H = (s[0] - '0') * 10 + s[1] - '0'; 84 M = (s[3] - '0') * 10 + s[4] - '0'; 85 while (1) { 86 if (M == m) { 87 H++, M = 0; 88 } 89 if (H == h) { 90 H = 0; 91 } 92 if (get(M) < h && get(H) < m) { 93 cout << good(H) << ":" << good(M) << '\n'; 94 break; 95 } 96 M++; 97 } 98 } 99 return 0; 100 } 101 ``` 102 103 [1493C - K-beautiful Strings](/contest/1493/problem/C "Codeforces Round 705 (Div. 2)") 104 105 Idea: [74TrAkToR](/profile/74TrAkToR "Master 74TrAkToR") 106 107 **Tutorial** 108 109 Tutorial is loading... 110 111 **Solution (74TrAkToR)** 112 113 ``` 114 #include <bits/stdc++.h> 115 116 using namespace std; 117 118 int cnt[26]; 119 120 int get(int x, int k) { 121 return (k - x % k) % k; 122 } 123 124 main() { 125 ios_base::sync_with_stdio(0); 126 cin.tie(0); 127 cout.tie(0); 128 int n, k, t; 129 cin >> t; 130 while (t--) { 131 cin >> n >> k; 132 string s; 133 cin >> s; 134 for (int j = 0; j < 26; ++j) cnt[j] = 0; 135 for (auto c : s) cnt[c - 'a']++; 136 137 int sum = 0, flag = 1; 138 for (int i = 0; i < 26; ++i) { 139 sum += get(cnt[i], k); 140 } 141 142 if (sum == 0) { 143 cout << s << '\n'; 144 flag = 0; 145 } 146 147 if (n % k != 0) { 148 cout << -1 << '\n'; 149 continue; 150 } 151 152 for (int i = n - 1; i >= 0 && flag; --i) { 153 sum -= get(cnt[s[i] - 'a'], k); 154 cnt[s[i] - 'a']--; 155 sum += get(cnt[s[i] - 'a'], k); 156 for (int j = s[i] - 'a' + 1; j < 26; ++j) { 157 158 int lst_sum = sum; 159 sum -= get(cnt[j], k); 160 cnt[j]++; 161 sum += get(cnt[j], k); 162 163 if (i + sum + 1 <= n) { 164 for (int pos = 0; pos < i; ++pos) { 165 cout << s[pos]; 166 } 167 cout << char('a' + j); 168 169 string add = ""; 170 for (int w = 0; w < 26; ++w) { 171 int f = get(cnt[w], k); 172 while (f) { 173 f--; 174 add += char('a' + w); 175 } 176 } 177 while ((int)add.size() + i + 1 < n) { 178 add += "a"; 179 } 180 181 sort(add.begin(), add.end()); 182 cout << add << '\n'; 183 flag = 0; 184 break; 185 } 186 187 cnt[j]--; 188 sum = lst_sum; 189 } 190 } 191 } 192 return 0; 193 } 194 ``` 195 196 [1493D - GCD of an Array](/contest/1493/problem/D "Codeforces Round 705 (Div. 2)") 197 198 Idea: [74TrAkToR](/profile/74TrAkToR "Master 74TrAkToR") 199 200 **Tutorial** 201 202 Tutorial is loading... 203 204 **Solution (74TrAkToR)** 205 206 ``` 207 #include <bits/stdc++.h> 208 209 using namespace std; 210 211 typedef long long ll; 212 213 int const maxn = 2e5 + 5, max_val = 2e5 + 5; 214 ll mod = 1e9 + 7, ans = 1; 215 int nxt[max_val], n; 216 multiset <int> cnt[max_val]; 217 map <int, int> cnt_divisor[maxn]; 218 219 void add(int i, int x) { 220 while (x != 1) { 221 int div = nxt[x], add = 0; 222 while (nxt[x] == div) add++, x = x / nxt[x]; 223 224 int lst = cnt_divisor[i][div]; 225 cnt_divisor[i][div] += add; 226 int lst_min = 0; 227 if ((int)cnt[div].size() == n) { 228 lst_min = (*cnt[div].begin()); 229 } 230 if (lst != 0) { 231 cnt[div].erase(cnt[div].find(lst)); 232 } 233 cnt[div].insert(lst + add); 234 if ((int)cnt[div].size() == n) { 235 for (int j = lst_min + 1; j <= (*cnt[div].begin()); ++j) { 236 ans = ans * (ll)div % mod; 237 } 238 } 239 } 240 } 241 242 main() { 243 ios_base::sync_with_stdio(0); 244 cin.tie(0); 245 246 int q, l, x; 247 cin >> n >> q; 248 249 for (int i = 2; i < maxn; ++i) { 250 if (nxt[i] == 0) { 251 nxt[i] = i; 252 if (i > 10000) continue; 253 for (int j = i * i; j < maxn; j += i) { 254 if (nxt[j] == 0) nxt[j] = i; 255 } 256 } 257 } 258 259 for (int i = 1; i <= n; ++i) { 260 cin >> x; 261 add(i, x); 262 } 263 264 for (int i = 1; i <= q; ++i) { 265 cin >> l >> x; 266 add(l, x); 267 cout << ans << '\n'; 268 } 269 270 return 0; 271 } 272 ``` 273 274 [1493E - Enormous XOR](/contest/1493/problem/E "Codeforces Round 705 (Div. 2)") 275 276 Idea: [AlFlen](/profile/AlFlen "Master AlFlen") 277 278 **Tutorial** 279 280 Tutorial is loading... 281 282 **Solution (74TrAkToR)** 283 284 ``` 285 #include<bits/stdc++.h> 286 287 using namespace std; 288 289 string add(string s) { 290 int i = (int)s.size() - 1; 291 while (s[i] == '1') { 292 s[i] = '0'; 293 i--; 294 } 295 s[i] = '1'; 296 return s; 297 } 298 299 main() { 300 ios_base::sync_with_stdio(0); 301 cin.tie(0); 302 cout.tie(0); 303 int n; 304 cin >> n; 305 string l, r; 306 cin >> l >> r; 307 if (l == r) { 308 cout << r << '\n'; 309 return 0; 310 } 311 if (l[0] != r[0]) { 312 for (int i = 1; i <= n; ++i) cout << "1"; 313 return 0; 314 } 315 if (add(l) == r || r.back() == '1') { 316 cout << r << '\n'; 317 return 0; 318 } 319 cout << add(r) << '\n'; 320 return 0; 321 } 322 ``` 323 324 [1493F - Enchanted Matrix](/contest/1493/problem/F "Codeforces Round 705 (Div. 2)") 325 326 Idea: [74TrAkToR](/profile/74TrAkToR "Master 74TrAkToR") 327 328 **Tutorial** 329 330 Tutorial is loading... 331 332 **Solution (74TrAkToR)** 333 334 ``` 335 #include <bits/stdc++.h> 336 337 using namespace std; 338 339 int const maxn = 1005; 340 int dp[maxn]; 341 vector < vector < int > > T; 342 343 int ask(int lx1, int ly1, int rx1, int ry1, int lx2, int ly2, int rx2, int ry2) { 344 cout << "? " << rx1 - lx1 + 1 << " " << ry1 - ly1 + 1 << " " << lx1 << " " << ly1 345 << " " << lx2 << " " << ly2 << endl; 346 int ans; 347 cin >> ans; 348 return ans; 349 } 350 351 int good(int l, int r) { 352 if (l == r) return 1; 353 354 int cnt = (r - l + 1) / 2; 355 if (ask(T[l][0], T[l][1], T[l + cnt - 1][2], T[l + cnt - 1][3], T[l + cnt][0], T[l + cnt][1], T[l + 2 * cnt - 1][2], T[l + 2 * cnt - 1][3])) { 356 return good(l + cnt, r); 357 } 358 return 0; 359 } 360 361 main() { 362 ios_base::sync_with_stdio(0); 363 cin.tie(0); 364 cout.tie(0); 365 int n, m, cntn = 0, cntm = 0; 366 cin >> n >> m; 367 368 for (int i = n; i >= 1; --i) { 369 if (n % i != 0 || dp[i] != 0) continue; 370 371 for (int j = 2 * i; j <= n; j += i) { 372 if (n % j == 0 && j % i == 0) { 373 T = {}; 374 for (int k = 1; k <= j / i; ++k) { 375 T.push_back({(k - 1) * i + 1, 1, k * i, m}); 376 } 377 if (good(0, (int)T.size() - 1)) dp[i] = 1; 378 else dp[i] = 2; 379 break; 380 } 381 } 382 383 if (dp[i] == 2) { 384 for (int j = 1; j <= n; ++j) { 385 if (i % j == 0) dp[j] = 2; 386 } 387 } 388 else { 389 dp[i] = 1; 390 for (int j = i; j <= n; ++j) { 391 if (dp[j] == 1) { 392 int w = __gcd(i, j); 393 for (int pos = w; pos <= n; pos += w) { 394 dp[pos] = 1; 395 } 396 } 397 } 398 } 399 } 400 401 for (int i = 1; i <= n; ++i) { 402 if (n % i == 0) cntn += (dp[i] == 1); 403 dp[i] = 0; 404 } 405 406 for (int i = m; i >= 1; --i) { 407 if (m % i != 0 || dp[i] != 0) continue; 408 409 for (int j = 2 * i; j <= m; j += i) { 410 if (m % j == 0 && j % i == 0) { 411 T = {}; 412 for (int k = 1; k <= j / i; ++k) { 413 T.push_back({1, (k - 1) * i + 1, n, k * i}); 414 } 415 if (good(0, (int)T.size() - 1)) dp[i] = 1; 416 else dp[i] = 2; 417 break; 418 } 419 } 420 if (dp[i] == 2) { 421 for (int j = 1; j <= i; ++j) { 422 if (i % j == 0) { 423 dp[j] = 2; 424 } 425 } 426 } 427 else { 428 dp[i] = 1; 429 for (int j = i; j <= m; ++j) { 430 if (dp[j] == 1) { 431 int w = __gcd(i, j); 432 for (int pos = w; pos <= m; pos += w) { 433 dp[pos] = 1; 434 } 435 } 436 } 437 } 438 } 439 440 for (int i = 1; i <= m; ++i) { 441 if (m % i == 0) cntm += (dp[i] == 1); 442 } 443 cout << "! " << cntn * cntm << endl; 444 return 0; 445 } 446 ```