codeforces-scrape

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

1334.md (13216B)


      1 Source: https://codeforces.com/blog/entry/75877
      2 
      3 [1334A - Level Statistics](/contest/1334/problem/A "Educational Codeforces Round 85 (Rated for Div. 2)")
      4 
      5 Idea: [awoo](/profile/awoo "Grandmaster awoo")
      6 
      7 **Tutorial**
      8 
      9 Tutorial is loading...
     10 
     11 **Solution (pikmike)**
     12 
     13 ```
     14 #include <bits/stdc++.h>
     15 
     16 #define forn(i, n) for (int i = 0; i < int(n); i++)
     17 
     18 using namespace std;
     19 
     20 int main() {
     21 	int tc;
     22 	scanf("%d", &tc);
     23 	while (tc--){
     24 		int n;
     25 		scanf("%d", &n);
     26 		int p = 0, c = 0;
     27 		bool fl = true;
     28 		forn(i, n){
     29 			int x, y;
     30 			scanf("%d%d", &x, &y);
     31 			if (x < p || y < c || y - c > x - p)
     32 				fl = false;
     33 			p = x, c = y;
     34 		}
     35 		puts(fl ? "YES" : "NO");
     36 	}
     37 	return 0;
     38 }
     39 ```
     40 
     41 [1334B - Middle Class](/contest/1334/problem/B "Educational Codeforces Round 85 (Rated for Div. 2)")
     42 
     43 Idea: [adedalic](/profile/adedalic "International Master adedalic")
     44 
     45 **Tutorial**
     46 
     47 Tutorial is loading...
     48 
     49 **Solution (adedalic)**
     50 
     51 ```
     52 fun main() {
     53     val T = readLine()!!.toInt()
     54     for (tc in 1..T) {
     55         val (n, x) = readLine()!!.split(' ').map { it.toInt() }
     56         val a = readLine()!!.split(' ').map { it.toInt() }.sortedDescending()
     57 
     58         var cnt = 0
     59         var sum = 0L
     60         while (cnt < n && sum + a[cnt] >= (cnt + 1) * x.toLong()) {
     61             sum += a[cnt]
     62             cnt++
     63         }
     64         println(cnt)
     65     }
     66 }
     67 ```
     68 
     69 [1334C - Circle of Monsters](/contest/1334/problem/C "Educational Codeforces Round 85 (Rated for Div. 2)")
     70 
     71 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
     72 
     73 **Tutorial**
     74 
     75 Tutorial is loading...
     76 
     77 **Solution (Ne0n25)**
     78 
     79 ```
     80 #include <bits/stdc++.h>
     81 
     82 using namespace std;
     83 
     84 #define forn(i, n) for (int i = 0; i < int(n); ++i)
     85 
     86 typedef long long li;
     87 
     88 const int N = 300 * 1000 + 13;
     89 
     90 int n;
     91 li a[N], b[N];
     92 
     93 void solve() {
     94 	scanf("%d", &n);
     95 	forn(i, n) scanf("%lld%lld", &a[i], &b[i]);
     96 	
     97 	li ans = 0, mn = 1e18;
     98 	forn(i, n) {
     99 		int ni = (i + 1) % n;
    100 		li val = min(a[ni], b[i]);
    101 		ans += a[ni] - val;
    102 		mn = min(mn, val);
    103 	}
    104 	ans += mn;
    105 	printf("%lld\n", ans);
    106 }
    107 
    108 int main() {
    109 	int T;
    110 	scanf("%d", &T);
    111 	forn(i, T)
    112 		solve();
    113 }
    114 ```
    115 
    116 [1334D - Minimum Euler Cycle](/contest/1334/problem/D "Educational Codeforces Round 85 (Rated for Div. 2)")
    117 
    118 Idea: [adedalic](/profile/adedalic "International Master adedalic")
    119 
    120 **Tutorial**
    121 
    122 Tutorial is loading...
    123 
    124 **Solution (adedalic)**
    125 
    126 ```
    127 #include<bits/stdc++.h>
    128 
    129 using namespace std;
    130 
    131 #define fore(i, l, r) for(int i = int(l); i < int(r); i++)
    132 #define sz(a) int((a).size())
    133 
    134 #define x first
    135 #define y second
    136 
    137 typedef long long li;
    138 typedef long double ld;
    139 typedef pair<int, int> pt;
    140 
    141 int n;
    142 li l, r;
    143 
    144 inline bool read() {
    145 	if(!(cin >> n >> l >> r))
    146 		return false;
    147 	return true;
    148 }
    149 
    150 bool intersect(li l1, li r1, li l2, li r2) {
    151 	return min(r1, r2) > max(l1, l2);
    152 }
    153 
    154 vector<int> ans;
    155 
    156 void calc(int lf, int rg, li &id) {
    157 	if(lf == rg) return;
    158 	
    159 	if(intersect(l, r, id, id + 2 * (rg - lf))) {
    160 		fore(to, lf + 1, rg + 1) {
    161 			if(l <= id && id < r)
    162 				ans.push_back(lf);
    163 			id++;
    164 			
    165 			if(l <= id && id < r)
    166 				ans.push_back(to);
    167 			id++;
    168 		}
    169 	} else
    170 		id += 2 * (rg - lf);
    171 	
    172 	calc(lf + 1, rg, id);
    173 	
    174 	if(lf == 0) {
    175 		if(l <= id && id < r)
    176 			ans.push_back(lf);
    177 		id++;
    178 	}
    179 }
    180 
    181 inline void solve() {
    182 	ans.clear();
    183 	li id = 0;
    184 	l--;
    185 	calc(0, n - 1, id);
    186 	
    187 	assert(sz(ans) == r - l);
    188 	assert(id == n * li(n - 1) + 1);
    189 	
    190 	for(int v : ans)
    191 		cout << v + 1 << " ";
    192 	cout << endl;
    193 }
    194 
    195 int main() {
    196 #ifdef _DEBUG
    197 	freopen("input.txt", "r", stdin);
    198 	int tt = clock();
    199 #endif
    200 	ios_base::sync_with_stdio(false);
    201 	cin.tie(0), cout.tie(0);
    202 	cout << fixed << setprecision(15);
    203 	
    204 	int tc; cin >> tc;
    205 	
    206 	while(tc--) {
    207 		read();
    208 		solve();
    209 		
    210 #ifdef _DEBUG
    211 		cerr << "TIME = " << clock() - tt << endl;
    212 		tt = clock();
    213 #endif
    214 	}
    215 	return 0;
    216 }
    217 ```
    218 
    219 [1334E - Divisor Paths](/contest/1334/problem/E "Educational Codeforces Round 85 (Rated for Div. 2)")
    220 
    221 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    222 
    223 **Tutorial**
    224 
    225 Tutorial is loading...
    226 
    227 **Solution (pikmike)**
    228 
    229 ```
    230 #include <bits/stdc++.h>
    231 
    232 #define forn(i, n) for (int i = 0; i < int(n); i++)
    233 
    234 using namespace std;
    235 
    236 const int MOD = 998244353;
    237 
    238 int add(int a, int b){
    239 	a += b;
    240 	if (a >= MOD)
    241 		a -= MOD;
    242 	if (a < 0)
    243 		a += MOD;
    244 	return a;
    245 }
    246 
    247 int mul(int a, int b){
    248 	return a * 1ll * b % MOD;
    249 }
    250 
    251 int binpow(int a, int b){
    252 	int res = 1;
    253 	while (b){
    254 		if (b & 1)
    255 			res = mul(res, a);
    256 		a = mul(a, a);
    257 		b >>= 1;
    258 	}
    259 	return res;
    260 }
    261 
    262 int main() {
    263 	long long d;
    264 	scanf("%lld", &d);
    265 	int q;
    266 	scanf("%d", &q);
    267 	
    268 	vector<long long> primes;
    269 	for (long long i = 2; i * i <= d; ++i) if (d % i == 0){
    270 		primes.push_back(i);
    271 		while (d % i == 0) d /= i;
    272 	}
    273 	if (d > 1){
    274 		primes.push_back(d);
    275 	}
    276 	
    277 	vector<int> fact(100), rfact(100);
    278 	fact[0] = 1;
    279 	for (int i = 1; i < 100; ++i)
    280 		fact[i] = mul(fact[i - 1], i);
    281 	rfact[99] = binpow(fact[99], MOD - 2);
    282 	for (int i = 98; i >= 0; --i)
    283 		rfact[i] = mul(rfact[i + 1], i + 1);
    284 	
    285 	forn(i, q){
    286 		long long x, y;
    287 		scanf("%lld%lld", &x, &y);
    288 		vector<int> up, dw;
    289 		for (auto p : primes){
    290 			int cnt = 0;
    291 			while (x % p == 0){
    292 				--cnt;
    293 				x /= p;
    294 			}
    295 			while (y % p == 0){
    296 				++cnt;
    297 				y /= p;
    298 			}
    299 			if (cnt < 0) dw.push_back(-cnt);
    300 			else if (cnt > 0) up.push_back(cnt);
    301 		}
    302 		int ans = 1;
    303 		ans = mul(ans, fact[accumulate(up.begin(), up.end(), 0)]);
    304 		for (auto it : up) ans = mul(ans, rfact[it]);
    305 		ans = mul(ans, fact[accumulate(dw.begin(), dw.end(), 0)]);
    306 		for (auto it : dw) ans = mul(ans, rfact[it]);
    307 		printf("%d\n", ans);
    308 	}
    309 	
    310 	return 0;
    311 }
    312 ```
    313 
    314 [1334F - Strange Function](/contest/1334/problem/F "Educational Codeforces Round 85 (Rated for Div. 2)")
    315 
    316 Idea: [Roms](/profile/Roms "Master Roms") и [BledDest](/profile/BledDest "International Grandmaster BledDest")
    317 
    318 **Tutorial**
    319 
    320 Tutorial is loading...
    321 
    322 **Solution (BledDest)**
    323 
    324 ```
    325 #include<bits/stdc++.h>
    326 
    327 using namespace std;
    328 
    329 typedef long long li;
    330 const li INF64 = li(1e18);
    331 const int N = 500043;
    332 
    333 li f[N];
    334 
    335 li get(int x)
    336 {
    337     li ans = 0;    
    338     for (; x >= 0; x = (x & (x + 1)) - 1)
    339         ans += f[x];
    340     return ans;
    341 }
    342 
    343 void inc(int x, li d)
    344 {
    345     for (; x < N; x = (x | (x + 1)))
    346         f[x] += d;    
    347 }
    348 
    349 li get(int l, int r)
    350 {
    351     return get(r) - get(l - 1);
    352 }
    353 
    354 li dp[N];
    355 int a[N], b[N], p[N];
    356 int n, m;
    357 
    358 int main()
    359 {
    360     scanf("%d", &n);
    361     for(int i = 0; i < n; i++)
    362         scanf("%d", &a[i]);
    363     for(int i = 0; i < n; i++)
    364         scanf("%d", &p[i]);
    365     scanf("%d", &m);
    366     for(int i = 0; i < m; i++)
    367         scanf("%d", &b[i]);
    368 
    369     for(int i = 0; i < n; i++)
    370         dp[i] = -INF64;
    371     map<int, vector<int> > pos;
    372     for(int i = 0; i < n; i++)
    373         pos[a[i]].push_back(i);
    374     set<pair<int, int> > q;
    375     for(int i = 0; i < n; i++)
    376         q.insert(make_pair(a[i], i));
    377     
    378     for(auto x : pos[b[0]])
    379         dp[x] = p[x];
    380     while(!q.empty() && q.begin()->first <= b[0])
    381     {
    382         int k = q.begin()->second;
    383         q.erase(q.begin());
    384         if(p[k] > 0)
    385             inc(k, p[k]);
    386     }  
    387 
    388     for(int i = 1; i < m; i++)
    389     {
    390         int i1 = b[i - 1], i2 = b[i];
    391         vector<int> both_pos;
    392         for(auto x : pos[i1])
    393             both_pos.push_back(x);
    394         for(auto x : pos[i2])
    395             both_pos.push_back(x);
    396         li best = -INF64;
    397         int last = -1;
    398         sort(both_pos.begin(), both_pos.end());
    399         for(auto x : both_pos)
    400         {
    401             best += get(last + 1, x);
    402             last = x;
    403             if(a[x] == i1)
    404                 best = max(best, dp[x]);
    405             else
    406                 dp[x] = best + p[x];
    407         }
    408         while(!q.empty() && q.begin()->first <= i2)
    409         {
    410             int k = q.begin()->second;
    411             q.erase(q.begin());
    412             if(p[k] > 0)
    413                 inc(k, p[k]);
    414         }
    415     }
    416 
    417     li best_dp = -INF64;
    418     for(int i = 0; i < n; i++)
    419         if(a[i] == b[m - 1])
    420             best_dp = max(best_dp, dp[i] + get(i + 1, n - 1));
    421     li ans = 0;
    422     for(int i = 0; i < n; i++)
    423         ans += p[i];
    424     ans -= best_dp;
    425     if(ans > li(1e15))
    426         puts("NO");
    427     else     
    428         printf("YES\n%lld\n", ans);
    429     
    430 }
    431 ```
    432 
    433 [1334G - Substring Search](/contest/1334/problem/G "Educational Codeforces Round 85 (Rated for Div. 2)")
    434 
    435 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    436 
    437 **Tutorial**
    438 
    439 Tutorial is loading...
    440 
    441 **Solution (BledDest)**
    442 
    443 ```
    444 #include<bits/stdc++.h>
    445 
    446 using namespace std;
    447 
    448 #define forn(i, n) for(int i = 0; i < n; i++)
    449 #define sz(a) ((int)(a).size())
    450 
    451 const int LOGN = 20;
    452 const int N = (1 << LOGN);
    453 
    454 typedef long double ld;
    455 typedef long long li;
    456 
    457 const ld PI = acos(-1.0);
    458 
    459 struct comp 
    460 {
    461     ld x, y;
    462     comp(ld x = .0, ld y = .0) : x(x), y(y) {}
    463     inline comp conj() { return comp(x, -y); }
    464 };
    465 
    466 inline comp operator +(const comp &a, const comp &b) 
    467 {
    468     return comp(a.x + b.x, a.y + b.y);
    469 }
    470 
    471 inline comp operator -(const comp &a, const comp &b) 
    472 {
    473     return comp(a.x - b.x, a.y - b.y);
    474 }
    475 
    476 inline comp operator *(const comp &a, const comp &b) 
    477 {
    478     return comp(a.x * b.x - a.y * b.y, a.x * b.y + a.y * b.x);
    479 }
    480 
    481 inline comp operator /(const comp &a, const ld &b) 
    482 {
    483     return comp(a.x / b, a.y / b);
    484 }
    485 
    486 vector<comp> w[LOGN];
    487 vector<int> rv[LOGN];
    488 
    489 void precalc() 
    490 {
    491     for(int st = 0; st < LOGN; st++) 
    492     {
    493         w[st].assign(1 << st, comp());
    494         for(int k = 0; k < (1 << st); k++) 
    495         {
    496             double ang = PI / (1 << st) * k;
    497             w[st][k] = comp(cos(ang), sin(ang));
    498         }
    499         
    500         rv[st].assign(1 << st, 0);
    501         if(st == 0) 
    502         {
    503             rv[st][0] = 0;
    504             continue;
    505         }
    506         int h = (1 << (st - 1));
    507         for(int k = 0; k < (1 << st); k++)
    508             rv[st][k] = (rv[st - 1][k & (h - 1)] << 1) | (k >= h);
    509     }
    510 }
    511 
    512 inline void fft(comp a[N], int n, int ln, bool inv) 
    513 {
    514     for(int i = 0; i < n; i++) 
    515     {
    516         int ni = rv[ln][i];
    517         if(i < ni)
    518             swap(a[i], a[ni]);
    519     }
    520     
    521     for(int st = 0; (1 << st) < n; st++) 
    522     {
    523         int len = (1 << st);
    524         for(int k = 0; k < n; k += (len << 1)) 
    525         {
    526             for(int pos = k; pos < k + len; pos++) 
    527             {
    528                 comp l = a[pos];
    529                 comp r = a[pos + len] * (inv ? w[st][pos - k].conj() : w[st][pos - k]);
    530                 
    531                 a[pos] = l + r;
    532                 a[pos + len] = l - r;
    533             }
    534         }
    535     }
    536     
    537     if(inv) for(int i = 0; i < n; i++)
    538         a[i] = a[i] / n;
    539 }
    540 
    541 comp aa[N];
    542 comp bb[N];
    543 comp cc[N];
    544 
    545 inline void multiply(comp a[N], int sza, comp b[N], int szb, comp c[N], int &szc) 
    546 {
    547     int n = 1, ln = 0;
    548     while(n < (sza + szb))
    549         n <<= 1, ln++;
    550     for(int i = 0; i < n; i++)
    551         aa[i] = (i < sza ? a[i] : comp());
    552     for(int i = 0; i < n; i++)
    553         bb[i] = (i < szb ? b[i] : comp());
    554         
    555     fft(aa, n, ln, false);
    556     fft(bb, n, ln, false);
    557     
    558     for(int i = 0; i < n; i++)
    559         cc[i] = aa[i] * bb[i];
    560         
    561     fft(cc, n, ln, true);
    562     
    563     szc = n;
    564     for(int i = 0; i < n; i++)
    565         c[i] = cc[i];
    566 }
    567 
    568 comp a[N];
    569 comp b[N];
    570 comp c[N];
    571 
    572 vector<int> p_function(const vector<int>& v)
    573 {
    574     int n = v.size();
    575     vector<int> p(n);
    576     for(int i = 1; i < n; i++)
    577     {
    578         int j = p[i - 1];
    579         while(j > 0 && v[j] != v[i])
    580             j = p[j - 1];
    581         if(v[j] == v[i])
    582             j++;
    583         p[i] = j;   
    584     }
    585     return p;
    586 }
    587 
    588 int p[26];
    589 char buf[N];
    590 string s, t;
    591 
    592 int main()
    593 {
    594     precalc();                  
    595     for(int i = 0; i < 26; i++)
    596     {
    597         scanf("%d", &p[i]);
    598         p[i]--;
    599     }
    600     scanf("%s", buf);
    601     s = buf;
    602     scanf("%s", buf);
    603     t = buf;
    604 
    605     int n = s.size();
    606     int m = t.size();
    607     vector<int> color(26, 0);
    608     vector<vector<int> > cycles;
    609     for(int i = 0; i < 26; i++)
    610     {
    611         if(color[i])
    612             continue;
    613         vector<int> cycle;
    614         int cc = cycles.size() + 1;
    615         int cur = i;
    616         while(color[cur] == 0)
    617         {
    618             cycle.push_back(cur);
    619             color[cur] = cc;
    620             cur = p[cur];
    621         }
    622         cycles.push_back(cycle);
    623     }
    624 
    625     vector<int> ans(m - n + 1);
    626     vector<int> s1, t1;
    627     for(int i = 0; i < n; i++)
    628         s1.push_back(color[int(s[i] - 'a')]);
    629     for(int i = 0; i < m; i++)
    630         t1.push_back(color[int(t[i] - 'a')]);
    631     vector<int> st = s1;
    632     st.push_back(0);
    633     for(auto x : t1)
    634         st.push_back(x);
    635     vector<int> pf = p_function(st);
    636     for(int i = 0; i < m - n + 1; i++)
    637         if(pf[2 * n + i] == n)
    638             ans[i] = 1;
    639     map<char, comp> m1, m2;
    640     for(auto cur : cycles)
    641     {
    642         int k = cur.size();
    643         for(int i = 0; i < k; i++)
    644         {
    645             ld ang1 = 2 * PI * i / k;
    646             ld ang2 = (PI - 2 * PI * i) / k;
    647             m1[char('a' + cur[i])] = comp(cosl(ang1), sinl(ang1));
    648             m2[char('a' + cur[i])] = comp(cosl(ang2), sinl(ang2));
    649         }
    650     }
    651 
    652     ld ideal = 0;
    653     for(int i = 0; i < n; i++)
    654         ideal += (m1[s[i]] * m2[s[i]]).x;
    655     reverse(s.begin(), s.end());
    656     for(int i = 0; i < n; i++)                  
    657         a[i] = m1[s[i]];                
    658     for(int i = 0; i < m; i++)
    659         b[i] = m2[t[i]];
    660     int szc;
    661     multiply(a, n, b, m, c, szc);
    662     for(int i = 0; i < m - n + 1; i++)
    663         if(fabsl(c[i + n - 1].x - ideal) > 0.01)
    664             ans[i] = 0;
    665     
    666 
    667     for(int i = 0; i < m - n + 1; i++)
    668         printf("%d", ans[i]);
    669     return 0;
    670 }
    671 ```