codeforces-scrape

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

1165.md (6511B)


      1 Source: https://codeforces.com/blog/entry/67041
      2 
      3 [1165A - Remainder](/contest/1165/problem/A "Codeforces Round 560 (Div. 3)")
      4 
      5 Idea: [vovuh](/profile/vovuh "Candidate Master vovuh")
      6 
      7 **Tutorial**
      8 
      9 Tutorial is loading...
     10 
     11 **Solution**
     12 
     13 ```
     14 #include <bits/stdc++.h>
     15 
     16 using namespace std;
     17 
     18 int main() {
     19 #ifdef _DEBUG
     20 	freopen("input.txt", "r", stdin);
     21 //	freopen("output.txt", "w", stdout);
     22 #endif
     23 	
     24 	int n, x, y;
     25 	string s;
     26 	cin >> n >> x >> y >> s;
     27 	
     28 	int ans = 0;
     29 	for (int i = n - x; i < n; ++i) {
     30 		if (i == n - y - 1) ans += s[i] != '1';
     31 		else ans += s[i] != '0';
     32 	}
     33 	
     34 	cout << ans << endl;
     35 	
     36 	return 0;
     37 }
     38 ```
     39 
     40 [1165B - Polycarp Training](/contest/1165/problem/B "Codeforces Round 560 (Div. 3)")
     41 
     42 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
     43 
     44 **Tutorial**
     45 
     46 Tutorial is loading...
     47 
     48 **Solution**
     49 
     50 ```
     51 #include <bits/stdc++.h>
     52 
     53 using namespace std;
     54 
     55 int main() {
     56 #ifdef _DEBUG
     57 	freopen("input.txt", "r", stdin);
     58 //	freopen("output.txt", "w", stdout);
     59 #endif
     60 	
     61 	int n;
     62 	cin >> n;
     63 	vector<int> a(n);
     64 	for (int i = 0; i < n; ++i) {
     65 		cin >> a[i];
     66 	}
     67 	sort(a.begin(), a.end());
     68 	
     69 	int pos = 1;
     70 	for (int i = 0; i < n; ++i) {
     71 		if (a[i] >= pos) ++pos;
     72 	}
     73 	
     74 	cout << pos - 1 << endl;
     75 	
     76 	return 0;
     77 }
     78 ```
     79 
     80 [1165C - Good String](/contest/1165/problem/C "Codeforces Round 560 (Div. 3)")
     81 
     82 Idea: [BledDest](/profile/BledDest "Grandmaster BledDest")
     83 
     84 **Tutorial**
     85 
     86 Tutorial is loading...
     87 
     88 **Solution**
     89 
     90 ```
     91 #include<bits/stdc++.h>
     92 
     93 using namespace std;
     94 
     95 string s;
     96 int n;
     97 string res;
     98 
     99 int main()
    100 {
    101 	cin >> n >> s;
    102 	for(int i = 0; i < n; i++)
    103 	{
    104 		if(res.size() % 2 == 0 || res.back() != s[i])
    105 			res.push_back(s[i]);
    106 	}
    107 	if(res.size() % 2 == 1) res.pop_back();
    108 	cout << n - int(res.size()) << endl << res << endl;
    109 	return 0;
    110 }
    111 ```
    112 
    113 [1165D - Almost All Divisors](/contest/1165/problem/D "Codeforces Round 560 (Div. 3)")
    114 
    115 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
    116 
    117 **Tutorial**
    118 
    119 Tutorial is loading...
    120 
    121 **Solution**
    122 
    123 ```
    124 #include <bits/stdc++.h>
    125 
    126 using namespace std;
    127 
    128 int main() {
    129 #ifdef _DEBUG
    130 	freopen("input.txt", "r", stdin);
    131 //	freopen("output.txt", "w", stdout);
    132 #endif
    133 
    134 	int t;
    135 	cin >> t;
    136 	for (int i = 0; i < t; ++i) {
    137 
    138 		int n;
    139 		cin >> n;
    140 		vector<long long> d(n);
    141 		for (int i = 0; i < n; ++i) {
    142 			cin >> d[i];
    143 		}
    144 		sort(d.begin(), d.end());
    145 		long long x = d[0] * d[n - 1];
    146 		
    147 		vector<long long> dd;
    148 		for (int i = 2; i * 1ll * i <= x; ++i) {
    149 			if (x % i == 0) {
    150 				dd.push_back(i);
    151 				if (i != x / i) {
    152 					dd.push_back(x / i);
    153 				}
    154 			}
    155 		}
    156 		sort(dd.begin(), dd.end());
    157 		
    158 		if (dd == d) {
    159 			cout << x << endl;
    160 		} else {
    161 			cout << -1 << endl;
    162 		}
    163 	}
    164 	
    165 	return 0;
    166 }
    167 ```
    168 
    169 [1165E - Two Arrays and Sum of Functions](/contest/1165/problem/E "Codeforces Round 560 (Div. 3)")
    170 
    171 Idea: [vovuh](/profile/vovuh "Candidate Master vovuh")
    172 
    173 **Tutorial**
    174 
    175 Tutorial is loading...
    176 
    177 **Solution**
    178 
    179 ```
    180 #include <bits/stdc++.h>
    181 
    182 using namespace std;
    183 
    184 const int MOD = 998244353;
    185 
    186 int main() {
    187 #ifdef _DEBUG
    188 	freopen("input.txt", "r", stdin);
    189 //	freopen("output.txt", "w", stdout);
    190 #endif
    191 	
    192 	int n;
    193 	cin >> n;
    194 	vector<int> a(n), b(n);
    195 	for (int i = 0; i < n; ++i) {
    196 		cin >> a[i];
    197 	}
    198 	for (int i = 0; i < n; ++i) {
    199 		cin >> b[i];
    200 	}
    201 	
    202 	sort(b.begin(), b.end());
    203 	vector<pair<long long, int>> val(n);
    204 	for (int i = 0; i < n; ++i) {
    205 		val[i].first = (i + 1) * 1ll * (n - i) * a[i];
    206 		val[i].second = i;
    207 	}
    208 	sort(val.rbegin(), val.rend());
    209 	int ans = 0;
    210 	for (int i = 0; i < n; ++i) {
    211 		ans = (ans + (val[i].first % MOD * 1ll * b[i]) % MOD) % MOD;
    212 	}
    213 	cout << ans << endl;
    214 	
    215 	return 0;
    216 }
    217 ```
    218 
    219 [1165F1 - Microtransactions (easy version)](/contest/1165/problem/F1 "Codeforces Round 560 (Div. 3)")
    220 
    221 Idea: [BledDest](/profile/BledDest "Grandmaster BledDest")
    222 
    223 **Tutorial**
    224 
    225 Tutorial is loading...
    226 
    227 **Solution**
    228 
    229 ```
    230 #include <bits/stdc++.h>
    231 
    232 using namespace std;
    233 
    234 int n, m;
    235 vector<int> k;
    236 vector<pair<int, int>> q(1001);
    237 
    238 bool can(int day) {
    239 	vector<int> lst(n, -1);
    240 	for (int i = 0; i < m; ++i) {
    241 		if (q[i].first <= day) {
    242 			lst[q[i].second] = max(lst[q[i].second], q[i].first);
    243 		}
    244 	}
    245 	vector<vector<int>> off(1001);
    246 	for (int i = 0; i < n; ++i) {
    247 		if (lst[i] != -1) {
    248 			off[lst[i]].push_back(i);
    249 		}
    250 	}
    251 	vector<int> need = k;
    252 	int cur_money = 0;
    253 	for (int i = 0; i <= day; ++i) {
    254 		++cur_money;
    255 		if (i > 1000) continue;
    256 		for (auto it : off[i]) {
    257 			if (cur_money >= need[it]) {
    258 				cur_money -= need[it];
    259 				need[it] = 0;
    260 			} else {
    261 				need[it] -= cur_money;
    262 				cur_money = 0;
    263 				break;
    264 			}
    265 		}
    266 	}
    267 	return accumulate(need.begin(), need.end(), 0) * 2 <= cur_money;
    268 }
    269 
    270 int main() {
    271 #ifdef _DEBUG
    272 	freopen("input.txt", "r", stdin);
    273 //	freopen("output.txt", "w", stdout);
    274 #endif
    275 	
    276 	cin >> n >> m;
    277 	k = vector<int>(n);
    278 	for (int i = 0; i < n; ++i) {
    279 		cin >> k[i];
    280 	}
    281 	for (int i = 0; i < m; ++i) {
    282 		cin >> q[i].first >> q[i].second;
    283 		--q[i].first;
    284 		--q[i].second;
    285 	}
    286 	
    287 	for (int l = 0; l <= 2000; ++l) {
    288 		if (can(l)) {
    289 			cout << l + 1 << endl;
    290 			return 0;
    291 		}
    292 	}
    293 	
    294 	assert(false);
    295 	
    296 	return 0;
    297 }
    298 ```
    299 
    300 [1165F2 - Microtransactions (hard version)](/contest/1165/problem/F2 "Codeforces Round 560 (Div. 3)")
    301 
    302 Idea: [BledDest](/profile/BledDest "Grandmaster BledDest")
    303 
    304 **Tutorial**
    305 
    306 Tutorial is loading...
    307 
    308 **Solution**
    309 
    310 ```
    311 #include <bits/stdc++.h>
    312 
    313 using namespace std;
    314 
    315 int n, m;
    316 vector<int> k;
    317 vector<pair<int, int>> q(200001);
    318 
    319 bool can(int day) {
    320 	vector<int> lst(n, -1);
    321 	for (int i = 0; i < m; ++i) {
    322 		if (q[i].first <= day) {
    323 			lst[q[i].second] = max(lst[q[i].second], q[i].first);
    324 		}
    325 	}
    326 	vector<vector<int>> off(200001);
    327 	for (int i = 0; i < n; ++i) {
    328 		if (lst[i] != -1) {
    329 			off[lst[i]].push_back(i);
    330 		}
    331 	}
    332 	vector<int> need = k;
    333 	int cur_money = 0;
    334 	for (int i = 0; i <= day; ++i) {
    335 		++cur_money;
    336 		if (i > 200000) continue;
    337 		for (auto it : off[i]) {
    338 			if (cur_money >= need[it]) {
    339 				cur_money -= need[it];
    340 				need[it] = 0;
    341 			} else {
    342 				need[it] -= cur_money;
    343 				cur_money = 0;
    344 				break;
    345 			}
    346 		}
    347 	}
    348 	return accumulate(need.begin(), need.end(), 0) * 2 <= cur_money;
    349 }
    350 
    351 int main() {
    352 #ifdef _DEBUG
    353 	freopen("input.txt", "r", stdin);
    354 //	freopen("output.txt", "w", stdout);
    355 #endif
    356 	
    357 	cin >> n >> m;
    358 	k = vector<int>(n);
    359 	for (int i = 0; i < n; ++i) {
    360 		cin >> k[i];
    361 	}
    362 	for (int i = 0; i < m; ++i) {
    363 		cin >> q[i].first >> q[i].second;
    364 		--q[i].first;
    365 		--q[i].second;
    366 	}
    367 	
    368 	int l = 0, r = 400000;
    369 	while (r - l > 1) {
    370 		int mid = (l + r) >> 1;
    371 		if (can(mid)) r = mid;
    372 		else l = mid;
    373 	}
    374 	
    375 	for (int i = l; i <= r; ++i) {
    376 		if (can(i)) {
    377 			cout << i + 1 << endl;
    378 			return 0;
    379 		}
    380 	}
    381 	
    382 	assert(false);
    383 	
    384 	return 0;
    385 }
    386 ```