codeforces-scrape

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

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