1506.md (7159B)
1 Source: https://codeforces.com/blog/entry/89007 2 3 [1506A - Strange Table](/contest/1506/problem/A "Codeforces Round 710 (Div. 3)") 4 5 Problem author: [sodafago](/profile/sodafago "Specialist sodafago") 6 7 **Editorial** 8 9 Tutorial is loading... 10 11 **Solution** 12 13 ``` 14 #include <bits/stdc++.h> 15 16 using namespace std; 17 using ll = long long; 18 19 void solve() { 20 ll n, m, x; 21 cin >> n >> m >> x; 22 x--; 23 ll col = x / n; 24 ll row = x % n; 25 cout << row * m + col + 1 << "\n"; 26 } 27 28 int main() { 29 ios_base::sync_with_stdio(false); 30 cin.tie(nullptr); cout.tie(nullptr); 31 int n; 32 cin >> n; 33 while (n--) { 34 solve(); 35 } 36 } 37 ``` 38 39 [1506B - Partial Replacement](/contest/1506/problem/B "Codeforces Round 710 (Div. 3)") 40 41 Problem author: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 42 43 **Editorial** 44 45 Tutorial is loading... 46 47 **Solution** 48 49 ``` 50 #include <bits/stdc++.h> 51 using namespace std; 52 53 void solve() { 54 int n, k; 55 cin >> n >> k; 56 string s; 57 cin >> s; 58 int res = 1; 59 int i = s.find_first_of('*'); 60 while (true) { 61 int j = min(n - 1, i + k); 62 for (; i < j && s[j] == '.'; j--) {} 63 if (i == j) { 64 break; 65 } 66 res++; 67 i = j; 68 } 69 cout << res << "\n"; 70 } 71 72 int main() { 73 int tests; 74 cin >> tests; 75 while (tests-- > 0) { 76 solve(); 77 } 78 return 0; 79 } 80 ``` 81 82 [1506C - Double-ended Strings](/contest/1506/problem/C "Codeforces Round 710 (Div. 3)") 83 84 Problem author: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 85 86 **Editorial** 87 88 Tutorial is loading... 89 90 **Solution** 91 92 ``` 93 #include <bits/stdc++.h> 94 95 using namespace std; 96 using ll = long long; 97 98 void solve() { 99 string a, b; 100 cin >> a >> b; 101 int n = a.size(), m = b.size(); 102 int ans = 0; 103 for (int len = 1; len <= min(n, m); len++) { 104 for (int i = 0; i + len <= n; i++) { 105 for (int j = 0; j + len <= m; j++) { 106 if (a.substr(i, len) == b.substr(j, len)) { 107 ans = max(ans, len); 108 } 109 } 110 } 111 } 112 cout << a.size() + b.size() - 2 * ans << "\n"; 113 } 114 115 int main() { 116 ios_base::sync_with_stdio(false); 117 cin.tie(nullptr); cout.tie(nullptr); 118 int n; 119 cin >> n; 120 while (n--) { 121 solve(); 122 } 123 } 124 ``` 125 126 [1506D - Epic Transformation](/contest/1506/problem/D "Codeforces Round 710 (Div. 3)") 127 128 Problem author: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 129 130 **Editorial** 131 132 Tutorial is loading... 133 134 **Solution** 135 136 ``` 137 #include <bits/stdc++.h> 138 139 using namespace std; 140 using ll = long long; 141 142 void solve() { 143 priority_queue<pair<int, int>> q; 144 int n; 145 cin >> n; 146 map<int, int> v; 147 for (int i = 0; i < n; i++) { 148 int x; 149 cin >> x; 150 v[x]++; 151 } 152 for (auto [x, y] : v) { 153 q.push({y, x}); 154 } 155 int sz = n; 156 while (q.size() >= 2) { 157 auto [cnt1, x1] = q.top(); 158 q.pop(); 159 auto [cnt2, x2] = q.top(); 160 q.pop(); 161 cnt1--; 162 cnt2--; 163 sz -= 2; 164 if (cnt1) { 165 q.push({cnt1, x1}); 166 } 167 if (cnt2) { 168 q.push({cnt2, x2}); 169 } 170 } 171 cout << sz << "\n"; 172 } 173 174 int main() { 175 ios_base::sync_with_stdio(false); 176 cin.tie(nullptr); cout.tie(nullptr); 177 int n; 178 cin >> n; 179 while (n--) { 180 solve(); 181 } 182 } 183 ``` 184 185 [1506E - Restoring the Permutation](/contest/1506/problem/E "Codeforces Round 710 (Div. 3)") 186 187 Problem author: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 188 189 **Editorial** 190 191 Tutorial is loading... 192 193 **Solution** 194 195 ``` 196 #include <bits/stdc++.h> 197 using namespace std; 198 199 void placeLeft(vector<int> &q, bool minimize) { 200 set<int> left; 201 for (int i = 1; i <= (int) q.size(); i++) { 202 left.insert(i); 203 } 204 for (int i : q) { 205 if (i != -1) { 206 left.erase(i); 207 } 208 } 209 int lastPlaced = -1; 210 for (int &i : q) { 211 if (i == -1) { 212 set<int>::const_iterator it; 213 if (minimize) { 214 it = left.begin(); 215 } else { 216 it = --left.lower_bound(lastPlaced); 217 } 218 i = *it; 219 left.erase(it); 220 } else { 221 lastPlaced = i; 222 } 223 } 224 } 225 226 void solve() { 227 int n; 228 cin >> n; 229 vector<int> q(n); 230 for (int i = 0; i < n; i++) { 231 cin >> q[i]; 232 } 233 234 vector<int> res1(n, -1), res2(n, -1); 235 for (int i = 0, lastPlaced = -1; i < n; lastPlaced = q[i], i++) { 236 if (lastPlaced != q[i]) { 237 res1[i] = q[i]; 238 res2[i] = q[i]; 239 } 240 } 241 placeLeft(res1, true); 242 placeLeft(res2, false); 243 for (int x : res1) { 244 cout << x << " "; 245 } 246 cout << "\n"; 247 for (int x : res2) { 248 cout << x << " "; 249 } 250 cout << "\n"; 251 } 252 253 int main() { 254 int tests; 255 cin >> tests; 256 while (tests-- > 0) { 257 solve(); 258 } 259 return 0; 260 } 261 ``` 262 263 [1506F - Triangular Paths](/contest/1506/problem/F "Codeforces Round 710 (Div. 3)") 264 265 Problem author: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov"), [Stepavly](/profile/Stepavly "Master Stepavly"), [Supermagzzz](/profile/Supermagzzz "Master Supermagzzz") 266 267 **Editorial** 268 269 Tutorial is loading... 270 271 **Solution** 272 273 ``` 274 #include <bits/stdc++.h> 275 using namespace std; 276 277 bool isLeftArrow(int r, int c) { 278 return (r + c) % 2 == 0; 279 } 280 281 bool isRightArrow(int r, int c) { 282 return (r + c) % 2 == 1; 283 } 284 285 int calcDist(int r1, int c1, int r2, int c2) { 286 if (r1 - c1 == r2 - c2) { 287 return isRightArrow(r1, c1) ? 0 : r2 - r1; 288 } 289 r2 -= r1 - 1; 290 c2 -= c1 - 1; 291 if (isLeftArrow(r1, c1)) { 292 return (r2 - c2) / 2; 293 } else { 294 return (r2 - c2 + 1) / 2; 295 } 296 } 297 298 void solve() { 299 int n; 300 cin >> n; 301 vector<int> r(n); 302 vector<int> c(n); 303 for (int i = 0; i < n; i++) { 304 cin >> r[i]; 305 } 306 for (int i = 0; i < n; i++) { 307 cin >> c[i]; 308 } 309 vector<pair<int, int>> pts; 310 for (int i = 0; i < n; i++) { 311 pts.emplace_back(r[i], c[i]); 312 } 313 sort(pts.begin(), pts.end()); 314 int curR = 1, curC = 1; 315 int res = 0; 316 for (auto[nextR, nextC] : pts) { 317 res += calcDist(curR, curC, nextR, nextC); 318 curR = nextR; 319 curC = nextC; 320 } 321 cout << res << "\n"; 322 } 323 324 int main() { 325 int tests; 326 cin >> tests; 327 while (tests-- > 0) { 328 solve(); 329 } 330 return 0; 331 } 332 ``` 333 334 [1506G - Maximize the Remaining String](/contest/1506/problem/G "Codeforces Round 710 (Div. 3)") 335 336 Problem author: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 337 338 **Editorial** 339 340 Tutorial is loading... 341 342 **Solution** 343 344 ``` 345 #include <bits/stdc++.h> 346 using namespace std; 347 348 int distinct(string s) { 349 sort(s.begin(), s.end()); 350 return unique(s.begin(), s.end()) - s.begin(); 351 } 352 353 string filter(const string &s, char c) { 354 string t; 355 bool foundFirst = false; 356 for (char a : s) { 357 if (a != c && foundFirst) { 358 t += a; 359 } else if (a == c) { 360 foundFirst = true; 361 } 362 } 363 return t; 364 } 365 366 void solve() { 367 string s; 368 cin >> s; 369 int m = distinct(s); 370 unordered_set<char> used(s.begin(), s.end()); 371 string t; 372 while (m > 0) { 373 char maxC = -1; 374 for (char c : used) { 375 if (distinct(filter(s, c)) == m - 1) { 376 maxC = max(maxC, c); 377 } 378 } 379 t += maxC; 380 s = filter(s, maxC); 381 used.erase(maxC); 382 m--; 383 } 384 cout << t << "\n"; 385 } 386 387 int main() { 388 int tests; 389 cin >> tests; 390 while (tests-- > 0) { 391 solve(); 392 } 393 return 0; 394 } 395 ```