codeforces-scrape

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

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