codeforces-scrape

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

1295.md (9847B)


      1 Source: https://codeforces.com/blog/entry/73467
      2 
      3 [1295A - Display The Number](/contest/1295/problem/A "Educational Codeforces Round 81 (Rated for Div. 2)")
      4 
      5 Idea: [adedalic](/profile/adedalic "International Master adedalic")
      6 
      7 **Tutorial**
      8 
      9 Tutorial is loading...
     10 
     11 **Solution (BledDest)**
     12 
     13 ```
     14 t = int(input())
     15 for i in range(t):
     16     n = int(input())
     17     if(n % 2 == 1):
     18         print(7, end='')
     19         n -= 3
     20     while(n > 0):
     21         print(1, end='')
     22         n -= 2
     23     print()
     24 ```
     25 
     26 [1295B - Infinite Prefixes](/contest/1295/problem/B "Educational Codeforces Round 81 (Rated for Div. 2)")
     27 
     28 Idea: [Roms](/profile/Roms "Master Roms")
     29 
     30 **Tutorial**
     31 
     32 Tutorial is loading...
     33 
     34 **Solution (adedalic)**
     35 
     36 ```
     37 #include<bits/stdc++.h>
     38 
     39 using namespace std;
     40 
     41 typedef long long li;
     42 
     43 int n, x;
     44 string s;
     45 
     46 inline bool read() {
     47 	if(!(cin >> n >> x >> s))
     48 		return false;
     49 	return true;
     50 }
     51 
     52 inline void solve() {
     53 	int ans = 0;
     54 	bool infAns = false;
     55 	
     56 	int cntZeros = (int)count(s.begin(), s.end(), '0');
     57 	int total = cntZeros - (n - cntZeros);
     58 	
     59 	int bal = 0;
     60 	for(int i = 0; i < n; i++) {
     61 		if(total == 0) {
     62 			if(bal == x)
     63 				infAns = true;
     64 		}
     65 		else if(abs(x - bal) % abs(total) == 0) {
     66 			if((x - bal) / total >= 0)
     67 				ans++;
     68 		}
     69 		
     70 		if(s[i] == '0')
     71 			bal++;
     72 		else
     73 			bal--;
     74 	}
     75 	
     76 	if(infAns) ans = -1;
     77 	cout << ans << endl;
     78 }
     79 
     80 int main() {
     81 #ifdef _DEBUG
     82 	freopen("input.txt", "r", stdin);
     83 #endif
     84 	ios_base::sync_with_stdio(false);
     85 	cin.tie(0), cout.tie(0);
     86 	cout << fixed << setprecision(15);
     87 	
     88 	int tc; cin >> tc;
     89 	while(tc--) {
     90 		read();
     91 		solve();
     92 	}
     93 	
     94 	return 0;
     95 }
     96 ```
     97 
     98 [1295C - Obtain The String](/contest/1295/problem/C "Educational Codeforces Round 81 (Rated for Div. 2)")
     99 
    100 Idea: [Roms](/profile/Roms "Master Roms")
    101 
    102 **Tutorial**
    103 
    104 Tutorial is loading...
    105 
    106 **Solution (Roms)**
    107 
    108 ```
    109 #include<bits/stdc++.h>
    110 using namespace std;
    111 
    112 const int N = int(2e5) + 99;
    113 const int INF = int(1e9) + 99;
    114 
    115 int tc;
    116 string s, t;
    117 int nxt[N][26];
    118 
    119 int main() {
    120     cin >> tc;
    121     while(tc--){
    122         cin >> s >> t;
    123         for(int i = 0; i < s.size() + 5; ++i)
    124             for(int j = 0; j < 26; ++j)
    125                 nxt[i][j] = INF;
    126     	
    127         for(int i = int(s.size()) - 1; i >= 0; --i){
    128             for(int j = 0; j < 26; ++j)
    129                 nxt[i][j] = nxt[i + 1][j];
    130             nxt[i][s[i] - 'a'] = i;
    131         }    
    132     
    133         int res = 1, pos = 0;
    134         for(int i = 0; i < t.size(); ++i){
    135             if(pos == s.size()){
    136                 pos = 0;
    137                 ++res;
    138             }
    139             if(nxt[pos][t[i] - 'a'] == INF){
    140                 pos = 0; 
    141                 ++res;
    142     		}
    143     		if(nxt[pos][t[i] - 'a'] == INF && pos == 0){
    144                 res = INF;
    145                 break;
    146             }    
    147             pos = nxt[pos][t[i] - 'a'] + 1;
    148             
    149         }
    150     
    151         if(res >= INF) cout << -1 << endl;
    152         else cout << res << endl;
    153     }
    154     return 0;
    155 }
    156 ```
    157 
    158 [1295D - Same GCDs](/contest/1295/problem/D "Educational Codeforces Round 81 (Rated for Div. 2)")
    159 
    160 Idea: [adedalic](/profile/adedalic "International Master adedalic")
    161 
    162 **Tutorial**
    163 
    164 Tutorial is loading...
    165 
    166 **Solution (adedalic)**
    167 
    168 ```
    169 fun gcd(a : Long, b : Long) : Long {
    170     return if (a == 0L) b else gcd(b % a, a)
    171 }
    172 fun phi(a : Long) : Long {
    173     var (tmp, ans) = listOf(a, a)
    174     var d = 2L
    175     while (d * d <= tmp) {
    176         var cnt = 0
    177         while (tmp % d == 0L) {
    178             tmp /= d
    179             cnt++
    180         }
    181         if (cnt > 0) ans -= ans / d
    182         d++
    183     }
    184     if (tmp > 1L) ans -= ans / tmp
    185     return ans
    186 }
    187 
    188 fun main() {
    189     val t = readLine()!!.toInt()
    190     for (tc in 1..t) {
    191         val (a, m) = readLine()!!.split(' ').map { it.toLong() }
    192         println(phi(m / gcd(a, m)))
    193     }
    194 }
    195 ```
    196 
    197 [1295E - Permutation Separation](/contest/1295/problem/E "Educational Codeforces Round 81 (Rated for Div. 2)")
    198 
    199 Idea: [adedalic](/profile/adedalic "International Master adedalic")
    200 
    201 **Tutorial**
    202 
    203 Tutorial is loading...
    204 
    205 **Solution (adedalic)**
    206 
    207 ```
    208 #include<bits/stdc++.h>
    209 using namespace std;
    210 
    211 const int N = int(2e5) + 99;
    212 
    213 int n;
    214 int p[N];
    215 int rp[N];
    216 int a[N];
    217 
    218 long long b[N];
    219 long long t[4 * N];
    220 long long add[4 * N];
    221 
    222 void build(int v, int l, int r){
    223 	if(r - l == 1){
    224 		t[v] = b[l];
    225 		return;
    226 	}
    227 
    228 	int mid = (l + r) / 2;	
    229 	build(v * 2 + 1, l, mid);
    230 	build(v * 2 + 2, mid, r);
    231 	t[v] = min(t[v * 2 + 1], t[v * 2 + 2]); 
    232 }
    233 
    234 void push(int v, int l, int r){
    235 	if(add[v] != 0){
    236 		if(r - l > 1)
    237 			for(int i = v+v+1; i < v+v+3; ++i){
    238 				add[i] += add[v];
    239 				t[i] += add[v];
    240 			}
    241 		add[v] = 0;
    242 	}
    243 }
    244 
    245 void upd(int v, int l, int r, int L, int R, int x){
    246 	if(L >= R) return;
    247 	if(l == L && r == R){
    248 		add[v] += x;
    249 		t[v] += x;
    250 		push(v, l, r);
    251 		return;
    252 	}
    253 	
    254 	push(v, l, r);
    255 	int mid = (l + r) / 2;
    256 	upd(v * 2 + 1, l, mid, L, min(mid, R), x);
    257 	upd(v * 2 + 2, mid, r, max(mid, L), R, x);
    258 
    259 	t[v] = min(t[v * 2 + 1], t[v * 2 + 2]);
    260 }
    261 
    262 void upd(int l, int r, int x){
    263 	upd(0, 0, n, l, r, x);
    264 }
    265 
    266 long long get(int v, int l, int r, int L, int R){
    267 	if(L >= R) return 1e18;
    268 
    269 	push(v, l, r);
    270 	if(l == L && r == R)
    271 		return t[v];
    272 
    273 	int mid = (l + r) / 2;
    274 	return min(get(v * 2 + 1, l, mid, L, min(R, mid)), 
    275 		   get(v * 2 + 2, mid, r, max(L, mid), R));		
    276 }
    277 
    278 long long get(int l, int r){
    279 	return get(0, 0, n, l, r);
    280 }
    281 
    282 int main() {
    283 	scanf("%d", &n);
    284 	for(int i = 0; i < n; ++i){
    285 		scanf("%d", p + i);
    286         --p[i];
    287         rp[p[i]] = i;
    288 	}
    289 	for(int i = 0; i < n; ++i)
    290 		scanf("%d", a + i);
    291 	
    292 	b[0] = a[0];
    293 	for(int i = 1; i < n; ++i)
    294 		b[i] = a[i] + b[i - 1];
    295 	build(0, 0, n);
    296 	
    297 	long long res = get(0, n - 1);
    298 	//for(int i = 0; i < n; ++i) cout << get(i, i+1) << ' ';cout << endl;
    299 	for(int i = 0; i < n; ++i){
    300 	    int pos = rp[i];
    301 		upd(pos, n, -a[pos]);
    302 		upd(0, pos, a[pos]);
    303 		res = min(res, get(0, n - 1));
    304 		//for(int i = 0; i < n; ++i) cout << get(i, i+1) << ' ';cout << endl;
    305 	}
    306 	
    307 	cout << res << endl;
    308 	return 0;
    309 }
    310 ```
    311 
    312 [1295F - Good Contest](/contest/1295/problem/F "Educational Codeforces Round 81 (Rated for Div. 2)")
    313 
    314 Idea: [Roms](/profile/Roms "Master Roms")
    315 
    316 **Tutorial**
    317 
    318 Tutorial is loading...
    319 
    320 **Solution (BledDest)**
    321 
    322 ```
    323 #include <bits/stdc++.h>
    324 
    325 using namespace std;
    326 
    327 const int MOD = 998244353;
    328 
    329 int add(int x, int y)
    330 {
    331     x += y;
    332     while(x >= MOD) x -= MOD;
    333     while(x < 0) x += MOD;
    334     return x;
    335 }
    336 
    337 int mul(int x, int y)
    338 {
    339     return (x * 1ll * y) % MOD;
    340 }
    341 
    342 int binpow(int x, int y)
    343 {
    344     int z = 1;
    345     while(y)
    346     {
    347         if(y & 1) z = mul(z, x);
    348         x = mul(x, x);
    349         y >>= 1;
    350     }
    351     return z;
    352 }
    353 
    354 int inv(int x)
    355 {
    356     return binpow(x, MOD - 2);
    357 }
    358 
    359 int divide(int x, int y)
    360 {
    361     return mul(x, inv(y));
    362 }
    363 
    364 typedef vector<int> poly;
    365 
    366 void norm(poly& p)
    367 {
    368     while(p.size() > 0 && p.back() == 0)
    369         p.pop_back();
    370 }
    371 
    372 poly operator +(const poly& a, const poly& b)
    373 {
    374     poly c = a;
    375     while(c.size() < b.size()) c.push_back(0);
    376     for(int i = 0; i < b.size(); i++) c[i] = add(c[i], b[i]);
    377     norm(c);
    378     return c;
    379 }
    380 
    381 poly operator +(const poly& a, int b)
    382 {
    383     return a + poly(1, b);
    384 }
    385 
    386 poly operator +(int a, const poly& b)
    387 {
    388     return b + a;
    389 }
    390 
    391 poly operator *(const poly& a, int b)
    392 {
    393     poly c = a;                               
    394     for(int i = 0; i < c.size(); i++) c[i] = mul(c[i], b);
    395     norm(c);
    396     return c;
    397 }
    398 
    399 poly operator /(const poly& a, int b)
    400 {   
    401     return a * inv(b);
    402 }
    403 
    404 poly operator *(const poly& a, const poly& b)
    405 {
    406     poly c(a.size() + b.size() - 1);
    407     for(int i = 0; i < a.size(); i++)
    408         for(int j = 0; j < b.size(); j++)
    409             c[i + j] = add(c[i + j], mul(a[i], b[j]));
    410 
    411     norm(c);
    412     return c;
    413 }
    414 
    415 poly interpolate(const vector<int>& x, const vector<int>& y)
    416 {
    417     int n = int(x.size()) - 1;
    418     vector<vector<int> > f(n + 1);
    419     f[0] = y;
    420     for(int i = 1; i <= n; i++)
    421         for(int j = 0; j <= n - i; j++)
    422             f[i].push_back(divide(add(f[i - 1][j + 1], -f[i - 1][j]), add(x[i + j], -x[j])));
    423     
    424     poly cur = poly(1, 1);
    425     poly res;
    426     for(int i = 0; i <= n; i++)
    427     {
    428         res = res + cur * f[i][0];
    429         cur = cur * poly({add(0, -x[i]), 1});
    430     }
    431 
    432     return res;
    433 }
    434 
    435 int eval(const poly& a, int x)
    436 {
    437     int res = 0;
    438     for(int i = int(a.size()) - 1; i >= 0; i--)
    439         res = add(mul(res, x), a[i]);
    440     return res;
    441 }
    442 
    443 poly sumFromL(const poly& a, int L, int n)
    444 {
    445     vector<int> x;
    446     for(int i = 0; i <= n; i++)
    447         x.push_back(L + i);
    448     vector<int> y;
    449     int cur = 0;
    450     for(int i = 0; i <= n; i++)
    451     {
    452         cur = add(cur, eval(a, x[i]));
    453         y.push_back(cur);
    454     }
    455     return interpolate(x, y);
    456 }
    457 
    458 int sumOverSegment(const poly& a, int L, int R)
    459 {
    460     return eval(sumFromL(a, L, a.size()), R - 1);
    461 }
    462 
    463 int main() {
    464     int n;
    465     cin >> n;
    466     vector<int> L(n), R(n);
    467     for(int i = 0; i < n; i++)
    468     {
    469         cin >> L[i] >> R[i];
    470         R[i]++;
    471     }
    472     reverse(L.begin(), L.end());
    473     reverse(R.begin(), R.end());
    474 
    475     vector<int> coord = {0, MOD - 2};
    476     for(int i = 0; i < n; i++)
    477     {
    478         coord.push_back(L[i]);
    479         coord.push_back(R[i]);
    480     }
    481     sort(coord.begin(), coord.end());
    482     coord.erase(unique(coord.begin(), coord.end()), coord.end());
    483     vector<int> cL = coord, cR = coord;
    484     cL.pop_back();
    485     cR.erase(cR.begin());
    486     int cnt = coord.size() - 1;
    487     vector<poly> cur(cnt);
    488     for(int i = 0; i < cnt; i++)
    489         if(cL[i] >= L[0] && cR[i] <= R[0])
    490             cur[i] = poly(1, inv(R[0] - L[0]));
    491     for(int i = 1; i < n; i++)
    492     {
    493         vector<poly> nxt(cnt);        
    494         int curSum = 0;
    495         for(int j = 0; j < cnt; j++)
    496         {
    497             nxt[j] = sumFromL(cur[j], cL[j], i) + curSum;
    498             curSum = add(curSum, sumOverSegment(cur[j], cL[j], cR[j]));    
    499         }
    500         for(int j = 0; j < cnt; j++)
    501             nxt[j] = nxt[j] * (cL[j] >= L[i] && cR[j] <= R[i] ? inv(R[i] - L[i]) : 0);
    502         cur = nxt;
    503     }
    504     int ans = 0;
    505     for(int i = 0; i < cnt; i++)
    506         ans = add(ans, sumOverSegment(cur[i], cL[i], cR[i]));
    507 
    508     cout << ans << endl;
    509 }
    510 ```