1294.md (6255B)
1 Source: https://codeforces.com/blog/entry/73274 2 3 Thanks to [Rox](/profile/Rox "Candidate Master Rox") and [_overrated_](/profile/_overrated_ "Master _overrated_") for help with problem ideas and preparation! 4 5 [1294A - Collecting Coins](/contest/1294/problem/A "Codeforces Round 615 (Div. 3)") 6 7 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 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 q; 27 cin >> q; 28 for (int i = 0; i < q; ++i) { 29 int a[3], n; 30 cin >> a[0] >> a[1] >> a[2] >> n; 31 sort(a, a + 3); 32 n -= 2 * a[2] - a[1] - a[0]; 33 if (n < 0 || n % 3 != 0) { 34 cout << "NO" << endl; 35 } else { 36 cout << "YES" << endl; 37 } 38 } 39 40 return 0; 41 } 42 ``` 43 44 [1294B - Collecting Packages](/contest/1294/problem/B "Codeforces Round 615 (Div. 3)") 45 46 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 47 48 **Tutorial** 49 50 Tutorial is loading... 51 52 **Solution** 53 54 ``` 55 #include <bits/stdc++.h> 56 57 using namespace std; 58 59 int main() { 60 #ifdef _DEBUG 61 freopen("input.txt", "r", stdin); 62 // freopen("output.txt", "w", stdout); 63 #endif 64 int t; 65 cin >> t; 66 67 for (int tt = 0; tt < t; tt++) { 68 int n; 69 cin >> n; 70 vector<pair<int, int>> a(n); 71 for (int i = 0; i < n; ++i) { 72 cin >> a[i].first >> a[i].second; 73 } 74 sort(a.begin(), a.end()); 75 pair<int, int> cur = make_pair(0, 0); 76 string ans; 77 bool ok = true; 78 for (int i = 0; i < n; ++i) { 79 int r = a[i].first - cur.first; 80 int u = a[i].second - cur.second; 81 if (r < 0 || u < 0) { 82 cout << "NO" << endl; 83 ok = false; 84 break; 85 } 86 ans += string(r, 'R'); 87 ans += string(u, 'U'); 88 cur = a[i]; 89 } 90 91 if (ok) 92 cout << "YES" << endl << ans << endl; 93 } 94 95 return 0; 96 } 97 ``` 98 99 [1294C - Product of Three Numbers](/contest/1294/problem/C "Codeforces Round 615 (Div. 3)") 100 101 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 102 103 **Tutorial** 104 105 Tutorial is loading... 106 107 **Solution** 108 109 ``` 110 #include <bits/stdc++.h> 111 112 using namespace std; 113 114 int main() { 115 #ifdef _DEBUG 116 freopen("input.txt", "r", stdin); 117 // freopen("output.txt", "w", stdout); 118 #endif 119 120 int q; 121 cin >> q; 122 for (int i = 0; i < q; ++i) { 123 int n; 124 cin >> n; 125 set<int> used; 126 for (int i = 2; i * i <= n; ++i) { 127 if (n % i == 0 && !used.count(i)) { 128 used.insert(i); 129 n /= i; 130 break; 131 } 132 } 133 for (int i = 2; i * i <= n; ++i) { 134 if (n % i == 0 && !used.count(i)) { 135 used.insert(i); 136 n /= i; 137 break; 138 } 139 } 140 if (int(used.size()) < 2 || used.count(n) || n == 1) { 141 cout << "NO" << endl; 142 } else { 143 cout << "YES" << endl; 144 used.insert(n); 145 for (auto it : used) cout << it << " "; 146 cout << endl; 147 } 148 } 149 150 return 0; 151 } 152 ``` 153 154 [1294D - MEX maximizing](/contest/1294/problem/D "Codeforces Round 615 (Div. 3)") 155 156 Idea: [vovuh](/profile/vovuh "Master vovuh") 157 158 **Tutorial** 159 160 Tutorial is loading... 161 162 **Solution** 163 164 ``` 165 #include <bits/stdc++.h> 166 167 using namespace std; 168 169 int main() { 170 #ifdef _DEBUG 171 freopen("input.txt", "r", stdin); 172 // freopen("output.txt", "w", stdout); 173 #endif 174 175 int q, x; 176 cin >> q >> x; 177 vector<int> mods(x); 178 179 set<pair<int, int>> vals; 180 for (int i = 0; i < x; ++i) { 181 vals.insert(make_pair(mods[i], i)); 182 } 183 184 for (int i = 0; i < q; ++i) { 185 int cur; 186 cin >> cur; 187 cur %= x; 188 vals.erase(make_pair(mods[cur], cur)); 189 ++mods[cur]; 190 vals.insert(make_pair(mods[cur], cur)); 191 cout << vals.begin()->first * x + vals.begin()->second << endl; 192 } 193 194 return 0; 195 } 196 ``` 197 198 [1294E - Obtain a Permutation](/contest/1294/problem/E "Codeforces Round 615 (Div. 3)") 199 200 Idea: [vovuh](/profile/vovuh "Master vovuh") 201 202 **Tutorial** 203 204 Tutorial is loading... 205 206 **Solution** 207 208 ``` 209 #include <bits/stdc++.h> 210 211 using namespace std; 212 213 int main() { 214 #ifdef _DEBUG 215 freopen("input.txt", "r", stdin); 216 // freopen("output.txt", "w", stdout); 217 #endif 218 219 int n, m; 220 cin >> n >> m; 221 vector<vector<int>> a(n, vector<int>(m)); 222 for (int i = 0; i < n; ++i) { 223 for (int j = 0; j < m; ++j) { 224 cin >> a[i][j]; 225 --a[i][j]; 226 } 227 } 228 229 long long ans = 0; 230 for (int j = 0; j < m; ++j) { 231 vector<int> cnt(n); 232 for (int i = 0; i < n; ++i) { 233 if (a[i][j] % m == j) { 234 int pos = a[i][j] / m; 235 if (pos < n) { 236 ++cnt[(i - pos + n) % n]; 237 } 238 } 239 } 240 int cur = n - cnt[0]; 241 for (int i = 1; i < n; ++i) { 242 cur = min(cur, n - cnt[i] + i); 243 } 244 ans += cur; 245 } 246 247 cout << ans << endl; 248 249 return 0; 250 } 251 ``` 252 253 [1294F - Three Paths on a Tree](/contest/1294/problem/F "Codeforces Round 615 (Div. 3)") 254 255 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 256 257 **Tutorial** 258 259 Tutorial is loading... 260 261 **Solution** 262 263 ``` 264 #include <bits/stdc++.h> 265 266 using namespace std; 267 268 #define x first 269 #define y second 270 271 vector<int> p; 272 vector<vector<int>> g; 273 274 pair<int, int> dfs(int v, int par = -1, int dist = 0) { 275 p[v] = par; 276 pair<int, int> res = make_pair(dist, v); 277 for (auto to : g[v]) { 278 if (to == par) continue; 279 res = max(res, dfs(to, v, dist + 1)); 280 } 281 return res; 282 } 283 284 int main() { 285 #ifdef _DEBUG 286 freopen("input.txt", "r", stdin); 287 // freopen("output.txt", "w", stdout); 288 #endif 289 290 int n; 291 cin >> n; 292 p = vector<int>(n); 293 g = vector<vector<int>>(n); 294 for (int i = 0; i < n - 1; ++i) { 295 int x, y; 296 cin >> x >> y; 297 --x, --y; 298 g[x].push_back(y); 299 g[y].push_back(x); 300 } 301 302 303 pair<int, int> da = dfs(0); 304 pair<int, int> db = dfs(da.y); 305 vector<int> diam; 306 int v = db.y; 307 while (v != da.y) { 308 diam.push_back(v); 309 v = p[v]; 310 } 311 diam.push_back(da.y); 312 313 if (int(diam.size()) == n) { 314 cout << n - 1 << " " << endl << diam[0] + 1 << " " << diam[1] + 1 << " " << diam.back() + 1 << endl; 315 } else { 316 queue<int> q; 317 vector<int> d(n, -1); 318 for (auto v : diam) { 319 d[v] = 0; 320 q.push(v); 321 } 322 while (!q.empty()) { 323 int v = q.front(); 324 q.pop(); 325 for (auto to : g[v]) { 326 if (d[to] == -1) { 327 d[to] = d[v] + 1; 328 q.push(to); 329 } 330 } 331 } 332 pair<int, int> mx = make_pair(d[0], 0); 333 for (int v = 1; v < n; ++v) { 334 mx = max(mx, make_pair(d[v], v)); 335 } 336 cout << int(diam.size()) - 1 + mx.x << endl << diam[0] + 1 << " " << mx.y + 1 << " " << diam.back() + 1 << endl; 337 } 338 339 return 0; 340 } 341 ```