codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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 ```