1932.md (8967B)
1 Source: https://codeforces.com/blog/entry/126196 2 3 [1932A - Thorns and Coins](/contest/1932/problem/A "Codeforces Round 927 (Div. 3)") 4 5 Idea: [denk](/profile/denk "Expert denk") 6 7 **Tutorial** 8 9 Tutorial is loading... 10 11 **Solution** 12 13 ``` 14 #include <bits/stdc++.h> 15 16 using namespace std; 17 18 signed main() { 19 cin.tie(nullptr); 20 cout.tie(nullptr); 21 ios::sync_with_stdio(false); 22 23 int t; 24 cin >> t; 25 for(int _ = 0; _ < t; ++_){ 26 int n, ans = 0; 27 cin >> n; 28 string s; 29 cin >> s; 30 for (int i = 1; i < n; i++) { 31 ans += (s[i] == '@'); 32 if (s[i] == '*' && s[i - 1] == '*') 33 break; 34 } 35 cout << ans << "\n"; 36 } 37 return 0; 38 } 39 ``` 40 41 [1932B - Chaya Calendar](/contest/1932/problem/B "Codeforces Round 927 (Div. 3)") 42 43 Idea: [Vladosiya](/profile/Vladosiya "Expert Vladosiya") 44 45 **Tutorial** 46 47 Tutorial is loading... 48 49 **Solution** 50 51 ``` 52 def solve(): 53 n = int(input()) 54 a = [int(x) for x in input().split()] 55 cur = 0 56 for e in a: 57 cur += e - cur % e 58 print(cur) 59 60 61 for _ in range(1, int(input()) + 1): 62 solve() 63 ``` 64 65 [1932C - LR-remainders](/contest/1932/problem/C "Codeforces Round 927 (Div. 3)") 66 67 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 68 69 **Tutorial** 70 71 Tutorial is loading... 72 73 **Solution** 74 75 ``` 76 #include <bits/stdc++.h> 77 78 using namespace std; 79 80 #define forn(i, n) for (int i = 0; i < int(n); i++) 81 82 int main() { 83 int t; 84 cin >> t; 85 forn(tt, t) { 86 int n, m; 87 cin >> n >> m; 88 vector<int> a(n); 89 forn(i, n) 90 cin >> a[i]; 91 string s; 92 cin >> s; 93 94 int l = 0; 95 int r = n - 1; 96 forn(i, n - 1) 97 if (s[i] == 'L') 98 l++; 99 else 100 r--; 101 assert(l == r); 102 103 vector<int> b(n); 104 b[n - 1] = a[l] % m; 105 106 for (int i = n - 2; i >= 0; i--) { 107 if (s[i] == 'L') 108 b[i] = (b[i + 1] * a[--l]) % m; 109 else 110 b[i] = (b[i + 1] * a[++r]) % m; 111 } 112 assert(l == 0); 113 assert(r == n - 1); 114 115 forn(i, n) 116 cout << b[i] << " "; 117 cout << endl; 118 } 119 } 120 ``` 121 122 [1932D - Card Game](/contest/1932/problem/D "Codeforces Round 927 (Div. 3)") 123 124 Idea: [goncharovmike](/profile/goncharovmike "Candidate Master goncharovmike") 125 126 **Tutorial** 127 128 Tutorial is loading... 129 130 **Solution** 131 132 ``` 133 #include <bits/stdc++.h> 134 135 #define long long long int 136 #define DEBUG 137 using namespace std; 138 139 // @author: pashka 140 141 int main() { 142 ios::sync_with_stdio(false); 143 144 int t; 145 cin >> t; 146 for (int tt = 0; tt < t; tt++) { 147 int n; 148 cin >> n; 149 150 string suites = "CDHS"; 151 152 string ts; 153 cin >> ts; 154 int trump = suites.find(ts[0]); 155 156 vector<int> bs[4]; 157 for (int i = 0; i < 2 * n; i++) { 158 string s; 159 cin >> s; 160 bs[suites.find(s[1])].push_back(s[0] - '2'); 161 } 162 163 vector<string> res; 164 vector<string> left; 165 for (int i = 0; i < 4; i++) { 166 sort(bs[i].begin(), bs[i].end()); 167 if (i == trump) continue; 168 if (bs[i].size() % 2 == 1) { 169 int x = bs[i].back(); 170 left.push_back(string() + char('2' + x) + suites[i]); 171 bs[i].pop_back(); 172 } 173 for (int j = 0; j < (int) bs[i].size(); j++) { 174 int x = bs[i][j]; 175 res.push_back(string() + char('2' + x) + suites[i]); 176 } 177 } 178 if (left.size() > bs[trump].size()) { 179 cout << "IMPOSSIBLE\n"; 180 } else { 181 for (string s : left) { 182 res.push_back(s); 183 int x = bs[trump].back(); 184 bs[trump].pop_back(); 185 res.push_back(string() + char('2' + x) + suites[trump]); 186 } 187 for (int j = 0; j < (int) bs[trump].size(); j++) { 188 int x = bs[trump][j]; 189 res.push_back(string() + char('2' + x) + suites[trump]); 190 } 191 for (int i = 0; i < 2 * n; i += 2) { 192 cout << res[i] << " " << res[i + 1] << "\n"; 193 } 194 } 195 } 196 } 197 ``` 198 199 [1932E - Final Countdown](/contest/1932/problem/E "Codeforces Round 927 (Div. 3)") 200 201 Idea: [step_by_step](/profile/step_by_step "International Grandmaster step_by_step") 202 203 **Tutorial** 204 205 Tutorial is loading... 206 207 **Solution** 208 209 ``` 210 #include <bits/stdc++.h> 211 #define long long long int 212 #define DEBUG 213 using namespace std; 214 215 // @author: pashka 216 217 int main() { 218 ios::sync_with_stdio(false); 219 220 int t; 221 cin >> t; 222 while (t--) { 223 int n; 224 cin >> n; 225 string s; 226 cin >> s; 227 reverse(s.begin(), s.end()); 228 vector<int> a(n + 1); 229 for (int i = n - 1; i >= 0; i--) { 230 a[i] = a[i + 1] + (s[i] - '0'); 231 } 232 string res; 233 int c = 0; 234 for (int i = 0; i < n; i++) { 235 c += a[i]; 236 res += (char)(c % 10 + '0'); 237 c /= 10; 238 } 239 res += (char)(c + '0'); 240 while (res.back() == '0') { 241 res.pop_back(); 242 } 243 reverse(res.begin(), res.end()); 244 cout << res << "\n"; 245 } 246 247 return 0; 248 } 249 ``` 250 251 [1932F - Feed Cats](/contest/1932/problem/F "Codeforces Round 927 (Div. 3)") 252 253 Idea: [denk](/profile/denk "Expert denk") 254 255 **Tutorial** 256 257 Tutorial is loading... 258 259 **Solution** 260 261 ``` 262 #include <bits/stdc++.h> 263 264 //#define int long long 265 #define pb emplace_back 266 #define mp make_pair 267 #define x first 268 #define y second 269 #define all(a) a.begin(), a.end() 270 #define rall(a) a.rbegin(), a.rend() 271 272 typedef long double ld; 273 typedef long long ll; 274 275 using namespace std; 276 277 mt19937 rnd(time(nullptr)); 278 279 const ll inf = 1e18; 280 const ll M = 998244353; 281 const ld pi = atan2(0, -1); 282 const ld eps = 1e-6; 283 284 void solve(int tc){ 285 int n, m; 286 cin >> n >> m; 287 vector<pair<int, int>> a(m); 288 vector<int> op(n + 1); 289 vector<vector<int>> del(n + 1); 290 for(auto &e: a) { 291 cin >> e.x >> e.y; 292 op[e.x]++; 293 del[e.y].emplace_back(e.x); 294 } 295 multiset<int> cur; 296 vector<int> dp(n + 1); 297 for(int i = 1; i <= n; ++i){ 298 dp[i] = dp[i - 1]; 299 for(int j = 0; j < op[i]; ++j){ 300 cur.insert(i); 301 } 302 if(!cur.empty()){ 303 dp[i] = max(dp[i], int(dp[*cur.begin() - 1] + cur.size())); 304 } 305 for(int e: del[i]){ 306 cur.erase(cur.find(e)); 307 } 308 } 309 cout << dp[n]; 310 } 311 312 bool multi = true; 313 314 signed main() { 315 int t = 1; 316 if (multi)cin >> t; 317 for (int i = 1; i <= t; ++i) { 318 solve(i); 319 cout << "\n"; 320 } 321 return 0; 322 } 323 ``` 324 325 [1932G - Moving Platforms](/contest/1932/problem/G "Codeforces Round 927 (Div. 3)") 326 327 Idea: [denk](/profile/denk "Expert denk") 328 329 **Tutorial** 330 331 Tutorial is loading... 332 333 **Solution** 334 335 ``` 336 #include <bits/stdc++.h> 337 #define long long long int 338 #define DEBUG 339 using namespace std; 340 341 // @author: pashka 342 343 struct triple { 344 long d, x, y; 345 }; 346 347 triple eucl(long a, long b) { 348 if (b == 0) { 349 return {a, 1, 0}; 350 } 351 long k = a / b; 352 auto [d, x, y] = eucl(b, a - k * b); 353 return {d, y, x - k * y}; 354 } 355 356 struct test { 357 void solve() { 358 int n, m, H; 359 cin >> n >> m >> H; 360 vector<long> l(n); 361 for (int i = 0; i < n; i++) cin >> l[i]; 362 vector<long> s(n); 363 for (int i = 0; i < n; i++) cin >> s[i]; 364 365 vector<vector<int>> g(n); 366 for (int i = 0; i < m; i++) { 367 int x, y; 368 cin >> x >> y; 369 x--; 370 y--; 371 g[x].push_back(y); 372 g[y].push_back(x); 373 } 374 375 const long INF = 1e18; 376 vector<long> d(n, INF); 377 d[0] = 0; 378 set<pair<long, int>> q; 379 q.insert({d[0], 0}); 380 while (!q.empty()) { 381 auto p = *q.begin(); 382 q.erase(p); 383 int v = p.second; 384 long t = d[v]; 385 for (int u: g[v]) { 386 long a = (l[v] + (t % H) * s[v]) - (l[u] + (t % H) * s[u]); 387 a %= H; 388 if (a < 0) a += H; 389 long b = s[u] - s[v]; 390 b %= H; 391 if (b < 0) b += H; 392 // a - bx = yH 393 auto [dd, x, y] = eucl(b, H); 394 // xb + yH = dd 395 if (a % dd != 0) continue; 396 x *= a / dd; 397 x %= (H / dd); 398 if (x < 0) x += H / dd; 399 long dt = x; 400 if (d[v] + dt + 1 < d[u]) { 401 q.erase({d[u], u}); 402 d[u] = d[v] + dt + 1; 403 q.insert({d[u], u}); 404 } 405 } 406 } 407 long res = d[n - 1]; 408 if (res == INF) res = -1; 409 cout << res << "\n"; 410 } 411 }; 412 413 int main() { 414 ios::sync_with_stdio(false); 415 416 int n; 417 cin >> n; 418 for (int i = 0; i < n; i++) { 419 test().solve(); 420 } 421 422 return 0; 423 } 424 ```