1626.md (5904B)
1 Source: https://codeforces.com/blog/entry/99136 2 3 [1626A - Equidistant Letters](/contest/1626/problem/A "Educational Codeforces Round 121 (Rated for Div. 2)") 4 5 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 6 7 **Tutorial** 8 9 Tutorial is loading... 10 11 **Solution (awoo)** 12 13 ``` 14 for _ in range(int(input())): 15 print(''.join(sorted(input()))) 16 ``` 17 18 [1626B - Minor Reduction](/contest/1626/problem/B "Educational Codeforces Round 121 (Rated for Div. 2)") 19 20 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 21 22 **Tutorial** 23 24 Tutorial is loading... 25 26 **Solution (awoo)** 27 28 ``` 29 for _ in range(int(input())): 30 x = [ord(c) - ord('0') for c in input()] 31 n = len(x) 32 for i in range(n - 2, -1, -1): 33 if x[i] + x[i + 1] >= 10: 34 x[i + 1] += x[i] - 10 35 x[i] = 1 36 break 37 else: 38 x[1] += x[0] 39 x.pop(0) 40 print(''.join([chr(c + ord('0')) for c in x])) 41 ``` 42 43 [1626C - Monsters And Spells](/contest/1626/problem/C "Educational Codeforces Round 121 (Rated for Div. 2)") 44 45 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 46 47 **Tutorial** 48 49 Tutorial is loading... 50 51 **Solution (awoo)** 52 53 ``` 54 for _ in range(int(input())): 55 n = int(input()) 56 k = list(map(int, input().split())) 57 h = list(map(int, input().split())) 58 st = [] 59 for i in range(n): 60 st.append([k[i] - h[i], k[i]]) 61 st.sort() 62 l, r = -1, -1 63 ans = 0 64 for it in st: 65 if it[0] >= r: 66 ans += (r - l) * (r - l + 1) // 2 67 l, r = it 68 else: 69 r = max(r, it[1]) 70 ans += (r - l) * (r - l + 1) // 2 71 print(ans) 72 ``` 73 74 [1626D - Martial Arts Tournament](/contest/1626/problem/D "Educational Codeforces Round 121 (Rated for Div. 2)") 75 76 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 77 78 **Tutorial** 79 80 Tutorial is loading... 81 82 **Solution (awoo)** 83 84 ``` 85 calc = 1 86 nxt = [1, 0] 87 88 for _ in range(int(input())): 89 n = int(input()) 90 a = sorted(list(map(int, input().split()))) 91 while calc <= n: 92 for i in range(calc): 93 nxt.append(calc - i - 1) 94 calc *= 2 95 left = [] 96 for i in range(n + 1): 97 if i == 0 or i == n or a[i] != a[i - 1]: 98 left.append(i) 99 else: 100 left.append(left[-1]) 101 mid = 1 102 ans = n + 2 103 while mid <= n: 104 for len1 in range(n + 1): 105 if left[len1] == len1: 106 len2 = left[min(n, len1 + mid)] - len1 107 len3 = n - len1 - len2 108 ans = min(ans, nxt[len1] + (mid - len2) + nxt[len3]) 109 mid *= 2 110 print(ans) 111 ``` 112 113 [1626E - Black and White Tree](/contest/1626/problem/E "Educational Codeforces Round 121 (Rated for Div. 2)") 114 115 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 116 117 **Tutorial** 118 119 Tutorial is loading... 120 121 **Solution (BledDest)** 122 123 ``` 124 #include<bits/stdc++.h> 125 126 using namespace std; 127 128 const int N = 300043; 129 130 vector<int> g[N]; 131 int cnt[N]; 132 int c[N]; 133 vector<int> g2[N]; 134 int par[N]; 135 int used[N]; 136 137 void dfs(int x, int p = -1) 138 { 139 par[x] = p; 140 for(auto y : g[x]) 141 if(y != p) 142 { 143 dfs(y, x); 144 cnt[x] += cnt[y]; 145 } 146 cnt[x] += c[x]; 147 } 148 149 int main() 150 { 151 int n; 152 scanf("%d", &n); 153 for(int i = 0; i < n; i++) scanf("%d", &c[i]); 154 for(int i = 1; i < n; i++) 155 { 156 int x, y; 157 scanf("%d %d", &x, &y); 158 --x; 159 --y; 160 g[x].push_back(y); 161 g[y].push_back(x); 162 } 163 dfs(0); 164 for(int i = 0; i < n; i++) 165 for(auto j : g[i]) 166 { 167 if(i == par[j]) 168 { 169 if(c[i] == 1 || cnt[0] - cnt[j] > 1) 170 g2[i].push_back(j); 171 } 172 else 173 { 174 if(c[i] == 1 || cnt[i] > 1) 175 g2[i].push_back(j); 176 } 177 } 178 queue<int> q; 179 for(int i = 0; i < n; i++) 180 { 181 if(c[i] == 1) 182 { 183 q.push(i); 184 used[i] = 1; 185 } 186 } 187 while(!q.empty()) 188 { 189 int k = q.front(); 190 q.pop(); 191 for(auto y : g2[k]) 192 if(used[y] == 0) 193 { 194 used[y] = 1; 195 q.push(y); 196 } 197 } 198 for(int i = 0; i < n; i++) 199 printf("%d ", used[i]); 200 puts(""); 201 } 202 ``` 203 204 [1626F - A Random Code Problem](/contest/1626/problem/F "Educational Codeforces Round 121 (Rated for Div. 2)") 205 206 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 207 208 **Tutorial** 209 210 Tutorial is loading... 211 212 **Solution (BledDest)** 213 214 ``` 215 #include <bits/stdc++.h> 216 217 using namespace std; 218 219 const int MOD = 998244353; 220 const int L = 720720; 221 222 int add(int x, int y, int m = MOD) 223 { 224 x += y; 225 if(x >= m) x -= m; 226 return x; 227 } 228 229 int mul(int x, int y, int m = MOD) 230 { 231 return (x * 1ll * y) % m; 232 } 233 234 int binpow(int x, int y) 235 { 236 int z = 1; 237 while(y > 0) 238 { 239 if(y % 2 == 1) z = mul(z, x); 240 x = mul(x, x); 241 y /= 2; 242 } 243 return z; 244 } 245 246 int inv(int x) 247 { 248 return binpow(x, MOD - 2); 249 } 250 251 int divide(int x, int y) 252 { 253 return mul(x, inv(y)); 254 } 255 256 int main() 257 { 258 int n, a0, x, y, k, M; 259 cin >> n >> a0 >> x >> y >> k >> M; 260 vector<int> arr(n); 261 arr[0] = a0; 262 for(int i = 1; i < n; i++) 263 arr[i] = add(mul(arr[i - 1], x, M), y, M); 264 int ans = 0; 265 int total_ways = binpow(n, k); 266 int coeff = mul(divide(total_ways, n), k); 267 vector<vector<int>> dp(k, vector<int>(L)); 268 for(int i = 0; i < n; i++) 269 { 270 int p = arr[i] / L; 271 int q = arr[i] % L; 272 dp[0][q]++; 273 ans = add(ans, mul(p, mul(L, coeff))); 274 } 275 int cur_coeff = divide(total_ways, n); 276 for(int i = 1; i <= k; i++) 277 { 278 for(int j = 0; j < L; j++) 279 { 280 int cur = dp[i - 1][j]; 281 if(i < k) 282 dp[i][j] = add(dp[i][j], mul(n - 1, cur)); 283 ans = add(ans, mul(j, mul(cur, cur_coeff))); 284 if(i < k) 285 dp[i][j - (j % i)] = add(dp[i][j - (j % i)], cur); 286 } 287 cur_coeff = divide(cur_coeff, n); 288 } 289 cout << ans << endl; 290 } 291 ```