1624.md (7953B)
1 Source: https://codeforces.com/blog/entry/98942 2 3 [1624A - Plus One on the Subset](/contest/1624/problem/A "Codeforces Round 764 (Div. 3)") 4 5 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 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 typedef long long ll; 19 20 #define forn(i, n) for (int i = 0; i < int(n); i++) 21 22 void solve() { 23 int n; 24 cin >> n; 25 int a[n]; 26 for (int i = 0; i < n; ++i) { 27 cin >> a[i]; 28 } 29 int MIN = INT_MAX; 30 int MAX = INT_MIN; 31 for (int i = 0; i < n; ++i) { 32 MIN = min(MIN, a[i]); 33 MAX = max(MAX, a[i]); 34 } 35 cout << MAX - MIN << '\n'; 36 } 37 int main() { 38 int tests; 39 cin >> tests; 40 forn(tt, tests) { 41 solve(); 42 } 43 } 44 ``` 45 46 [1624B - Make AP](/contest/1624/problem/B "Codeforces Round 764 (Div. 3)") 47 48 Idea: [ibraevdmitriy](/profile/ibraevdmitriy "Master ibraevdmitriy") 49 50 **Tutorial** 51 52 Tutorial is loading... 53 54 **Solution** 55 56 ``` 57 #include<bits/stdc++.h> 58 59 using namespace std; 60 61 void solveTest() { 62 int a, b, c; 63 cin >> a >> b >> c; 64 65 int new_a = b - (c - b); 66 if(new_a >= a && new_a % a == 0 && new_a != 0) { 67 cout << "YES\n"; 68 return; 69 } 70 71 int new_b = a + (c - a)/2; 72 if(new_b >= b && (c-a)%2 == 0 && new_b % b == 0 && new_b != 0) { 73 cout << "YES\n"; 74 return; 75 } 76 77 int new_c = a + 2*(b - a); 78 if(new_c >= c && new_c % c == 0 && new_c != 0) { 79 cout << "YES\n"; 80 return; 81 } 82 83 cout << "NO\n"; 84 return; 85 } 86 87 int main() { 88 ios_base::sync_with_stdio(false); 89 cin.tie(0); cout.tie(0); 90 int tt; 91 cin >> tt; 92 while(tt--) 93 solveTest(); 94 return 0; 95 } 96 ``` 97 98 [1624C - Division by Two and Permutation](/contest/1624/problem/C "Codeforces Round 764 (Div. 3)") 99 100 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 101 102 **Tutorial** 103 104 Tutorial is loading... 105 106 **Solution** 107 108 ``` 109 #include<bits/stdc++.h> 110 using namespace std; 111 112 void solve(){ 113 int n; 114 cin >> n; 115 vector<int>a(n), used(n + 1, false); 116 for(auto &i : a) cin >> i; 117 sort(a.begin(), a.end(), [] (int a, int b) { 118 return a > b; 119 }); 120 bool ok = true; 121 for(auto &i : a){ 122 int x = i; 123 while(x > n or used[x]) x /= 2; 124 if(x > 0) used[x] = true; 125 else ok = false; 126 } 127 cout << (ok ? "YES" : "NO") << '\n'; 128 129 } 130 131 int main(){ 132 ios_base :: sync_with_stdio(false); 133 cin.tie(nullptr); 134 int t; 135 cin >> t; 136 while(t--){ 137 solve(); 138 } 139 return 0; 140 } 141 ``` 142 143 [1624D - Palindromes Coloring](/contest/1624/problem/D "Codeforces Round 764 (Div. 3)") 144 145 Idea: [ibraevdmitriy](/profile/ibraevdmitriy "Master ibraevdmitriy") 146 147 **Tutorial** 148 149 Tutorial is loading... 150 151 **Solution** 152 153 ``` 154 #include <iostream> 155 #include <vector> 156 #include <stack> 157 #include <algorithm> 158 159 using namespace std; 160 161 typedef long long ll; 162 const int MAX_N = 2e5; 163 164 int main(int argc, char* argv[]) { 165 int t; 166 cin >> t; 167 for (int _ = 0; _ < t; ++_) { 168 int n, k; 169 string s; 170 cin >> n >> k >> s; 171 vector<int> cnt(26); 172 for (char c : s) { 173 cnt[c - 'a']++; 174 } 175 int cntPairs = 0, cntOdd = 0; 176 for (int c : cnt) { 177 cntPairs += c / 2; 178 cntOdd += c % 2; 179 } 180 int ans = 2 * (cntPairs / k); 181 cntOdd += 2 * (cntPairs % k); 182 if (cntOdd >= k) { 183 ans++; 184 } 185 cout << ans << '\n'; 186 } 187 } 188 ``` 189 190 [1624E - Masha-forgetful](/contest/1624/problem/E "Codeforces Round 764 (Div. 3)") 191 192 Idea: [Aris](/profile/Aris "Candidate Master Aris") 193 194 **Tutorial** 195 196 Tutorial is loading... 197 198 **Solution** 199 200 ``` 201 #include <bits/stdc++.h> 202 203 using namespace std; 204 205 #define forn(i, n) for (int i = 0; i < int(n); i++) 206 #define sz(v) (int)v.size() 207 208 const int N = 1e4; 209 map<string, bool> have; 210 map<string, tuple<int,int,int>> pos; 211 212 void solve() { 213 int n, m; cin >> n >> m; 214 vector<bool> dp(m+1, false); 215 vector<int> pr(m+1); 216 vector<string> cache; 217 dp[0] = true; 218 219 forn(i, n) { 220 string s; cin >> s; 221 forn(j, m) { 222 string t; 223 t += s[j]; 224 for(int k = 1; k <= 2; k++) { 225 if (k + j >= m) break; 226 t += s[j+k]; 227 228 if (!have[t]) { 229 have[t] = true; 230 pos[t] = make_tuple(j, j+k, i); 231 cache.push_back(t); 232 } 233 } 234 } 235 } 236 237 string s; cin >> s; 238 forn(i, m) { 239 string t; 240 t += s[i]; 241 for (int k = 1; k <= 2; k++) { 242 if (i - k < 0) break; 243 t = s[i-k] + t; 244 if (have[t] && dp[i-k]) { 245 dp[i+1] = true; 246 pr[i+1] = i-k; 247 } 248 if (dp[i+1]) break; 249 } 250 } 251 for (string t : cache) { 252 have[t] = false; 253 } 254 255 if (!dp[m]) { 256 cout << "-1\n"; 257 return; 258 } 259 vector<tuple<int,int,int>> ans; 260 261 for (int k = m; k > 0; ) { 262 int p = pr[k]; 263 string t = s.substr(p, k - p); 264 ans.emplace_back(pos[t]); 265 k = p; 266 } 267 268 cout << sz(ans) << '\n'; 269 reverse(ans.begin(), ans.end()); 270 for (auto [l,r,i] : ans) cout << l+1 << ' ' << r+1 << ' ' << i+1 << '\n'; 271 } 272 273 int main() { 274 int t; 275 cin >> t; 276 277 forn(tt, t) { 278 solve(); 279 } 280 } 281 ``` 282 283 [1624F - Interacdive Problem](/contest/1624/problem/F "Codeforces Round 764 (Div. 3)") 284 285 Idea: [Vladosiya](/profile/Vladosiya "Expert Vladosiya") 286 287 **Tutorial** 288 289 Tutorial is loading... 290 291 **Solution** 292 293 ``` 294 #include <bits/stdc++.h> 295 296 #define int long long 297 #define mp make_pair 298 #define x first 299 #define y second 300 #define all(a) (a).begin(), (a).end() 301 #define rall(a) (a).rbegin(), (a).rend() 302 303 typedef long double ld; 304 typedef long long ll; 305 306 using namespace std; 307 308 mt19937 rnd(143); 309 310 const int inf = 1e10; 311 const int M = 998244353; 312 const ld pi = atan2(0, -1); 313 const ld eps = 1e-4; 314 315 signed main(){ 316 int n; 317 cin >> n; 318 int l = 1, r = n; 319 int div = 0; 320 while(r - l > 1){ 321 int mid = (r + l) / 2; 322 cout << "+ "<< n - mid << endl; 323 int d; 324 cin >> d; 325 if(d > div)l = mid; 326 else r = mid; 327 l = (l + n - mid) % n; 328 r = (r + n - mid) % n; 329 if(r == 0) r = n; 330 div = d; 331 } 332 cout << "! " << div * n + l; 333 return 0; 334 } 335 ``` 336 337 [1624G - MinOr Tree](/contest/1624/problem/G "Codeforces Round 764 (Div. 3)") 338 339 Idea: [Vladosiya](/profile/Vladosiya "Expert Vladosiya") 340 341 **Tutorial** 342 343 Tutorial is loading... 344 345 **Solution** 346 347 ``` 348 #include <bits/stdc++.h> 349 350 #define int long long 351 #define mp make_pair 352 #define x first 353 #define y second 354 #define all(a) (a).begin(), (a).end() 355 #define rall(a) (a).rbegin(), (a).rend() 356 357 typedef long double ld; 358 typedef long long ll; 359 360 using namespace std; 361 362 mt19937 rnd(143); 363 364 const int inf = 1e9; 365 const int M = 998244353; 366 const ld pi = atan2(0, -1); 367 const ld eps = 1e-4; 368 369 int n, cur; 370 vector<vector<pair<int, int>>> sl; 371 372 void dfs(int v, vector<bool> &used){ 373 used[v] = true; 374 for(auto e: sl[v]){ 375 int u = e.x, w = e.y; 376 if(!used[u] && (cur | w) == cur){ 377 dfs(u, used); 378 } 379 } 380 } 381 382 void cnt(int pw){ 383 if(pw < 0) return; 384 int d = (ll) 1 << pw; 385 cur -= d; 386 vector<bool> used(n); 387 dfs(0, used); 388 for(bool b: used){ 389 if(!b) { 390 cur += d; 391 break; 392 } 393 } 394 cnt(pw - 1); 395 } 396 397 void solve() { 398 int m; 399 cin >> n >> m; 400 sl.assign(n, vector<pair<int, int>>(0)); 401 for(int i = 0; i < m; ++i){ 402 int u, v, w; 403 cin >> u >> v >> w; 404 --u, --v; 405 sl[u].emplace_back(v, w); 406 sl[v].emplace_back(u, w); 407 } 408 cur = 1; 409 int bit = 0; 410 for(; cur < inf; bit++){ 411 cur = 2 * cur + 1; 412 } 413 cnt(bit); 414 cout << cur; 415 } 416 417 bool multi = true; 418 419 signed main() { 420 int t = 1; 421 if (multi) { 422 cin >> t; 423 } 424 for (; t != 0; --t) { 425 solve(); 426 cout << "\n"; 427 } 428 return 0; 429 } 430 ```