1366.md (8342B)
1 Source: https://codeforces.com/blog/entry/78735 2 3 [1366A - Shovels and Swords](/contest/1366/problem/A "Educational Codeforces Round 89 (Rated for Div. 2)") 4 5 Idea: [Roms](/profile/Roms "Master Roms") 6 7 **Tutorial** 8 9 Tutorial is loading... 10 11 **Solution (Roms)** 12 13 ``` 14 for _ in range(int(input())): 15 l, r = map(int, input().split()) 16 print(min(l, r, (l + r) // 3)) 17 ``` 18 19 [1366B - Shuffle](/contest/1366/problem/B "Educational Codeforces Round 89 (Rated for Div. 2)") 20 21 Idea: [Roms](/profile/Roms "Master Roms") 22 23 **Tutorial** 24 25 Tutorial is loading... 26 27 **Solution (Roms)** 28 29 ``` 30 for _ in range(int(input())): 31 n, x, m = map(int, input().split()) 32 l, r = x, x 33 for _ in range(m): 34 L, R = map(int, input().split()) 35 if max(l, L) <= min(r, R): 36 l = min(l, L) 37 r = max(r, R) 38 39 print(r - l + 1) 40 ``` 41 42 [1366C - Palindromic Paths](/contest/1366/problem/C "Educational Codeforces Round 89 (Rated for Div. 2)") 43 44 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 45 46 **Tutorial** 47 48 Tutorial is loading... 49 50 **Solution (BledDest)** 51 52 ``` 53 #include <bits/stdc++.h> 54 55 using namespace std; 56 57 void solve() 58 { 59 int n, m; 60 cin >> n >> m; 61 vector<vector<int> > a(n, vector<int>(m)); 62 for(int i = 0; i < n; i++) 63 for(int j = 0; j < m; j++) 64 cin >> a[i][j]; 65 vector<vector<int> > cnt(n + m - 1, vector<int>(2)); 66 for(int i = 0; i < n; i++) 67 for(int j = 0; j < m; j++) 68 cnt[i + j][a[i][j]]++; 69 int ans = 0; 70 for(int i = 0; i <= n + m - 2; i++) 71 { 72 int j = n + m - 2 - i; 73 if(i <= j) continue; 74 ans += min(cnt[i][0] + cnt[j][0], cnt[i][1] + cnt[j][1]); 75 } 76 cout << ans << endl; 77 } 78 79 int main() { 80 int t; 81 cin >> t; 82 for(int i = 0; i < t; i++) 83 solve(); 84 } 85 ``` 86 87 [1366D - Two Divisors](/contest/1366/problem/D "Educational Codeforces Round 89 (Rated for Div. 2)") 88 89 Idea: [adedalic](/profile/adedalic "International Master adedalic") 90 91 **Tutorial** 92 93 Tutorial is loading... 94 95 **Solution (adedalic)** 96 97 ``` 98 fun main() { 99 val n = readLine()!!.toInt() 100 val a = readLine()!!.split(' ').map { it.toInt() } 101 102 val minDiv = IntArray(1e7.toInt() + 2) { it } 103 for (i in 2 until minDiv.size) { 104 if (minDiv[i] != i) 105 continue 106 for (j in i until minDiv.size step i) 107 minDiv[j] = minOf(minDiv[j], i) 108 } 109 110 fun getPrimeDivisors(v: Int): ArrayList<Int> { 111 val ans = ArrayList<Int>() 112 var curVal = v 113 while (curVal != 1) { 114 if (ans.isEmpty() || ans.last() != minDiv[curVal]) 115 ans.add(minDiv[curVal]) 116 curVal /= minDiv[curVal] 117 } 118 return ans 119 } 120 121 val d1 = IntArray(n) 122 val d2 = IntArray(n) 123 for (id in a.indices) { 124 val list = getPrimeDivisors(a[id]) 125 if (list.size < 2) { 126 d1[id] = -1 127 d2[id] = -1 128 } else { 129 d1[id] = list[0] 130 list.removeAt(0) 131 d2[id] = list.reduce { s, t -> s * t } 132 } 133 } 134 println(d1.joinToString(" ")) 135 println(d2.joinToString(" ")) 136 } 137 ``` 138 139 [1366E - Two Arrays](/contest/1366/problem/E "Educational Codeforces Round 89 (Rated for Div. 2)") 140 141 Idea: [Roms](/profile/Roms "Master Roms") 142 143 **Tutorial** 144 145 Tutorial is loading... 146 147 **Solution (Roms)** 148 149 ``` 150 #include <bits/stdc++.h> 151 152 using namespace std; 153 154 const int N = 200005; 155 const int MOD = 998244353; 156 157 int mul(int a, int b) { 158 return (a * 1LL * b) % MOD; 159 } 160 161 int n, m; 162 int a[N], b[N]; 163 164 int main() { 165 scanf("%d %d", &n, &m); 166 for (int i = 0; i < n; ++i) scanf("%d", a + i); 167 for (int i = 0; i < m; ++i) scanf("%d", b + i); 168 169 reverse(a, a + n); 170 reverse(b, b + m); 171 a[n] = -1; 172 173 int mn = a[0]; 174 int pos = 0; 175 while (pos < n && mn > b[0]) { 176 ++pos; 177 mn = min(mn, a[pos]); 178 } 179 180 if (pos == n || mn < b[0]) { 181 puts("0"); 182 return 0; 183 } 184 185 assert(mn == b[0]); 186 int res = 1; 187 int ib = 0; 188 while (true) { 189 assert(mn == b[ib]); 190 if (ib == m - 1){ 191 if(*min_element(a + pos, a + n) != b[ib]) { 192 puts("0"); 193 return 0; 194 } 195 break; 196 } 197 198 bool f = true; 199 int npos = pos; 200 while (npos < n && mn != b[ib + 1]) { 201 ++npos; 202 mn = min(mn, a[npos]); 203 204 if (f && mn < b[ib]){ 205 f = false; 206 res = mul(res, npos - pos); 207 } 208 } 209 210 if (npos == n || mn != b[ib + 1]) { 211 puts("0"); 212 return 0; 213 } 214 215 ++ib; 216 pos = npos; 217 } 218 219 printf("%d\n", res); 220 return 0; 221 } 222 ``` 223 224 [1366F - Jog Around The Graph](/contest/1366/problem/F "Educational Codeforces Round 89 (Rated for Div. 2)") 225 226 Idea: [Neon](/profile/Neon "Candidate Master Neon") 227 228 **Tutorial** 229 230 Tutorial is loading... 231 232 **Solution (pikmike)** 233 234 ``` 235 #include <bits/stdc++.h> 236 237 #define forn(i, n) for (int i = 0; i < int(n); i++) 238 239 using namespace std; 240 241 const long long INF = 1e18; 242 const int MOD = 1000'000'007; 243 const int inv2 = (MOD + 1) / 2; 244 245 struct edge{ 246 int v, u, w; 247 }; 248 249 struct frac{ 250 long long x, y; 251 frac(long long a, long long b){ 252 if (b < 0) a = -a, b = -b; 253 x = a, y = b; 254 } 255 }; 256 257 bool operator <=(const frac &a, const frac &b){ 258 return a.x * b.y <= a.y * b.x; 259 } 260 261 struct line{ 262 long long m, c; 263 frac intersectX(const line &l) { return frac(c - l.c, l.m - m); } 264 }; 265 266 int add(int a, int b){ 267 a += b; 268 if (a >= MOD) 269 a -= MOD; 270 if (a < 0) 271 a += MOD; 272 return a; 273 } 274 275 int mul(int a, int b){ 276 return a * 1ll * b % MOD; 277 } 278 279 int calc(int a1, int d, int n){ 280 assert(n >= 0); 281 return mul(mul(n, inv2), add(mul(2, a1), mul(add(n, -1), d))); 282 } 283 284 int main() { 285 int n, m; 286 long long q; 287 scanf("%d%d%lld", &n, &m, &q); 288 vector<edge> e(m); 289 vector<int> hv(n); 290 forn(i, m){ 291 scanf("%d%d%d", &e[i].v, &e[i].u, &e[i].w); 292 --e[i].v, --e[i].u; 293 hv[e[i].v] = max(hv[e[i].v], e[i].w); 294 hv[e[i].u] = max(hv[e[i].u], e[i].w); 295 } 296 297 int ans = 0; 298 vector<long long> d(n, -INF), nd(n); 299 d[0] = 0; 300 forn(val, m){ 301 long long mx = 0; 302 forn(i, n) 303 mx = max(mx, d[i]); 304 if (val) 305 ans = add(ans, mx % MOD); 306 nd = d; 307 forn(i, m){ 308 nd[e[i].v] = max(nd[e[i].v], d[e[i].u] + e[i].w); 309 nd[e[i].u] = max(nd[e[i].u], d[e[i].v] + e[i].w); 310 } 311 d = nd; 312 } 313 314 vector<line> fin; 315 forn(i, n) fin.push_back({hv[i], d[i]}); 316 sort(fin.begin(), fin.end(), [](const line &a, const line &b){ 317 if (a.m != b.m) 318 return a.m < b.m; 319 return a.c > b.c; 320 }); 321 fin.resize(unique(fin.begin(), fin.end(), [](const line &a, const line &b){ 322 return a.m == b.m; 323 }) - fin.begin()); 324 325 vector<line> ch; 326 for (auto cur : fin){ 327 while (ch.size() >= 2 && cur.intersectX(ch.back()) <= ch.back().intersectX(ch[int(ch.size()) - 2])) 328 ch.pop_back(); 329 ch.push_back(cur); 330 } 331 332 long long prv = 0; 333 q -= m; 334 forn(i, int(ch.size()) - 1){ 335 frac f = ch[i].intersectX(ch[i + 1]); 336 if (f.x < 0) continue; 337 long long lst = min(q, f.x / f.y); 338 if (lst < prv) continue; 339 ans = add(ans, calc((ch[i].c + ch[i].m * prv) % MOD, ch[i].m % MOD, lst - prv + 1)); 340 prv = lst + 1; 341 } 342 ans = add(ans, calc((ch.back().c + ch.back().m * prv) % MOD, ch.back().m % MOD, q - prv + 1)); 343 344 printf("%d\n", ans); 345 return 0; 346 } 347 ``` 348 349 [1366G - Construct the String](/contest/1366/problem/G "Educational Codeforces Round 89 (Rated for Div. 2)") 350 351 Idea: [Neon](/profile/Neon "Candidate Master Neon") 352 353 **Tutorial** 354 355 Tutorial is loading... 356 357 **Solution (Ne0n25)** 358 359 ``` 360 #include <bits/stdc++.h> 361 362 using namespace std; 363 364 #define x first 365 #define y second 366 #define mp make_pair 367 #define pb push_back 368 #define sz(a) int((a).size()) 369 #define forn(i, n) for (int i = 0; i < int(n); ++i) 370 #define fore(i, l, r) for (int i = int(l); i < int(r); ++i) 371 372 const int INF = 1e9; 373 const int N = 10010; 374 375 int n, m; 376 string s, t; 377 int dp[N][N]; 378 int nxt[N]; 379 380 int main() { 381 cin >> s >> t; 382 n = sz(s), m = sz(t); 383 384 forn(i, n) if (s[i] != '.') { 385 int bal = 0; 386 nxt[i] = -1; 387 fore(j, i, n) { 388 if (s[j] == '.') --bal; 389 else ++bal; 390 if (bal == 0) { 391 nxt[i] = j; 392 break; 393 } 394 } 395 } 396 397 forn(i, n + 1) forn(j, m + 1) 398 dp[i][j] = INF; 399 dp[0][0] = 0; 400 401 forn(i, n) forn(j, m + 1) { 402 dp[i + 1][j] = min(dp[i + 1][j], dp[i][j] + 1); 403 if (j < m && s[i] == t[j]) 404 dp[i + 1][j + 1] = min(dp[i + 1][j + 1], dp[i][j]); 405 if (s[i] != '.' && nxt[i] != -1) 406 dp[nxt[i] + 1][j] = min(dp[nxt[i] + 1][j], dp[i][j]); 407 } 408 409 cout << dp[n][m] << endl; 410 } 411 ```