1811.md (9076B)
1 Source: https://codeforces.com/blog/entry/114788 2 3 [1811A - Insert Digit](/contest/1811/problem/A "Codeforces Round 863 (Div. 3)") 4 5 Idea: [ibraevdmitriy](/profile/ibraevdmitriy "Master ibraevdmitriy"), prepared: [ibraevdmitriy](/profile/ibraevdmitriy "Master ibraevdmitriy") 6 7 **Tutorial** 8 9 Tutorial is loading... 10 11 **Solution** 12 13 ``` 14 #include <iostream> 15 16 using namespace std; 17 18 void solve() { 19 int n, d; 20 cin >> n >> d; 21 string s; 22 cin >> s; 23 for (int i = 0; i < n; ++i) { 24 if (s[i] - '0' >= d) { 25 cout << s[i]; 26 } else { 27 cout << d; 28 for (int j = i; j < n; ++j) { 29 cout << s[j]; 30 } 31 cout << '\n'; 32 return; 33 } 34 } 35 cout << d << '\n'; 36 } 37 38 int main() { 39 int t; 40 cin >> t; 41 for (int _ = 0; _ < t; ++_) { 42 solve(); 43 } 44 return 0; 45 } 46 ``` 47 48 [1811B - Conveyor Belts](/contest/1811/problem/B "Codeforces Round 863 (Div. 3)") 49 50 Idea: [Vladosiya](/profile/Vladosiya "Expert Vladosiya"), prepared: [ibraevdmitriy](/profile/ibraevdmitriy "Master ibraevdmitriy") 51 52 **Tutorial** 53 54 Tutorial is loading... 55 56 **Solution** 57 58 ``` 59 def layer(n, x, y): 60 return min([x, y, n + 1 - x, n + 1 - y]) 61 62 def solve(): 63 n, x1, y1, x2, y2 = map(int, input().split()) 64 print(abs(layer(n, x1, y1) - layer(n, x2, y2))) 65 66 t = int(input()) 67 for _ in range(t): 68 solve() 69 ``` 70 71 [1811C - Restore the Array](/contest/1811/problem/C "Codeforces Round 863 (Div. 3)") 72 73 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov"), prepared: [myav](/profile/myav "Pupil myav") 74 75 **Tutorial** 76 77 Tutorial is loading... 78 79 **Solution** 80 81 ``` 82 #include "bits/stdc++.h" 83 using namespace std; 84 85 void solve(){ 86 int n; 87 cin >> n; 88 vector<int>b(n-1), a; 89 for(int i = 0; i < n - 1; i++) cin >> b[i]; 90 a.emplace_back(b[0]); 91 for(int i = 0; i < n - 2; i++){ 92 a.emplace_back(min(b[i], b[i + 1])); 93 } 94 a.emplace_back(b[n - 2]); 95 for(auto &i : a) cout << i << ' '; 96 cout << "\n"; 97 } 98 int main(){ 99 int t; 100 cin >> t; 101 while(t--){ 102 solve(); 103 } 104 return 0; 105 } 106 ``` 107 108 [1811D - Umka and a Long Flight](/contest/1811/problem/D "Codeforces Round 863 (Div. 3)") 109 110 Idea: [Gornak40](/profile/Gornak40 "Expert Gornak40"), prepared: [Gornak40](/profile/Gornak40 "Expert Gornak40") 111 112 **Tutorial** 113 114 Tutorial is loading... 115 116 **Solution** 117 118 ``` 119 #include <bits/stdc++.h> 120 121 using namespace std; 122 123 const int MAXN = 50; 124 125 int fib[MAXN]; 126 127 void build() { 128 fib[0] = fib[1] = 1; 129 for (int i = 2; i < MAXN; ++i) 130 fib[i] = fib[i - 2] + fib[i - 1]; 131 } 132 133 bool solve(int n, int x, int y) { 134 if (n == 1) return true; 135 if (fib[n - 1] <= y && y < fib[n]) 136 return false; 137 if (fib[n] <= y) 138 y -= fib[n]; 139 return solve(n - 1, y, x); 140 } 141 142 int main() { 143 int t; cin >> t; 144 build(); 145 while (t--) { 146 int n, x, y; cin >> n >> x >> y; 147 cout << (solve(n, --x, --y) ? "YES" : "NO") << '\n'; 148 } 149 } 150 ``` 151 152 [1811E - Living Sequence](/contest/1811/problem/E "Codeforces Round 863 (Div. 3)") 153 154 Idea: [Aris](/profile/Aris "Candidate Master Aris"), prepared: [Aris](/profile/Aris "Candidate Master Aris") 155 156 **Tutorial** 157 158 Tutorial is loading... 159 160 **Solution** 161 162 ``` 163 #include <iostream> 164 #include <cmath> 165 #include <cctype> 166 #include <vector> 167 #include <algorithm> 168 #include <set> 169 #include <map> 170 #include <deque> 171 #include <stack> 172 #include <unordered_set> 173 #include <sstream> 174 #include <cstring> 175 #include <iomanip> 176 #include <queue> 177 #include <unordered_map> 178 #include <random> 179 #include <cfloat> 180 #include <chrono> 181 #include <bitset> 182 #include <complex> 183 #include <immintrin.h> 184 185 int main() { 186 std::ios::sync_with_stdio(false); 187 std::cin.tie(0); 188 189 int32_t num_tests; 190 std::cin >> num_tests; 191 192 for(int32_t t = 0; t < num_tests; t++) { 193 int64_t k; 194 std::cin >> k; 195 196 std::vector<int32_t> digits; 197 while(k > 0) { 198 digits.push_back(k % 9); 199 k /= 9; 200 } 201 std::reverse(digits.begin(), digits.end()); 202 203 for(int32_t i = 0; i < digits.size(); i++) 204 std::cout << (char)(digits[i] < 4 ? (digits[i] + '0') : (digits[i] + '1')); 205 std::cout << "\n"; 206 } 207 return 0; 208 } 209 ``` 210 211 [1811F - Is It Flower?](/contest/1811/problem/F "Codeforces Round 863 (Div. 3)") 212 213 Idea: [Vladosiya](/profile/Vladosiya "Expert Vladosiya"), prepared: [Vladosiya](/profile/Vladosiya "Expert Vladosiya") 214 215 **Tutorial** 216 217 Tutorial is loading... 218 219 **Solution** 220 221 ``` 222 #include <bits/stdc++.h> 223 224 using namespace std; 225 226 int sz(int v, vector<vector<int>> &g, vector<bool> &used){ 227 used[v] = true; 228 int s = 1; 229 for(int u: g[v]){ 230 if(!used[u]) s += sz(u, g, used); 231 } 232 return s; 233 } 234 235 void remove(vector<int> &from, int x){ 236 for(int &e: from){ 237 if(e == x){ 238 swap(e, from.back()); 239 from.pop_back(); 240 return; 241 } 242 } 243 } 244 245 void solve(int tc) { 246 int n, m; 247 cin >> n >> m; 248 vector<vector<int>> sl(n); 249 for(int i = 0; i < m; ++i){ 250 int u, v; 251 cin >> u >> v; 252 sl[--u].emplace_back(--v); 253 sl[v].emplace_back(u); 254 } 255 int k = sqrt(n); 256 if(n != k * k || m != n + k){ 257 cout << "NO"; 258 return; 259 } 260 for(int i = 0; i < n; ++i){ 261 if(sl[i].size() != 2 && sl[i].size() != 4){ 262 cout << "NO"; 263 return; 264 } 265 } 266 vector<bool> used(n); 267 if(sz(0, sl, used) != n){ 268 cout << "NO"; 269 return; 270 } 271 for(int i = 0; i < n; ++i){ 272 if(sl[i].size() == 2) continue; 273 for(int j = 0; j < sl[i].size();){ 274 int u = sl[i][j]; 275 if(sl[u].size() > 2){ 276 remove(sl[i], u); 277 remove(sl[u], i); 278 } 279 else{ 280 j++; 281 } 282 } 283 } 284 used = vector<bool>(n); 285 for(int i = 0; i < n; ++i){ 286 if(!used[i] && sz(i, sl, used) != k){ 287 cout << "NO"; 288 return; 289 } 290 } 291 cout << "YES"; 292 } 293 294 bool multi = true; 295 296 signed main() { 297 cout.tie(nullptr); 298 int t = 1; 299 if (multi)cin >> t; 300 for (int i = 1; i <= t; ++i) { 301 solve(i); 302 cout << "\n"; 303 } 304 return 0; 305 } 306 ``` 307 308 [1811G1 - Vlad and the Nice Paths (easy version)](/contest/1811/problem/G1 "Codeforces Round 863 (Div. 3)") 309 310 Idea: [Vladosiya](/profile/Vladosiya "Expert Vladosiya"), prepared: [Vladosiya](/profile/Vladosiya "Expert Vladosiya") 311 312 **Tutorial** 313 314 Tutorial is loading... 315 316 **Solution** 317 318 ``` 319 M = 10 ** 9 + 7 320 321 def pw(a, n): 322 if n == 0: 323 return 1 324 b = pw(a, n // 2) 325 return b * b % M * (a if n % 2 == 1 else 1) % M 326 327 def obr(x): 328 return pw(x, M - 2) 329 330 def cnk(n, k): 331 return fact[n] * obr(fact[k]) % M * obr(fact[n - k]) % M 332 333 def solve(): 334 n, k = map(int, input().split()) 335 c = [-1] + [int(x) for x in input().split()] 336 if k == 1: 337 print(1) 338 return 339 dp = [[0] * (n // k + 1) for i in range(n + 1)] # dp[i][j] = number for i prefix with j blocks 340 dp[0][0] = 1 341 for i in range(1, n + 1): 342 for j in range(0, n // k + 1): 343 if j > 0: 344 sz = 1 345 for s in range(i - 1, - 1, -1): 346 if c[s] == c[i]: 347 sz += 1 348 if sz >= k: 349 dp[i][j] += dp[s - 1][j - 1] * cnk(sz - 2, k - 2) % M 350 dp[i][j] %= M 351 dp[i][j] += dp[i - 1][j] 352 dp[i][j] %= M 353 for j in range(n // k, -1, -1): 354 if dp[n][j] > 0: 355 print(dp[n][j]) 356 return 357 358 t = int(input()) 359 fact = [1] * 101 360 for i in range(1, 101): 361 fact[i] = fact[i - 1] * i % M 362 for _ in range(t): 363 solve() 364 ``` 365 366 [1811G2 - Vlad and the Nice Paths (hard version)](/contest/1811/problem/G2 "Codeforces Round 863 (Div. 3)") 367 368 Idea: [Vladosiya](/profile/Vladosiya "Expert Vladosiya"), prepared: [Vladosiya](/profile/Vladosiya "Expert Vladosiya") 369 370 **Tutorial** 371 372 Tutorial is loading... 373 374 **Solution** 375 376 ``` 377 from sys import stdin 378 input = lambda: stdin.readline().strip() 379 380 M = 10 ** 9 + 7 381 cnk = [[0] * (5000 + 1) for i in range(5000 + 1)] 382 383 def solve(): 384 n, k = map(int, input().split()) 385 c = [-1] + [int(x) for x in input().split()] 386 if k == 1: 387 print(1) 388 return 389 dp = [[0, 0] for i in range(n + 1)] # dp[i] = [number, max] for i prefix 390 dp[0][0] = 1 391 for i in range(1, n + 1): 392 sz = 1 393 for s in range(i - 1, - 1, -1): 394 if c[s] == c[i]: 395 sz += 1 396 if sz == k: 397 dp[i][1] = dp[s - 1][1] + 1 398 if sz >= k: 399 if dp[s - 1][1] < dp[i][1] - 1: 400 break 401 dp[i][0] += dp[s - 1][0] * cnk[sz - 2][k - 2] % M 402 dp[i][0] %= M 403 if dp[i][1] < dp[i - 1][1]: 404 dp[i] = [0, dp[i - 1][1]] 405 if dp[i][1] == dp[i - 1][1]: 406 dp[i][0] += dp[i - 1][0] 407 dp[i][0] %= M 408 print(dp[n][0]) 409 410 for i in range(5000 + 1): 411 cnk[i][0] = 1 412 for i in range(1, 5000 + 1): 413 for j in range(1, i + 1): 414 cnk[i][j] = (cnk[i - 1][j] + cnk[i - 1][j - 1]) % M 415 416 t = int(input()) 417 for _ in range(t): 418 solve() 419 ```