1196.md (7052B)
1 Source: https://codeforces.com/blog/entry/68655 2 3 [1196A - Три кучки с конфетами](/contest/1196/problem/A "Codeforces Round 575 (Div. 3)") 4 5 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Штаб, MikeMirzayanov") 6 7 **Tutorial** 8 9 Tutorial is loading... 10 11 **Solution** 12 13 ``` 14 #include <bits/stdc++.h> 15 16 using namespace std; 17 18 int main() { 19 #ifdef _DEBUG 20 freopen("input.txt", "r", stdin); 21 // freopen("output.txt", "w", stdout); 22 #endif 23 24 int q; 25 cin >> q; 26 for (int i = 0; i < q; ++i) { 27 long long a, b, c; 28 cin >> a >> b >> c; 29 cout << (a + b + c) / 2 << endl; 30 } 31 32 return 0; 33 } 34 ``` 35 36 [1196B - Отрезки с нечетной суммой](/contest/1196/problem/B "Codeforces Round 575 (Div. 3)") 37 38 Idea: [vovuh](/profile/vovuh "Кандидат в мастера vovuh") 39 40 **Tutorial** 41 42 Tutorial is loading... 43 44 **Solution** 45 46 ``` 47 #include <bits/stdc++.h> 48 49 using namespace std; 50 51 int main() { 52 #ifdef _DEBUG 53 freopen("input.txt", "r", stdin); 54 // freopen("output.txt", "w", stdout); 55 #endif 56 57 int q; 58 cin >> q; 59 for (int i = 0; i < q; ++i) { 60 int n, k; 61 cin >> n >> k; 62 vector<int> a(n); 63 int cntodd = 0; 64 for (int j = 0; j < n; ++j) { 65 cin >> a[j]; 66 cntodd += a[j] % 2; 67 } 68 if (cntodd < k || cntodd % 2 != k % 2) { 69 cout << "NO" << endl; 70 continue; 71 } 72 cout << "YES" << endl; 73 for (int j = 0; j < n; ++j) { 74 if (k == 1) break; 75 if (a[j] % 2 == 1) { 76 cout << j + 1 << " "; 77 --k; 78 } 79 } 80 cout << n << endl; 81 } 82 return 0; 83 } 84 ``` 85 86 [1196C - Побег роботов](/contest/1196/problem/C "Codeforces Round 575 (Div. 3)") 87 88 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Штаб, MikeMirzayanov") and [vovuh](/profile/vovuh "Кандидат в мастера vovuh") 89 90 **Tutorial** 91 92 Tutorial is loading... 93 94 **Solution** 95 96 ``` 97 #include <algorithm> 98 #include <iostream> 99 100 using namespace std; 101 102 const int MAXC = 1e5; 103 104 int main() { 105 int q; 106 cin >> q; 107 while (q--) { 108 int n; 109 cin >> n; 110 int mnx = -MAXC, mxx = MAXC; 111 int mny = -MAXC, mxy = MAXC; 112 while (n--) { 113 int x, y, f1, f2, f3, f4; 114 cin >> x >> y >> f1 >> f2 >> f3 >> f4; 115 if (!f1) mnx = max(mnx, x); 116 if (!f2) mxy = min(mxy, y); 117 if (!f3) mxx = min(mxx, x); 118 if (!f4) mny = max(mny, y); 119 } 120 if (mnx <= mxx && mny <= mxy) 121 cout << "1 " << mnx << " " << mny << "\n"; 122 else 123 cout << "0\n"; 124 } 125 126 return 0; 127 } 128 ``` 129 130 [1196D1 - Подстрока RGB (простая версия)](/contest/1196/problem/D1 "Codeforces Round 575 (Div. 3)") 131 132 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Штаб, MikeMirzayanov") 133 134 **Tutorial** 135 136 Tutorial is loading... 137 138 **Solution** 139 140 ``` 141 #include <bits/stdc++.h> 142 143 using namespace std; 144 145 int main() { 146 #ifdef _DEBUG 147 freopen("input.txt", "r", stdin); 148 // freopen("output.txt", "w", stdout); 149 #endif 150 151 const string t = "RGB"; 152 153 int q; 154 cin >> q; 155 for (int i = 0; i < q; ++i) { 156 int n, k; 157 string s; 158 cin >> n >> k >> s; 159 int ans = 1e9; 160 for (int j = 0; j < n - k + 1; ++j) { 161 for (int offset = 0; offset < 3; ++offset) { 162 int cur = 0; 163 for (int pos = 0; pos < k; ++pos) { 164 if (s[j + pos] != t[(pos + offset) % 3]) { 165 ++cur; 166 } 167 } 168 ans = min(ans, cur); 169 } 170 } 171 cout << ans << endl; 172 } 173 174 return 0; 175 } 176 ``` 177 178 [1196D2 - Подстрока RGB (сложная версия)](/contest/1196/problem/D2 "Codeforces Round 575 (Div. 3)") 179 180 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Штаб, MikeMirzayanov") 181 182 **Tutorial** 183 184 Tutorial is loading... 185 186 **Solution** 187 188 ``` 189 #include <bits/stdc++.h> 190 191 using namespace std; 192 193 int main() { 194 #ifdef _DEBUG 195 freopen("input.txt", "r", stdin); 196 // freopen("output.txt", "w", stdout); 197 #endif 198 199 const string t = "RGB"; 200 201 int q; 202 cin >> q; 203 for (int i = 0; i < q; ++i) { 204 int n, k; 205 string s; 206 cin >> n >> k >> s; 207 int ans = 1e9; 208 for (int offset = 0; offset < 3; ++offset) { 209 vector<int> res(n); 210 int cur = 0; 211 for (int j = 0; j < n; ++j) { 212 res[j] = (s[j] != t[(j + offset) % 3]); 213 cur += res[j]; 214 if (j >= k) cur -= res[j - k]; 215 if (j >= k - 1) ans = min(ans, cur); 216 } 217 } 218 cout << ans << endl; 219 } 220 221 return 0; 222 } 223 ``` 224 225 [1196E - Компонента связности шахматной доски](/contest/1196/problem/E "Codeforces Round 575 (Div. 3)") 226 227 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Штаб, MikeMirzayanov") 228 229 **Tutorial** 230 231 Tutorial is loading... 232 233 **Solution** 234 235 ``` 236 #include <bits/stdc++.h> 237 238 using namespace std; 239 240 int main() { 241 #ifdef _DEBUG 242 freopen("input.txt", "r", stdin); 243 // freopen("output.txt", "w", stdout); 244 #endif 245 246 int q; 247 cin >> q; 248 for (int i = 0; i < q; ++i) { 249 int b, w; 250 cin >> b >> w; 251 vector<pair<int, int>> res; 252 bool need = b < w; 253 if (need) swap(w, b); 254 int x = 2, y = 2; 255 while (w > 0) { 256 if ((x + y) % 2 == 1) { 257 res.push_back({x, y}); 258 --b; 259 } else { 260 res.push_back({x, y}); 261 --w; 262 } 263 ++y; 264 } 265 int cx = 1, cy = 2; 266 while (b > 0 && cy <= y) { 267 res.push_back({cx, cy}); 268 --b; 269 cy += 2; 270 } 271 cx = 3, cy = 2; 272 while (b > 0 && cy <= y) { 273 res.push_back({cx, cy}); 274 --b; 275 cy += 2; 276 } 277 if (b > 0) { 278 res.push_back({2, 1}); 279 --b; 280 } 281 if (b > 0) { 282 res.push_back({2, y}); 283 --b; 284 } 285 if (b > 0) { 286 cout << "NO" << endl; 287 } else { 288 assert(w == 0); 289 cout << "YES" << endl; 290 for (auto it : res) cout << it.first << " " << it.second + need << endl; 291 } 292 } 293 294 return 0; 295 } 296 ``` 297 298 [1196F - К-й путь](/contest/1196/problem/F "Codeforces Round 575 (Div. 3)") 299 300 **Tutorial** 301 302 Tutorial is loading... 303 304 **Solution** 305 306 ``` 307 #include <bits/stdc++.h> 308 309 using namespace std; 310 311 const long long INF64 = 1e18; 312 313 int main() { 314 #ifdef _DEBUG 315 freopen("input.txt", "r", stdin); 316 // freopen("output.txt", "w", stdout); 317 #endif 318 319 int n, m, k; 320 scanf("%d %d %d", &n, &m, &k); 321 vector<pair<int, pair<int, int>>> e; 322 for (int i = 0; i < m; ++i) { 323 int x, y, w; 324 scanf("%d %d %d", &x, &y, &w); 325 --x, --y; 326 e.push_back(make_pair(w, make_pair(x, y))); 327 } 328 sort(e.begin(), e.end()); 329 330 vector<int> vert; 331 for (int i = 0; i < min(m, k); ++i) { 332 vert.push_back(e[i].second.first); 333 vert.push_back(e[i].second.second); 334 } 335 sort(vert.begin(), vert.end()); 336 vert.resize(unique(vert.begin(), vert.end()) - vert.begin()); 337 int cntv = vert.size(); 338 vector<vector<long long>> dist(cntv, vector<long long>(cntv, INF64)); 339 for (int i = 0; i < cntv; ++i) dist[i][i] = 0; 340 341 for (int i = 0; i < min(m, k); ++i) { 342 int x = lower_bound(vert.begin(), vert.end(), e[i].second.first) - vert.begin(); 343 int y = lower_bound(vert.begin(), vert.end(), e[i].second.second) - vert.begin(); 344 dist[x][y] = dist[y][x] = min(dist[x][y], (long long)e[i].first); 345 } 346 347 for (int z = 0; z < cntv; ++z) { 348 for (int x = 0; x < cntv; ++x) { 349 for (int y = 0; y < cntv; ++y) { 350 dist[x][y] = min(dist[x][y], dist[x][z] + dist[z][y]); 351 } 352 } 353 } 354 355 vector<long long> res; 356 for (int i = 0; i < cntv; ++i) { 357 for (int j = 0; j < i; ++j) { 358 res.push_back(dist[i][j]); 359 } 360 } 361 362 sort(res.begin(), res.end()); 363 cout << res[k - 1] << endl; 364 365 return 0; 366 } 367 ```