codeforces-scrape

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

1154.md (7821B)


      1 Source: https://codeforces.com/blog/entry/66586
      2 
      3 [1154A - Restoring Three Numbers](/contest/1154/problem/A "Codeforces Round 552 (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 int main() {
     19 #ifdef _DEBUG
     20 	freopen("input.txt", "r", stdin);
     21 //	freopen("output.txt", "w", stdout);
     22 #endif
     23 	
     24 	vector<int> a(4);
     25 	for (int i = 0; i < 4; ++i) {
     26 		cin >> a[i];
     27 	}
     28 	sort(a.begin(), a.end());
     29 	cout << a[3] - a[0] << " " << a[3] - a[1] << " " << a[3] - a[2] << endl;
     30 	
     31 	return 0;
     32 }
     33 ```
     34 
     35 [1154B - Make Them Equal](/contest/1154/problem/B "Codeforces Round 552 (Div. 3)")
     36 
     37 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
     38 
     39 **Tutorial**
     40 
     41 Tutorial is loading...
     42 
     43 **Solution**
     44 
     45 ```
     46 #include <bits/stdc++.h>
     47 
     48 using namespace std;
     49 
     50 int main() {
     51 #ifdef _DEBUG
     52 	freopen("input.txt", "r", stdin);
     53 //	freopen("output.txt", "w", stdout);
     54 #endif
     55 	
     56 	int n;
     57 	cin >> n;
     58 	vector<int> a(n);
     59 	for (int i = 0; i < n; ++i) {
     60 		cin >> a[i];
     61 	}
     62 	sort(a.begin(), a.end());
     63 	a.resize(unique(a.begin(), a.end()) - a.begin());
     64 	if (a.size() > 3) {
     65 		cout << -1 << endl;
     66 	} else {
     67 		if (a.size() == 1) {
     68 			cout << 0 << endl;
     69 		} else if (a.size() == 2) {
     70 			if ((a[1] - a[0]) % 2 == 0) {
     71 				cout << (a[1] - a[0]) / 2 << endl;
     72 			} else {
     73 				cout << a[1] - a[0] << endl;
     74 			}
     75 		} else {
     76 			if (a[1] - a[0] != a[2] - a[1]) {
     77 				cout << -1 << endl;
     78 			} else {
     79 				cout << a[1] - a[0] << endl;
     80 			}
     81 		}
     82 	}
     83 	
     84 	return 0;
     85 }
     86 ```
     87 
     88 [1154C - Gourmet Cat](/contest/1154/problem/C "Codeforces Round 552 (Div. 3)")
     89 
     90 Idea: [le.mur](/profile/le.mur "Unrated, le.mur")
     91 
     92 **Tutorial**
     93 
     94 Tutorial is loading...
     95 
     96 **Solution**
     97 
     98 ```
     99 #include <bits/stdc++.h>
    100 
    101 using namespace std;
    102 
    103 int main() {
    104 #ifdef _DEBUG
    105 	freopen("input.txt", "r", stdin);
    106 //	freopen("output.txt", "w", stdout);
    107 #endif
    108 	
    109 	vector<int> a(3);
    110 	cin >> a[0] >> a[1] >> a[2];
    111 	
    112 	vector<int> idx({0, 1, 2, 0, 2, 1, 0});
    113 	
    114 	int full = min({a[0] / 3, a[1] / 2, a[2] / 2});
    115 	a[0] -= full * 3;
    116 	a[1] -= full * 2;
    117 	a[2] -= full * 2;
    118 	
    119 	int ans = 0;
    120 	for (int start = 0; start < 7; ++start) {
    121 		int day = start;
    122 		vector<int> b = a;
    123 		int cur = 0;
    124 		while (b[idx[day]] > 0) {
    125 			--b[idx[day]];
    126 			day = (day + 1) % 7;
    127 			++cur;
    128 		}
    129 		ans = max(ans, full * 7 + cur);
    130 	}
    131 	
    132 	cout << ans << endl;
    133 	
    134 	return 0;
    135 }
    136 ```
    137 
    138 [1154D - Walking Robot](/contest/1154/problem/D "Codeforces Round 552 (Div. 3)")
    139 
    140 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
    141 
    142 **Tutorial**
    143 
    144 Tutorial is loading...
    145 
    146 **Solution**
    147 
    148 ```
    149 #include<bits/stdc++.h>
    150 
    151 using namespace std;
    152 
    153 int a, b, maxa;
    154 
    155 void use_battery(int s)
    156 {
    157 	if(s == 1) a = min(a + 1, maxa);
    158 	--b;	
    159 }
    160 
    161 void use_accum()
    162 {
    163 	--a;
    164 }
    165 
    166 int main()
    167 {
    168 	int ans = 0;
    169 	int n;
    170 	cin >> n >> b >> a;
    171 	maxa = a;
    172 	vector<int> s(n);
    173 	for(int i = 0; i < n; i++) cin >> s[i];
    174 	for(int i = 0; i < n; i++)
    175 	{
    176 		if(a == 0 && b == 0)
    177 			break;
    178 		else if(a == 0)
    179 			use_battery(s[i]);
    180 		else if(b == 0)
    181 			use_accum();
    182 		else if(s[i] == 1 && a < maxa)
    183 			use_battery(s[i]);
    184 		else use_accum();
    185 		ans++;
    186 	}
    187 	cout << ans << endl;
    188 }
    189 ```
    190 
    191 [1154E - Two Teams](/contest/1154/problem/E "Codeforces Round 552 (Div. 3)")
    192 
    193 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
    194 
    195 **Tutorial**
    196 
    197 Tutorial is loading...
    198 
    199 **Solution**
    200 
    201 ```
    202 #include <bits/stdc++.h>
    203 
    204 using namespace std;
    205 
    206 int main() {
    207 #ifdef _DEBUG
    208 	freopen("input.txt", "r", stdin);
    209 //	freopen("output.txt", "w", stdout);
    210 #endif
    211 	
    212 	int n, k;
    213 	cin >> n >> k;
    214 	vector<pair<int, int>> a(n);
    215 	for (int i = 0; i < n; ++i) {
    216 		cin >> a[i].first;
    217 		a[i].second = i;
    218 	}
    219 	
    220 	sort(a.rbegin(), a.rend());
    221 	queue<int> q;
    222 	for (int i = 0; i < n; ++i) {
    223 		q.push(a[i].second);
    224 	}
    225 	
    226 	set<int> idx;
    227 	for (int i = 0; i < n; ++i) {
    228 		idx.insert(i);
    229 	}
    230 	string ans(n, '0');
    231 	int who = 0;
    232 	while (!idx.empty()) {
    233 		while (!idx.count(q.front())) {
    234 			q.pop();
    235 		}
    236 		int pos = q.front();
    237 		q.pop();
    238 		
    239 		vector<int> add;
    240 		auto it = idx.find(pos);
    241 		for (int i = 0; i <= k; ++i) {
    242 			add.push_back(*it);
    243 			if (it == idx.begin()) break;
    244 			--it;
    245 		}
    246 		it = next(idx.find(pos));
    247 		for (int i = 0; i < k; ++i) {
    248 			if (it == idx.end()) break;
    249 			add.push_back(*it);
    250 			++it;
    251 		}
    252 		for (auto it : add) {
    253 			idx.erase(it);
    254 			ans[it] = '1' + who;
    255 		}
    256 		who ^= 1;
    257 	}
    258 	
    259 	cout << ans << endl;
    260 	
    261 	return 0;
    262 }
    263 ```
    264 
    265 [1154F - Shovels Shop](/contest/1154/problem/F "Codeforces Round 552 (Div. 3)")
    266 
    267 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
    268 
    269 **Tutorial**
    270 
    271 Tutorial is loading...
    272 
    273 **Solution**
    274 
    275 ```
    276 #include <bits/stdc++.h>
    277 
    278 using namespace std;
    279 
    280 const int INF = 1e9;
    281 
    282 int main() {
    283 #ifdef _DEBUG
    284 	freopen("input.txt", "r", stdin);
    285 //	freopen("output.txt", "w", stdout);
    286 #endif
    287 	
    288 	int n, m, k;
    289 	cin >> n >> m >> k;
    290 	vector<int> a(n);
    291 	for (int i = 0; i < n; ++i) {
    292 		cin >> a[i];
    293 	}
    294 	
    295 	sort(a.begin(), a.end());
    296 	a.resize(k);
    297 	reverse(a.begin(), a.end());
    298 	
    299 	vector<int> offers(k + 1);
    300 	for (int i = 0; i < m; ++i) {
    301 		int x, y;
    302 		cin >> x >> y;
    303 		if (x <= k) {
    304 			offers[x] = max(offers[x], y);
    305 		}
    306 	}
    307 	
    308 	vector<int> pref(k + 1);
    309 	for (int i = 0; i < k; ++i) {
    310 		pref[i + 1] = pref[i] + a[i];
    311 	}
    312 	
    313 	vector<int> dp(k + 1, INF);
    314 	dp[0] = 0;
    315 	for (int i = 0; i < k; ++i) {
    316 		dp[i + 1] = min(dp[i + 1], dp[i] + a[i]);
    317 		for (int j = 1; j <= k; ++j) {
    318 			if (offers[j] == 0) continue;
    319 			if (i + j > k) break;
    320 			dp[i + j] = min(dp[i + j], dp[i] + pref[i + j - offers[j]] - pref[i]);
    321 		}
    322 	}
    323 	
    324 	cout << dp[k] << endl;
    325 	
    326 	return 0;
    327 }
    328 ```
    329 
    330 [1154G - Minimum Possible LCM](/contest/1154/problem/G "Codeforces Round 552 (Div. 3)")
    331 
    332 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
    333 
    334 **Tutorial**
    335 
    336 Tutorial is loading...
    337 
    338 **Solution**
    339 
    340 ```
    341 #include <bits/stdc++.h>
    342 
    343 using namespace std;
    344 
    345 const int INF = 1e9;
    346 const int N = 10 * 1000 * 1000 + 11;
    347 
    348 int n;
    349 vector<int> a;
    350 
    351 int mind[N];
    352 
    353 pair<int, int> mins[N];
    354 vector<pair<int, int>> divs;
    355 
    356 void build_sieve() {
    357 	vector<int> pr;
    358 	mind[0] = mind[1] = 1;
    359 	for (int i = 2; i < N; ++i) {
    360 		if (mind[i] == 0) {
    361 			pr.push_back(i);
    362 			mind[i] = i;
    363 		}
    364 		for (int j = 0; j < int(pr.size()) && pr[j] <= mind[i] && i * pr[j] < N; ++j) {
    365 			mind[i * pr[j]] = pr[j];
    366 		}
    367 	}
    368 }
    369 
    370 void add_to_mins(int curd, int idx) {
    371     if(mins[curd].first == -1)
    372         mins[curd].first = idx;
    373     else if(mins[curd].second == -1)
    374         mins[curd].second = idx;
    375 }
    376 
    377 void rec(int pos, int curd, int idx) {
    378 	if (pos == int(divs.size())) {
    379 		add_to_mins(curd, idx);
    380 		return;
    381 	}
    382 	int curm = 1;
    383 	for (int i = 0; i <= divs[pos].second; ++i) {
    384 		rec(pos + 1, curd * curm, idx);
    385 		curm *= divs[pos].first;
    386 	}
    387 }
    388 
    389 void add(int idx) {
    390 	int value = a[idx];
    391 	divs.clear();
    392 	while (value > 1) {
    393 		int d = mind[value];
    394 		if (!divs.empty() && divs.back().first == d) {
    395 			++divs.back().second;
    396 		} else {
    397 			divs.push_back(make_pair(d, 1));
    398 		}
    399 		value /= d;
    400 	}
    401 	rec(0, 1, idx);
    402 }
    403 
    404 int main() {
    405 #ifdef _DEBUG
    406 	freopen("input.txt", "r", stdin);
    407 //	freopen("output.txt", "w", stdout);
    408 #endif
    409 	
    410 	cin >> n;
    411 	a.resize(n);
    412 	for (int i = 0; i < n; ++i) {
    413 		cin >> a[i];
    414 	}
    415 	for(int i = 0; i < N; i++)
    416 	    mins[i] = make_pair(-1, -1);
    417 	build_sieve();
    418 	
    419 	vector<pair<int, int> > vals;
    420 	for(int i = 0; i < n; i++)
    421 	    vals.push_back(make_pair(a[i], i));
    422 	sort(vals.begin(), vals.end());
    423 	for (int i = 0; i < n; ++i) {
    424 	    if(i > 1 && vals[i].first == vals[i - 2].first) continue;
    425 		add(vals[i].second);
    426 	}
    427 	
    428 	long long l = INF * 1ll * INF;
    429 	int ansi = -1, ansj = -1;
    430 	for (int i = 1; i < N; ++i) {
    431 		pair<int, int> idxs = mins[i];
    432 		if (idxs.second == -1) continue;
    433 		long long curl = a[idxs.first] * 1ll * a[idxs.second] / i;
    434 		if (l > curl) {
    435 			l = curl;
    436 			ansi = min(idxs.first, idxs.second);
    437 			ansj = max(idxs.first, idxs.second);
    438 		}
    439 	}
    440 	
    441 	cout << ansi + 1 << " " << ansj + 1 << endl;
    442 	
    443 	return 0;
    444 }
    445 ```