codeforces-scrape

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

2204.md (9951B)


      1 Source: https://codeforces.com/blog/entry/152150
      2 
      3 [2204A - Passing the Ball](/contest/2204/problem/A "Educational Codeforces Round 188 (Rated for Div. 2)")
      4 
      5 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
      6 
      7 **Tutorial**
      8 
      9 Tutorial is loading...
     10 
     11 **Solution (BledDest)**
     12 
     13 ```
     14 #include<bits/stdc++.h>
     15  
     16 using namespace std;
     17  
     18 int main()
     19 {
     20     int t;
     21     cin >> t;
     22     for(int i = 0; i < t; i++)
     23     {
     24         int n;
     25         cin >> n;
     26         string s;
     27         cin >> s;             
     28         cout << s.find("RL") + 2 << endl;
     29     }
     30     return 0;
     31 }
     32 ```
     33 
     34 [2204B - Right Maximum](/contest/2204/problem/B "Educational Codeforces Round 188 (Rated for Div. 2)")
     35 
     36 Idea: [fcspartakm](/profile/fcspartakm "Candidate Master fcspartakm")
     37 
     38 **Tutorial**
     39 
     40 Tutorial is loading...
     41 
     42 **Solution (BledDest)**
     43 
     44 ```
     45 #include<bits/stdc++.h>
     46  
     47 using namespace std;
     48 
     49 void solve()
     50 {
     51     int n;
     52     cin >> n;
     53     vector<int> a(n);
     54     for(int i = 0; i < n; i++) cin >> a[i];
     55     int mx = 0;
     56     int ans = 0;
     57     for(int i = 0; i < n; i++)
     58     {
     59         if(a[i] >= mx) ans++;
     60         mx = max(mx, a[i]);
     61     }
     62     cout << ans << "\n";
     63 }
     64  
     65 int main()
     66 {
     67     ios_base::sync_with_stdio(0);
     68     cin.tie(0);
     69     int t;
     70     cin >> t;
     71     for(int i = 0; i < t; i++)
     72         solve();
     73     return 0;
     74 }
     75 ```
     76 
     77 [2204C - Spring](/contest/2204/problem/C "Educational Codeforces Round 188 (Rated for Div. 2)")
     78 
     79 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
     80 
     81 **Tutorial**
     82 
     83 Tutorial is loading...
     84 
     85 **Solution (BledDest)**
     86 
     87 ```
     88 #include<bits/stdc++.h>
     89  
     90 using namespace std;
     91  
     92 long long getOne(long long a, long long m)
     93 {
     94     return m / a;
     95 }
     96  
     97 long long getTwo(long long a, long long b, long long m)
     98 {
     99     return m / lcm(a, b);    
    100 }
    101  
    102 long long getThree(long long a, long long b, long long c, long long m)
    103 {
    104     return m / lcm(lcm(a, b), c);
    105 }
    106  
    107 long long get(long long a, long long b, long long c, long long m)
    108 {
    109     long long c1 = getOne(a, m);
    110     long long c2 = getTwo(a, b, m) + getTwo(a, c, m);
    111     long long c3 = getThree(a, b, c, m);
    112     return (c1 - c2 + c3) * 6 + (c2 - 2 * c3) * 3 + c3 * 2;
    113 }
    114  
    115 void solve()
    116 {
    117     long long a, b, c, m;
    118     cin >> a >> b >> c >> m;                                                                      
    119     cout << get(a, b, c, m) << " " << get(b, a, c, m) << " " << get(c, a, b, m) << endl;
    120 }
    121  
    122 int main()
    123 {
    124     ios_base::sync_with_stdio(0);
    125     cin.tie(0);
    126     int t;
    127     cin >> t;
    128     for(int i = 0; i < t; i++)
    129         solve();
    130     return 0;
    131 }
    132 ```
    133 
    134 [2204D - Alternating Path](/contest/2204/problem/D "Educational Codeforces Round 188 (Rated for Div. 2)")
    135 
    136 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    137 
    138 **Tutorial**
    139 
    140 Tutorial is loading...
    141 
    142 **Solution (awoo)**
    143 
    144 ```
    145 #include <bits/stdc++.h>
    146  
    147 #define forn(i, n) for (int i = 0; i < int(n); i++)
    148  
    149 using namespace std;
    150  
    151  
    152 int main() {
    153 	cin.tie(0);
    154 	ios::sync_with_stdio(false);
    155 	int t;
    156 	cin >> t;
    157 	while (t--){
    158 		int n, m;
    159 		cin >> n >> m;
    160 		vector<vector<int>> g(n);
    161 		forn(i, m){
    162 			int v, u;
    163 			cin >> v >> u;
    164 			--v, --u;
    165 			g[v].push_back(u);
    166 			g[u].push_back(v);
    167 		}
    168 		vector<int> clr(n, -1);
    169 		int ans = 0;
    170 		forn(i, n) if (clr[i] == -1){
    171 			queue<int> q;
    172 			q.push(i);
    173 			clr[i] = 0;
    174 			vector<int> cnt(2);
    175 			bool ok = true;
    176 			while (!q.empty()){
    177 				int v = q.front();
    178 				q.pop();
    179 				++cnt[clr[v]];
    180 				for (int u : g[v]){
    181 					if (clr[u] == clr[v])
    182 						ok = false;
    183 					else if (clr[u] == -1){
    184 						clr[u] = clr[v] ^ 1;
    185 						q.push(u);
    186 					}
    187 				}
    188 			}
    189 			if (ok) ans += max(cnt[0], cnt[1]);
    190 		}
    191 		cout << ans << '\n';
    192 	}
    193 	return 0;
    194 }
    195 ```
    196 
    197 [2204E - Sum of Digits (and Again)](/contest/2204/problem/E "Educational Codeforces Round 188 (Rated for Div. 2)")
    198 
    199 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    200 
    201 **Tutorial**
    202 
    203 Tutorial is loading...
    204 
    205 **Solution (BledDest)**
    206 
    207 ```
    208 #include<bits/stdc++.h>
    209  
    210 using namespace std;
    211  
    212 int f(int x)
    213 {
    214     int res = 0;
    215     while(x != 0)
    216     {
    217         res += x % 10;
    218         x /= 10;
    219     }
    220     return res;
    221 }
    222  
    223 void solve()
    224 {
    225     string s;
    226     cin >> s;
    227     int n = s.size();
    228     if(n == 1)
    229     {
    230         cout << s << "\n";
    231         return;
    232     }
    233     vector<int> cnt(10);
    234     int sum_digits = 0;
    235     for(auto x : s) 
    236     {
    237         cnt[x - '0']++;
    238         sum_digits += x - '0';
    239     }
    240     for(int x = 1; x <= n * 9; x++)
    241     {
    242         int nx = x;
    243         string sx = to_string(nx);
    244         while(nx > 9)
    245         {
    246             nx = f(nx);
    247             sx += to_string(nx);    
    248         }
    249         //cout << x << " " << sx << endl;               
    250         vector<int> need_cnt(10);
    251         int sum_digits_x = 0;
    252         for(auto y : sx)
    253         {
    254             need_cnt[y - '0']++;
    255             sum_digits_x += y - '0';
    256         }
    257         bool can = true;
    258         for(int i = 0; i <= 9; i++)
    259             if(need_cnt[i] > cnt[i]) can = false;
    260         if(sum_digits - sum_digits_x != x)
    261             can = false;
    262         if(can)
    263         {
    264             string res = "";
    265             for(int i = 9; i >= 0; i--)
    266             {
    267                 for(int j = 0; j < cnt[i] - need_cnt[i]; j++)
    268                     res.push_back(char('0' + i));
    269             }
    270             res += sx;
    271             cout << res << endl;
    272             return;
    273         }
    274     }
    275 }
    276  
    277 int main()
    278 {
    279     ios_base::sync_with_stdio(0);
    280     cin.tie(0);
    281     int t;
    282     cin >> t;
    283     for(int i = 0; i < t; i++)
    284         solve();
    285     return 0;
    286 }
    287 ```
    288 
    289 [2204F - Sum of Fractions](/contest/2204/problem/F "Educational Codeforces Round 188 (Rated for Div. 2)")
    290 
    291 Idea: [adedalic](/profile/adedalic "International Master adedalic")
    292 
    293 **Tutorial**
    294 
    295 Tutorial is loading...
    296 
    297 **Solution (adedalic)**
    298 
    299 ```
    300 #include<bits/stdc++.h>
    301  
    302 using namespace std;
    303  
    304 #define fore(i, l, r) for(int i = int(l); i < int(r); i++)
    305 #define sz(a) int((a).size())
    306  
    307 #define x first
    308 #define y second
    309  
    310 typedef long long li;
    311 typedef long double ld;
    312 typedef pair<int, int> pt;
    313  
    314 template<class A, class B> ostream& operator <<(ostream& out, const pair<A, B> &p) {
    315 	return out << "(" << p.x << ", " << p.y << ")";
    316 }
    317 template<class A> ostream& operator <<(ostream& out, const vector<A> &v) {
    318 	fore(i, 0, sz(v)) {
    319 		if(i) out << " ";
    320 		out << v[i];
    321 	}
    322 	return out;
    323 }
    324  
    325 const int INF = int(1e9);
    326 const li INF64 = li(1e18);
    327 const ld EPS = 1e-9;
    328  
    329 const int MOD = 998'244'353;
    330  
    331 int add(int a, int b) {
    332 	a += b;
    333 	while (a >= MOD)
    334 		a -= MOD;
    335 	while (a < 0)
    336 		a += MOD;
    337 	return a;
    338 }
    339 int mul(int a, int b) {
    340 	return a * 1ll * b % MOD;
    341 }
    342 int binPow(int a, int k) {
    343 	int ans = 1;
    344 	while (k > 0) {
    345 		if (k & 1)
    346 			ans = mul(ans, a);
    347 		a = mul(a, a);
    348 		k >>= 1;
    349 	}
    350 	return ans;
    351 }
    352  
    353 int n, m;
    354 vector<int> a, k;
    355  
    356 inline bool read() {
    357 	if(!(cin >> n >> m))
    358 		return false;
    359 	a.resize(n);
    360 	fore (i, 0, n)
    361 		cin >> a[i];
    362 	k.resize(m);
    363 	fore (i, 0, m)
    364 		cin >> k[i];
    365 	return true;
    366 }
    367  
    368 inline void solve() {
    369 	vector<int> lf(n, -1), rg(n, n);
    370 	vector<int> st;
    371 	fore (i, 0, n) {
    372 		while (!st.empty() && a[st.back()] > a[i])
    373 			st.pop_back();
    374 		if (!st.empty())
    375 			lf[i] = st.back();
    376 		st.push_back(i);
    377 	}
    378 	st.clear();
    379 	for (int i = n - 1; i >= 0; i--) {
    380 		while (!st.empty() && a[st.back()] >= a[i])
    381 			st.pop_back();
    382 		if (!st.empty())
    383 			rg[i] = st.back();
    384 		st.push_back(i);
    385 	}
    386  
    387 	int commonSum = 0;
    388 	vector<int> la(m + 1), lk(m + 1), ra(m + 1), rk(m + 1);
    389  
    390 	//[l, r)
    391 	auto addSeg = [](vector<int> &pS, int l, int r, int val) {
    392 		pS[l] = add(pS[l], val);
    393 		pS[r] = add(pS[r], -val);
    394 	};
    395  
    396 	fore (i, 0, n) {
    397 		int cnt = mul(i - lf[i], rg[i] - i);
    398 		int rem = add(mul(i + 1, n - i), -cnt);
    399 		int ia = binPow(a[i], MOD - 2);
    400 		commonSum = add(commonSum, mul(rem, ia));
    401  
    402 		int p = lower_bound(k.begin(), k.end(), a[i]) - k.begin();
    403 		addSeg(la, 0, p, mul(cnt, ia));
    404 		addSeg(lk, 0, p, mul(cnt, ia));
    405 		addSeg(ra, p, m, cnt);
    406 		addSeg(rk, p, m, mul(cnt, add(2, -a[i])));
    407 	}
    408 	fore (i, 0, m) {
    409 		la[i + 1] = add(la[i + 1], la[i]);
    410 		lk[i + 1] = add(lk[i + 1], lk[i]);
    411 		ra[i + 1] = add(ra[i + 1], ra[i]);
    412 		rk[i + 1] = add(rk[i + 1], rk[i]);
    413 	}
    414  
    415 	fore (i, 0, m) {
    416 		int ans = commonSum;
    417 		ans = add(ans, mul(add(la[i], ra[i]), k[i]));
    418 		ans = add(ans, add(lk[i], rk[i]));
    419 		cout << ans << '\n';
    420 	}
    421 }
    422  
    423 int main() {
    424 #ifdef _DEBUG
    425 	freopen("input.txt", "r", stdin);
    426 	int tt = clock();
    427 #endif
    428 	ios_base::sync_with_stdio(false);
    429 	cin.tie(0), cout.tie(0);
    430 	cout << fixed << setprecision(15);
    431 	
    432 	if(read()) {
    433 		solve();
    434 		
    435 #ifdef _DEBUG
    436 		cerr << "TIME = " << clock() - tt << endl;
    437 		tt = clock();
    438 #endif
    439 	}
    440 	return 0;
    441 }
    442 ```
    443 
    444 [2204G - Grid Path](/contest/2204/problem/G "Educational Codeforces Round 188 (Rated for Div. 2)")
    445 
    446 Idea: [Roms](/profile/Roms "Master Roms")
    447 
    448 **Tutorial**
    449 
    450 Tutorial is loading...
    451 
    452 **Solution (Neon)**
    453 
    454 ```
    455 #include <bits/stdc++.h>
    456  
    457 using namespace std;
    458  
    459 #define forn(i, n) for (int i = 0; i < int(n); ++i)
    460  
    461 const int K = 301;
    462  
    463 using mat = vector<vector<int>>;
    464  
    465 int n, m, mod, k;
    466  
    467 int add(int x, int y) {
    468   x += y;
    469   if (x >= mod) x -= mod;
    470   return x;
    471 }
    472  
    473 int mul(int x, int y) {
    474   return x * 1LL * y % mod;
    475 }
    476  
    477 unsigned long long aux[K][K];
    478  
    479 mat mul(mat a, mat b) {
    480   mat b2(k, vector<int>(k));
    481   forn(x, k) forn(y, k) b2[x][y] = b[y][x];
    482   mat c(k, vector<int>(k));
    483   forn(x, k) forn(y, k) {
    484     aux[x][y] = 0;
    485     forn(z, k) {
    486       aux[x][y] += a[x][z] * 1ll * b2[y][z];
    487       if((z & 15) == 15)
    488         aux[x][y] %= mod;
    489     }
    490     c[x][y] = aux[x][y] % mod;
    491   }
    492   return c;
    493 }
    494  
    495 mat binpow(mat a, int b) {
    496   mat c(k, vector<int>(k));
    497   forn(i, k) c[i][i] = 1;
    498   while (b) {
    499     if (b & 1) c = mul(c, a);
    500     a = mul(a, a);
    501     b >>= 1;
    502   }
    503   return c;
    504 }
    505  
    506 int main() {
    507   cin >> n >> m >> mod;
    508   k = 2 * m + 1;
    509   mat a(k, vector<int>(k));
    510   a[k - 1][k - 1] = 1;
    511   forn(i, m) forn(f, 2) {
    512     for (int l = f ? 0 : i; l <= i; ++l) {
    513       for (int r = i; r < m; ++r) {
    514         a[i * 2 + f][k - 1] = add(a[i * 2 + f][k - 1], 1);
    515         for (int j = l; j <= r; ++j) {
    516           a[i * 2 + f][j * 2 + (j == l)] = add(a[i * 2 + f][j * 2 + (j == l)], 1);
    517         }
    518       }
    519     }
    520   }
    521   auto res = binpow(a, n);
    522   cout << res[1][k - 1] << endl;
    523 }
    524 ```