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