1367.md (7120B)
1 Source: https://codeforces.com/blog/entry/78864 2 3 All problems were developed by me [Supermagzzz](/profile/Supermagzzz "Мастер Supermagzzz") and [Stepavly](/profile/Stepavly "Мастер Stepavly"). 4 5 [1367A - Короткие подстроки](/contest/1367/problem/A "Codeforces Round 650 (Div. 3)") 6 7 Author: [MikeMirzayanov](/profile/MikeMirzayanov "Штаб, MikeMirzayanov") 8 9 **Editorial** 10 11 Tutorial is loading... 12 13 **Solution** 14 15 ``` 16 #include <bits/stdc++.h> 17 using namespace std; 18 19 int main() { 20 int t; 21 cin >> t; 22 23 for (int test = 1; test <= t; test++) { 24 string b; 25 cin >> b; 26 27 string a = b.substr(0, 2); 28 29 for (int i = 3; i < b.size(); i += 2) { 30 a += b[i]; 31 } 32 33 cout << a << endl; 34 } 35 36 return 0; 37 } 38 ``` 39 40 [1367B - Четный массив](/contest/1367/problem/B "Codeforces Round 650 (Div. 3)") 41 42 Авторы: [Supermagzzz](/profile/Supermagzzz "Мастер Supermagzzz"), [Stepavly](/profile/Stepavly "Мастер Stepavly") 43 44 **Editorial** 45 46 Tutorial is loading... 47 48 **Solution** 49 50 ``` 51 #include <bits/stdc++.h> 52 53 using namespace std; 54 using ld = long double; 55 using ll = long long; 56 57 void solve() { 58 int n; 59 cin >> n; 60 int a = 0, b = 0; 61 for (int i = 0; i < n; i++) { 62 int x; 63 cin >> x; 64 if (x % 2 != i % 2) { 65 if (i % 2 == 0) { 66 a++; 67 } else { 68 b++; 69 } 70 } 71 } 72 if (a != b) { 73 cout << -1 << endl; 74 } else { 75 cout << a << endl; 76 } 77 } 78 79 int main() { 80 int n; 81 cin >> n; 82 while (n--) { 83 solve(); 84 } 85 } 86 ``` 87 88 [1367C - Социальная дистанция](/contest/1367/problem/C "Codeforces Round 650 (Div. 3)") 89 90 Авторы: [Supermagzzz](/profile/Supermagzzz "Мастер Supermagzzz"), [Stepavly](/profile/Stepavly "Мастер Stepavly") 91 92 **Editorial** 93 94 Tutorial is loading... 95 96 **Solution** 97 98 ``` 99 #include <bits/stdc++.h> 100 using namespace std; 101 102 int main() { 103 int t; 104 cin >> t; 105 106 for (int test = 1; test <= t; test++) { 107 int n, k; 108 cin >> n >> k; 109 string s; 110 cin >> s; 111 112 int res = 0; 113 114 for (int i = 0; i < n;) { 115 int j = i + 1; 116 117 for (; j < n && s[j] != '1'; j++); 118 119 int left = s[i] == '1' ? k : 0; 120 int right = j < n && s[j] == '1' ? k : 0; 121 int len = j - i; 122 123 if (left == k) { 124 len--; 125 } 126 127 len -= left + right; 128 129 if (len > 0) { 130 res += (len + k) / (k + 1); 131 } 132 133 i = j; 134 } 135 136 cout << res << endl; 137 } 138 139 return 0; 140 } 141 ``` 142 143 [1367D - Задача на доске](/contest/1367/problem/D "Codeforces Round 650 (Div. 3)") Автор: [MikeMirzayanov](/profile/MikeMirzayanov "Штаб, MikeMirzayanov") 144 145 **Editorial** 146 147 Tutorial is loading... 148 149 **Solution** 150 151 ``` 152 #include <bits/stdc++.h> 153 154 using namespace std; 155 156 #define forn(i, n) for (int i = 0; i < int(n); i++) 157 158 int main() { 159 int q; 160 cin >> q; 161 forn(qq, q) { 162 string s; 163 cin >> s; 164 int n; 165 cin >> n; 166 vector<int> b(n); 167 forn(i, n) 168 cin >> b[i]; 169 vector<vector<int>> groups; 170 while (true) { 171 vector<int> pos; 172 forn(i, n) 173 if (b[i] == 0) 174 pos.push_back(i); 175 if (pos.empty()) 176 break; 177 groups.push_back(pos); 178 forn(i, n) 179 if (b[i] == 0) 180 b[i] = INT_MAX; 181 else 182 for (int pp: pos) 183 b[i] -= abs(i - pp); 184 } 185 map<char, int> cnts; 186 forn(i, s.size()) 187 cnts[s[i]]++; 188 auto j = cnts.rbegin(); 189 string t(n, '?'); 190 for (auto g: groups) { 191 while (j->second < g.size()) 192 j++; 193 for (int pp: g) 194 t[pp] = j->first; 195 j++; 196 } 197 cout << t << endl; 198 } 199 } 200 ``` 201 202 [1367E - Сборка ожерелья](/contest/1367/problem/E "Codeforces Round 650 (Div. 3)") 203 204 Автор: [MikeMirzayanov](/profile/MikeMirzayanov "Штаб, MikeMirzayanov") 205 206 **Editorial** 207 208 Tutorial is loading... 209 210 **Solution** 211 212 ``` 213 #include <bits/stdc++.h> 214 using namespace std; 215 216 int main() { 217 int test; 218 cin >> test; 219 220 while (test--) { 221 int n, k; 222 cin >> n >> k; 223 string s; 224 cin >> s; 225 226 vector<int> cnt(26); 227 228 for (char c : s) { 229 cnt[c - 'a']++; 230 } 231 232 for (int len = n; len >= 1; len--) { 233 vector<bool> used(len); 234 vector<int> cycles; 235 236 for (int i = 0; i < len; i++) { 237 if (used[i]) { 238 continue; 239 } 240 241 int j = (i + k) % len; 242 used[i] = true; 243 cycles.push_back(0); 244 cycles.back()++; 245 246 while (!used[j]) { 247 cycles.back()++; 248 used[j] = true; 249 j = (j + k) % len; 250 } 251 } 252 253 vector<int> cur_cnt(cnt); 254 255 sort(cycles.begin(), cycles.end()); 256 sort(cur_cnt.begin(), cur_cnt.end()); 257 258 bool can_fill = true; 259 260 while (!cycles.empty()) { 261 if (cur_cnt.back() < cycles.back()) { 262 can_fill = false; 263 break; 264 } else { 265 cur_cnt.back() -= cycles.back(); 266 cycles.pop_back(); 267 sort(cur_cnt.begin(), cur_cnt.end()); 268 } 269 } 270 271 if (can_fill) { 272 cout << len << endl; 273 break; 274 } 275 } 276 } 277 } 278 ``` 279 280 [1367F2 - Летающая сортировка (сложная версия)](/contest/1367/problem/F2 "Codeforces Round 650 (Div. 3)") 281 282 Автор: [MikeMirzayanov](/profile/MikeMirzayanov "Штаб, MikeMirzayanov") [Stepavly](/profile/Stepavly "Мастер Stepavly") [Supermagzzz](/profile/Supermagzzz "Мастер Supermagzzz") 283 284 **Editorial** 285 286 Tutorial is loading... 287 288 **Solution** 289 290 ``` 291 #include <bits/stdc++.h> 292 293 using namespace std; 294 using ld = long double; 295 using ll = long long; 296 297 void solve() { 298 int n; 299 cin >> n; 300 vector<int> v(n); 301 vector<pair<int, int>> a(n); 302 for (int i = 0; i < n; i++) { 303 cin >> v[i]; 304 a[i] = {v[i], i}; 305 } 306 sort(a.begin(), a.end()); 307 vector<int> p(n); 308 int j = 0; 309 unordered_multiset<int> next; 310 for (int i = 0; i < n; i++) { 311 if (i > 0 && a[i].first != a[i - 1].first) { 312 j++; 313 } 314 p[a[i].second] = j; 315 next.insert(j); 316 } 317 unordered_map<int, int> d; 318 vector<int> dp1(n), dp2(n), dp3(n), cnt(n); 319 for (int i = 0; i < n; i++) { 320 if (next.count(p[i])) { 321 next.erase(next.find(p[i])); 322 } 323 if (d.count(p[i] - 1)) { 324 if (!d.count(p[i])) { 325 dp2[i] = max(dp2[i], dp1[d[p[i] - 1]] + 1); 326 if (!next.count(p[i] - 1)) { 327 dp2[i] = max(dp2[i], dp2[d[p[i] - 1]] + 1); 328 } 329 } 330 if (!next.count(p[i] - 1)) { 331 dp3[i] = max(dp3[i], dp2[d[p[i] - 1]] + 1); 332 } 333 dp3[i] = max(dp3[i], dp1[d[p[i] - 1]] + 1); 334 } 335 if (d.count(p[i])) { 336 dp3[i] = max(dp3[i], dp3[d[p[i]]] + 1); 337 dp2[i] = max(dp2[i], dp2[d[p[i]]] + 1); 338 dp1[i] = dp1[d[p[i]]] + 1; 339 } else { 340 dp1[i] = 1; 341 } 342 dp2[i] = max(dp2[i], dp1[i]); 343 dp3[i] = max(dp3[i], dp2[i]); 344 d[p[i]] = i; 345 } 346 cout << n - *max_element(dp3.begin(), dp3.end()) << "\n"; 347 } 348 349 int main() { 350 int n; 351 cin >> n; 352 while (n--) { 353 solve(); 354 } 355 } 356 ```