2004.md (7215B)
1 Source: https://codeforces.com/blog/entry/132790 2 3 [2004A - Closest Point](/contest/2004/problem/A "Educational Codeforces Round 169 (Rated for Div. 2)") 4 5 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 6 7 **Tutorial** 8 9 Tutorial is loading... 10 11 **Solution (BledDest)** 12 13 ``` 14 t = int(input()) 15 for i in range(t): 16 n = int(input()) 17 x = list(map(int, input().split())) 18 if n > 2 or x[0] + 1 == x[-1]: 19 print('NO') 20 else: 21 print('YES') 22 ``` 23 24 [2004B - Game with Doors](/contest/2004/problem/B "Educational Codeforces Round 169 (Rated for Div. 2)") 25 26 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 27 28 **Tutorial** 29 30 Tutorial is loading... 31 32 **Solution (Neon)** 33 34 ``` 35 #include <bits/stdc++.h> 36 37 using namespace std; 38 39 int main() { 40 int t; 41 cin >> t; 42 while (t--) { 43 int l, r, L, R; 44 cin >> l >> r >> L >> R; 45 int inter = min(r, R) - max(l, L) + 1; 46 int ans = inter - 1; 47 if (inter <= 0) { 48 ans = 1; 49 } else { 50 ans += (l != L); 51 ans += (r != R); 52 } 53 cout << ans << '\n'; 54 } 55 } 56 ``` 57 58 [2004C - Splitting Items](/contest/2004/problem/C "Educational Codeforces Round 169 (Rated for Div. 2)") 59 60 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 61 62 **Tutorial** 63 64 Tutorial is loading... 65 66 **Solution (adedalic)** 67 68 ``` 69 fun main() { 70 repeat(readln().toInt()) { 71 val (n, k) = readln().split(" ").map { it.toInt() } 72 val a = readln().split(" ").map { it.toInt() }.sortedDescending().toIntArray() 73 74 var score = 0L 75 var rem = k 76 for (i in a.indices) { 77 if (i % 2 == 0) { 78 score += a[i] 79 } 80 else { 81 val needed = minOf(rem, a[i - 1] - a[i]) 82 a[i] += needed 83 rem -= needed 84 score -= a[i] 85 } 86 } 87 println(score) 88 } 89 } 90 ``` 91 92 [2004D - Colored Portals](/contest/2004/problem/D "Educational Codeforces Round 169 (Rated for Div. 2)") 93 94 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 95 96 **Tutorial** 97 98 Tutorial is loading... 99 100 **Solution (Neon)** 101 102 ``` 103 #include <bits/stdc++.h> 104 105 using namespace std; 106 107 const int INF = 1e9; 108 const string vars[] = {"BG", "BR", "BY", "GR", "GY", "RY"}; 109 110 int main() { 111 ios::sync_with_stdio(false); cin.tie(0); 112 int t; 113 cin >> t; 114 while (t--) { 115 int n, q; 116 cin >> n >> q; 117 vector<int> a(n); 118 for (int i = 0; i < n; ++i) { 119 char s[5]; 120 cin >> s; 121 a[i] = find(vars, vars + 6, s) - vars; 122 } 123 vector<vector<int>> lf(n), rg(n); 124 for (int o = 0; o < 2; ++o) { 125 vector<int> last(6, -INF); 126 for (int i = 0; i < n; ++i) { 127 last[a[i]] = (o ? n - i - 1 : i); 128 (o ? rg[n - i - 1] : lf[i]) = last; 129 } 130 reverse(a.begin(), a.end()); 131 } 132 while (q--) { 133 int x, y; 134 cin >> x >> y; 135 --x; --y; 136 int ans = INF; 137 for (int j = 0; j < 6; ++j) { 138 if (a[x] + j != 5 && j + a[y] != 5) { 139 ans = min(ans, abs(x - lf[x][j]) + abs(lf[x][j] - y)); 140 ans = min(ans, abs(x - rg[x][j]) + abs(rg[x][j] - y)); 141 } 142 } 143 if (ans > INF / 2) ans = -1; 144 cout << ans << '\n'; 145 } 146 } 147 } 148 ``` 149 150 [2004E - Not a Nim Problem](/contest/2004/problem/E "Educational Codeforces Round 169 (Rated for Div. 2)") 151 152 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 153 154 **Tutorial** 155 156 Tutorial is loading... 157 158 **Solution (BledDest)** 159 160 ``` 161 #include<bits/stdc++.h> 162 163 using namespace std; 164 165 const int MOD = 998244353; 166 167 const int N = int(1e7) + 43; 168 169 int lp[N + 1]; 170 vector<int> pr; 171 int idx[N + 1]; 172 173 void precalc() 174 { 175 for (int i = 2; i <= N; i++) 176 { 177 if (lp[i] == 0) 178 { 179 lp[i] = i; 180 pr.push_back(i); 181 } 182 for (int j = 0; j < pr.size() && pr[j] <= lp[i] && i * 1ll * pr[j] <= N; ++j) 183 lp[i * pr[j]] = pr[j]; 184 } 185 for (int i = 0; i < pr.size(); i++) 186 idx[pr[i]] = i + 1; 187 } 188 189 int get(int x) 190 { 191 if(x == 1) return 1; 192 x = lp[x]; 193 if(x == 2) 194 return 0; 195 else return idx[x]; 196 } 197 198 void solve() 199 { 200 int n; 201 scanf("%d", &n); 202 int res = 0; 203 for(int i = 0; i < n; i++) 204 { 205 int x; 206 scanf("%d", &x); 207 res ^= get(x); 208 } 209 if(res) puts("Alice"); 210 else puts("Bob"); 211 } 212 213 int main() 214 { 215 precalc(); 216 int t; 217 scanf("%d", &t); 218 for(int i = 0; i < t; i++) solve(); 219 } 220 ``` 221 222 [2004F - Make a Palindrome](/contest/2004/problem/F "Educational Codeforces Round 169 (Rated for Div. 2)") 223 224 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 225 226 **Tutorial** 227 228 Tutorial is loading... 229 230 **Solution (Neon)** 231 232 ``` 233 #include <bits/stdc++.h> 234 235 using namespace std; 236 237 int main() { 238 int t; 239 cin >> t; 240 while (t--) { 241 int n; 242 cin >> n; 243 vector<int> a(n); 244 for (auto& x : a) cin >> x; 245 vector<int> p(n + 1); 246 for (int i = 0; i < n; ++i) p[i + 1] = p[i] + a[i]; 247 map<int, int> cnt; 248 long long ans = 0; 249 for (int len = 0; len <= n; ++len) { 250 for (int i = 0; i <= n - len; ++i) { 251 int s = p[i] + p[i + len]; 252 ans += len; 253 ans -= 2 * cnt[s]; 254 ans -= (s % 2 == 1 || !binary_search(p.begin(), p.end(), s / 2)); 255 cnt[s] += 1; 256 } 257 } 258 cout << ans << '\n'; 259 } 260 } 261 ``` 262 263 [2004G - Substring Compression](/contest/2004/problem/G "Educational Codeforces Round 169 (Rated for Div. 2)") 264 265 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 266 267 **Tutorial** 268 269 Tutorial is loading... 270 271 **Solution (awoo)** 272 273 ``` 274 #include <bits/stdc++.h> 275 276 #define forn(i, n) for (int i = 0; i < int(n); i++) 277 278 using namespace std; 279 280 const int D = 10; 281 const int INF = 1e9; 282 283 typedef array<array<int, D>, D> mat; 284 285 mat mul(const mat &a, const mat &b, bool fl){ 286 mat c; 287 forn(i, D) forn(j, D) c[i][j] = INF; 288 if (fl){ 289 forn(i, D) forn(j, D){ 290 c[j][i] = min(c[j][i], min(a[j][0] + b[0][i], a[j][i] + b[i][i])); 291 c[j][0] = min(c[j][0], a[j][i] + b[i][0]); 292 } 293 } 294 else{ 295 forn(i, D) forn(j, D){ 296 c[i][j] = min(c[i][j], min(a[i][0] + b[0][j], a[i][i] + b[i][j])); 297 c[0][j] = min(c[0][j], a[0][i] + b[i][j]); 298 } 299 } 300 return c; 301 } 302 303 struct minqueue{ 304 vector<pair<mat, mat>> st1, st2; 305 306 void push(const mat &a){ 307 if (!st1.empty()) 308 st1.push_back({a, mul(st1.back().second, a, true)}); 309 else 310 st1.push_back({a, a}); 311 } 312 313 void pop(){ 314 if (st2.empty()){ 315 st2 = st1; 316 reverse(st2.begin(), st2.end()); 317 st1.clear(); 318 assert(!st2.empty()); 319 st2[0].second = st2[0].first; 320 forn(i, int(st2.size()) - 1) 321 st2[i + 1].second = mul(st2[i + 1].first, st2[i].second, false); 322 } 323 st2.pop_back(); 324 } 325 326 int get(){ 327 if (st1.empty()) return st2.back().second[0][0]; 328 if (st2.empty()) return st1.back().second[0][0]; 329 int ans = INF; 330 forn(i, D) ans = min(ans, st2.back().second[0][i] + st1.back().second[i][0]); 331 return ans; 332 } 333 }; 334 335 mat tran[D]; 336 337 void init(int d){ 338 forn(i, D) forn(j, D) tran[d][i][j] = INF; 339 for (int i = 1; i <= 9; ++i){ 340 tran[d][i][i] = i; 341 tran[d][i][0] = i; 342 } 343 tran[d][0][d] = 0; 344 } 345 346 int main() { 347 cin.tie(0); 348 ios::sync_with_stdio(false); 349 for (int i = 1; i <= 9; ++i) init(i); 350 int n, k; 351 cin >> n >> k; 352 string s; 353 cin >> s; 354 minqueue q; 355 forn(i, n){ 356 q.push(tran[s[i] - '0']); 357 if (i - k >= 0) q.pop(); 358 if (i - k >= -1) cout << q.get() << ' '; 359 } 360 cout << '\n'; 361 return 0; 362 } 363 ```