1238.md (7073B)
1 Source: https://codeforces.com/blog/entry/70450 2 3 [1238A - Prime Subtraction](/contest/1238/problem/A "Educational Codeforces Round 74 (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 16 for i in range(t): 17 x, y = map(int, input().split()) 18 if(x - y > 1): 19 print('YES') 20 else: 21 print('NO') 22 ``` 23 24 [1238B - Kill `Em All](/contest/1238/problem/B "Educational Codeforces Round 74 (Rated for Div. 2)") 25 26 Idea: [Neon](/profile/Neon "Candidate Master Neon") 27 28 **Tutorial** 29 30 Tutorial is loading... 31 32 **Solution (Ne0n25)** 33 34 ``` 35 #include <bits/stdc++.h> 36 37 using namespace std; 38 39 #define forn(i, n) for (int i = 0; i < int(n); i++) 40 41 const int N = 100 * 1000 + 13; 42 43 int n, r; 44 int a[N]; 45 46 void solve() { 47 scanf("%d%d", &n, &r); 48 forn(i, n) scanf("%d", &a[i]); 49 50 sort(a, a + n); 51 n = unique(a, a + n) - a; 52 53 int ans = 0; 54 for (int i = n - 1; i >= 0; i--) 55 ans += (a[i] - ans * r > 0); 56 57 printf("%d\n", ans); 58 } 59 60 int main() { 61 int q; 62 scanf("%d", &q); 63 forn(i, q) solve(); 64 } 65 ``` 66 67 [1238C - Standard Free2play](/contest/1238/problem/C "Educational Codeforces Round 74 (Rated for Div. 2)") 68 69 Idea: [adedalic](/profile/adedalic "International Master adedalic") 70 71 **Tutorial** 72 73 Tutorial is loading... 74 75 **Solution (adedalic)** 76 77 ``` 78 #include<bits/stdc++.h> 79 80 using namespace std; 81 82 #define fore(i, l, r) for(int i = int(l); i < int(r); i++) 83 #define sz(a) int((a).size()) 84 85 #define x first 86 #define y second 87 88 const int INF = int(1e9); 89 90 int h, n; 91 vector<int> p; 92 93 inline bool read() { 94 if(!(cin >> h >> n)) 95 return false; 96 p.resize(n); 97 fore(i, 0, n) 98 cin >> p[i]; 99 return true; 100 } 101 102 inline void solve() { 103 int ans = 0; 104 105 int lf = 0; 106 fore(i, 0, n) { 107 if (i > 0 && p[i - 1] > p[i] + 1) { 108 if (lf > 0) 109 ans += (i - lf) & 1; 110 else 111 ans += 1 - ((i - lf) & 1); 112 lf = i; 113 } 114 } 115 if (p[n - 1] > 1) { 116 if (lf != 0) 117 ans += (n - lf) & 1; 118 else 119 ans += 1 - ((n - lf) & 1); 120 } 121 122 cout << ans << endl; 123 } 124 125 int main() { 126 #ifdef _DEBUG 127 freopen("input.txt", "r", stdin); 128 #endif 129 ios_base::sync_with_stdio(false); 130 cin.tie(0), cout.tie(0); 131 cout << fixed << setprecision(15); 132 133 int tc; cin >> tc; 134 while(tc--) { 135 read(); 136 solve(); 137 } 138 return 0; 139 } 140 ``` 141 142 [1238D - AB-string](/contest/1238/problem/D "Educational Codeforces Round 74 (Rated for Div. 2)") 143 144 Idea: [Roms](/profile/Roms "Master Roms") 145 146 **Tutorial** 147 148 Tutorial is loading... 149 150 **Solution (Roms)** 151 152 ``` 153 n = int(input()) 154 s = input() 155 res = n * (n - 1) // 2 156 157 for x in range(2): 158 cur = 1 159 for i in range(1, n): 160 if s[i] == s[i - 1]: 161 cur += 1 162 else: 163 res -= cur - x 164 cur = 1 165 s = s[::-1] 166 167 print(res) 168 ``` 169 170 [1238E - Keyboard Purchase](/contest/1238/problem/E "Educational Codeforces Round 74 (Rated for Div. 2)") 171 172 Idea: [Roms](/profile/Roms "Master Roms") 173 174 **Tutorial** 175 176 Tutorial is loading... 177 178 **Solution (Roms)** 179 180 ``` 181 #include <bits/stdc++.h> 182 183 using namespace std; 184 185 void upd(int &a, int b){ 186 a = min(a, b); 187 } 188 189 const int N = 20; 190 const int M = (1 << N) + 55; 191 const int INF = int(1e9) + 100; 192 193 int a, n; 194 string s; 195 int cnt[N][N]; 196 int d[M][N]; 197 int dp[M]; 198 int cntBit[M]; 199 int minBit[M]; 200 201 int main() { 202 cin >> n >> a >> s; 203 204 int B = (1 << a) - 1; 205 for(int i = 1; i < s.size(); ++i){ 206 ++cnt[s[i] - 'a'][s[i - 1] - 'a']; 207 ++cnt[s[i - 1] - 'a'][s[i] - 'a']; 208 } 209 for(int i = 0; i < M; ++i) 210 dp[i] = INF; 211 dp[0] = 0; 212 for(int msk = 1; msk < M; ++msk){ 213 cntBit[msk] = 1 + cntBit[msk & (msk - 1)]; 214 for(int i = 0; i < N; ++i) if((msk >> i) & 1){ 215 minBit[msk] = i; 216 break; 217 } 218 } 219 for(int msk = 1; msk < M; ++msk) 220 for(int i = 0; i < a; ++i){ 221 int b = minBit[msk]; 222 d[msk][i] = d[msk ^ (1 << b)][i] + cnt[i][b]; 223 } 224 225 for(int msk = 0; msk < (1 << a); ++msk){ 226 for(int i = 0; i < a; ++i){ 227 if((msk >> i) & 1) continue; 228 //i -> x 229 int pos = cntBit[msk]; 230 int nmsk = msk | (1 << i); 231 upd(dp[nmsk], dp[msk] + pos * (d[msk][i] - d[B ^ nmsk][i])); 232 } 233 } 234 235 cout << dp[B] << endl; 236 return 0; 237 } 238 ``` 239 240 [1238F - The Maximum Subtree](/contest/1238/problem/F "Educational Codeforces Round 74 (Rated for Div. 2)") 241 242 Idea: [Roms](/profile/Roms "Master Roms") 243 244 **Tutorial** 245 246 Tutorial is loading... 247 248 **Solution (Roms)** 249 250 ``` 251 #include <bits/stdc++.h> 252 253 using namespace std; 254 255 const int N = int(3e5) + 99; 256 257 int n; 258 vector <int> g[N]; 259 int d[N]; 260 int dp[N][2]; 261 262 void dfs(int v, int p){ 263 vector <int> d1; 264 dp[v][1] = d[v] - 1; 265 for(auto to : g[v]){ 266 if(to == p) continue; 267 dfs(to, v); 268 dp[v][0] = max(dp[v][0], dp[to][0]); 269 if(g[to].size() > 1){ 270 d1.push_back(dp[to][1]); 271 dp[v][1] = max(dp[v][1], d[v] + dp[to][1] - 1); 272 } 273 } 274 275 sort(d1.rbegin(), d1.rend()); 276 int x = d[v] + 1; 277 for(int i = 0; i < 2; ++i) 278 if(i < d1.size()) 279 x += d1[i]; 280 dp[v][0] = max(dp[v][0], x); 281 } 282 283 int main() { 284 int q; 285 scanf("%d", &q); 286 for(int qc = 0; qc < q; ++qc){ 287 scanf("%d", &n); 288 for(int i = 0; i < n; ++i){ 289 g[i].clear(); 290 d[i] = 0; 291 dp[i][0] = dp[i][1] = 0; 292 } 293 for(int i = 0; i < n - 1; ++i){ 294 int u, v; 295 scanf("%d %d", &u, &v); 296 --u, --v; 297 g[u].push_back(v), g[v].push_back(u); 298 } 299 300 if(n <= 2){ 301 printf("%d\n", n); 302 continue; 303 } 304 305 for(int v = 0; v < n; ++v){ 306 //d[v] = 1; 307 //for(auto to : g[v]) 308 // d[v] += g[to].size() == 1; 309 d[v] = g[v].size(); 310 } 311 312 int r = -1; 313 for(int v = 0; v < n; ++v) 314 if(g[v].size() != 1) 315 r = v; 316 317 dfs(r, r); 318 printf("%d\n", dp[r][0]); 319 } 320 return 0; 321 } 322 ``` 323 324 [1238G - Adilbek and the Watering System](/contest/1238/problem/G "Educational Codeforces Round 74 (Rated for Div. 2)") 325 326 Idea: [Neon](/profile/Neon "Candidate Master Neon") 327 328 **Tutorial** 329 330 Tutorial is loading... 331 332 **Solution (Ne0n25)** 333 334 ``` 335 #include <bits/stdc++.h> 336 337 using namespace std; 338 339 #define x first 340 #define y second 341 #define mp make_pair 342 #define forn(i, n) for (int i = 0; i < int(n); ++i) 343 344 typedef long long li; 345 typedef pair<int, int> pt; 346 347 const int N = 500 * 1000 + 13; 348 349 int n, m, c, c0; 350 pair<int, pt> a[N]; 351 352 li solve() { 353 scanf("%d%d%d%d", &n, &m, &c, &c0); 354 forn(i, n) scanf("%d%d%d", &a[i].x, &a[i].y.x, &a[i].y.y); 355 a[n++] = mp(m, mp(0, 0)); 356 sort(a, a + n); 357 358 int sum = c0; 359 map<int, int> q; 360 q[0] = c0; 361 362 li ans = 0; 363 forn(i, n) { 364 int x = a[i].x; 365 int cnt = a[i].y.x; 366 int cost = a[i].y.y; 367 368 int dist = x - (i ? a[i - 1].x : 0); 369 while (!q.empty() && dist > 0) { 370 int can = min(q.begin()->y, dist); 371 ans += q.begin()->x * 1ll * can; 372 sum -= can; 373 dist -= can; 374 q.begin()->y -= can; 375 if (q.begin()->y == 0) q.erase(q.begin()); 376 } 377 378 if (dist > 0) 379 return -1; 380 381 int add = min(c - sum, cnt); 382 sum += add; 383 384 while (add < cnt && !q.empty() && q.rbegin()->x > cost) { 385 if (cnt - add >= q.rbegin()->y) { 386 add += q.rbegin()->y; 387 q.erase(--q.end()); 388 } else { 389 q.rbegin()->y -= cnt - add; 390 add = cnt; 391 } 392 } 393 394 q[cost] += add; 395 } 396 397 return ans; 398 } 399 400 int main() { 401 int q; 402 scanf("%d", &q); 403 forn(i, q) printf("%lld\n", solve()); 404 } 405 ```