codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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 ```