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 ```