2230.md (7898B)
1 Source: https://codeforces.com/blog/entry/153834 2 3 [2230A - Optimal Purchase](/contest/2230/problem/A "Educational Codeforces Round 190 (Rated for Div. 2)") 4 5 Idea: [fcspartakm](/profile/fcspartakm "Candidate Master fcspartakm"), preparation: [fcspartakm](/profile/fcspartakm "Candidate Master fcspartakm") 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, a, b = map(int, input().split()) 17 c = n // 3 18 d = n % 3 19 print(min((c + 1) * b, c * b + d * a, n * a)) 20 ``` 21 22 [2230B - Digit String](/contest/2230/problem/B "Educational Codeforces Round 190 (Rated for Div. 2)") 23 24 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest"), preparation: [Neon](/profile/Neon "Candidate Master Neon") 25 26 **Tutorial** 27 28 Tutorial is loading... 29 30 **Solution (BledDest)** 31 32 ``` 33 t = int(input()) 34 for i in range(t): 35 s = input() 36 pref2 = 0 37 suf = 0 38 for x in s: 39 if x == '1' or x == '3': 40 suf += 1 41 ans = pref2 + suf 42 for x in s: 43 if x == '2': 44 pref2 += 1 45 if x == '1' or x == '3': 46 suf -= 1 47 ans = max(ans, pref2 + suf) 48 print(len(s) - ans) 49 ``` 50 51 [2230C - Arrange the Numbers in a Circle](/contest/2230/problem/C "Educational Codeforces Round 190 (Rated for Div. 2)") 52 53 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest"), preparation: [BledDest](/profile/BledDest "International Grandmaster BledDest") 54 55 **Tutorial** 56 57 Tutorial is loading... 58 59 **Solution (BledDest)** 60 61 ``` 62 t = int(input()) 63 for i in range(t): 64 n = int(input()) 65 c = list(map(int, input().split())) 66 67 s = sum(c) 68 ones = 0 69 slots = 0 70 for x in c: 71 if x == 1: 72 ones += 1 73 else: 74 slots += x // 2 - 1 75 if ones == n - 1: 76 slots += 1 77 wasted = max(0, ones - slots) 78 if s - wasted < 3: 79 print(0) 80 else: 81 print(s - wasted) 82 ``` 83 84 [2230D - Good Schedule](/contest/2230/problem/D "Educational Codeforces Round 190 (Rated for Div. 2)") 85 86 Idea: [Neon](/profile/Neon "Candidate Master Neon"), preparation: [Neon](/profile/Neon "Candidate Master Neon") 87 88 **Tutorial** 89 90 Tutorial is loading... 91 92 **Solution (Neon)** 93 94 ``` 95 #include <bits/stdc++.h> 96 97 using namespace std; 98 99 int main() { 100 ios::sync_with_stdio(false); cin.tie(0); 101 int t; 102 cin >> t; 103 while (t--) { 104 int n; 105 cin >> n; 106 vector<int> a(n), b(n); 107 for (auto &x : a) cin >> x, --x; 108 for (auto &x : b) cin >> x, --x; 109 vector<int> pa(n + 1, n), pb(n + 1, n), dp(n + 1, n); 110 long long ans = 0; 111 for (int i = n - 1; i >= 0; --i) { 112 pa[a[i]] = i; 113 pb[b[i]] = i; 114 if (a[i] == b[i]) { 115 int x = a[i] + 1; 116 if (pa[x] == pb[x]) { 117 dp[i] = dp[pa[x]]; 118 } else { 119 dp[i] = min(pa[x], pb[x]); 120 } 121 } 122 if (pa[0] != pb[0]) { 123 ans += min(pa[0], pb[0]) - i; 124 } else { 125 ans += dp[pa[0]] - i; 126 } 127 } 128 cout << ans << '\n'; 129 } 130 } 131 ``` 132 133 [2230E - Minimum Influence](/contest/2230/problem/E "Educational Codeforces Round 190 (Rated for Div. 2)") 134 135 Idea: [adedalic](/profile/adedalic "International Master adedalic"), preparation: [adedalic](/profile/adedalic "International Master adedalic") 136 137 **Tutorial** 138 139 Tutorial is loading... 140 141 **Solution (adedalic)** 142 143 ``` 144 import bisect 145 import sys 146 input = sys.stdin.readline 147 148 INF = int(1e9) + 7 149 A = int(1e6) + 3 150 151 n = int(input()) 152 a = [list(map(int, input().split())) for i in range(2)] 153 154 minVal = [[INF] * A for i in range(2)] 155 pMin = [[INF] * A for i in range(2)] 156 sMin = [[INF] * A for i in range(2)] 157 for k in range(2): 158 for i in range(n): 159 minVal[k][a[k][i]] = min(minVal[k][a[k][i]], a[k ^ 1][i]) 160 161 for v in range(A - 1): 162 pMin[k][v + 1] = min(pMin[k][v], minVal[k][v]) 163 164 for v in range(A - 2, -1, -1): 165 sMin[k][v] = min(sMin[k][v + 1], minVal[k][v]) 166 167 mid = 0 168 for i in range(n): 169 if a[0][mid] + a[1][mid] > a[0][i] + a[1][i]: 170 mid = i 171 172 m = int(input()) 173 t = [list(map(int, input().split())) for i in range(3)] 174 175 def I(val, l, r): 176 if val < l: 177 return 0 178 return min(val, r) 179 180 ans = [] 181 for id in range(m): 182 cur = I(a[0][mid], t[0][id], t[0][id] + t[2][id]) + I(a[1][mid], t[1][id], t[1][id] + t[2][id]) 183 for k in range(2): 184 pos_l = t[k][id] 185 pos_r = min(A - 1, t[k][id] + t[2][id]) 186 187 if pMin[k][pos_l] < INF: 188 cur = min(cur, I(pMin[k][pos_l], t[k ^ 1][id], t[k ^ 1][id] + t[2][id])) 189 if sMin[k][pos_r] < INF: 190 cur = min(cur, pos_r + I(sMin[k][pos_r], t[k ^ 1][id], t[k ^ 1][id] + t[2][id])) 191 ans.append(cur) 192 193 print("\n".join(map(str, ans))) 194 ``` 195 196 [2230F - Game on Growing Tree](/contest/2230/problem/F "Educational Codeforces Round 190 (Rated for Div. 2)") 197 198 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest"), preparation: [BledDest](/profile/BledDest "International Grandmaster BledDest") 199 200 **Tutorial** 201 202 Tutorial is loading... 203 204 **Solution (BledDest)** 205 206 ``` 207 #include<bits/stdc++.h> 208 209 using namespace std; 210 211 const int N = 200043; 212 const int K = 3; 213 const int LN = 20; 214 215 vector<int> g[N]; 216 int p[N]; 217 pair<int, int> dp_down[N][K]; 218 int dp_up[N]; 219 int q_index; 220 int ans[N]; 221 int f[N]; 222 223 void upd_down(int idx, pair<int, int> p) 224 { 225 if(dp_down[idx][K - 1] < p) 226 { 227 dp_down[idx][K - 1] = p; 228 int j = K - 1; 229 while(j != 0) 230 { 231 if(dp_down[idx][j - 1] < dp_down[idx][j]) 232 { 233 swap(dp_down[idx][j - 1], dp_down[idx][j]); 234 j--; 235 } 236 else break; 237 } 238 } 239 } 240 241 void upd(pair<int, int>& p, int x) 242 { 243 if(p.second < x) p.second = x; 244 if(p.first < p.second) swap(p.first, p.second); 245 } 246 247 int get_cur(int x) 248 { 249 pair<int, int> cur_ans = {0, 0}; 250 for(int i = 0; i < K; i++) 251 if(dp_down[x][i].second != f[x]) 252 upd(cur_ans, dp_down[x][i].first); 253 if(f[x] != -1) 254 upd(cur_ans, dp_up[x]); 255 return cur_ans.second + 1; 256 } 257 258 int get_full(int x) 259 { 260 pair<int, int> cur_ans = {0, 0}; 261 for(int i = 0; i < K; i++) 262 upd(cur_ans, dp_down[x][i].first); 263 upd(cur_ans, dp_up[x]); 264 return cur_ans.second + 1; 265 } 266 267 void dfs1(int x, int parent = -1) 268 { 269 p[x] = parent; 270 for(auto y : g[x]) 271 { 272 if(y > q_index) continue; 273 if(y != parent) 274 { 275 dfs1(y, x); 276 upd_down(x, make_pair(get_cur(y), y)); 277 } 278 } 279 } 280 281 void dfs2(int x) 282 { 283 if(p[x] != -1) 284 dp_up[x] = get_cur(p[x]); 285 for(auto y : g[x]) 286 { 287 if(y > q_index) continue; 288 if(y != p[x]) 289 { 290 f[x] = y; 291 dfs2(y); 292 f[x] = -1; 293 } 294 } 295 } 296 297 int get_ans(int x) 298 { 299 q_index = x + 2; 300 for(int i = 1; i <= q_index; i++) 301 { 302 dp_up[i] = 0; 303 for(int j = 0; j < K; j++) 304 dp_down[i][j] = {0, -1}; 305 p[i] = -1; 306 f[i] = -1; 307 } 308 dfs1(1); 309 dfs2(1); 310 int ans = 1; 311 for(int i = 1; i <= q_index; i++) 312 ans = max(ans, get_full(i)); 313 return ans; 314 } 315 316 void rec(int l, int r, int L, int R) 317 { 318 if(l >= r) return; 319 if(L == R) 320 { 321 for(int i = l; i < r; i++) 322 ans[i] = L; 323 return; 324 } 325 int mid = (l + r) / 2; 326 ans[mid] = get_ans(mid); 327 rec(l, mid, L, ans[mid]); 328 rec(mid + 1, r, ans[mid], R); 329 } 330 331 void solve() 332 { 333 int q; 334 cin >> q; 335 for(int i = 0; i < q; i++) 336 { 337 int x; 338 cin >> x; 339 g[x].push_back(i + 2); 340 g[i + 2].push_back(x); 341 } 342 rec(0, q, 1, LN); 343 for(int i = 0; i < q; i++) 344 cout << ans[i] << " "; 345 cout << "\n"; 346 } 347 348 int main() 349 { 350 ios_base::sync_with_stdio(0); 351 cin.tie(0); 352 int t = 1; 353 for(int i = 0; i < t; i++) 354 solve(); 355 return 0; 356 } 357 ```