1941.md (8139B)
1 Source: https://codeforces.com/blog/entry/127018 2 3 [1941A - Rudolf and the Ticket](/contest/1941/problem/A "Codeforces Round 933 (Div. 3)") 4 5 Author: [daha.002](/profile/daha.002 "Newbie daha.002") 6 7 **Tutorial** 8 9 Tutorial is loading... 10 11 **Solution** 12 13 ``` 14 #include <iostream> 15 #include <vector> 16 17 using namespace std; 18 19 int main() { 20 int t; 21 cin >> t; 22 while (t--) { 23 int n, m, k; 24 cin >> n >> m >> k; 25 int ans = 0; 26 vector<int> v1(n); 27 for (int i = 0; i < n; i++) { 28 cin >> v1[i]; 29 } 30 int o; 31 for (int j = 0; j < m; j++) { 32 cin >> o; 33 for (int i = 0; i < n; i++) { 34 if ((o + v1[i]) <= k) ans++; 35 } 36 } 37 cout << ans << "\n"; 38 } 39 return 0; 40 } 41 ``` 42 43 **Rate the problem** 44 45 * Didn't solve 46 * Good task 47 * Average task 48 * Bad task 49 50 [1941B - Rudolf and 121](/contest/1941/problem/B "Codeforces Round 933 (Div. 3)") 51 52 Author: [Vladosiya](/profile/Vladosiya "Expert Vladosiya") 53 54 **Tutorial** 55 56 Tutorial is loading... 57 58 **Solution** 59 60 ``` 61 def solve(): 62 n = int(input()) 63 a = [int(x) for x in input().split()] 64 for i in range(n - 2): 65 if a[i] < 0: 66 print('NO') 67 return 68 op = a[i] 69 a[i] -= op 70 a[i + 1] -= 2 * op 71 a[i + 2] -= op 72 if a[-1] != 0 or a[-2] != 0: 73 print('NO') 74 else: 75 print('YES') 76 77 78 for _ in range(int(input())): 79 solve() 80 ``` 81 82 **Rate the problem** 83 84 * Didn't solve 85 * Good task 86 * Average task 87 * Bad task 88 89 [1941C - Rudolf and the Ugly String](/contest/1941/problem/C "Codeforces Round 933 (Div. 3)") 90 91 Author: [Mordvin13](/profile/Mordvin13 "Newbie Mordvin13") 92 93 **Tutorial** 94 95 Tutorial is loading... 96 97 **Solution** 98 99 ``` 100 #include <iostream> 101 #include <vector> 102 #include <string> 103 #include <algorithm> 104 105 using namespace std; 106 107 int main() { 108 long long t; 109 cin>>t; 110 for(long long c=0;c<t;c++){ 111 long long n; 112 cin >> n; 113 string s; 114 cin >> s; 115 vector<long long> va; 116 for (string sul : {"mapie", "pie", "map"}) { 117 for (size_t pos = 0; (pos = s.find(sul, pos)) != string::npos;) { 118 s[pos + sul.length() / 2] = '?'; 119 va.push_back(pos + sul.length() / 2); 120 } 121 } 122 cout << va.size() << endl; 123 } 124 return 0; 125 } 126 ``` 127 128 **Rate the problem** 129 130 * Didn't solve 131 * Good task 132 * Average task 133 * Bad task 134 135 [1941D - Rudolf and the Ball Game](/contest/1941/problem/D "Codeforces Round 933 (Div. 3)") 136 137 Author: [Alexey_Parsh](/profile/Alexey_Parsh "Expert Alexey_Parsh") 138 139 **Tutorial** 140 141 Tutorial is loading... 142 143 **Solution** 144 145 ``` 146 #include <iostream> 147 #include <set> 148 149 using namespace std; 150 151 int main() 152 { 153 int t; cin >> t; 154 while (t--) { 155 int n, m, a; cin >> n >> m >> a; 156 set <int> q[2]; 157 int ix = 0; 158 q[ix].insert(a); 159 while (m--) { 160 int x; char ch; cin >> x >> ch; 161 while (!q[ix].empty()) { 162 int u = *(q[ix].begin()); 163 q[ix].erase(u); 164 if (ch == '?' || ch == '0') { 165 q[ix ^ 1].insert((u + x - 1) % n + 1); 166 } 167 if (ch == '?' || ch == '1') { 168 q[ix ^ 1].insert((u - x - 1 + n) % n + 1); 169 } 170 } 171 ix ^= 1; 172 } 173 cout << q[ix].size() << '\n'; 174 for (auto& x : q[ix]) { 175 cout << x << ' '; 176 } 177 cout << '\n'; 178 } 179 return 0; 180 } 181 ``` 182 183 **Rate the problem** 184 185 * Didn't solve 186 * Good task 187 * Average task 188 * Bad task 189 190 [1941E - Rudolf and k Bridges](/contest/1941/problem/E "Codeforces Round 933 (Div. 3)") 191 192 Author: [t0rtik](/profile/t0rtik "Expert t0rtik") 193 194 **Tutorial** 195 196 Tutorial is loading... 197 198 **Solution** 199 200 ``` 201 #include <iostream> 202 #include <vector> 203 #include <algorithm> 204 #include <set> 205 206 using namespace std; 207 208 int main() { 209 210 int t = 1; 211 cin >> t; 212 while (t--) { 213 int N, M, K, D; 214 cin >> N >> M >> K >> D; 215 vector<long long> a(N); 216 for (int i = 0; i < N; i++) { 217 vector<long long> dp(M, 1e9); 218 vector<int> v(M); 219 multiset<long long> mst = {1}; 220 dp[0] = 1; 221 cin >> v[0]; 222 for (int j = 1; j < M - 1; j++) { 223 cin >> v[j]; 224 dp[j] = *mst.begin() + v[j] + 1; 225 if (j - D - 1 >= 0) 226 mst.erase(mst.find((dp[j - D - 1]))); 227 mst.insert(dp[j]); 228 } 229 cin >> v.back(); 230 dp.back() = 1 + *mst.begin(); 231 a[i] = dp.back(); 232 } 233 234 long long cur = 0; 235 for (int i = 0; i < K; i++) 236 cur += a[i]; 237 238 long long mn = cur; 239 240 for (int i = K; i < N; i++) { 241 cur += a[i] - a[i - K]; 242 mn = min(cur, mn); 243 } 244 cout << mn << endl; 245 } 246 return 0; 247 } 248 ``` 249 250 **Rate the problem** 251 252 * Didn't solve 253 * Good task 254 * Average task 255 * Bad task 256 257 [1941F - Rudolf and Imbalance](/contest/1941/problem/F "Codeforces Round 933 (Div. 3)") 258 259 Author: [Vladosiya](/profile/Vladosiya "Expert Vladosiya") 260 261 **Tutorial** 262 263 Tutorial is loading... 264 265 **Solution** 266 267 ``` 268 def solve(): 269 n, m, k = map(int, input().split()) 270 a = [int(x) for x in input().split()] 271 d = [int(x) for x in input().split()] 272 f = [int(x) for x in input().split()] 273 d.sort() 274 f.sort() 275 276 m1, m2 = 0, 0 277 ind = -1 278 for i in range(1, n): 279 e = a[i] - a[i - 1] 280 m2 = max(m2, e) 281 if m2 > m1: 282 m1, m2 = m2, m1 283 ind = i - 1 284 285 ans = m1 286 287 target = (a[ind] + a[ind + 1]) // 2 288 for model in d: 289 l, r = 0, k - 1 290 while r - l > 1: 291 mid = (r + l) // 2 292 if model + f[mid] <= target: 293 l = mid 294 else: 295 r = mid 296 ans = min(ans, max(m2, abs(model + f[l] - a[ind]), abs(model + f[l] - a[ind + 1]))) 297 ans = min(ans, max(m2, abs(model + f[r] - a[ind]), abs(model + f[r] - a[ind + 1]))) 298 print(ans) 299 300 for _ in range(int(input())): 301 solve() 302 ``` 303 304 **Rate the problem** 305 306 * Didn't solve 307 * Good task 308 * Average task 309 * Bad task 310 311 [1941G - Rudolf and Subway](/contest/1941/problem/G "Codeforces Round 933 (Div. 3)") 312 313 Author: [natalina](/profile/natalina "Expert natalina") 314 315 **Tutorial** 316 317 Tutorial is loading... 318 319 **Solution** 320 321 ``` 322 #include<bits/stdc++.h> 323 324 using LL = long long; 325 using ld = long double; 326 327 using namespace std; 328 329 int main() { 330 ios::sync_with_stdio(false); 331 cin.tie(0); 332 cout.tie(0); 333 cout << fixed << setprecision(10); 334 335 int _ = 0, __ = 1; 336 cin >> __; 337 338 for (int _ = 0; _ < __; ++_) { 339 int n, m; 340 cin >> n >> m; 341 vector<vector<pair<int, int>>> g(n + 1); 342 map<int, int> clrs; 343 int idx = n + 1; 344 for (int i = 0; i < m; ++i) { 345 int u, v, c; 346 cin >> u >> v >> c; 347 g[u].push_back({v, c}); 348 g[v].push_back({u, c}); 349 if (!clrs.count(c)) { 350 clrs[c] = idx; 351 idx++; 352 } 353 } 354 int s, t; 355 cin >> s >> t; 356 357 if (s == t) 358 { 359 cout << 0 << endl; 360 continue; 361 } 362 363 vector<set<int>> bg(n + clrs.size() + 3); 364 365 for (int i = 1; i <= n; ++i) { 366 for(auto &[to, c] : g[i]) 367 { 368 int clr_v = clrs[c]; 369 bg[i].insert(clr_v); 370 bg[clr_v].insert(i); 371 372 bg[to].insert(clr_v); 373 bg[clr_v].insert(to); 374 } 375 } 376 377 vector<int> used(bg.size()); 378 vector<int> d(bg.size(), -1); 379 auto bfs = [&](int v) 380 { 381 queue<int> q; 382 q.push(v); 383 used[v] = 1; 384 d[v] = 0; 385 while (!q.empty()) 386 { 387 auto from = q.front(); 388 q.pop(); 389 for (auto& to : bg[from]) 390 { 391 if (!used[to]) 392 { 393 q.push(to); 394 used[to] = 1; 395 d[to] = d[from] + 1; 396 } 397 } 398 } 399 }; 400 bfs(s); 401 if (d[t] > 0) cout << d[t] / 2 << endl; 402 else cout << -1 << endl; 403 404 } 405 406 return 0; 407 } 408 ``` 409 410 **Rate the problem** 411 412 * Didn't solve 413 * Good task 414 * Average task 415 * Bad task