1927.md (7381B)
1 Source: https://codeforces.com/blog/entry/125597 2 3 [1927A - Make it White](/contest/1927/problem/A "Codeforces Round 923 (Div. 3)") 4 5 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 6 7 **Tutorial** 8 9 Tutorial is loading... 10 11 **Solution** 12 13 ``` 14 from collections import deque 15 16 def solve(): 17 n = int(input()) 18 s = deque(input()) 19 while len(s) > 0 and s[0] == 'W': 20 s.popleft() 21 while len(s) > 0 and s[-1] == 'W': 22 s.pop() 23 print(len(s)) 24 25 26 for _ in range(int(input())): 27 solve() 28 ``` 29 30 [1927B - Following the String](/contest/1927/problem/B "Codeforces Round 923 (Div. 3)") 31 32 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 33 34 **Tutorial** 35 36 Tutorial is loading... 37 38 **Solution** 39 40 ``` 41 def solve(): 42 n = int(input()) 43 a = [int(x) for x in input().split()] 44 cnt = [0] * 26 45 s = '' 46 for i in range(n): 47 for j in range(26): 48 if cnt[j] == a[i]: 49 cnt[j] += 1 50 s += chr(97 + j) 51 break 52 print(s) 53 54 55 for _ in range(int(input())): 56 solve() 57 ``` 58 59 [1927C - Choose the Different Ones!](/contest/1927/problem/C "Codeforces Round 923 (Div. 3)") 60 61 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 62 63 **Tutorial** 64 65 Tutorial is loading... 66 67 **Solution** 68 69 ``` 70 def solve(): 71 n, m, k = map(int, input().split()) 72 a = [int(x) for x in input().split()] 73 b = [int(x) for x in input().split()] 74 cnt = [0] * (k + 1) 75 for e in a: 76 if e <= k: 77 cnt[e] |= 1 78 for e in b: 79 if e <= k: 80 cnt[e] |= 2 81 c = [0] * 4 82 for e in cnt: 83 c[e] += 1 84 if c[1] > k // 2 or c[2] > k // 2 or c[1] + c[2] + c[3] != k: 85 print("NO") 86 else: 87 print("YES") 88 89 90 for _ in range(int(input())): 91 solve() 92 ``` 93 94 [1927D - Find the Different Ones!](/contest/1927/problem/D "Codeforces Round 923 (Div. 3)") 95 96 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 97 98 **Tutorial** 99 100 Tutorial is loading... 101 102 **Solution** 103 104 ``` 105 def solve(): 106 n = int(input()) 107 a = [int(x) for x in input().split()] 108 p = [-1] * n 109 for i in range(1, n): 110 p[i] = p[i - 1] 111 if a[i] != a[i - 1]: 112 p[i] = i - 1 113 for i in range(int(input())): 114 l, r = map(int, input().split()) 115 l -= 1 116 r -= 1 117 if p[r] < l: 118 print("-1 -1") 119 else: 120 print(p[r] + 1, r + 1) 121 122 123 t = int(input()) 124 for _ in range(t): 125 solve() 126 if _ + 1 != t: 127 print() 128 ``` 129 130 [1927E - Klever Permutation](/contest/1927/problem/E "Codeforces Round 923 (Div. 3)") 131 132 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 133 134 **Tutorial** 135 136 Tutorial is loading... 137 138 **Solution** 139 140 ``` 141 def solve(): 142 n, k = map(int, input().split()) 143 l, r = 1, n 144 ans = [0] * n 145 for i in range(k): 146 for j in range(i, n, k): 147 if i % 2 == 0: 148 ans[j] = l 149 l += 1 150 else: 151 ans[j] = r 152 r -= 1 153 print(*ans) 154 155 156 for _ in range(int(input())): 157 solve() 158 ``` 159 160 [1927F - Microcycle](/contest/1927/problem/F "Codeforces Round 923 (Div. 3)") 161 162 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 163 164 **Tutorial** 165 166 Tutorial is loading... 167 168 **Solution** 169 170 ``` 171 #include <bits/stdc++.h> 172 173 #define int long long 174 #define pb emplace_back 175 #define mp make_pair 176 #define x first 177 #define y second 178 #define all(a) a.begin(), a.end() 179 #define rall(a) a.rbegin(), a.rend() 180 181 typedef long double ld; 182 typedef long long ll; 183 184 using namespace std; 185 186 mt19937 rnd(time(nullptr)); 187 188 const ll inf = 1e18; 189 const ll M = 998244353; 190 const ld pi = atan2(0, -1); 191 const ld eps = 1e-6; 192 193 struct dsu{ 194 vector<int> p, lvl; 195 196 dsu(int n){ 197 p.resize(n); 198 iota(p.begin(), p.end(), 0); 199 lvl.assign(n, 0); 200 } 201 202 int get(int i){ 203 if (p[i] == i) return i; 204 return p[i] = get(p[i]); 205 } 206 207 bool unite(int a, int b){ 208 a = get(a); 209 b = get(b); 210 if(a == b) return false; 211 if(lvl[a] < lvl[b]) swap(a, b); 212 p[b] = a; 213 if(lvl[a] == lvl[b]) lvl[a]++; 214 return true; 215 } 216 }; 217 218 bool found; 219 vector<int> ans, path; 220 221 void dfs(int v, int p, vector<vector<int>> &g, int f){ 222 path.push_back(v); 223 if(v == f){ 224 ans = path; 225 found = true; 226 return; 227 } 228 for(int u: g[v]){ 229 if(u != p) dfs(u, v, g, f); 230 if (found) return; 231 } 232 path.pop_back(); 233 } 234 235 void solve(int tc){ 236 int n, m; 237 cin >> n >> m; 238 vector<vector<int>> sl(n); 239 vector<pair<int, pair<int, int>>> edges; 240 for(int i = 0; i < m; ++i){ 241 int u, v, w; 242 cin >> u >> v >> w; 243 --u, --v; 244 edges.push_back({w, {u, v}}); 245 } 246 sort(rall(edges)); 247 dsu g(n); 248 pair<int, int> fin; 249 int best = INT_MAX; 250 for(auto e: edges){ 251 if(!g.unite(e.y.x, e.y.y)){ 252 fin = e.y; 253 best = e.x; 254 } 255 else{ 256 sl[e.y.x].push_back(e.y.y); 257 sl[e.y.y].push_back(e.y.x); 258 } 259 } 260 found = false; 261 path.resize(0); 262 dfs(fin.x, -1, sl, fin.y); 263 cout << best << " " << ans.size() << "\n"; 264 for(int e: ans) cout << e + 1 << " "; 265 } 266 267 bool multi = true; 268 269 signed main() { 270 int t = 1; 271 if (multi)cin >> t; 272 for (int i = 1; i <= t; ++i) { 273 solve(i); 274 cout << "\n"; 275 } 276 return 0; 277 } 278 ``` 279 280 [1927G - Paint Charges](/contest/1927/problem/G "Codeforces Round 923 (Div. 3)") 281 282 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 283 284 **Tutorial** 285 286 Tutorial is loading... 287 288 **Solution** 289 290 ``` 291 #include <bits/stdc++.h> 292 293 using namespace std; 294 295 #define forn(i, n) for (int i = 0; i < int(n); i++) 296 297 int main() { 298 int t; 299 cin >> t; 300 forn(tt, t) { 301 int n; 302 cin >> n; 303 vector<int> a(n); 304 forn(i, n) 305 cin >> a[i]; 306 307 vector<vector<vector<int>>> d(n + 1, vector<vector<int>>(n + 1, vector<int>(n + 1, INT_MAX))); 308 d[0][0][0] = 0; 309 310 forn(i, n) 311 forn(j, n) 312 forn(k, n + 1) 313 if (d[i][j][k] < INT_MAX) { 314 int ai = a[i]; 315 316 // Z 317 { 318 int ni = i + 1; 319 int nj = j > 0 ? j + 1 : (k == 0 ? 1 : 0); 320 int nk = max(0, k - 1); 321 d[ni][nj][nk] = min(d[ni][nj][nk], d[i][j][k]); 322 } 323 324 // L 325 { 326 int ni = i + 1; 327 int nj = j > 0 ? j + 1 : 0; 328 if (nj <= ai) 329 nj = 0; 330 int nk = max(0, k - 1); 331 d[ni][nj][nk] = min(d[ni][nj][nk], d[i][j][k] + 1); 332 } 333 334 // R 335 { 336 int ni = i + 1; 337 int nj = j > 0 ? j + 1 : 0; 338 int nk = max(ai - 1, k - 1); 339 d[ni][nj][nk] = min(d[ni][nj][nk], d[i][j][k] + 1); 340 } 341 } 342 343 cout << *min_element(d[n][0].begin(), d[n][0].end()) << endl; 344 } 345 } 346 ```