codeforces-scrape

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

1841.md (7499B)


      1 Source: https://codeforces.com/blog/entry/117262
      2 
      3 [1841A - Game with Board](/contest/1841/problem/A "Educational Codeforces Round 150 (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 t = int(input())
     15 for i in range(t):
     16     n = int(input())
     17     print('Alice' if n >= 5 else 'Bob')
     18 ```
     19 
     20 [1841B - Keep it Beautiful](/contest/1841/problem/B "Educational Codeforces Round 150 (Rated for Div. 2)")
     21 
     22 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
     23 
     24 **Tutorial**
     25 
     26 Tutorial is loading...
     27 
     28 **Solution (awoo)**
     29 
     30 ```
     31 for _ in range(int(input())):
     32 	q = int(input())
     33 	a = []
     34 	cnt = 0
     35 	for x in map(int, input().split()):
     36 		nw_cnt = cnt + (len(a) > 0 and a[-1] > x)
     37 		if nw_cnt == 0 or (nw_cnt == 1 and x <= a[0]):
     38 			a.append(x)
     39 			cnt = nw_cnt
     40 			print('1', end="")
     41 		else:
     42 			print('0', end="")
     43 	print()
     44 ```
     45 
     46 [1841C - Ranom Numbers](/contest/1841/problem/C "Educational Codeforces Round 150 (Rated for Div. 2)")
     47 
     48 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
     49 
     50 **Tutorial**
     51 
     52 Tutorial is loading...
     53 
     54 **Solution 1 (Neon)**
     55 
     56 ```
     57 #include <bits/stdc++.h>
     58 
     59 using namespace std;
     60 
     61 const int val[] = {1, 10, 100, 1000, 10000};
     62 const int INF = 1e9;
     63 
     64 string s;
     65 int dp[2][5][2];
     66 
     67 int main() {
     68   ios::sync_with_stdio(false); cin.tie(0);
     69   int t;
     70   cin >> t;
     71   while (t--) {
     72     cin >> s;
     73     reverse(s.begin(), s.end());
     74     for (int j = 0; j < 5; ++j)
     75       dp[0][j][0] = dp[0][j][1] = -INF;
     76     dp[0][0][0] = 0;
     77     for (auto c : s) {
     78       int x = c - 'A';
     79       for (int j = 0; j < 5; ++j)
     80         dp[1][j][0] = dp[1][j][1] = -INF;
     81       for (int j = 0; j < 5; ++j) {
     82       	for (int t = 0; t < 2; ++t) {
     83       	  for (int y = 0; y < 5; ++y) {
     84       	  	int nj = max(j, y);
     85       	  	int nt = t + (x != y);
     86       	  	if (nt < 2) dp[1][nj][nt] = max(dp[1][nj][nt], dp[0][j][t] + (y < nj ? -val[y] : val[y]));
     87       	  }	
     88       	}
     89       }
     90       swap(dp[0], dp[1]);
     91     }
     92     int ans = -INF;
     93     for (int j = 0; j < 5; ++j)
     94       ans = max(ans, max(dp[0][j][0], dp[0][j][1]));
     95     cout << ans << '\n';
     96   }
     97 }
     98 ```
     99 
    100 **Solution 2 (BledDest)**
    101 
    102 ```
    103 def replace_char(s, i, c):
    104     return s[:i] + c + s[i + 1:]
    105     
    106 def id(c):
    107     return ord(c) - ord('A')
    108     
    109 def evaluate(s):
    110     t = s[::-1]
    111     ans = 0
    112     max_id = -1
    113     for x in t:
    114         i = id(x)
    115         if max_id > i:
    116             ans -= 10 ** i
    117         else:
    118             ans += 10 ** i
    119         max_id = max(max_id, i)
    120     return ans
    121 
    122 t = int(input())
    123 for i in range(t):
    124     s = input()
    125     candidates = []
    126     for x in ['A', 'B', 'C', 'D', 'E']:
    127         for y in ['A', 'B', 'C', 'D', 'E']:
    128             if not (x in s):
    129                 continue
    130             candidates.append(replace_char(s, s.find(x), y))
    131             candidates.append(replace_char(s, s.rfind(x), y))
    132     print(max(map(evaluate, candidates)))
    133 ```
    134 
    135 [1841D - Pairs of Segments](/contest/1841/problem/D "Educational Codeforces Round 150 (Rated for Div. 2)")
    136 
    137 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    138 
    139 **Tutorial**
    140 
    141 Tutorial is loading...
    142 
    143 **Solution (BledDest)**
    144 
    145 ```
    146 #include<bits/stdc++.h>
    147 
    148 using namespace std;
    149 
    150 bool comp(const pair<int, int>& a, const pair<int, int>& b)
    151 {
    152 	return a.second < b.second;
    153 }
    154 
    155 void solve()
    156 {
    157 	int n;
    158 	scanf("%d", &n);
    159 	vector<pair<int, int>> s(n);
    160 	for(int i = 0; i < n; i++)
    161 		scanf("%d %d", &s[i].first, &s[i].second);
    162 	
    163 	vector<pair<int, int>> pairs;
    164 	for(int i = 0; i < n; i++)
    165 		for(int j = i + 1; j < n; j++)
    166 			if(max(s[i].first, s[j].first) <= min(s[i].second, s[j].second))
    167 				pairs.push_back(make_pair(min(s[i].first, s[j].first), max(s[i].second, s[j].second)));
    168 			
    169 	int cnt_pairs = 0;
    170 	sort(pairs.begin(), pairs.end(), comp);
    171 	int last_pos = -1;
    172 	for(auto x : pairs)
    173 		if(x.first > last_pos)
    174 		{
    175 			cnt_pairs++;
    176 			last_pos = x.second;
    177 		}
    178 		
    179 	printf("%d\n", n - cnt_pairs * 2);
    180 }
    181 
    182 int main()
    183 {
    184 	int t;
    185 	scanf("%d", &t);
    186 	for(int i = 0; i < t; i++) solve();
    187 }
    188 ```
    189 
    190 [1841E - Fill the Matrix](/contest/1841/problem/E "Educational Codeforces Round 150 (Rated for Div. 2)")
    191 
    192 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    193 
    194 **Tutorial**
    195 
    196 Tutorial is loading...
    197 
    198 **Solution (awoo)**
    199 
    200 ```
    201 #include <bits/stdc++.h>
    202 
    203 #define forn(i, n) for (int i = 0; i < int(n); i++)
    204 
    205 using namespace std;
    206 
    207 struct seg{
    208 	int l, r;
    209 };
    210 
    211 bool operator <(const seg &a, const seg &b){
    212 	return a.l < b.l;
    213 }
    214 
    215 int main() {
    216 	int t;
    217 	scanf("%d", &t);
    218 	while (t--){
    219 		int n;
    220 		scanf("%d", &n);
    221 		vector<int> a(n);
    222 		forn(i, n) scanf("%d", &a[i]);
    223 		long long m;
    224 		scanf("%lld", &m);
    225 		map<seg, int> used;
    226 		used[{0, n}] = n;
    227 		vector<int> ord(n);
    228 		iota(ord.begin(), ord.end(), 0);
    229 		sort(ord.begin(), ord.end(), [&a](int x, int y){
    230 			return a[x] > a[y];
    231 		});
    232 		long long ans = 0;
    233 		int j = 0;
    234 		vector<long long> cnt(n + 1);
    235 		for (int i = n; i >= 0; --i){
    236 			while (j < n && a[ord[j]] >= i){
    237 				auto it = used.upper_bound({ord[j], -1});
    238 				--it;
    239 				auto tmp = it->first;
    240 				cnt[tmp.r - tmp.l] += it->second - i;
    241 				used.erase(it);
    242 				if (tmp.l != ord[j])
    243 					used[{tmp.l, ord[j]}] = i;
    244 				if (tmp.r != ord[j] + 1)
    245 					used[{ord[j] + 1, tmp.r}] = i;
    246 				++j;
    247 			}
    248 		}
    249 		for (int i = n; i > 0; --i){
    250 			long long t = min(cnt[i], m / i);
    251 			ans += t * 1ll * (i - 1);
    252 			m -= t * 1ll * i;
    253 			if (t != cnt[i] && m > 0){
    254 				ans += m - 1;
    255 				m = 0;
    256 			}
    257 		}
    258 		printf("%lld\n", ans);
    259 	}
    260 	return 0;
    261 }
    262 ```
    263 
    264 [1841F - Monocarp and a Strategic Game](/contest/1841/problem/F "Educational Codeforces Round 150 (Rated for Div. 2)")
    265 
    266 Idea: [TheWayISteppedOutTheCar](/profile/TheWayISteppedOutTheCar "Grandmaster TheWayISteppedOutTheCar") and [BledDest](/profile/BledDest "International Grandmaster BledDest")
    267 
    268 **Tutorial**
    269 
    270 Tutorial is loading...
    271 
    272 **Solution (TheWayISteppedOutTheCar)**
    273 
    274 ```
    275 #include <iostream>
    276 #include <algorithm>
    277 using namespace std;
    278 #define int long long
    279 #define x first
    280 #define y second
    281 const int MAXN = 2e6 + 16;
    282 int a[MAXN], b[MAXN];
    283 pair<int, int> v[MAXN];
    284 int section(pair<int, int> a) {
    285     if (a.x > 0 && a.y >= 0)
    286         return 0;
    287     else if (a.x <= 0 && a.y > 0)
    288         return 1;
    289     else if (a.x < 0 && a.y <= 0)
    290         return 2;
    291     else
    292         return 3;
    293 }
    294 bool cmp(pair<int, int> a, pair<int, int> b) {
    295     if (section(a) != section(b))
    296         return section(a) < section(b);
    297     else
    298         return (__int128)a.x * (__int128)b.y - (__int128)a.y * (__int128)b.x > 0;
    299 }
    300 void print(__int128 x) {
    301     if (x < 0) {
    302         putchar('-');
    303         x = -x;
    304     }
    305     if (x > 9) print(x / 10);
    306     putchar(x % 10 + '0');
    307 }
    308 signed main() {
    309     ios_base::sync_with_stdio(false);
    310     
    311     int n;
    312     cin >> n;
    313     for (int i = 0; i < n; ++i) {
    314 		vector<int> t(4);
    315 		for(int j = 0; j < 4; j++)
    316 			cin >> t[j];
    317 		a[i] = t[0] - t[1];
    318 		b[i] = t[2] - t[3];
    319 	}
    320     int it = 0;
    321     __int128 sx = 0, sy = 0;
    322     for (int i = 0; i < n; ++i) {
    323         v[i << 1].x = a[it];
    324         v[i << 1].y = b[it];
    325         ++it;
    326         v[i << 1 ^ 1].x = -v[i << 1].x;
    327         v[i << 1 ^ 1].y = -v[i << 1].y;
    328         if (!v[i << 1].x && !v[i << 1].y) {
    329             --i, --n;
    330             continue;
    331         }
    332         if (v[i << 1].y < 0 || (!v[i << 1].y && v[i << 1].x < 0))
    333             sx += v[i << 1].x, sy += v[i << 1].y;
    334     }
    335     sort(v, v + 2 * n, cmp);
    336     __int128 ans = sx * sx + sy * sy;
    337     for (int i = 0; i < 2 * n; ++i) {
    338         sx += v[i].x;
    339         sy += v[i].y;
    340         ans = std::max(ans, sx * sx + sy * sy);
    341     }
    342     print(ans);
    343 
    344     return 0;
    345 }
    346 ```