1519.md (7789B)
1 Source: https://codeforces.com/blog/entry/90212 2 3 [1519A - Red and Blue Beans](/contest/1519/problem/A "Educational Codeforces Round 108 (Rated for Div. 2)") 4 5 Idea: [adedalic](/profile/adedalic "International Master adedalic") 6 7 **Tutorial** 8 9 Tutorial is loading... 10 11 **Solution (adedalic)** 12 13 ``` 14 fun main() { 15 repeat(readLine()!!.toInt()) { 16 val (r, b, d) = readLine()!!.split(' ').map { it.toInt() } 17 println(if (minOf(r, b) * (d + 1).toLong() >= maxOf(r, b)) "YES" else "NO") 18 } 19 } 20 ``` 21 22 [1519B - The Cake Is a Lie](/contest/1519/problem/B "Educational Codeforces Round 108 (Rated for Div. 2)") 23 24 Idea: [adedalic](/profile/adedalic "International Master adedalic") 25 26 **Tutorial** 27 28 Tutorial is loading... 29 30 **Solution (adedalic)** 31 32 ``` 33 fun main() { 34 repeat(readLine()!!.toInt()) { 35 val (n, m, k) = readLine()!!.split(' ').map { it.toInt() } 36 println(if (n * m - 1 == k) "YES" else "NO") 37 } 38 } 39 ``` 40 41 [1519C - Berland Regional](/contest/1519/problem/C "Educational Codeforces Round 108 (Rated for Div. 2)") 42 43 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 44 45 **Tutorial** 46 47 Tutorial is loading... 48 49 **Solution (awoo)** 50 51 ``` 52 #include <bits/stdc++.h> 53 54 #define forn(i, n) for (int i = 0; i < int(n); i++) 55 56 using namespace std; 57 58 int main() { 59 int t; 60 scanf("%d", &t); 61 forn(_, t){ 62 int n; 63 scanf("%d", &n); 64 vector<int> s(n), u(n); 65 forn(i, n){ 66 scanf("%d", &s[i]); 67 --s[i]; 68 } 69 forn(i, n){ 70 scanf("%d", &u[i]); 71 } 72 vector<vector<int>> bst(n); 73 forn(i, n) bst[s[i]].push_back(u[i]); 74 forn(i, n) sort(bst[i].begin(), bst[i].end(), greater<int>()); 75 vector<vector<long long>> pr(n, vector<long long>(1, 0)); 76 forn(i, n) for (int x : bst[i]) pr[i].push_back(pr[i].back() + x); 77 vector<long long> ans(n); 78 forn(i, n) for (int k = 1; k <= int(bst[i].size()); ++k) 79 ans[k - 1] += pr[i][bst[i].size() / k * k]; 80 forn(i, n) 81 printf("%lld ", ans[i]); 82 puts(""); 83 } 84 return 0; 85 } 86 ``` 87 88 [1519D - Maximum Sum of Products](/contest/1519/problem/D "Educational Codeforces Round 108 (Rated for Div. 2)") 89 90 Idea: [vovuh](/profile/vovuh "Master vovuh") 91 92 **Tutorial** 93 94 Tutorial is loading... 95 96 **Solution (Neon)** 97 98 ``` 99 #include <bits/stdc++.h> 100 101 using namespace std; 102 103 using li = long long; 104 105 int main() { 106 int n; 107 cin >> n; 108 vector<li> a(n), b(n); 109 for (auto& x : a) cin >> x; 110 for (auto& x : b) cin >> x; 111 vector<li> pr(n + 1, 0); 112 for (int i = 0; i < n; ++i) 113 pr[i + 1] = pr[i] + a[i] * b[i]; 114 li ans = pr[n]; 115 for (int c = 0; c < n; ++c) { 116 li cur = a[c] * b[c]; 117 for (int l = c - 1, r = c + 1; l >= 0 && r < n; --l, ++r) { 118 cur += a[l] * b[r]; 119 cur += a[r] * b[l]; 120 ans = max(ans, cur + pr[l] + (pr[n] - pr[r + 1])); 121 } 122 cur = 0; 123 for (int l = c, r = c + 1; l >= 0 && r < n; --l, ++r) { 124 cur += a[l] * b[r]; 125 cur += a[r] * b[l]; 126 ans = max(ans, cur + pr[l] + (pr[n] - pr[r + 1])); 127 } 128 } 129 cout << ans << endl; 130 } 131 ``` 132 133 [1519E - Off by One](/contest/1519/problem/E "Educational Codeforces Round 108 (Rated for Div. 2)") 134 135 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 136 137 **Tutorial** 138 139 Tutorial is loading... 140 141 **Solution (awoo)** 142 143 ``` 144 #include <bits/stdc++.h> 145 146 #define forn(i, n) for (int i = 0; i < int(n); i++) 147 #define x first 148 #define y second 149 150 using namespace std; 151 152 struct point{ 153 int a, b, c, d; 154 }; 155 156 typedef pair<long long, long long> frac; 157 typedef pair<int, int> pt; 158 159 int n; 160 vector<point> a; 161 map<frac, int> sv; 162 163 frac norm(long long x, long long y){ 164 long long g = __gcd(x, y); 165 return {x / g, y / g}; 166 } 167 168 vector<vector<pt>> g; 169 vector<int> used; 170 vector<pt> ans; 171 172 int dfs(int v){ 173 used[v] = 1; 174 int cur = -1; 175 for (auto it : g[v]){ 176 int u = it.x; 177 int i = it.y; 178 if (used[u] == 1) continue; 179 int nw = i; 180 if (!used[u]){ 181 int tmp = dfs(u); 182 if (tmp != -1){ 183 ans.push_back({nw, tmp}); 184 nw = -1; 185 } 186 } 187 if (nw != -1){ 188 if (cur != -1){ 189 ans.push_back({cur, nw}); 190 cur = -1; 191 } 192 else{ 193 cur = nw; 194 } 195 } 196 } 197 used[v] = 2; 198 return cur; 199 } 200 201 int main() { 202 scanf("%d", &n); 203 a.resize(n); 204 forn(i, n) scanf("%d%d%d%d", &a[i].a, &a[i].b, &a[i].c, &a[i].d); 205 g.resize(2 * n); 206 forn(i, n){ 207 frac f1 = norm((a[i].a + a[i].b) * 1ll * a[i].d, a[i].b * 1ll * a[i].c); 208 frac f2 = norm(a[i].a * 1ll * a[i].d, a[i].b * 1ll * (a[i].c + a[i].d)); 209 if (!sv.count(f1)){ 210 int k = sv.size(); 211 sv[f1] = k; 212 } 213 if (!sv.count(f2)){ 214 int k = sv.size(); 215 sv[f2] = k; 216 } 217 g[sv[f1]].push_back({sv[f2], i}); 218 g[sv[f2]].push_back({sv[f1], i}); 219 } 220 used.resize(sv.size()); 221 forn(i, sv.size()) if (!used[i]) 222 dfs(i); 223 printf("%d\n", int(ans.size())); 224 for (auto it : ans) printf("%d %d\n", it.x + 1, it.y + 1); 225 } 226 ``` 227 228 [1519F - Chests and Keys](/contest/1519/problem/F "Educational Codeforces Round 108 (Rated for Div. 2)") 229 230 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 231 232 **Tutorial** 233 234 Tutorial is loading... 235 236 **Solution (BledDest)** 237 238 ``` 239 #include<bits/stdc++.h> 240 241 using namespace std; 242 243 const int N = 6; 244 const int M = 400; 245 const int INF = int(1e9); 246 247 int a[N]; 248 int b[N]; 249 int c[N][N]; 250 int n, m; 251 252 struct state 253 { 254 vector<int> need; 255 int v2; 256 int v1; 257 int rem; 258 state() {}; 259 state(vector<int> need, int v1, int v2, int rem) : need(need), v1(v1), v2(v2), rem(rem) {}; 260 }; 261 262 int get_code(const vector<int>& v) 263 { 264 int ans = 0; 265 for(int i = 0; i < v.size(); i++) 266 ans = ans * 5 + v[i]; 267 return ans; 268 } 269 270 int get_code(const state& s) 271 { 272 int code = get_code(s.need); 273 code = code * 6 + s.v2; 274 code = code * 6 + s.v1; 275 code = code * 5 + s.rem; 276 return code; 277 } 278 279 vector<int> get_vector(int code, int n) 280 { 281 vector<int> res(n); 282 for(int i = n - 1; i >= 0; i--) 283 { 284 res[i] = code % 5; 285 code /= 5; 286 } 287 return res; 288 } 289 290 state get_state(int code) 291 { 292 int rem = code % 5; 293 code /= 5; 294 int v1 = code % 6; 295 code /= 6; 296 int v2 = code % 6; 297 code /= 6; 298 vector<int> need = get_vector(code, n); 299 return state(need, v1, v2, rem); 300 } 301 302 const int Z = 40 * int(1e6); 303 int dp[Z]; 304 305 int main() 306 { 307 cin >> n >> m; 308 for(int i = 0; i < n; i++) 309 cin >> a[i]; 310 for(int i = 0; i < m; i++) 311 cin >> b[i]; 312 for(int i = 0; i < n; i++) 313 for(int j = 0; j < m; j++) 314 cin >> c[i][j]; 315 for(int i = 0; i < Z; i++) 316 dp[i] = INF; 317 state start(vector<int>(n, 0), 0, 0, 0); 318 int ans = INF; 319 dp[get_code(start)] = 0; 320 for(int i = 0; i < Z; i++) 321 { 322 if(dp[i] == INF) continue; 323 state s = get_state(i); 324 for(int f = 0; f <= 4; f++) 325 { 326 if(s.need[s.v1] + f > a[s.v1] || s.rem + f > b[s.v2]) 327 continue; 328 int add = (f == 0 ? 0 : c[s.v1][s.v2]); 329 state nw = s; 330 nw.need[s.v1] += f; 331 nw.rem += f; 332 if(s.v1 == n - 1) 333 { 334 nw.v1 = 0; 335 nw.v2 = s.v2 + 1; 336 nw.rem = 0; 337 } 338 else 339 { 340 nw.v1 = s.v1 + 1; 341 } 342 if(nw.need == vector<int>(a, a + n)) 343 ans = min(ans, dp[i] + add); 344 if(nw.v2 < m) 345 { 346 int code = get_code(nw); 347 dp[code] = min(dp[code], dp[i] + add); 348 } 349 } 350 } 351 if(ans == INF) ans = -1; 352 cout << ans << endl; 353 354 } 355 ```