codeforces-scrape

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

1183.md (7436B)


      1 Source: https://codeforces.com/blog/entry/68003
      2 
      3 [1183A - Nearest Interesting Number](/contest/1183/problem/A "Codeforces Round 570 (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 <bits/stdc++.h>
     15 
     16 using namespace std;
     17 
     18 #define forn(i, n) for (int i = 0; i < int(n); i++)
     19 
     20 int sum(int a) {
     21     int result = 0;
     22     while (a > 0) {
     23         result += a % 10;
     24         a /= 10;
     25     }
     26     return result;
     27 }
     28 
     29 int main() {
     30     int a;
     31     cin >> a;
     32     while (sum(a) % 4 != 0) {
     33         a++;
     34     }
     35     cout << a << endl;
     36 }
     37 ```
     38 
     39 [1183B - Equalize Prices](/contest/1183/problem/B "Codeforces Round 570 (Div. 3)")
     40 
     41 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
     42 
     43 **Tutorial**
     44 
     45 Tutorial is loading...
     46 
     47 **Solution**
     48 
     49 ```
     50 #include <bits/stdc++.h>
     51 
     52 using namespace std;
     53 
     54 int main() {
     55 #ifdef _DEBUG
     56 	freopen("input.txt", "r", stdin);
     57 //	freopen("output.txt", "w", stdout);
     58 #endif
     59 	
     60 	int q;
     61 	cin >> q;
     62 	for (int i = 0; i < q; ++i) {
     63 		int n, k;
     64 		cin >> n >> k;
     65 		vector<int> a(n);
     66 		for (int j = 0; j < n; ++j) {
     67 			cin >> a[j];
     68 		}
     69 		int mn = *min_element(a.begin(), a.end());
     70 		int mx = *max_element(a.begin(), a.end());
     71 		if (mx - mn > 2 * k) cout << -1 << endl;
     72 		else cout << mn + k << endl;
     73 	}
     74 	
     75 	return 0;
     76 }
     77 ```
     78 
     79 [1183C - Computer Game](/contest/1183/problem/C "Codeforces Round 570 (Div. 3)")
     80 
     81 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") and [vovuh](/profile/vovuh "Candidate Master vovuh") and [BledDest](/profile/BledDest "Grandmaster BledDest")
     82 
     83 **Tutorial**
     84 
     85 Tutorial is loading...
     86 
     87 **Solution**
     88 
     89 ```
     90 #include <bits/stdc++.h>
     91 
     92 using namespace std;
     93 
     94 int main() {
     95 #ifdef _DEBUG
     96 	freopen("input.txt", "r", stdin);
     97 //	freopen("output.txt", "w", stdout);
     98 #endif
     99 	
    100 	int q;
    101 	cin >> q;
    102 	for (int i = 0; i < q; ++i) {
    103 		long long k, n, a, b;
    104 		cin >> k >> n >> a >> b;
    105 		k -= n * a;
    106 		if (k > 0) {
    107 			cout << n << endl;
    108 		} else {
    109 			k = -k;
    110 			++k;
    111 			long long diff = a - b;
    112 			long long turns = (k + diff - 1) / diff;
    113 			if (turns > n) {
    114 				cout << -1 << '\n';
    115 			} else {
    116 				cout << n - turns << '\n';
    117 			}
    118 		}
    119 	}
    120 	
    121 	return 0;
    122 }
    123 ```
    124 
    125 [1183D - Candy Box (easy version)](/contest/1183/problem/D "Codeforces Round 570 (Div. 3)")
    126 
    127 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
    128 
    129 **Tutorial**
    130 
    131 Tutorial is loading...
    132 
    133 **Solution**
    134 
    135 ```
    136 #include <bits/stdc++.h>
    137 
    138 using namespace std;
    139 
    140 int main() {
    141 #ifdef _DEBUG
    142 	freopen("input.txt", "r", stdin);
    143 //	freopen("output.txt", "w", stdout);
    144 #endif
    145 
    146 	int q;
    147 	cin >> q;
    148 	for (int t = 0; t < q; ++t) {
    149 		int n;
    150 		cin >> n;
    151 		vector<int> cnt(n + 1);
    152 		for (int i = 0; i < n; ++i) {
    153 			int x;
    154 			cin >> x;
    155 			++cnt[x];
    156 		}
    157 		sort(cnt.rbegin(), cnt.rend());
    158 		int ans = cnt[0];
    159 		int lst = cnt[0];
    160 		for (int i = 1; i <= n; ++i) {
    161 			if (lst == 0) break;
    162 			if (cnt[i] >= lst) {
    163 				ans += lst - 1;
    164 				lst -= 1;
    165 			} else {
    166 				ans += cnt[i];
    167 				lst = cnt[i];
    168 			}
    169 		}
    170 		cout << ans << endl;
    171 	}
    172 	
    173 	return 0;
    174 }
    175 ```
    176 
    177 [1183E - Subsequences (easy version)](/contest/1183/problem/E "Codeforces Round 570 (Div. 3)")
    178 
    179 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
    180 
    181 **Tutorial**
    182 
    183 Tutorial is loading...
    184 
    185 **Solution**
    186 
    187 ```
    188 #include <bits/stdc++.h>
    189 
    190 using namespace std;
    191 
    192 int main() {
    193 #ifdef _DEBUG
    194 	freopen("input.txt", "r", stdin);
    195 //	freopen("output.txt", "w", stdout);
    196 #endif
    197 	
    198 	int n, k;
    199 	cin >> n >> k;
    200 	string s;
    201 	cin >> s;
    202 	
    203 	int ans = 0;
    204 	queue<string> q;
    205 	set<string> st;
    206 	q.push(s);
    207 	st.insert(s);
    208 	while (!q.empty() && int(st.size()) < k) {
    209 		string v = q.front();
    210 		q.pop();
    211 		for (int i = 0; i < int(v.size()); ++i) {
    212 			string nv = v;
    213 			nv.erase(i, 1);
    214 			if (!st.count(nv) && int(st.size()) + 1 <= k) {
    215 				q.push(nv);
    216 				st.insert(nv);
    217 				ans += n - nv.size();
    218 			}
    219 		}
    220 	}
    221 	
    222 	if (int(st.size()) < k) cout << -1 << endl;
    223 	else cout << ans << endl;
    224 	
    225 	return 0;
    226 }
    227 ```
    228 
    229 [1183F - Topforces Strikes Back](/contest/1183/problem/F "Codeforces Round 570 (Div. 3)")
    230 
    231 Idea: [vovuh](/profile/vovuh "Candidate Master vovuh")
    232 
    233 **Tutorial**
    234 
    235 Tutorial is loading...
    236 
    237 **Solution**
    238 
    239 ```
    240 #include <bits/stdc++.h>
    241 
    242 using namespace std;
    243 
    244 int main() {
    245 #ifdef _DEBUG
    246 	freopen("input.txt", "r", stdin);
    247 //	freopen("output.txt", "w", stdout);
    248 #endif
    249 	
    250 	int q;
    251 	cin >> q;
    252 	for (int i = 0; i < q; ++i) {
    253 		int n;
    254 		cin >> n;
    255 		set<int> st;
    256 		for (int j = 0; j < n; ++j) {
    257 			int x;
    258 			cin >> x;
    259 			st.insert(x);
    260 		}
    261 		
    262 		int ans = 0;
    263 		int mx = *st.rbegin();
    264 		if (mx % 2 == 0 && mx % 3 == 0 && mx % 5 == 0) {
    265 			if (st.count(mx / 2) && st.count(mx / 3) && st.count(mx / 5)) {
    266 				ans = max(ans, mx / 2 + mx / 3 + mx / 5);
    267 			}
    268 		}
    269 		
    270 		vector<int> res;
    271 		while (!st.empty() && int(res.size()) < 3) {
    272 			int x = *st.rbegin();
    273 			st.erase(prev(st.end()));
    274 			bool ok = true;
    275 			for (auto it : res) ok &= (it % x != 0);
    276 			if (ok) res.push_back(x);
    277 		}
    278 		
    279 		ans = max(ans, accumulate(res.begin(), res.end(), 0));
    280 		
    281 		cout << ans << endl;
    282 	}
    283 	
    284 	return 0;
    285 }
    286 ```
    287 
    288 [1183G - Candy Box (hard version)](/contest/1183/problem/G "Codeforces Round 570 (Div. 3)")
    289 
    290 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
    291 
    292 **Tutorial**
    293 
    294 Tutorial is loading...
    295 
    296 **Solution**
    297 
    298 ```
    299 #include<bits/stdc++.h>
    300 
    301 using namespace std;
    302 
    303 void solve()
    304 {
    305 	int n;
    306 	scanf("%d", &n);
    307 	vector<int> cnt(n);
    308 	vector<int> cnt_good(n);
    309 	for(int i = 0; i < n; i++)
    310 	{
    311 		int a, f;
    312 		scanf("%d %d", &a, &f);
    313 		--a;
    314 		cnt[a]++;
    315 		if(f) cnt_good[a]++;
    316 	}
    317 	vector<vector<int> > types(n + 1);
    318 	for(int i = 0; i < n; i++)
    319 		types[cnt[i]].push_back(cnt_good[i]);
    320 	int ans1 = 0;
    321 	int ans2 = 0;
    322 	multiset<int> cur;
    323 	for(int i = n; i > 0; i--)
    324 	{
    325 		for(auto x : types[i]) cur.insert(x);
    326 		if(!cur.empty())
    327 		{
    328 			int z = *cur.rbegin();
    329 			ans1 += i;
    330 			ans2 += min(i, z);
    331 			cur.erase(cur.find(z));
    332 		}
    333 	}
    334 	printf("%d %d\n", ans1, ans2);
    335 }
    336 
    337 int main()
    338 {
    339 	int t;
    340 	scanf("%d", &t);
    341 	for(int i = 0; i < t; i++)
    342 		solve();
    343 }
    344 ```
    345 
    346 [1183H - Subsequences (hard version)](/contest/1183/problem/H "Codeforces Round 570 (Div. 3)")
    347 
    348 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
    349 
    350 **Tutorial**
    351 
    352 Tutorial is loading...
    353 
    354 **Solution**
    355 
    356 ```
    357 #include <bits/stdc++.h>
    358 
    359 using namespace std;
    360 
    361 const long long INF64 = 1e12;
    362 
    363 int main() {
    364 #ifdef _DEBUG
    365 	freopen("input.txt", "r", stdin);
    366 //	freopen("output.txt", "w", stdout);
    367 #endif
    368 	
    369 	int n;
    370 	long long k;
    371 	cin >> n >> k;
    372 	--k; // the whole string costs nothing
    373 	string s;
    374 	cin >> s;
    375 	
    376 	vector<vector<int>> lst(n, vector<int>(26, -1));
    377 	for (int i = 0; i < n; ++i) {
    378 		for (int j = 0; j < 26; ++j) {
    379 			if (i > 0) lst[i][j] = lst[i - 1][j];
    380 		}
    381 		lst[i][s[i] - 'a'] = i;
    382 	}
    383 	
    384 	vector<vector<long long>> dp(n + 1, vector<long long>(n + 1));
    385 	for (int i = 0; i < n; ++i) {
    386 		dp[i][1] = 1;
    387 	}
    388 	
    389 	for (int len = 2; len < n; ++len) {
    390 		for (int i = 1; i < n; ++i) {
    391 			for (int j = 0; j < 26; ++j) {
    392 				if (lst[i - 1][j] != -1) {
    393 					dp[i][len] = min(INF64, dp[i][len] + dp[lst[i - 1][j]][len - 1]);
    394 				}
    395 			}
    396 		}
    397 	}
    398 	
    399 	long long ans = 0;
    400 	for (int len = n - 1; len >= 1; --len) {
    401 		long long cnt = 0;
    402 		for (int j = 0; j < 26; ++j) {
    403 			if (lst[n - 1][j] != -1) {
    404 				cnt += dp[lst[n - 1][j]][len];
    405 			}
    406 		}
    407 		if (cnt >= k) {
    408 			ans += k * (n - len);
    409 			k = 0;
    410 			break;
    411 		} else {
    412 			ans += cnt * (n - len);
    413 			k -= cnt;
    414 		}
    415 	}
    416 	
    417 	if (k == 1) {
    418 		ans += n;
    419 		--k;
    420 	}
    421 	
    422 	if (k > 0) cout << -1 << endl;
    423 	else cout << ans << endl;
    424 	
    425 	return 0;
    426 }
    427 ```