1207.md (9591B)
1 Source: https://codeforces.com/blog/entry/69314 2 3 [1207A - There Are Two Types Of Burgers](/contest/1207/problem/A "Educational Codeforces Round 71 (Rated for Div. 2)") 4 5 Idea: [BledDest](/profile/BledDest "Grandmaster BledDest") 6 7 **Tutorial** 8 9 Tutorial is loading... 10 11 **Solution (Roms)** 12 13 ``` 14 #include <bits/stdc++.h> 15 16 using namespace std; 17 18 int t; 19 int b, p, f; 20 int h, c; 21 22 int main() { 23 cin >> t; 24 for(int tc = 0; tc < t; ++tc){ 25 cin >> b >> p >> f; 26 cin >> h >> c; 27 28 b /= 2; 29 if(h < c){ 30 swap(h, c); 31 swap(p, f); 32 } 33 34 int res = 0; 35 36 int cnt = min(b, p); 37 b -= cnt, p -= cnt; 38 res += h * cnt; 39 40 cnt = min(b, f); 41 b -= cnt, f -= cnt; 42 res += c * cnt; 43 44 cout << res << endl; 45 } 46 return 0; 47 } 48 ``` 49 50 [1207B - Square Filling](/contest/1207/problem/B "Educational Codeforces Round 71 (Rated for Div. 2)") 51 52 Idea: [BledDest](/profile/BledDest "Grandmaster BledDest") 53 54 **Tutorial** 55 56 Tutorial is loading... 57 58 **Solution (BledDest)** 59 60 ``` 61 n, m = map(int, input().split()) 62 a = [[] for i in range(n)] 63 for i in range(n): 64 a[i] = list(map(int, input().split())) 65 66 ans = [] 67 for i in range(n - 1): 68 for j in range(m - 1): 69 if(a[i][j] * a[i][j + 1] * a[i + 1][j] * a[i + 1][j + 1] > 0): 70 a[i][j] = 2 71 a[i + 1][j] = 2 72 a[i][j + 1] = 2 73 a[i + 1][j + 1] = 2 74 ans.append([i, j]) 75 76 cnt1 = 0 77 for i in range(n): 78 for j in range(m): 79 if(a[i][j] == 1): 80 cnt1 += 1 81 82 if(cnt1 != 0): 83 print(-1) 84 else: 85 print(len(ans)) 86 for x in ans: 87 print(x[0] + 1, x[1] + 1) 88 ``` 89 90 [1207C - Gas Pipeline](/contest/1207/problem/C "Educational Codeforces Round 71 (Rated for Div. 2)") 91 92 Idea: [adedalic](/profile/adedalic "International Master adedalic") 93 94 **Tutorial** 95 96 Tutorial is loading... 97 98 **Solution (adedalic)** 99 100 ``` 101 const val INF64 = 1e18.toLong() 102 103 fun main(args: Array<String>) { 104 val tc = readLine()!!.toInt() 105 for (t in 1..tc) { 106 val (n, a, b) = readLine()!!.split(' ').map { it.toInt() } 107 val s = readLine()!! 108 109 val d = Array(n + 1) { arrayOf(INF64, INF64) } 110 d[0][0] = b.toLong() 111 112 for (pos in 0 until n) { 113 if (s[pos] == '0') { 114 d[pos + 1][0] = minOf(d[pos + 1][0], d[pos][0] + a + b) 115 d[pos + 1][1] = minOf(d[pos + 1][1], d[pos][0] + 2 * (a + b)) 116 117 d[pos + 1][1] = minOf(d[pos + 1][1], d[pos][1] + a + 2 * b) 118 d[pos + 1][0] = minOf(d[pos + 1][0], d[pos][1] + 2 * a + b) 119 } else { 120 d[pos + 1][1] = minOf(d[pos + 1][1], d[pos][1] + a + 2 * b) 121 } 122 } 123 println(d[n][0]) 124 } 125 } 126 ``` 127 128 [1207D - Number Of Permutations](/contest/1207/problem/D "Educational Codeforces Round 71 (Rated for Div. 2)") 129 130 Idea: [Roms](/profile/Roms "Master Roms") 131 132 **Tutorial** 133 134 Tutorial is loading... 135 136 **Solution (Roms)** 137 138 ``` 139 #include <bits/stdc++.h> 140 141 using namespace std; 142 143 const int N = int(3e5) + 99; 144 const int MOD = 998244353; 145 146 int mul(int a, int b){ 147 return (a * 1LL * b) % MOD; 148 } 149 150 int sum(int a, int b){ 151 return (a + b) % MOD; 152 } 153 154 int n; 155 pair<int, int> a[N]; 156 int f[N]; 157 158 int main() { 159 scanf("%d", &n); 160 for(int i = 0; i < n; ++i) 161 scanf("%d%d", &a[i].first, &a[i].second); 162 163 f[0] = 1; 164 for(int i = 1; i < N; ++i) 165 f[i] = mul(i, f[i - 1]); 166 167 int res = f[n]; 168 for(int c = 0; c < 2; ++c){ 169 int d = 1; 170 sort(a, a + n); 171 int l = 0; 172 while(l < n){ 173 int r = l + 1; 174 while(r < n && a[l].first == a[r].first) ++r; 175 d = mul(d, f[r - l]); 176 l = r; 177 } 178 res = sum(res, MOD - d); 179 for(int i = 0; i < n; ++i) 180 swap(a[i].first, a[i].second); 181 } 182 183 sort(a, a + n); 184 int l = 0; 185 int d = 1; 186 while(l < n){ 187 int r = l + 1; 188 while(r < n && a[l].first == a[r].first) ++r; 189 map<int, int> m; 190 for(int i = l; i < r; ++i) ++m[a[i].second]; 191 for(auto p : m) d = mul(d, f[p.second]); 192 l = r; 193 } 194 for(int i = 1; i < n; ++i) 195 if(a[i - 1].second > a[i].second) d = 0; 196 197 res = sum(res, d); 198 printf("%d\n", res); 199 return 0; 200 } 201 ``` 202 203 [1207E - XOR Guessing](/contest/1207/problem/E "Educational Codeforces Round 71 (Rated for Div. 2)") 204 205 Idea: [adedalic](/profile/adedalic "International Master adedalic"), [Neon](/profile/Neon "Candidate Master Neon"), [BledDest](/profile/BledDest "Grandmaster BledDest") 206 207 **Tutorial** 208 209 Tutorial is loading... 210 211 **Solution (BledDest)** 212 213 ``` 214 #include<bits/stdc++.h> 215 216 using namespace std; 217 218 int main() 219 { 220 cout << "?"; 221 for(int i = 1; i <= 100; i++) 222 cout << " " << i; 223 cout << endl; 224 cout.flush(); 225 int res1; 226 cin >> res1; 227 cout << "?"; 228 for(int i = 1; i <= 100; i++) 229 cout << " " << (i << 7); 230 cout << endl; 231 cout.flush(); 232 int res2; 233 cin >> res2; 234 int x = 0; 235 x |= (res1 & (((1 << 7) - 1) << 7)); 236 x |= (res2 & ((1 << 7) - 1)); 237 cout << "! " << x << endl; 238 cout.flush(); 239 return 0; 240 } 241 ``` 242 243 [1207F - Remainder Problem](/contest/1207/problem/F "Educational Codeforces Round 71 (Rated for Div. 2)") 244 245 Idea: [BledDest](/profile/BledDest "Grandmaster BledDest") 246 247 **Tutorial** 248 249 Tutorial is loading... 250 251 **Solution (BledDest)** 252 253 ``` 254 #include <bits/stdc++.h> 255 256 using namespace std; 257 258 const int N = 500043; 259 const int K = 750; 260 261 int a[N]; 262 int sum[K][K]; 263 264 int main() 265 { 266 int q; 267 scanf("%d", &q); 268 for(int i = 0; i < q; i++) 269 { 270 int t, x, y; 271 scanf("%d %d %d", &t, &x, &y); 272 if(t == 1) 273 { 274 a[x] += y; 275 for(int i = 1; i < K; i++) 276 sum[i][x % i] += y; 277 } 278 else 279 { 280 if(x >= K) 281 { 282 int ans = 0; 283 for(int i = y; i <= 500000; i += x) 284 ans += a[i]; 285 printf("%d\n", ans); 286 } 287 else 288 printf("%d\n", sum[x][y]); 289 } 290 } 291 return 0; 292 } 293 ``` 294 295 [1207G - Indie Album](/contest/1207/problem/G "Educational Codeforces Round 71 (Rated for Div. 2)") 296 297 Idea: [adedalic](/profile/adedalic "International Master adedalic") 298 299 **Tutorial** 300 301 Tutorial is loading... 302 303 **Solution (PikMike)** 304 305 ``` 306 #include <bits/stdc++.h> 307 308 #define forn(i, n) for (int i = 0; i < int(n); i++) 309 310 using namespace std; 311 312 const int AL = 26; 313 const int N = 400 * 1000 + 13; 314 315 struct node{ 316 int nxt[AL]; 317 node(){ 318 memset(nxt, -1, sizeof(nxt)); 319 } 320 int& operator [](int x){ 321 return nxt[x]; 322 } 323 }; 324 325 struct node_at{ 326 int nxt[AL]; 327 int p; 328 char pch; 329 int link; 330 int go[AL]; 331 node_at(){ 332 memset(nxt, -1, sizeof(nxt)); 333 memset(go, -1, sizeof(go)); 334 link = p = -1; 335 } 336 int& operator [](int x){ 337 return nxt[x]; 338 } 339 }; 340 341 int cntnm; 342 node trienm[N]; 343 344 int cntqr; 345 node_at trieqr[N]; 346 347 int add_string(string s){ 348 int v = 0; 349 for (auto it : s){ 350 int c = it - 'a'; 351 if (trieqr[v][c] == -1){ 352 trieqr[cntqr] = node_at(); 353 trieqr[cntqr].p = v; 354 trieqr[cntqr].pch = c; 355 trieqr[v][c] = cntqr; 356 ++cntqr; 357 } 358 v = trieqr[v][c]; 359 } 360 return v; 361 } 362 363 int go(int v, int c); 364 365 int get_link(int v){ 366 if (trieqr[v].link == -1){ 367 if (v == 0 || trieqr[v].p == 0) 368 trieqr[v].link = 0; 369 else 370 trieqr[v].link = go(get_link(trieqr[v].p), trieqr[v].pch); 371 } 372 return trieqr[v].link; 373 } 374 375 int go(int v, int c) { 376 if (trieqr[v].go[c] == -1){ 377 if (trieqr[v][c] != -1) 378 trieqr[v].go[c] = trieqr[v][c]; 379 else 380 trieqr[v].go[c] = (v == 0 ? 0 : go(get_link(v), c)); 381 } 382 return trieqr[v].go[c]; 383 } 384 385 int add_letter(int v, int c){ 386 if (trienm[v][c] == -1){ 387 trienm[cntnm] = node(); 388 trienm[v][c] = cntnm; 389 ++cntnm; 390 } 391 return trienm[v][c]; 392 } 393 394 vector<int> g[N]; 395 int tin[N], tout[N], T; 396 397 void dfs_init(int v){ 398 tin[v] = T++; 399 for (auto u : g[v]) 400 dfs_init(u); 401 tout[v] = T; 402 } 403 404 int f[N]; 405 406 void upd(int v, int val){ 407 for (int i = tin[v]; i < N; i |= i + 1) 408 f[i] += val; 409 } 410 411 int get(int x){ 412 int sum = 0; 413 for (int i = x; i >= 0; i = (i & (i + 1)) - 1) 414 sum += f[i]; 415 return sum; 416 } 417 418 int sum(int v){ 419 return get(tout[v] - 1) - get(tin[v] - 1); 420 } 421 422 int n, m; 423 int nm[N], qr[N]; 424 vector<int> nms[N]; 425 vector<int> reqs[N]; 426 int ans[N]; 427 428 void dfs(int v, int cur){ 429 upd(cur, 1); 430 for (auto it : nms[v]) 431 for (auto q : reqs[it]) 432 ans[q] = sum(qr[q]); 433 forn(i, AL) if (trienm[v][i] != -1) 434 dfs(trienm[v][i], go(cur, i)); 435 upd(cur, -1); 436 } 437 438 int main(){ 439 cntqr = 0; 440 trieqr[cntqr++] = node_at(); 441 442 cntnm = 0; 443 trienm[cntnm++] = node(); 444 445 char buf[N]; 446 scanf("%d", &n); 447 forn(i, n){ 448 int t; 449 scanf("%d", &t); 450 if (t == 1){ 451 scanf("%s", buf); 452 nm[i] = add_letter(0, buf[0] - 'a'); 453 } 454 else{ 455 int j; 456 scanf("%d%s", &j, buf); 457 --j; 458 nm[i] = add_letter(nm[j], buf[0] - 'a'); 459 } 460 nms[nm[i]].push_back(i); 461 } 462 463 scanf("%d", &m); 464 forn(i, m){ 465 int j; 466 scanf("%d%s", &j, buf); 467 --j; 468 reqs[j].push_back(i); 469 qr[i] = add_string(buf); 470 } 471 472 for (int v = 1; v < cntqr; ++v) 473 g[get_link(v)].push_back(v); 474 475 T = 0; 476 dfs_init(0); 477 dfs(0, 0); 478 479 forn(i, m) 480 printf("%d\n", ans[i]); 481 } 482 ```