codeforces-scrape

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

1433.md (6521B)


      1 Source: https://codeforces.com/blog/entry/83903
      2 
      3 I'm really sorry about issues with problems E and F. Can't say anything more because I don't want to justify my mistakes.
      4 
      5 [1433A - Boring Apartments](/contest/1433/problem/A "Codeforces Round 677 (Div. 3)")
      6 
      7 Idea: [vovuh](/profile/vovuh "Master vovuh")
      8 
      9 **Tutorial**
     10 
     11 Tutorial is loading...
     12 
     13 **Solution**
     14 
     15 ```
     16 #include <bits/stdc++.h>
     17 
     18 using namespace std;
     19 
     20 int main() {
     21 #ifdef _DEBUG
     22 	freopen("input.txt", "r", stdin);
     23 //	freopen("output.txt", "w", stdout);
     24 #endif
     25 	
     26 	int t;
     27 	cin >> t;
     28 	while (t--) {
     29 		string x;
     30 		cin >> x;
     31 		int dig = x[0] - '0' - 1;
     32 		int len = x.size();
     33 		cout << dig * 10 + len * (len + 1) / 2 << endl;
     34 	}
     35 	
     36 	return 0;
     37 }
     38 ```
     39 
     40 [1433B - Yet Another Bookshelf](/contest/1433/problem/B "Codeforces Round 677 (Div. 3)")
     41 
     42 Idea: [vovuh](/profile/vovuh "Master vovuh")
     43 
     44 **Tutorial**
     45 
     46 Tutorial is loading...
     47 
     48 **Solution**
     49 
     50 ```
     51 #include <bits/stdc++.h>
     52 
     53 using namespace std;
     54 
     55 int main() {
     56 #ifdef _DEBUG
     57 	freopen("input.txt", "r", stdin);
     58 //	freopen("output.txt", "w", stdout);
     59 #endif
     60 	
     61 	int t;
     62 	cin >> t;
     63 	while (t--) {
     64 		int n;
     65 		cin >> n;
     66 		vector<int> a(n);
     67 		for (auto &it : a) cin >> it;
     68 		while (a.back() == 0) a.pop_back();
     69 		reverse(a.begin(), a.end());
     70 		while (a.back() == 0) a.pop_back();
     71 		cout << count(a.begin(), a.end(), 0) << endl;
     72 	}
     73 	
     74 	return 0;
     75 }
     76 ```
     77 
     78 [1433C - Dominant Piranha](/contest/1433/problem/C "Codeforces Round 677 (Div. 3)")
     79 
     80 Idea: [vovuh](/profile/vovuh "Master vovuh")
     81 
     82 **Tutorial**
     83 
     84 Tutorial is loading...
     85 
     86 **Solution**
     87 
     88 ```
     89 #include <bits/stdc++.h>
     90 
     91 using namespace std;
     92 
     93 int main() {
     94 #ifdef _DEBUG
     95 	freopen("input.txt", "r", stdin);
     96 //	freopen("output.txt", "w", stdout);
     97 #endif
     98 	
     99 	int t;
    100 	cin >> t;
    101 	while (t--) {
    102 		int n;
    103 		cin >> n;
    104 		vector<int> a(n);
    105 		int mx = 0;
    106 		for (auto &it : a) {
    107 			cin >> it;
    108 			mx = max(mx, it);
    109 		}
    110 		int idx = -1;
    111 		for (int i = 0; i < n; ++i) {
    112 			if (a[i] != mx) continue;
    113 			if (i > 0 && a[i - 1] != mx) idx = i + 1;
    114 			if (i < n - 1 && a[i + 1] != mx) idx = i + 1;
    115 		}
    116 		cout << idx << endl;
    117 	}
    118 	
    119 	return 0;
    120 }
    121 ```
    122 
    123 [1433D - Districts Connection](/contest/1433/problem/D "Codeforces Round 677 (Div. 3)")
    124 
    125 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
    126 
    127 **Tutorial**
    128 
    129 Tutorial is loading...
    130 
    131 **Solution**
    132 
    133 ```
    134 #include <bits/stdc++.h>
    135 
    136 using namespace std;
    137 
    138 int main() {
    139 #ifdef _DEBUG
    140 	freopen("input.txt", "r", stdin);
    141 //	freopen("output.txt", "w", stdout);
    142 #endif
    143 	
    144 	int t;
    145 	cin >> t;
    146 	while (t--) {
    147 		int n;
    148 		cin >> n;
    149 		vector<int> a(n);
    150 		for (auto &it : a) cin >> it;
    151 		vector<pair<int, int>> res;
    152 		int idx = -1;
    153 		for (int i = 1; i < n; ++i) {
    154 			if (a[i] != a[0]) {
    155 				idx = i;
    156 				res.push_back({1, i + 1});
    157 			}
    158 		}
    159 		if (idx == -1) {
    160 			cout << "NO" << endl;
    161 			continue;
    162 		}
    163 		for (int i = 1; i < n; ++i) {
    164 			if (a[i] == a[0]) {
    165 				res.push_back({idx + 1, i + 1});
    166 			}
    167 		}
    168 		cout << "YES" << endl;
    169 		for (auto [x, y] : res) cout << x << " " << y << endl;
    170 	}
    171 	
    172 	return 0;
    173 }
    174 ```
    175 
    176 [1433E - Two Round Dances](/contest/1433/problem/E "Codeforces Round 677 (Div. 3)")
    177 
    178 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
    179 
    180 **Tutorial**
    181 
    182 Tutorial is loading...
    183 
    184 **Solution**
    185 
    186 ```
    187 #include <bits/stdc++.h>
    188 
    189 using namespace std;
    190 
    191 const int N = 21;
    192 
    193 long long f[N];
    194 
    195 int main() {
    196 #ifdef _DEBUG
    197 	freopen("input.txt", "r", stdin);
    198 //	freopen("output.txt", "w", stdout);
    199 #endif
    200 	
    201 	int n;
    202 	cin >> n;
    203 	f[0] = 1;
    204 	for (int i = 1; i < N; ++i) {
    205 		f[i] = f[i - 1] * i;
    206 	}
    207 	
    208 	long long ans = f[n] / f[n / 2] / f[n / 2];
    209 	ans = ans * f[n / 2 - 1];
    210 	ans = ans * f[n / 2 - 1];
    211 	ans /= 2;
    212 	
    213 	cout << ans << endl;
    214 	
    215 	return 0;
    216 }
    217 ```
    218 
    219 [1433F - Zero Remainder Sum](/contest/1433/problem/F "Codeforces Round 677 (Div. 3)")
    220 
    221 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
    222 
    223 **Tutorial**
    224 
    225 Tutorial is loading...
    226 
    227 **Solution**
    228 
    229 ```
    230 #include <bits/stdc++.h>
    231 
    232 using namespace std;
    233 
    234 #define forn(i, n) for (int i = 0; i < int(n); ++i)
    235 
    236 const int N = 75;
    237 const int INF = 1e9;
    238 
    239 int a[N][N];
    240 int dp[N][N][N][N];
    241 
    242 int main() {
    243 #ifdef _DEBUG
    244 	freopen("input.txt", "r", stdin);
    245 //	freopen("output.txt", "w", stdout);
    246 #endif
    247 	
    248 	int n, m, k;
    249 	cin >> n >> m >> k;
    250 	forn(i, n) forn(j, m) {
    251 		cin >> a[i][j];
    252 	}
    253 	
    254 	forn(i, N) forn(j, N) forn(cnt, N) forn(rem, N) dp[i][j][cnt][rem] = -INF;
    255 	dp[0][0][0][0] = 0;
    256 	forn(i, n) forn(j, m) forn(cnt, m / 2 + 1) forn(rem, k) {
    257 		if (dp[i][j][cnt][rem] == -INF) continue;
    258 		int ni = (j == m - 1 ? i + 1 : i);
    259 		int nj = (j == m - 1 ? 0 : j + 1);
    260 		if (i != ni) {
    261 			dp[ni][nj][0][rem] = max(dp[ni][nj][0][rem], dp[i][j][cnt][rem]);
    262 		} else {
    263 			dp[ni][nj][cnt][rem] = max(dp[ni][nj][cnt][rem], dp[i][j][cnt][rem]);
    264 		}
    265 		if (cnt + 1 <= m / 2) {
    266 			int nrem = (rem + a[i][j]) % k;
    267 			if (i != ni) {
    268 				dp[ni][nj][0][nrem] = max(dp[ni][nj][0][nrem], dp[i][j][cnt][rem] + a[i][j]);
    269 			} else {
    270 				dp[ni][nj][cnt + 1][nrem] = max(dp[ni][nj][cnt + 1][nrem], dp[i][j][cnt][rem] + a[i][j]);
    271 			}
    272 		}
    273 	}
    274 	
    275 	cout << max(0, dp[n][0][0][0]) << endl;
    276 	
    277 	return 0;
    278 }
    279 ```
    280 
    281 [1433G - Reducing Delivery Cost](/contest/1433/problem/G "Codeforces Round 677 (Div. 3)")
    282 
    283 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
    284 
    285 **Tutorial**
    286 
    287 Tutorial is loading...
    288 
    289 **Solution**
    290 
    291 ```
    292 #include <bits/stdc++.h>
    293 
    294 using namespace std;
    295 
    296 const int INF = 1e9;
    297 
    298 int n;
    299 vector<vector<int>> d;
    300 vector<vector<pair<int, int>>> g;
    301 
    302 void dijkstra(int s, vector<int> &d) {
    303 	d = vector<int>(n, INF);
    304 	d[s] = 0;
    305 	set<pair<int, int>> st;
    306 	st.insert({d[s], s});
    307 	while (!st.empty()) {
    308 		int v = st.begin()->second;
    309 		st.erase(st.begin());
    310 		for (auto [to, w] : g[v]) {
    311 			if (d[to] > d[v] + w) {
    312 				auto it = st.find({d[to], to});
    313 				if (it != st.end()) st.erase(it);
    314 				d[to] = d[v] + w;
    315 				st.insert({d[to], to});
    316 			}
    317 		}
    318 	}
    319 }
    320 
    321 int main() {
    322 #ifdef _DEBUG
    323 	freopen("input.txt", "r", stdin);
    324 //	freopen("output.txt", "w", stdout);
    325 #endif
    326 	
    327 	int m, k;
    328 	cin >> n >> m >> k;
    329 	g = vector<vector<pair<int, int>>>(n);
    330 	for (int i = 0; i < m; ++i) {
    331 		int x, y, w;
    332 		cin >> x >> y >> w;
    333 		--x, --y;
    334 		g[x].push_back({y, w});
    335 		g[y].push_back({x, w});
    336 	}
    337 	
    338 	vector<pair<int, int>> r(k);
    339 	for (auto &[a, b] : r) {
    340 		cin >> a >> b;
    341 		--a, --b;
    342 	}
    343 	
    344 	d = vector<vector<int>>(n);
    345 	for (int v = 0; v < n; ++v) {
    346 		dijkstra(v, d[v]);
    347 	}
    348 	
    349 	int ans = INF;
    350 	for (int v = 0; v < n; ++v) {
    351 		for (auto [to, w] : g[v]) {
    352 			int cur = 0;
    353 			for (auto [a, b] : r) {
    354 				cur += min({d[a][b], d[a][v] + d[to][b], d[a][to] + d[v][b]});
    355 			}
    356 			ans = min(ans, cur);
    357 		}
    358 	}
    359 	
    360 	cout << ans << endl;
    361 	
    362 	return 0;
    363 }
    364 ```