1931.md (7329B)
1 Source: https://codeforces.com/blog/entry/125878 2 3 [1931A - Recovering a Small String](/contest/1931/problem/A "Codeforces Round 925 (Div. 3)") 4 5 Idea: [myav](/profile/myav "Pupil myav") Prepared by: [myav](/profile/myav "Pupil myav") 6 7 **Tutorial** 8 9 Tutorial is loading... 10 11 **Solution** 12 13 ``` 14 #include<bits/stdc++.h> 15 using namespace std; 16 17 18 void solve(){ 19 int n, sz = 26; 20 cin >> n; 21 string mins = "zzz", cur; 22 for(int i = 0; i < sz; i++){ 23 for(int j = 0; j < sz; j++){ 24 for(int k = 0; k < sz; k++){ 25 if(i + j + k + 3 == n){ 26 cur += char(i + 'a'); 27 cur += char(j + 'a'); 28 cur += char(k + 'a'); 29 mins = min(cur, mins); 30 } 31 } 32 } 33 } 34 cout << mins << "\n"; 35 36 } 37 int main(){ 38 int t; 39 cin >> t; 40 while(t--) { 41 solve(); 42 } 43 } 44 ``` 45 46 [1931B - Make Equal](/contest/1931/problem/B "Codeforces Round 925 (Div. 3)") 47 48 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") Prepared by: [Vladosiya](/profile/Vladosiya "Expert Vladosiya") 49 50 **Tutorial** 51 52 Tutorial is loading... 53 54 **Solution** 55 56 ``` 57 def solve(): 58 n = int(input()) 59 a = [int(x) for x in input().split()] 60 k = sum(a) // n 61 for i in range(n - 1): 62 if a[i] < k: 63 print('NO') 64 return 65 a[i + 1] += a[i] - k 66 a[i] = k 67 print('YES') 68 69 70 for _ in range(int(input())): 71 solve() 72 ``` 73 74 [1931C - Make Equal Again](/contest/1931/problem/C "Codeforces Round 925 (Div. 3)") 75 76 Idea: [ibraevdmitriy](/profile/ibraevdmitriy "Master ibraevdmitriy") Prepared by: [ibraevdmitriy](/profile/ibraevdmitriy "Master ibraevdmitriy") 77 78 **Tutorial** 79 80 Tutorial is loading... 81 82 **Solution** 83 84 ``` 85 def solve(): 86 n = int(input()) 87 a = list(map(int, input().split())) 88 i1 = 0 89 i2 = 0 90 while i1 < n and a[i1] == a[0]: 91 i1 += 1 92 while i2 < n and a[n - i2 - 1] == a[n - 1]: 93 i2 += 1 94 res = n 95 if a[0] == a[n - 1]: 96 res -= i1 97 res -= i2 98 else: 99 res -= max(i1, i2) 100 print(max(0, res)) 101 102 103 t = int(input()) 104 105 106 for i in range(t): 107 solve() 108 ``` 109 110 [1931D - Divisible Pairs](/contest/1931/problem/D "Codeforces Round 925 (Div. 3)") 111 112 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") Prepared by: [Vladosiya](/profile/Vladosiya "Expert Vladosiya") 113 114 **Tutorial** 115 116 Tutorial is loading... 117 118 **Solution** 119 120 ``` 121 def solve(): 122 n, x, y = map(int, input().split()) 123 a = [int(x) for x in input().split()] 124 cnt = dict() 125 ans = 0 126 for e in a: 127 xx, yy = e % x, e % y 128 ans += cnt.get(((x - xx) % x, yy), 0) 129 cnt[(xx, yy)] = cnt.get((xx, yy), 0) + 1 130 print(ans) 131 132 133 for _ in range(int(input())): 134 solve() 135 ``` 136 137 [1931E - Anna and the Valentine's Day Gift](/contest/1931/problem/E "Codeforces Round 925 (Div. 3)") 138 139 Idea: [Gornak40](/profile/Gornak40 "Expert Gornak40") Prepared by: [Gornak40](/profile/Gornak40 "Expert Gornak40") 140 141 **Tutorial** 142 143 Tutorial is loading... 144 145 **Solution** 146 147 ``` 148 #include <bits/stdc++.h> 149 150 #define all(arr) arr.begin(), arr.end() 151 152 using namespace std; 153 154 const int MAXN = 200200; 155 156 int n, m; 157 string arr[MAXN]; 158 int len[MAXN], zrr[MAXN]; 159 160 void build() { 161 memset(zrr, 0, sizeof(*zrr) * n); 162 for (int i = 0; i < n; ++i) { 163 len[i] = arr[i].size(); 164 for (auto it = arr[i].rbegin(); it != arr[i].rend() && *it == '0'; ++it) { 165 ++zrr[i]; 166 } 167 } 168 } 169 170 string solve() { 171 int ans = 0; 172 for (int i = 0; i < n; ++i) { 173 ans += len[i] - zrr[i]; 174 } 175 sort(zrr, zrr + n); 176 reverse(zrr, zrr + n); 177 for (int i = 0; i < n; ++i) { 178 if (i & 1) ans += zrr[i]; 179 } 180 return (ans - 1 >= m ? "Sasha" : "Anna"); 181 } 182 183 int main() { 184 int t; cin >> t; 185 while (t--) { 186 cin >> n >> m; 187 for (int i = 0; i < n; ++i) 188 cin >> arr[i]; 189 build(); 190 cout << solve() << '\n'; 191 } 192 } 193 ``` 194 195 [1931F - Chat Screenshots](/contest/1931/problem/F "Codeforces Round 925 (Div. 3)") 196 197 Idea: [ibraevdmitriy](/profile/ibraevdmitriy "Master ibraevdmitriy") Prepared by: [ibraevdmitriy](/profile/ibraevdmitriy "Master ibraevdmitriy") 198 199 **Tutorial** 200 201 Tutorial is loading... 202 203 **Solution** 204 205 ``` 206 #include <iostream> 207 #include <vector> 208 #include <set> 209 #include <queue> 210 #include <algorithm> 211 212 using namespace std; 213 214 typedef long long ll; 215 216 int timer = 0; 217 218 void dfs(int v, vector<vector<int>> &g, vector<bool> &vis, vector<int> &tout) { 219 vis[v] = true; 220 for (int u: g[v]) { 221 if (!vis[u]) { 222 dfs(u, g, vis, tout); 223 } 224 } 225 tout[v] = timer++; 226 } 227 228 void solve() { 229 timer = 0; 230 int n, k; 231 cin >> n >> k; 232 vector<vector<int>> a(k, vector<int>(n)); 233 vector<int> authors(k); 234 for (int i = 0; i < k; ++i) { 235 for (int j = 0; j < n; ++j) { 236 cin >> a[i][j]; 237 a[i][j]--; 238 } 239 authors[i] = a[i][0]; 240 } 241 vector<vector<int>> g(n); 242 for (int i = 0; i < k; ++i) { 243 for (int j = 1; j + 1 < n; ++j) { 244 int i1 = a[i][j], i2 = a[i][j + 1]; 245 g[i1].push_back(i2); 246 } 247 } 248 vector<int> tout(n, -1); 249 vector<bool> vis(n); 250 for (int i = 0; i < n; ++i) { 251 if (tout[i] == -1) { 252 dfs(i, g, vis, tout); 253 } 254 } 255 for (int i = 0; i < k; ++i) { 256 for (int j = 1; j + 1 < n; ++j) { 257 int i1 = a[i][j], i2 = a[i][j + 1]; 258 if (tout[i1] < tout[i2]) { 259 cout << "NO"; 260 return; 261 } 262 } 263 } 264 cout << "YES"; 265 } 266 267 int main() { 268 int t; 269 cin >> t; 270 for (int _ = 0; _ < t; ++_) { 271 solve(); 272 cout << "\n"; 273 } 274 } 275 ``` 276 277 [1931G - One-Dimensional Puzzle](/contest/1931/problem/G "Codeforces Round 925 (Div. 3)") 278 279 Idea: [ibraevdmitriy](/profile/ibraevdmitriy "Master ibraevdmitriy") Prepared by: [ibraevdmitriy](/profile/ibraevdmitriy "Master ibraevdmitriy") 280 281 **Tutorial** 282 283 Tutorial is loading... 284 285 **Solution** 286 287 ``` 288 #include <iostream> 289 #include <vector> 290 #include <set> 291 #include <queue> 292 #include <algorithm> 293 294 using namespace std; 295 296 typedef long long ll; 297 298 const int mod = 998244353; 299 300 ll pow_mod(ll x, ll p) { 301 if (p == 0) { 302 return 1; 303 } 304 if (p % 2 == 0) { 305 ll y = pow_mod(x, p / 2); 306 return (y * y) % mod; 307 } 308 return (x * pow_mod(x, p - 1)) % mod; 309 } 310 311 ll inv(ll x) { 312 return pow_mod(x, mod - 2); 313 } 314 315 vector<ll> fact = {1}; 316 317 ll cnk(ll n, ll k) { 318 ll res = fact[n]; 319 res = (res * inv(fact[k])) % mod; 320 res = (res * inv(fact[n - k])) % mod; 321 return res; 322 } 323 324 ll calc(int n1, int n2, int n3, int n4) { 325 return (cnk(n1 + n3 - 1, n3) * cnk(n2 + n4 - 1, n4)) % mod; 326 } 327 328 void solve() { 329 int n1, n2, n3, n4; 330 cin >> n1 >> n2 >> n3 >> n4; 331 if (n1 + n2 == 0) { 332 cout << (n3 == 0 || n4 == 0 ? 1 : 0) << '\n'; 333 return; 334 } 335 if (abs(n1 - n2) > 1) { 336 cout << "0\n"; 337 return; 338 } 339 ll res = 0; 340 if (n1 <= n2) { 341 res += calc(n1 + 1, n2, n3, n4); 342 } 343 if (n2 <= n1) { 344 res += calc(n1, n2 + 1, n3, n4); 345 } 346 cout << res % mod << '\n'; 347 } 348 349 int main() { 350 for (ll i = 1; i <= 4e6; ++i) { 351 fact.push_back((fact.back() * i) % mod); 352 } 353 int t; 354 cin >> t; 355 for (int _ = 0; _ < t; ++_) { 356 solve(); 357 } 358 } 359 ```