2072.md (7526B)
1 Source: https://codeforces.com/blog/entry/140039 2 3 ### Thanks for participating in the most isekai NyaForces contest! 4 5 We honestly strived to make good tasks. 6 7 [2072A - New World, New Me, New Array](/contest/2072/problem/A "Codeforces Round 1006 (Div. 3)") 8 9 Idea: [ne_justlm](/profile/ne_justlm "Specialist ne_justlm") 10 11 **Tutorial** 12 13 Tutorial is loading... 14 15 **Solution** 16 17 ``` 18 #include <bits/stdc++.h> 19 20 using namespace std; 21 22 void solve() { 23 int n, k, p; 24 cin >> n >> k >> p; 25 if (-n * p <= k && k <= n * p) { 26 cout << (abs(k) + p - 1) / p << '\n'; 27 } else { 28 cout << "-1\n"; 29 } 30 } 31 32 int main() { 33 int tt; 34 cin >> tt; 35 while (tt --> 0) { 36 solve(); 37 } 38 return 0; 39 } 40 ``` 41 42 **Rate the problem** 43 44 * Didn't solve 45 * Good task 46 * Average task 47 * Bad task 48 49 [2072B - Having Been a Treasurer in the Past, I Help Goblins Deceive](/contest/2072/problem/B "Codeforces Round 1006 (Div. 3)") 50 51 Idea: [ne_justlm](/profile/ne_justlm "Specialist ne_justlm") 52 53 **Tutorial** 54 55 Tutorial is loading... 56 57 **Solution** 58 59 ``` 60 #include <bits/stdc++.h> 61 62 using namespace std; 63 64 void solve() { 65 int n; 66 string s; 67 cin >> n >> s; 68 int64_t dash = count(s.begin(), s.end(), '-'); 69 int64_t under = n - dash; 70 int64_t ans = (dash / 2) * (dash - dash / 2) * under; 71 cout << ans << '\n'; 72 } 73 74 int main() { 75 int tt; 76 cin >> tt; 77 while (tt --> 0) { 78 solve(); 79 } 80 return 0; 81 } 82 ``` 83 84 **Rate the problem** 85 86 * Didn't solve 87 * Good task 88 * Average task 89 * Bad task 90 91 [2072C - Creating Keys for StORages Has Become My Main Skill](/contest/2072/problem/C "Codeforces Round 1006 (Div. 3)") 92 93 Idea: [ne_justlm](/profile/ne_justlm "Specialist ne_justlm"), [IceHydra](/profile/IceHydra "Expert IceHydra") 94 95 **Tutorial** 96 97 Tutorial is loading... 98 99 **Solution** 100 101 ``` 102 #include <iostream> 103 #include <vector> 104 105 using namespace std; 106 107 void Solve() { 108 int len, val; 109 cin >> len >> val; 110 vector<int> ans(len, val); 111 int or_val = 0; 112 bool flag = true; 113 for (int i = 0; i < len - 1; ++i) { 114 if (((or_val | i) & val) == (or_val | i)) { 115 or_val |= i; 116 ans[i] = i; 117 } else { 118 flag = false; 119 break; 120 } 121 } 122 if (flag && (or_val | (len - 1)) == val) { 123 ans[len - 1] = len - 1; 124 } 125 for (auto it : ans) cout << it << ' '; 126 cout << '\n'; 127 } 128 129 signed main() { 130 cin.tie(0)->sync_with_stdio(0); 131 int test_count = 1; 132 cin >> test_count; 133 while (test_count --> 0) Solve(); 134 } 135 ``` 136 137 **Rate the problem** 138 139 * Didn't solve 140 * Good task 141 * Average task 142 * Bad task 143 144 [2072D - For Wizards, the Exam Is Easy, but I Couldn't Handle It](/contest/2072/problem/D "Codeforces Round 1006 (Div. 3)") 145 146 Idea: [ne_justlm](/profile/ne_justlm "Specialist ne_justlm") 147 148 **Tutorial** 149 150 Tutorial is loading... 151 152 **Solution** 153 154 ``` 155 #include <bits/stdc++.h> 156 157 using namespace std; 158 159 void solve() { 160 int n; 161 cin >> n; 162 vector<int> a(n); 163 for (int i = 0; i < n; ++i) { 164 cin >> a[i]; 165 } 166 167 int best_diff = 0, L = 0, R = 0; 168 for (int i = 0; i < n; ++i) { 169 int cnt_greater = 0, cnt_less = 0; 170 for (int j = i + 1; j < n; ++j) { 171 cnt_greater += a[j] > a[i]; 172 cnt_less += a[j] < a[i]; 173 174 if (best_diff > cnt_greater - cnt_less) { 175 best_diff = cnt_greater - cnt_less; 176 L = i, R = j; 177 } 178 } 179 } 180 181 cout << L + 1 << ' ' << R + 1 << '\n'; 182 } 183 184 int main() { 185 int tt = 1; 186 cin >> tt; 187 while (tt --> 0) { 188 solve(); 189 } 190 return 0; 191 } 192 ``` 193 194 **Rate the problem** 195 196 * Didn't solve 197 * Good task 198 * Average task 199 * Bad task 200 201 [2072E - Do You Love Your Hero and His Two-Hit Multi-Target Attacks?](/contest/2072/problem/E "Codeforces Round 1006 (Div. 3)") 202 203 Idea: [ne_justlm](/profile/ne_justlm "Specialist ne_justlm") 204 205 **Tutorial** 206 207 Tutorial is loading... 208 209 **Solution** 210 211 ``` 212 #include <bits/stdc++.h> 213 214 using namespace std; 215 216 vector<pair<int64_t, int64_t>> rec(int64_t k, int64_t x0 = 0, int64_t y0 = 0) { 217 if (!k) { 218 return {}; 219 } 220 int64_t delta = 0; 221 while (delta * (delta - 1) / 2 <= k) { 222 delta++; 223 } 224 delta--; 225 auto remaining = rec(k - delta * (delta - 1) / 2, x0 + delta + 1, y0 + 1); 226 vector<pair<int64_t, int64_t>> ans; 227 for (int x = x0; x < x0 + delta; ++x) { 228 ans.push_back({x, y0}); 229 } 230 ans.insert(ans.end(), remaining.begin(), remaining.end()); 231 return ans; 232 } 233 234 void solve() { 235 int64_t k; 236 cin >> k; 237 if (!k) { 238 cout << "1\n69 52\n"; 239 return; 240 } 241 auto ans = rec(k, 0, 0); 242 cout << ans.size() << '\n'; 243 for (auto [x, y] : ans) { 244 cout << x << ' ' << y << '\n'; 245 } 246 } 247 248 int main() { 249 int tt = 1; 250 cin >> tt; 251 while (tt --> 0) { 252 solve(); 253 } 254 return 0; 255 } 256 ``` 257 258 **Rate the problem** 259 260 * Didn't solve 261 * Good task 262 * Average task 263 * Bad task 264 265 [2072F - Goodbye, Banker Life](/contest/2072/problem/F "Codeforces Round 1006 (Div. 3)") 266 267 Idea: [itz_pabloo](/profile/itz_pabloo "Expert itz_pabloo") 268 269 **Tutorial** 270 271 Tutorial is loading... 272 273 **Solution** 274 275 ``` 276 #include <bits/stdc++.h> 277 278 using namespace std; 279 280 constexpr int64_t kMaxN = 1e6 + 69; 281 vector<int64_t> c(kMaxN); 282 283 void precalc() { 284 c[0] = c[1] = 0; 285 for (int i = 2; i < kMaxN; ++i) { 286 c[i] = c[i - 1]; 287 int x = i; 288 while (x % 2 == 0) { 289 x /= 2, c[i]++; 290 } 291 } 292 } 293 294 void solve() { 295 int n, k; 296 cin >> n >> k; 297 298 --n; 299 for (int i = 0; i <= n; ++i) { 300 cout << k * (c[n] == c[i] + c[n - i]) << " \n"[i == n]; 301 } 302 } 303 304 int main() { 305 ios::sync_with_stdio(0); 306 cin.tie(0); 307 308 precalc(); 309 310 int tt = 1; 311 cin >> tt; 312 while (tt --> 0) { 313 solve(); 314 } 315 return 0; 316 } 317 ``` 318 319 **Rate the problem** 320 321 * Didn't solve 322 * Good task 323 * Average task 324 * Bad task 325 326 [2072G - I've Been Flipping Numbers for 300 Years and Calculated the Sum](/contest/2072/problem/G "Codeforces Round 1006 (Div. 3)") 327 328 Idea: [ne_justlm](/profile/ne_justlm "Specialist ne_justlm"), [IceHydra](/profile/IceHydra "Expert IceHydra") 329 330 **Tutorial** 331 332 Tutorial is loading... 333 334 **Solution** 335 336 ``` 337 #include <bits/stdc++.h> 338 339 using namespace std; 340 341 constexpr int64_t mod = 1e9 + 7; 342 constexpr int64_t twoInv = 500'000'004; 343 constexpr int64_t sixInv = 166'666'668; 344 345 int64_t add(int64_t a, int64_t b) { 346 return (a % mod + b % mod) % mod; 347 } 348 349 int64_t mns(int64_t a, int64_t b) { 350 return (a % mod - b % mod + mod) % mod; 351 } 352 353 int64_t mul(int64_t a, int64_t b) { 354 return (a % mod) * (b % mod) % mod; 355 } 356 357 int64_t rev(int64_t n, int64_t p) { 358 int64_t res = 0; 359 while (n) { 360 res = add(mul(res, p), n % p); 361 n /= p; 362 } 363 return res; 364 } 365 366 int64_t stupid(int64_t n, int64_t k) { 367 int64_t res = 0; 368 for (int64_t p = 2; p <= k; ++p) { 369 res = add(res, rev(n, p)); 370 } 371 return res; 372 } 373 374 int64_t sum1(int64_t r) { 375 return mul(mul(r, r + 1), twoInv); 376 } 377 378 int64_t sum1(int64_t l, int64_t r) { 379 return mns(sum1(r), sum1(l - 1)); 380 } 381 382 int64_t sum2(int64_t r) { 383 return mul(mul(mul(r, r + 1), 2 * r + 1), sixInv); 384 } 385 386 int64_t sum2(int64_t l, int64_t r) { 387 return mns(sum2(r), sum2(l - 1)); 388 } 389 390 int64_t get(int64_t n, int64_t l, int64_t r) { 391 if (l > r) { 392 return 0; 393 } 394 395 int64_t res = mul(sum1(l, r), n); 396 int64_t minus = 0, plus = 0; 397 398 int64_t L = l; 399 while (L <= r) { 400 int64_t value = n / L; 401 int64_t R = min(r, n / value); 402 403 minus = add(minus, mul(sum2(L, R), value)); 404 plus = add(plus, mul(R - L + 1, value)); 405 406 L = R + 1; 407 } 408 409 return add(mns(res, minus), plus); 410 } 411 412 void solve() { 413 int64_t n, k; 414 cin >> n >> k; 415 416 int64_t sq = (int64_t)sqrtl((long double)n); 417 int64_t ans = mul(max<int64_t>(0, k - n), n); 418 ans = add(ans, stupid(n, min(sq, k))); 419 ans = add(ans, get(n, sq + 1, min(n, k))); 420 421 cout << ans << '\n'; 422 } 423 424 int main() { 425 int tt = 1; 426 cin >> tt; 427 while (tt --> 0) { 428 solve(); 429 } 430 return 0; 431 } 432 ``` 433 434 **Rate the problem** 435 436 * Didn't solve 437 * Good task 438 * Average task 439 * Bad task