1814.md (8447B)
1 Source: https://codeforces.com/blog/entry/114854 2 3 [1814A - Coins](/contest/1814/problem/A "Educational Codeforces Round 146 (Rated for Div. 2)") 4 5 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 6 7 **Tutorial** 8 9 Tutorial is loading... 10 11 **Solution (awoo)** 12 13 ``` 14 for _ in range(int(input())): 15 n, k = map(int, input().split()) 16 for x in range(2): 17 if n - x * k >= 0 and (n - x * k) % 2 == 0: 18 print("YES") 19 break 20 else: 21 print("NO") 22 ``` 23 24 [1814B - Long Legs](/contest/1814/problem/B "Educational Codeforces Round 146 (Rated for Div. 2)") 25 26 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 27 28 **Tutorial** 29 30 Tutorial is loading... 31 32 **Solution (awoo)** 33 34 ``` 35 for _ in range(int(input())): 36 a, b = map(int, input().split()) 37 ans = a + b 38 for m in range(1, 100000): 39 ans = min(ans, (a + m - 1) // m + (b + m - 1) // m + (m - 1)) 40 print(ans) 41 ``` 42 43 [1814C - Search in Parallel](/contest/1814/problem/C "Educational Codeforces Round 146 (Rated for Div. 2)") 44 45 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 46 47 **Tutorial** 48 49 Tutorial is loading... 50 51 **Solution (BledDest)** 52 53 ``` 54 #include<bits/stdc++.h> 55 56 using namespace std; 57 58 int main() 59 { 60 int t; 61 scanf("%d", &t); 62 for(int i = 0; i < t; i++) 63 { 64 int n; 65 scanf("%d", &n); 66 vector<int> s(2); 67 for(int j = 0; j < 2; j++) 68 scanf("%d", &s[j]); 69 vector<pair<int, int>> a(n); 70 for(int j = 0; j < n; j++) 71 { 72 scanf("%d", &a[j].first); 73 a[j].second = j + 1; 74 } 75 sort(a.begin(), a.end()); 76 reverse(a.begin(), a.end()); 77 vector<vector<int>> lists(2); 78 for(int j = 0; j < n; j++) 79 { 80 int cost1 = s[0] * (lists[0].size() + 1); 81 int cost2 = s[1] * (lists[1].size() + 1); 82 if(cost1 < cost2) 83 lists[0].push_back(a[j].second); 84 else 85 lists[1].push_back(a[j].second); 86 } 87 for(int j = 0; j < 2; j++) 88 { 89 cout << lists[j].size(); 90 for(auto x : lists[j]) cout << " " << x; 91 cout << endl; 92 } 93 } 94 } 95 ``` 96 97 [1814D - Balancing Weapons](/contest/1814/problem/D "Educational Codeforces Round 146 (Rated for Div. 2)") 98 99 Idea: [adedalic](/profile/adedalic "International Master adedalic") 100 101 **Tutorial** 102 103 Tutorial is loading... 104 105 **Solution (adedalic)** 106 107 ``` 108 fun main() { 109 repeat(readln().toInt()) { 110 val (n, k) = readln().split(' ').map { it.toInt() } 111 val f = readln().split(' ').map { it.toLong() } 112 val d = readln().split(' ').map { it.toLong() } 113 114 fun checkAround(pos : Long) : Int { 115 val qs = Array(2 * k + 1) { MutableList(0) { 0 } } 116 117 fun inside(x : Long, pos: Long) = (pos - k <= x) && (x <= pos + k) 118 for (i in f.indices) { 119 var newD = maxOf(1L, pos / f[i]) 120 if (newD != d[i] && newD + 1 != d[i] && inside(d[i] * f[i], pos)) { 121 val id = (i + 1) 122 qs[(d[i] * f[i] - pos + k).toInt()].add(id) 123 } 124 repeat(2) { 125 if (inside(newD * f[i], pos)) { 126 val id = if (newD == d[i]) (i + 1) else -(i + 1) 127 qs[(newD * f[i] - pos + k).toInt()].add(id) 128 } 129 newD++ 130 } 131 132 } 133 134 val cntPerId = IntArray(n) { 0 } 135 var cntDistinct = 0 136 var cntGood = 0 137 138 fun addToSeg(cid : Int) { 139 val id = -1 + if (cid > 0) cid else -cid 140 val c = if (cid > 0) 1 else 0 141 142 if (cntPerId[id] == 0) 143 cntDistinct++ 144 cntPerId[id]++ 145 146 cntGood += c 147 } 148 fun eraseFromSeg(cid : Int) { 149 val id = -1 + if (cid > 0) cid else -cid 150 val c = if (cid > 0) 1 else 0 151 152 cntPerId[id]-- 153 if (cntPerId[id] == 0) 154 cntDistinct-- 155 156 cntGood -= c 157 } 158 var ans = 0 159 for (p in 0 until k) 160 qs[p].forEach { addToSeg(it) } 161 for (p in 0..k) { 162 qs[p + k].forEach { addToSeg(it) } 163 if (cntDistinct == n) 164 ans = maxOf(ans, cntGood) 165 qs[p].forEach { eraseFromSeg(it) } 166 } 167 return n - ans 168 } 169 170 var ans = n 171 for (i in f.indices) { 172 ans = minOf(ans, checkAround(d[i] * f[i])) 173 } 174 println(ans) 175 } 176 } 177 ``` 178 179 [1814E - Chain Chips](/contest/1814/problem/E "Educational Codeforces Round 146 (Rated for Div. 2)") 180 181 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 182 183 **Tutorial** 184 185 Tutorial is loading... 186 187 **Solution (BledDest)** 188 189 ``` 190 #include<bits/stdc++.h> 191 192 using namespace std; 193 194 typedef long long li; 195 196 const li INF = (li)(1e18); 197 const int N = 200043; 198 199 struct data 200 { 201 array<array<long long, 2>, 2> d; 202 data() { 203 for(int i = 0; i < 2; i++) 204 for(int j = 0; j < 2; j++) 205 d[i][j] = INF; 206 }; 207 data(li x) 208 { 209 for(int i = 0; i < 2; i++) 210 for(int j = 0; j < 2; j++) 211 d[i][j] = INF; 212 d[0][0] = 0; 213 d[1][1] = x; 214 }; 215 data(data l, data r) 216 { 217 for(int i = 0; i < 2; i++) 218 for(int j = 0; j < 2; j++) 219 d[i][j] = INF; 220 for(int i = 0; i < 2; i++) 221 for(int j = 0; j < 2; j++) 222 for(int k = 0; k < 2; k++) 223 for(int x = 0; x < 2; x++) 224 { 225 if(j == 0 && k == 0) continue; 226 d[i][x] = min(d[i][x], l.d[i][j] + r.d[k][x]); 227 } 228 }; 229 }; 230 231 data T[4 * N]; 232 li a[N]; 233 234 void recalc(int v) 235 { 236 T[v] = data(T[v * 2 + 1], T[v * 2 + 2]); 237 } 238 239 void build(int v, int l, int r) 240 { 241 if(l == r - 1) T[v] = data(a[l]); 242 else 243 { 244 int m = (l + r) / 2; 245 build(v * 2 + 1, l, m); 246 build(v * 2 + 2, m, r); 247 recalc(v); 248 } 249 } 250 251 void upd(int v, int l, int r, int pos, li val) 252 { 253 if(l == r - 1) 254 { 255 a[l] = val; 256 T[v] = data(a[l]); 257 } 258 else 259 { 260 int m = (l + r) / 2; 261 if(pos < m) 262 upd(v * 2 + 1, l, m, pos, val); 263 else 264 upd(v * 2 + 2, m, r, pos, val); 265 recalc(v); 266 } 267 } 268 269 int main() 270 { 271 int n; 272 scanf("%d", &n); 273 for(int i = 0; i < n - 1; i++) 274 { 275 scanf("%lld", &a[i]); 276 } 277 build(0, 0, n - 1); 278 int q; 279 scanf("%d", &q); 280 for(int i = 0; i < q; i++) 281 { 282 int x; 283 li k; 284 scanf("%d %lld", &x, &k); 285 upd(0, 0, n - 1, x - 1, k); 286 printf("%lld\n", T[0].d[1][1] * 2); 287 } 288 } 289 ``` 290 291 [1814F - Communication Towers](/contest/1814/problem/F "Educational Codeforces Round 146 (Rated for Div. 2)") 292 293 Idea: [Neon](/profile/Neon "Candidate Master Neon") 294 295 **Tutorial** 296 297 Tutorial is loading... 298 299 **Solution (Neon)** 300 301 ``` 302 #include <bits/stdc++.h> 303 304 using namespace std; 305 306 #define sz(a) int((a).size()) 307 308 const int N = 200002; 309 const int V = 50 * N; 310 311 using pt = pair<int, int>; 312 313 int n, m; 314 pt a[N]; 315 vector<pt> t[4 * N]; 316 int p[N], rk[N], vs[N]; 317 int cntV; 318 pt g[V]; 319 bool ans[V]; 320 321 void upd(int v, int l, int r, int L, int R, pt e) { 322 if (L >= R) return; 323 if (l == L && r == R) { 324 t[v].push_back(e); 325 return; 326 } 327 int m = (l + r) / 2; 328 upd(v * 2 + 1, l, m, L, min(m, R), e); 329 upd(v * 2 + 2, m, r, max(m, L), R, e); 330 } 331 332 int k; 333 int* ptr[V]; 334 int val[V]; 335 336 void upd(int &a, int b) { 337 ptr[k] = &a; 338 val[k] = a; 339 k += 1; 340 a = b; 341 } 342 343 int getp(int v) { 344 return p[v] == v ? v : getp(p[v]); 345 } 346 347 void unite(int v, int u) { 348 v = getp(v), u = getp(u); 349 if (v == u) return; 350 if (rk[v] > rk[u]) swap(v, u); 351 upd(p[v], u); 352 g[cntV] = {vs[v], vs[u]}; 353 upd(vs[u], cntV++); 354 if (rk[v] == rk[u]) 355 upd(rk[u], rk[u] + 1); 356 } 357 358 void solve(int v, int l, int r) { 359 int cur = k; 360 for (auto& [v, u] : t[v]) 361 unite(v, u); 362 if (l + 1 == r) { 363 ans[vs[getp(0)]] = 1; 364 } else { 365 int m = (l + r) / 2; 366 solve(v * 2 + 1, l, m); 367 solve(v * 2 + 2, m, r); 368 } 369 while (k > cur) { 370 k -= 1; 371 (*ptr[k]) = val[k]; 372 } 373 } 374 375 int main() { 376 ios::sync_with_stdio(false); cin.tie(0); 377 378 cin >> n >> m; 379 for (int i = 0; i < n; ++i) 380 cin >> a[i].first >> a[i].second; 381 for (int i = 0; i < m; ++i) { 382 int x, y; 383 cin >> x >> y; 384 --x; --y; 385 int L = max(a[x].first, a[y].first); 386 int R = min(a[x].second, a[y].second); 387 upd(0, 0, N, L, R + 1, {x, y}); 388 } 389 390 for (int i = 0; i < n; ++i) { 391 p[i] = i; 392 rk[i] = 1; 393 vs[i] = i; 394 g[i] = {-1, -1}; 395 } 396 397 cntV = n; 398 solve(0, 0, N); 399 400 queue<int> q; 401 for (int i = 0; i < cntV; ++i) if (ans[i]) 402 q.push(i); 403 404 while (!q.empty()) { 405 int v = q.front(); q.pop(); 406 for (int u : {g[v].first, g[v].second}) { 407 if (u != -1 && !ans[u]) { 408 ans[u] = true; 409 q.push(u); 410 } 411 } 412 } 413 414 for (int i = 0; i < n; ++i) if (ans[i]) 415 cout << i + 1 << ' '; 416 } 417 ```