1256.md (5986B)
1 Source: https://codeforces.com/blog/entry/71184 2 3 [1256A - Payment Without Change](/contest/1256/problem/A "Codeforces Round 598 (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 <iostream> 15 16 using namespace std; 17 18 int main() { 19 int q; 20 cin >> q; 21 22 for (int qr = 0; qr < q; ++qr) { 23 int a, b, n, s; 24 cin >> a >> b >> n >> s; 25 26 if (s % n <= b && 1ll * a * n + b >= s) { 27 cout << "YES\n"; 28 } 29 else { 30 cout << "NO\n"; 31 } 32 } 33 } 34 ``` 35 36 [1256B - Minimize the Permutation](/contest/1256/problem/B "Codeforces Round 598 (Div. 3)") 37 38 Idea: [vovuh](/profile/vovuh "Candidate Master vovuh") 39 40 **Tutorial** 41 42 Tutorial is loading... 43 44 **Solution** 45 46 ``` 47 #include <bits/stdc++.h> 48 49 using namespace std; 50 51 int main() { 52 #ifdef _DEBUG 53 freopen("input.txt", "r", stdin); 54 // freopen("output.txt", "w", stdout); 55 #endif 56 57 int q; 58 cin >> q; 59 for (int i = 0; i < q; ++i) { 60 int n; 61 cin >> n; 62 vector<int> a(n); 63 for (int j = 0; j < n; ++j) { 64 cin >> a[j]; 65 --a[j]; 66 } 67 int pos = 0; 68 while (pos < n) { 69 int nxt = min_element(a.begin() + pos, a.end()) - a.begin(); 70 int el = a[nxt]; 71 a.erase(a.begin() + nxt); 72 a.insert(a.begin() + pos, el); 73 if (pos == nxt) pos = nxt + 1; 74 else pos = nxt; 75 } 76 for (auto it : a) cout << it + 1 << " "; 77 cout << endl; 78 } 79 80 return 0; 81 } 82 ``` 83 84 [1256C - Platforms Jumping](/contest/1256/problem/C "Codeforces Round 598 (Div. 3)") 85 86 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 87 88 **Tutorial** 89 90 Tutorial is loading... 91 92 **Solution** 93 94 ``` 95 #include <bits/stdc++.h> 96 97 using namespace std; 98 99 int main() { 100 #ifdef _DEBUG 101 freopen("input.txt", "r", stdin); 102 // freopen("output.txt", "w", stdout); 103 #endif 104 105 int n, m, d; 106 cin >> n >> m >> d; 107 vector<int> c(m); 108 for (int i = 0; i < m; ++i) { 109 cin >> c[i]; 110 } 111 112 vector<int> ans(n + 2); 113 for (int i = m - 1, pos = n; i >= 0; --i) { 114 for (int len = 0; len < c[i]; ++len) { 115 ans[pos - len] = i + 1; 116 } 117 pos -= c[i]; 118 } 119 120 int now = 0; 121 while (true) { 122 while (now + 1 < n + 1 && ans[now + 1] > 0) ++now; 123 if (now + d >= n + 1) break; 124 if (ans[now + d] == 0) { 125 int lpos = -1; 126 for (int i = now + d; i < n + 2; ++i) { 127 if (ans[i] != 0) { 128 lpos = i; 129 break; 130 } 131 } 132 if (lpos == -1) { 133 cout << "NO" << endl; 134 return 0; 135 } 136 int rpos = -1; 137 for (int i = lpos; i < n + 2; ++i) { 138 if (ans[i] == ans[lpos]) rpos = i; 139 } 140 while (ans[now + d] == 0) { 141 swap(ans[lpos - 1], ans[rpos]); 142 --lpos, --rpos; 143 } 144 } 145 now += d; 146 } 147 148 cout << "YES" << endl; 149 for (int i = 1; i <= n; ++i) { 150 cout << ans[i] << " "; 151 } 152 cout << endl; 153 154 return 0; 155 } 156 ``` 157 158 [1256D - Binary String Minimizing](/contest/1256/problem/D "Codeforces Round 598 (Div. 3)") 159 160 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 161 162 **Tutorial** 163 164 Tutorial is loading... 165 166 **Solution** 167 168 ``` 169 #include <bits/stdc++.h> 170 171 using namespace std; 172 173 int main() { 174 #ifdef _DEBUG 175 freopen("input.txt", "r", stdin); 176 // freopen("output.txt", "w", stdout); 177 #endif 178 179 int q; 180 cin >> q; 181 while (q--) { 182 int n; 183 long long k; 184 string s; 185 cin >> n >> k >> s; 186 string res; 187 int cnt = 0; 188 bool printed = false; 189 for (int i = 0; i < n; ++i) { 190 if (s[i] == '0') { 191 if (cnt <= k) { 192 res += '0'; 193 k -= cnt; 194 } else { 195 res += string(cnt - k, '1'); 196 res += '0'; 197 res += string(k, '1'); 198 res += s.substr(i + 1); 199 cout << res << endl; 200 printed = true; 201 break; 202 } 203 } else { 204 ++cnt; 205 } 206 } 207 208 if (!printed) { 209 res += string(cnt, '1'); 210 cout << res << endl; 211 } 212 } 213 214 return 0; 215 } 216 ``` 217 218 [1256E - Yet Another Division Into Teams](/contest/1256/problem/E "Codeforces Round 598 (Div. 3)") 219 220 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 221 222 **Tutorial** 223 224 Tutorial is loading... 225 226 **Solution** 227 228 ``` 229 #include <bits/stdc++.h> 230 231 using namespace std; 232 233 typedef pair<int, int> pt; 234 235 #define x first 236 #define y second 237 #define mp make_pair 238 239 const int N = 200043; 240 const int INF = int(1e9) + 43; 241 242 int n; 243 int dp[N]; 244 int p[N]; 245 pt a[N]; 246 int t[N]; 247 248 int main() { 249 scanf("%d", &n); 250 for(int i = 0; i < n; i++) 251 { 252 a[i].y = i; 253 scanf("%d", &a[i].x); 254 } 255 sort(a, a + n); 256 for(int i = 1; i <= n; i++) 257 { 258 dp[i] = INF; 259 p[i] = -1; 260 } 261 for(int i = 0; i < n; i++) 262 for(int j = 3; j <= 5 && i + j <= n; j++) 263 { 264 int diff = a[i + j - 1].x - a[i].x; 265 if(dp[i + j] > dp[i] + diff) 266 { 267 p[i + j] = i; 268 dp[i + j] = dp[i] + diff; 269 } 270 } 271 int cur = n; 272 int cnt = 0; 273 while(cur != 0) 274 { 275 for(int i = cur - 1; i >= p[cur]; i--) 276 t[a[i].y] = cnt; 277 cnt++; 278 cur = p[cur]; 279 } 280 printf("%d %d\n", dp[n], cnt); 281 for(int i = 0; i < n; i++) 282 { 283 if(i) printf(" "); 284 printf("%d", t[i] + 1); 285 } 286 puts(""); 287 return 0; 288 } 289 ``` 290 291 [1256F - Equalizing Two Strings](/contest/1256/problem/F "Codeforces Round 598 (Div. 3)") 292 293 Idea: [vovuh](/profile/vovuh "Candidate Master vovuh") 294 295 **Tutorial** 296 297 Tutorial is loading... 298 299 **Solution** 300 301 ``` 302 #include <bits/stdc++.h> 303 304 using namespace std; 305 306 int main() { 307 #ifdef _DEBUG 308 freopen("input.txt", "r", stdin); 309 // freopen("output.txt", "w", stdout); 310 #endif 311 312 int q; 313 cin >> q; 314 for (int i = 0; i < q; ++i) { 315 int n; 316 string s, t; 317 cin >> n >> s >> t; 318 vector<int> cnts(26), cntt(26); 319 for (int j = 0; j < n; ++j) { 320 ++cnts[s[j] - 'a']; 321 ++cntt[t[j] - 'a']; 322 } 323 bool ok = true; 324 bool good = false; 325 for (int j = 0; j < 26; ++j) { 326 ok &= cnts[j] == cntt[j]; 327 good |= cnts[j] > 1; 328 } 329 if (!ok) { 330 cout << "NO" << endl; 331 continue; 332 } 333 if (good) { 334 cout << "YES" << endl; 335 continue; 336 } 337 int invs = 0, invt = 0; 338 for (int l = 0; l < n; ++l) { 339 for (int r = 0; r < l; ++r) { 340 invs += s[l] > s[r]; 341 invt += t[l] > t[r]; 342 } 343 } 344 ok &= (invs & 1) == (invt & 1); 345 if (ok) cout << "YES" << endl; 346 else cout << "NO" << endl; 347 } 348 349 return 0; 350 } 351 ```