codeforces-scrape

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

1997.md (8309B)


      1 Source: https://codeforces.com/blog/entry/132154
      2 
      3 [1997A - Strong Password](/contest/1997/problem/A "Educational Codeforces Round 168 (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 void solve()
     19 {
     20 	string s;
     21 	cin >> s;
     22 	int n = s.size();
     23 	int idx = -1;
     24 	for(int i = 0; i + 1 < n; i++)
     25 		if(s[i] == s[i + 1])
     26 			idx = i;
     27 	if(idx == -1)
     28 	{
     29 		if(s.back() == 'a') cout << (s + "b") << endl;
     30 		else cout << (s + "a") << endl;
     31 	}
     32 	else
     33 	{
     34 		string t = "a";
     35 		if(s[idx] == 'a') t = "b";
     36 		cout << s.substr(0, idx + 1) + t + s.substr(idx + 1) << endl;
     37 	}
     38 }
     39  
     40 int main()
     41 {
     42 	int t;
     43 	cin >> t;
     44 	for(int i = 0; i < t; i++)
     45 		solve();
     46 }
     47 ```
     48 
     49 [1997B - Make Three Regions](/contest/1997/problem/B "Educational Codeforces Round 168 (Rated for Div. 2)")
     50 
     51 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
     52 
     53 **Tutorial**
     54 
     55 Tutorial is loading...
     56 
     57 **Solution (Neon)**
     58 
     59 ```
     60 #include <bits/stdc++.h>
     61  
     62 using namespace std;
     63  
     64 int main() {
     65   int t;
     66   cin >> t;
     67   while (t--) {
     68     int n;
     69     cin >> n;
     70     vector<string> s(2);
     71     for (auto& x : s) cin >> x;
     72     int ans = 0;
     73     for (int i = 1; i < n - 1; ++i) {
     74       bool ok = true;
     75       ok &= (s[0][i] == '.' && s[1][i] == '.');
     76       ok &= (s[0][i - 1] != s[1][i - 1]);
     77       ok &= (s[0][i + 1] != s[1][i + 1]);
     78       ok &= (s[0][i - 1] == s[0][i + 1]);
     79       ans += ok;
     80     }
     81     cout << ans << '\n';
     82   }
     83 }
     84 ```
     85 
     86 [1997C - Even Positions](/contest/1997/problem/C "Educational Codeforces Round 168 (Rated for Div. 2)")
     87 
     88 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
     89 
     90 **Tutorial**
     91 
     92 Tutorial is loading...
     93 
     94 **Solution (adedalic)**
     95 
     96 ```
     97 import java.util.LinkedList
     98  
     99 fun main() {
    100     repeat(readln().toInt()) {
    101         val n = readln().toInt()
    102         val s = readln()
    103  
    104         var ans = 0L
    105         val bracketPositions = LinkedList<Int>()
    106         for (i in s.indices) {
    107             var c = s[i]
    108             if (c == '_') {
    109                 c = if (bracketPositions.isEmpty()) '(' else ')'
    110             }
    111             if (c == ')') {
    112                 ans += i - bracketPositions.pollLast()
    113             }
    114             else
    115                 bracketPositions.addLast(i)
    116         }
    117         println(ans)
    118     }
    119 }
    120 ```
    121 
    122 [1997D - Maximize the Root](/contest/1997/problem/D "Educational Codeforces Round 168 (Rated for Div. 2)")
    123 
    124 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    125 
    126 **Tutorial**
    127 
    128 Tutorial is loading...
    129 
    130 **Solution (Neon)**
    131 
    132 ```
    133 #include <bits/stdc++.h>
    134  
    135 using namespace std;
    136  
    137 const int INF = 1e9;
    138  
    139 int main() {
    140   ios::sync_with_stdio(false); cin.tie(0);
    141   int t;
    142   cin >> t;
    143   while (t--) {
    144     int n;
    145     cin >> n;
    146     vector<int> a(n);
    147     for (auto& x : a) cin >> x;
    148     vector<vector<int>> g(n);
    149     for (int i = 1; i < n; ++i) {
    150         int p;
    151         cin >> p;
    152         g[p - 1].push_back(i);
    153     }
    154     
    155     auto check = [&](auto&& self, int v, int x) -> bool {
    156       if (x > INF) return false;
    157       bool isLeaf = true;
    158       if (v) x += max(0, x - a[v]);
    159       for (auto u : g[v]) {
    160         isLeaf = false;
    161         if (!self(self, u, x)) return false;
    162       }
    163       return (!isLeaf || x <= a[v]);
    164     };
    165     
    166     int l = 1, r = INF;
    167     while (l <= r) {
    168       int mid = (l + r) / 2;
    169       if (check(check, 0, mid)) {
    170         l = mid + 1;
    171       } else {
    172         r = mid - 1;
    173       }
    174     }
    175     
    176     cout << a[0] + l - 1 << '\n';
    177   }
    178 }
    179 ```
    180 
    181 [1997E - Level Up](/contest/1997/problem/E "Educational Codeforces Round 168 (Rated for Div. 2)")
    182 
    183 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    184 
    185 **Tutorial**
    186 
    187 Tutorial is loading...
    188 
    189 **Solution 1 (awoo)**
    190 
    191 ```
    192 #include <bits/stdc++.h>
    193 #include "ext/pb_ds/assoc_container.hpp"
    194  
    195 #define forn(i, n) for (int i = 0; i < int(n); i++)
    196  
    197 using namespace __gnu_pbds;
    198 using namespace std;
    199  
    200 template <typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
    201  
    202 struct query{
    203 	int i, j;
    204 };
    205  
    206 int main() {
    207 	cin.tie(0);
    208 	ios::sync_with_stdio(false);
    209 	int n, m;
    210 	cin >> n >> m;
    211 	vector<int> a(n);
    212 	forn(i, n) cin >> a[i];
    213 	vector<vector<query>> q(n + 1);
    214 	forn(j, m){
    215 		int i, x;
    216 		cin >> i >> x;
    217 		--i;
    218 		q[x].push_back({i, j});
    219 	}
    220 	forn(i, n + 1){
    221 		sort(q[i].begin(), q[i].end(), [](const query &a, const query &b){
    222 			return a.i > b.i;
    223 		});
    224 	}
    225 	vector<int> ord(n);
    226 	iota(ord.begin(), ord.end(), 0);
    227 	sort(ord.begin(), ord.end(), [&](int i, int j){
    228 		return a[i] > a[j];
    229 	});
    230 	
    231 	vector<int> cur(n + 1);
    232 	vector<char> ans(m);
    233 	ordered_set<int> alive(ord.begin(), ord.end());
    234 	for (int lvl = 1; lvl <= n; ++lvl){
    235 		for (int k = 1; k <= n; ++k){
    236 			if (cur[k] >= n) break;
    237 			int x = alive.order_of_key(cur[k]);
    238 			int nxt = x + k - 1 >= int(alive.size()) ? n : *alive.find_by_order(x + k - 1);
    239 			while (!q[k].empty() && q[k].back().i <= nxt){
    240 				ans[q[k].back().j] = (a[q[k].back().i] >= lvl);
    241 				q[k].pop_back();
    242 			}
    243 			cur[k] = nxt + 1;
    244 		}
    245 		while (!ord.empty() && a[ord.back()] == lvl){
    246 			alive.erase(ord.back());
    247 			ord.pop_back();
    248 		}
    249 	}
    250 	
    251 	for (auto x : ans) cout << (x ? "YES" : "NO") << '\n';
    252 	return 0;
    253 }
    254 ```
    255 
    256 **Solution 2 (awoo)**
    257 
    258 ```
    259 #include <bits/stdc++.h>
    260  
    261 #define forn(i, n) for (int i = 0; i < int(n); i++)
    262  
    263 using namespace std;
    264  
    265 struct query{
    266 	int i, j;
    267 };
    268  
    269 int main() {
    270 	cin.tie(0);
    271 	ios::sync_with_stdio(false);
    272 	int n, m;
    273 	cin >> n >> m;
    274 	vector<int> a(n);
    275 	forn(i, n) cin >> a[i];
    276 	vector<vector<query>> q(n + 1);
    277 	forn(j, m){
    278 		int i, x;
    279 		cin >> i >> x;
    280 		--i;
    281 		q[x].push_back({i, j});
    282 	}
    283 	forn(i, n + 1) sort(q[i].begin(), q[i].end(), [](const query &a, const query &b){
    284 		return a.i > b.i;
    285 	});
    286 	
    287 	int P = min(1000, n + 1);
    288 	
    289 	vector<char> ans(m);
    290 	for (int k = 1; k < P; ++k){
    291 		int cur = 1;
    292 		int cnt = 0;
    293 		forn(i, n){
    294 			bool fl = false;
    295 			if (a[i] >= cur){
    296 				++cnt;
    297 				fl = true;
    298 				if (cnt == k){
    299 					++cur;
    300 					cnt = 0;
    301 				}
    302 			}
    303 			while (!q[k].empty() && q[k].back().i == i){
    304 				ans[q[k].back().j] = fl;
    305 				q[k].pop_back();
    306 			}
    307 		}
    308 	}
    309 	
    310 	vector<int> sum1(n), sum2(n);
    311 	int p2 = ceil(sqrt(n + 2));
    312 	
    313 	auto add = [&](int i){
    314 		int bl = i / p2;
    315 		for (int j = bl + 1; j * p2 < n; ++j)
    316 			++sum1[j];
    317 		for (int j = i; j < (bl + 1) * p2 && j < n; ++j)
    318 			++sum2[j];
    319 	};
    320 	
    321 	int mx = n / P + 5;
    322 	vector<vector<int>> pos(mx);
    323 	forn(i, n){
    324 		if (a[i] < mx)
    325 			pos[a[i]].push_back(i);
    326 		else
    327 			add(i);
    328 	}
    329 	for (auto &it : pos) reverse(it.begin(), it.end());
    330 	
    331 	for (int k = P; k <= n; ++k){
    332 		while (true){
    333 			int mn = n;
    334 			int who = -1;
    335 			forn(lvl, mx) if (!pos[lvl].empty()){
    336 				int i = pos[lvl].back();
    337 				if (mn < i) continue;
    338 				int cnt = sum1[i / p2] + sum2[i];
    339 				if (a[i] >= cnt / k + 1){
    340 					mn = i;
    341 					who = lvl;
    342 				}
    343 			}
    344 			if (who == -1) break;
    345 			add(mn);
    346 			pos[who].pop_back();
    347 		}
    348 		for (auto it : q[k]){
    349 			int lvl = a[it.i];
    350 			ans[it.j] = (lvl >= mx || pos[lvl].empty() || pos[lvl].back() > it.i);
    351 		}
    352 	}
    353 	
    354 	for (auto x : ans) cout << (x ? "YES" : "NO") << '\n';
    355 	return 0;
    356 }
    357 ```
    358 
    359 [1997F - Chips on a Line](/contest/1997/problem/F "Educational Codeforces Round 168 (Rated for Div. 2)")
    360 
    361 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    362 
    363 **Tutorial**
    364 
    365 Tutorial is loading...
    366 
    367 **Solution (BledDest)**
    368 
    369 ```
    370 #include<bits/stdc++.h>
    371  
    372 using namespace std;
    373  
    374 const int MOD = 998244353;
    375  
    376 int add(int x, int y)
    377 {
    378  	x += y;
    379  	while(x >= MOD) x -= MOD;
    380  	while(x < 0) x += MOD;
    381  	return x;
    382 }
    383  
    384 int mul(int x, int y)
    385 {
    386  	return (x * 1ll * y) % MOD;
    387 }
    388  
    389 int main()
    390 {
    391  	int n, x, m;
    392  	cin >> n >> x >> m;
    393  	vector<int> fib = {0, 1};
    394  	for(int i = 2; i <= 30; i++)
    395  		fib.push_back(fib[i - 1] + fib[i - 2]);
    396  
    397  
    398  	int max_sum = fib[x] * n;
    399  	vector<vector<int>> dp(max_sum + 1, vector<int>(n + 1));
    400  	dp[0][0] = 1;
    401  	for(int i = 1; i <= x; i++)
    402  		for(int j = 0; j < max_sum; j++)
    403  			for(int k = 0; k < n; k++)
    404  			{
    405  			 	if(j + fib[i] <= max_sum)
    406  			 		dp[j + fib[i]][k + 1] = add(dp[j + fib[i]][k + 1], dp[j][k]);
    407  			}
    408 	
    409 	vector<int> cost(max_sum + 1, 1e9);
    410 	cost[0] = 0;
    411 	for(int j = 1; j <= max_sum; j++)
    412 		for(int i = 1; i <= 30; i++)
    413 			if(j >= fib[i])
    414 				cost[j] = min(cost[j], cost[j - fib[i]] + 1);
    415  
    416 	int ans = 0;
    417 	for(int i = 0; i <= max_sum; i++)
    418 		if(cost[i] == m)
    419 			ans = add(ans, dp[i][n]);
    420 	cout << ans << endl;
    421 }
    422 ```