codeforces-scrape

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

1117.md (9833B)


      1 Source: https://codeforces.com/blog/entry/65365
      2 
      3 [1117A - Best Subsegment](/contest/1117/problem/A "Educational Codeforces Round 60 (Rated for Div. 2)")
      4 
      5 **Tutorial**
      6 
      7 Tutorial is loading...
      8 
      9 **Solution (adedalic)**
     10 
     11 ```
     12 #include<iostream>
     13 using namespace std;
     14 
     15 int main() {
     16 	int n; cin >> n;
     17 	int mx = -1, lenMx = 0;
     18 	
     19 	int curEl = -1, curLen = 0;
     20 	for(int i = 0; i < n; i++) {
     21 		int a; cin >> a;
     22 		
     23 		if(curEl != a)
     24 			curEl = a, curLen = 0;
     25 		curLen++;
     26 		
     27 		if(mx < curEl)
     28 			mx = curEl, lenMx = 0;
     29 		if(mx == curEl)
     30 			lenMx = max(lenMx, curLen);
     31 	}
     32 	cout << lenMx << endl;
     33 	return 0;
     34 }
     35 ```
     36 
     37 [1117B - Emotes](/contest/1117/problem/B "Educational Codeforces Round 60 (Rated for Div. 2)")
     38 
     39 **Tutorial**
     40 
     41 Tutorial is loading...
     42 
     43 **Solution (Vovuh)**
     44 
     45 ```
     46 #include <bits/stdc++.h>
     47 
     48 using namespace std;
     49 
     50 int main() {
     51 #ifdef _DEBUG
     52 	freopen("input.txt", "r", stdin);
     53 //	freopen("output.txt", "w", stdout);
     54 #endif
     55 	
     56 	int n, m, k;
     57 	cin >> n >> m >> k;
     58 	
     59 	vector<int> a(n);
     60 	for (int i = 0; i < n; ++i) {
     61 		cin >> a[i];
     62 	}
     63 	sort(a.rbegin(), a.rend());
     64 	
     65 	cout << m / (k + 1) * 1ll * (a[0] * 1ll * k + a[1]) + m % (k + 1) * 1ll * a[0] << endl;
     66 	
     67 	return 0;
     68 }
     69 ```
     70 
     71 [1117C - Magic Ship](/contest/1117/problem/C "Educational Codeforces Round 60 (Rated for Div. 2)")
     72 
     73 **Tutorial**
     74 
     75 Tutorial is loading...
     76 
     77 **Solution (Roms)**
     78 
     79 ```
     80 #include <bits/stdc++.h>
     81 
     82 using namespace std;
     83 
     84 #define x first
     85 #define y second
     86 
     87 const int N = 100009;
     88 
     89 pair<int, int> st, fi;
     90 int n;
     91 string s;
     92 
     93 string mv = "UDLR";
     94 int dx[] = {0, 0, -1, 1};
     95 int dy[] = {1, -1, 0, 0};
     96 
     97 pair<int, int> d[N];
     98 
     99 int main(){
    100 	cin >> st.x >> st.y >> fi.x >> fi.y;
    101 	cin >> n >> s;		
    102 
    103 	for(int i = 0; i < n; ++i){
    104 		int id = -1;
    105 		for(int j = 0; j < 4; ++j)
    106 			if(mv[j] == s[i])
    107 				id = j;
    108 		assert(id != -1);
    109 		d[i + 1] = make_pair(d[i].x + dx[id], d[i].y + dy[id]);
    110 	}
    111 
    112 	long long l = 0, r = 1e18;
    113 	while(r - l > 1){
    114 		long long mid = (l + r) / 2;
    115 		long long cnt = mid / n, rem = mid % n;
    116 		long long x = st.x + d[rem].x + cnt *  1LL * d[n].x;
    117 		long long y = st.y + d[rem].y + cnt *  1LL * d[n].y;
    118 		long long dist = abs(x - fi.x) + abs(y - fi.y);
    119 		if(dist <= mid)
    120 			r = mid;
    121 		else
    122 			l = mid;	
    123 	} 
    124 
    125 	if(r > 5e17) r = -1;
    126 	cout << r << endl;
    127 
    128 	return 0;
    129 }
    130 ```
    131 
    132 [1117D - Magic Gems](/contest/1117/problem/D "Educational Codeforces Round 60 (Rated for Div. 2)")
    133 
    134 **Tutorial**
    135 
    136 Tutorial is loading...
    137 
    138 **Solution (Reziba)**
    139 
    140 ```
    141 #include<bits/stdc++.h>
    142 #define pb push_back
    143 #define mp make_pair
    144 #define fi first
    145 #define se second
    146 #define MOD 1000000007
    147 #define MOD9 1000000009
    148 #define pi 3.1415926535
    149 #define ms(s, n) memset(s, n, sizeof(s))
    150 #define prec(n) fixed<<setprecision(n)
    151 #define eps 0.000001
    152 #define all(v) v.begin(), v.end()
    153 #define allr(v) v.rbegin(), v.rend()
    154 #define bolt ios::sync_with_stdio(0)
    155 #define light cin.tie(0);cout.tie(0)
    156 #define forr(i,p,n) for(ll i=p;i<n;i++)
    157 #define MAXN 1000003
    158 typedef long long ll;
    159 using namespace std;
    160 ll mult(ll a,ll b, ll p=MOD){return ((a%p)*(b%p))%p;}
    161 ll add(ll a, ll b, ll p=MOD){return (a%p + b%p)%p;}
    162 ll fpow(ll n, ll k, ll p = MOD) {ll r = 1; for (; k; k >>= 1) {if (k & 1) r = r * n%p; n = n * n%p;} return r;}
    163 ll inv(ll a, ll p = MOD) {return fpow(a, p - 2, p);}
    164 ll inv_euclid(ll a, ll m = MOD){ll m0 = m;ll y = 0, x = 1;if (m == 1)return 0;while (a > 1){ll q = a / m;ll t = m;m = a % m, a = t;t = y;y = x - q * y;x = t;}if (x < 0)x += m0;return x;}
    165 
    166 ll bin[103][103];
    167 
    168 void mult_mat(ll m, ll ans[][100], ll bin[][100]){
    169     ll mult[m][m];
    170     forr(i,0,m){
    171         forr(j,0,m){
    172             mult[i][j]=0;
    173             forr(k,0,m){
    174                 mult[i][j]+=ans[i][k]*bin[k][j];
    175                 if(mult[i][j]>=MOD){
    176                     mult[i][j]%=MOD;
    177                 }
    178             }
    179         }
    180     }
    181     forr(i,0,m){
    182         forr(j,0,m){
    183             ans[i][j]=mult[i][j];
    184         }
    185     }
    186 }
    187 
    188 void pow_mat(ll n, ll fin[][100], ll m){
    189     ll ans[m][100];
    190     ll b[m][100];
    191     forr(i,0,m){
    192         forr(j,0,m){
    193             ans[i][j]=bin[i][j];
    194             b[i][j]=bin[i][j];
    195         }
    196     }
    197     n--;
    198     while(n>0){
    199         if(n%2==1){
    200             mult_mat(m,ans,b);
    201             n--;
    202         }else{
    203             n=n/2;
    204             mult_mat(m,b,b);
    205         }
    206     }
    207     forr(i,0,m){
    208         forr(j,0,m){
    209             fin[i][j]=ans[i][j];
    210         }
    211     }
    212 }
    213 
    214 int main(){
    215     bolt;
    216     ll n,m;
    217     cin>>n>>m;
    218     bin[0][0]=1;
    219     bin[0][m-1]=1;
    220     for(ll i=1;i<m;i++){
    221         bin[i][i-1]=1;
    222     }
    223     if(n<m){
    224         cout<<1<<"\n";
    225     }else{
    226         ll fin[m+1][100];
    227         pow_mat(n-m+1,fin,m);
    228         ll ans=0;
    229         forr(i,0,m){
    230             ans+=fin[0][i];
    231             if(ans>=MOD){
    232                 ans-=MOD;
    233             }
    234         }
    235         cout<<ans<<"\n";
    236     }
    237 }
    238 ```
    239 
    240 [1117E - Decypher the String](/contest/1117/problem/E "Educational Codeforces Round 60 (Rated for Div. 2)")
    241 
    242 **Tutorial**
    243 
    244 Tutorial is loading...
    245 
    246 **Solution (BledDest)**
    247 
    248 ```
    249 #include <bits/stdc++.h>
    250 
    251 using namespace std;
    252 
    253 int main()
    254 {
    255 	string t;
    256 	cin >> t;
    257 	int n = t.size();
    258 	string s1(n, 'a'), s2(n, 'a'), s3(n, 'a');
    259 	for(int i = 0; i < n; i++)
    260 	{
    261 		s1[i] = char('a' + (i % 26));
    262 		s2[i] = char('a' + ((i / 26) % 26));
    263 		s3[i] = char('a' + ((i / 26 / 26) % 26));
    264 	}
    265 	cout << "? " << s1 << endl;
    266 	string t1;
    267 	cin >> t1;
    268 	cout << "? " << s2 << endl;
    269 	string t2;
    270 	cin >> t2;
    271 	cout << "? " << s3 << endl;
    272 	string t3;
    273 	cin >> t3;
    274 	vector<int> p(n);
    275 	for(int i = 0; i < n; i++)
    276 		p[i] = (t1[i] - 'a') + (t2[i] - 'a') * 26 + (t3[i] - 'a') * 26 * 26;
    277 	string s(n, 'a');
    278 	for(int i = 0; i < n; i++)
    279 		s[p[i]] = t[i];
    280 	cout << "! " << s << endl;
    281 	return 0;
    282 }
    283 ```
    284 
    285 [1117F - Crisp String](/contest/1117/problem/F "Educational Codeforces Round 60 (Rated for Div. 2)")
    286 
    287 **Tutorial**
    288 
    289 Tutorial is loading...
    290 
    291 **Solution (PikMike)**
    292 
    293 ```
    294 #include <bits/stdc++.h>
    295 
    296 #define forn(i, n) for (int i = 0; i < int(n); i++)
    297 
    298 using namespace std;
    299 
    300 const int N = 100 * 1000 + 13;
    301 const int P = 17;
    302 
    303 int n, p;
    304 string s;
    305 int A[P][P];
    306 vector<int> pos[P];
    307 int pr[P][N];
    308 bitset<(1 << P)> legal, cur, dp;
    309 int cnt[P];
    310 
    311 int main() {
    312 	scanf("%d%d", &n, &p);
    313 	char buf[N];
    314 	scanf("%s", buf);
    315 	s = buf;
    316 	forn(i, p) forn(j, p)
    317 		scanf("%d", &A[i][j]);
    318 	
    319 	forn(i, n){
    320 		pos[s[i] - 'a'].push_back(i);
    321 		forn(j, p)
    322 			pr[j][i + 1] = pr[j][i] + (s[i] == 'a' + j);
    323 	}
    324 	
    325 	legal.reset();
    326 	legal.flip();
    327 	
    328 	int fl = (1 << p) - 1;
    329 	forn(c, p) forn(d, c + 1){
    330 		if (A[c][d]) continue;
    331 		cur.reset();
    332 		cur.flip();
    333 		int i = 0, j = 0;
    334 		while (i < pos[c].size() && j < pos[d].size()){
    335 			if (c == d && i == j){
    336 				++j;
    337 				continue;
    338 			}
    339 			int mask = 0;
    340 			if (pos[c][i] < pos[d][j]){
    341 				forn(e, p) if ((pr[e][pos[d][j]] - pr[e][pos[c][i] + 1]) != 0)
    342 					mask |= (1 << e);
    343 				++i;
    344 			}
    345 			else{
    346 				forn(e, p) if ((pr[e][pos[c][i]] - pr[e][pos[d][j] + 1]) != 0)
    347 					mask |= (1 << e);
    348 				++j;
    349 			}
    350 			if ((mask >> c) & 1) continue;
    351 			if ((mask >> d) & 1) continue;
    352 			cur[mask ^ fl] = 0;
    353 		}
    354 		for (int mask = fl; mask > 0; --mask){
    355 			if (cur[mask]) continue;
    356 			forn(e, p) if (c != e && d != e && ((mask >> e) & 1))
    357 				cur[mask ^ (1 << e)] = 0;
    358 		}
    359 		legal &= cur;
    360 	}
    361 	
    362 	dp[fl] = 1;
    363 	for (int mask = fl; mask > 0; --mask){
    364 		if (!dp[mask]) continue;
    365 		forn(i, p) if ((mask >> i) & 1){
    366 			int nmask = mask ^ (1 << i);
    367 			if (dp[nmask]) continue;
    368 			dp[nmask] = legal[nmask];
    369 		}
    370 	}
    371 	
    372 	forn(i, n)
    373 		++cnt[s[i] - 'a'];
    374 	
    375 	int ans = n;
    376 	forn(mask, 1 << p) if (dp[mask]){
    377 		int cur = 0;
    378 		forn(i, p) if ((mask >> i) & 1)
    379 			cur += cnt[i];
    380 		ans = min(ans, cur);
    381 	}
    382 	
    383 	printf("%d\n", ans);
    384 	
    385 	return 0;
    386 }
    387 ```
    388 
    389 [1117G - Recursive Queries](/contest/1117/problem/G "Educational Codeforces Round 60 (Rated for Div. 2)")
    390 
    391 **Tutorial**
    392 
    393 Tutorial is loading...
    394 
    395 **Solution (adedalic)**
    396 
    397 ```
    398 #include<bits/stdc++.h>
    399 using namespace std;
    400 
    401 #define fore(i, l, r) for(int i = int(l); i < int(r); i++)
    402 #define sz(a) int((a).size())
    403 
    404 #define x first
    405 #define y second
    406 
    407 typedef long long li;
    408 typedef pair<int, int> pt;
    409 
    410 int n, q;
    411 vector<int> a;
    412 vector< pair<pt, int> > qs;
    413 
    414 inline bool read() {
    415 	if(!(cin >> n >> q))
    416 		return false;
    417 	a.resize(n);
    418 	qs.resize(q);
    419 	
    420 	fore(i, 0, n)
    421 		cin >> a[i];
    422 	fore(i, 0, q) {
    423 		cin >> qs[i].x.x;
    424 		qs[i].x.x--;
    425 	}
    426 	fore(i, 0, q) {
    427 		cin >> qs[i].x.y;
    428 		qs[i].x.y--;
    429 		qs[i].y = i;
    430 	}
    431 	return true;
    432 }
    433 
    434 bool cmp(const pair<pt, int> &a, const pair<pt, int> &b) {
    435 	if(a.x.y != b.x.y)
    436 		return a.x.y < b.x.y;
    437 	if(a.x.x != b.x.x)
    438 		return a.x.x < b.x.x;
    439 	return a.y < b.y;
    440 }
    441 
    442 typedef pair<li, li> func;
    443 func operator +=(func &a, const func &b) {
    444 	a.x += b.x, a.y += b.y;
    445 	return a;
    446 }
    447 
    448 vector<func> t;
    449 void add(int l, int r, const func &f) {
    450 	for(l += n, r += n; l < r; l >>= 1, r >>= 1) {
    451 		if(l & 1) t[l++] += f;
    452 		if(r & 1) t[--r] += f;
    453 	}
    454 }
    455 func sum(int pos) {
    456 	func ans(0, 0);
    457 	for(pos += n; pos > 0; pos >>= 1)
    458 		ans += t[pos];
    459 	return ans;
    460 }
    461 
    462 inline void solve() {
    463 	vector<li> ans(q, 0);
    464 	fore(i, 0, q)
    465 		ans[i] = qs[i].x.y - qs[i].x.x + 1;
    466 	fore(_, 0, 2) {
    467 		vector<int> st;
    468 		vector<int> lf(n, -1);
    469 		fore(i, 0, n) {
    470 			while(!st.empty() && a[st.back()] < a[i])
    471 				st.pop_back();
    472 			if(!st.empty())
    473 				lf[i] = st.back();
    474 			st.push_back(i);
    475 		}
    476 		
    477 		sort(qs.begin(), qs.end(), cmp);
    478 		t.assign(2 * n, {0, 0});
    479 		
    480 		int uk = 0;
    481 		fore(i, 0, n) {
    482 			add(0, lf[i] + 1, {0, i - lf[i] - 1});
    483 			add(lf[i] + 1, i, {-1, i});
    484 			
    485 			while(uk < q && qs[uk].x.y == i) {
    486 				auto f = sum(qs[uk].x.x);
    487 				ans[qs[uk].y] += f.x * qs[uk].x.x + f.y;
    488 				uk++;
    489 			}
    490 		}
    491 		
    492 		reverse(a.begin(), a.end());
    493 		for(auto &p : qs) {
    494 			p.x.x = n - 1 - p.x.x;
    495 			p.x.y = n - 1 - p.x.y;
    496 			swap(p.x.x, p.x.y);
    497 		}
    498 	}
    499 	for(auto v : ans)
    500 		cout << v << ' ';
    501 	cout << endl;
    502 }
    503 
    504 int main() {
    505 #ifdef _DEBUG
    506 	freopen("input.txt", "r", stdin);
    507 	int tt = clock();
    508 #endif
    509 	ios_base::sync_with_stdio(false);
    510 	cin.tie(0), cout.tie(0);
    511 	cout << fixed << setprecision(15);
    512 	
    513 	if(read()) {
    514 		solve();
    515 		
    516 #ifdef _DEBUG
    517 		cerr << "TIME = " << clock() - tt << endl;
    518 		tt = clock();
    519 #endif
    520 	}
    521 	return 0;
    522 }
    523 ```