codeforces-scrape

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

988.md (9082B)


      1 Source: https://codeforces.com/blog/entry/59810
      2 
      3 [988A - Diverse Team](/contest/988/problem/A "Codeforces Round 486 (Div. 3)")
      4 
      5 **Tutorial**
      6 
      7 Tutorial is loading...
      8 
      9 **Solution (Vovuh)**
     10 
     11 ```
     12 #include <bits/stdc++.h>
     13 
     14 using namespace std;
     15 
     16 int main() {
     17 #ifdef _DEBUG
     18 	freopen("input.txt", "r", stdin);
     19 //	freopen("output.txt", "w", stdout);
     20 #endif
     21 	
     22 	int n, k;
     23 	cin >> n >> k;
     24 	set<int> el;
     25 	vector<int> ans;
     26 	for (int i = 0; i < n; ++i) {
     27 		int x;
     28 		cin >> x;
     29 		if (!el.count(x)) {
     30 			ans.push_back(i);
     31 			el.insert(x);
     32 		}
     33 	}
     34 	
     35 	if (int(ans.size()) < k) {
     36 		cout << "NO\n";
     37 	} else {
     38 		cout << "YES\n";
     39 		for (int i = 0; i < k; ++i)
     40 			cout << ans[i] + 1 << " ";
     41 		cout << endl;
     42 	}
     43 	
     44 	return 0;
     45 }
     46 ```
     47 
     48 [988B - Substrings Sort](/contest/988/problem/B "Codeforces Round 486 (Div. 3)")
     49 
     50 **Tutorial**
     51 
     52 Tutorial is loading...
     53 
     54 **Solution (Vovuh)**
     55 
     56 ```
     57 #include <bits/stdc++.h>
     58 
     59 using namespace std;
     60 
     61 int main() {
     62 #ifdef _DEBUG
     63 	freopen("input.txt", "r", stdin);
     64 //	freopen("output.txt", "w", stdout);
     65 #endif
     66 	
     67 	int n;
     68 	cin >> n;
     69 	vector<string> s(n);
     70 	for (int i = 0; i < n; ++i)
     71 		cin >> s[i];
     72 		
     73 	sort(s.begin(), s.end(), [&] (const string &s, const string &t) {
     74 		return s.size() < t.size();
     75 	});
     76 	
     77 	for (int i = 0; i < n - 1; ++i) {
     78 		if (s[i + 1].find(s[i]) == string::npos) {
     79 			cout << "NO\n";
     80 			return 0;
     81 		}
     82 	}
     83 	
     84 	cout << "YES\n";
     85 	for (auto it : s)
     86 		cout << it << endl;
     87 	
     88 	return 0;
     89 }
     90 ```
     91 
     92 [988C - Equal Sums](/contest/988/problem/C "Codeforces Round 486 (Div. 3)")
     93 
     94 **Tutorial**
     95 
     96 Tutorial is loading...
     97 
     98 **Solution (Vovuh)**
     99 
    100 ```
    101 #include <bits/stdc++.h>
    102 
    103 using namespace std;
    104 
    105 int main() {
    106 #ifdef _DEBUG
    107 	freopen("input.txt", "r", stdin);
    108 //	freopen("output.txt", "w", stdout);
    109 #endif
    110 	
    111 	int k;
    112 	cin >> k;
    113 	vector<pair<int, pair<int, int>>> a;
    114 	for (int i = 0; i < k; ++i) {
    115 		int n;
    116 		cin >> n;
    117 		vector<int> x(n);
    118 		for (int j = 0; j < n; ++j)
    119 			cin >> x[j];
    120 		int sum = accumulate(x.begin(), x.end(), 0);
    121 		for (int j = 0; j < n; ++j)
    122 			a.push_back(make_pair(sum - x[j], make_pair(i, j)));
    123 	}
    124 	
    125 	stable_sort(a.begin(), a.end());
    126 	for (int i = 0; i < int(a.size()) - 1; ++i) {
    127 		if (a[i].first == a[i + 1].first && (a[i].second.first != a[i + 1].second.first)) {
    128 			cout << "YES" << endl;
    129 			cout << a[i + 1].second.first + 1 << " " << a[i + 1].second.second + 1 << endl;
    130 			cout << a[i].second.first + 1 << " " << a[i].second.second + 1 << endl;
    131 			return 0;
    132 		}
    133 	}
    134 	
    135 	cout << "NO\n";
    136 	
    137 	return 0;
    138 }
    139 ```
    140 
    141 [988D - Points and Powers of Two](/contest/988/problem/D "Codeforces Round 486 (Div. 3)")
    142 
    143 **Tutorial**
    144 
    145 Tutorial is loading...
    146 
    147 **Solution (Vovuh)**
    148 
    149 ```
    150 #include <bits/stdc++.h>
    151 
    152 using namespace std;
    153 
    154 int main() {
    155 #ifdef _DEBUG
    156 	freopen("input.txt", "r", stdin);
    157 //	freopen("output.txt", "w", stdout);
    158 #endif
    159 	
    160 	int n;
    161 	cin >> n;
    162 	vector<int> x(n);
    163 	for (int i = 0; i < n; ++i) {
    164 		cin >> x[i];
    165 	}
    166 	
    167 	sort(x.begin(), x.end());
    168 	vector<int> res = { x[0] };
    169 	
    170 	for (int i = 0; i < n; ++i) {
    171 		for (int j = 0; j < 31; ++j) {
    172 			int lx = x[i] - (1 << j);
    173 			int rx = x[i] + (1 << j);
    174 			bool isl = binary_search(x.begin(), x.end(), lx);
    175 			bool isr = binary_search(x.begin(), x.end(), rx);
    176 			if (isl && isr && int(res.size()) < 3) {
    177 				res = { lx, x[i], rx };
    178 			}
    179 			if (isl && int(res.size()) < 2) {
    180 				res = { lx, x[i] };
    181 			}
    182 			if (isr && int(res.size()) < 2) {
    183 				res = { x[i], rx };
    184 			}
    185 		}
    186 	}
    187 	
    188 	cout << int(res.size()) << endl;
    189 	for (auto it : res)
    190 		cout << it << " ";
    191 	cout << endl;
    192 	
    193 	return 0;
    194 }
    195 ```
    196 
    197 [988E - Divisibility by 25](/contest/988/problem/E "Codeforces Round 486 (Div. 3)")
    198 
    199 **Tutorial**
    200 
    201 Tutorial is loading...
    202 
    203 **Solution (Vovuh)**
    204 
    205 ```
    206 #include <bits/stdc++.h>
    207 
    208 using namespace std;
    209 
    210 const int INF = 1000 * 1000 * 1000;
    211 
    212 int main() {
    213 #ifdef _DEBUG
    214 	freopen("input.txt", "r", stdin);
    215 //	freopen("output.txt", "w", stdout);
    216 #endif
    217 	
    218 	long long n;
    219 	cin >> n;
    220 	
    221 	string s = to_string(n);
    222 	
    223 	int ans = INF;
    224 	
    225 	int len = s.size();
    226 	for (int i = 0; i < len; ++i) {
    227 		for (int j = 0; j < len; ++j) {
    228 			if (i == j) continue;
    229 			string t = s;
    230 			int cur = 0;
    231 			for (int k = i; k < len - 1; ++k) {
    232 				swap(t[k], t[k + 1]);
    233 				++cur;
    234 			}
    235 			
    236 			for (int k = j - (j > i); k < len - 2; ++k) {
    237 				swap(t[k], t[k + 1]);
    238 				++cur;
    239 			}
    240 			
    241 			int pos = -1;
    242 			for (int k = 0; k < len; ++k) {
    243 				if (t[k] != '0') {
    244 					pos = k;
    245 					break;
    246 				}
    247 			}
    248 			
    249 			for (int k = pos; k > 0; --k) {
    250 				swap(t[k], t[k - 1]);
    251 				++cur;
    252 			}
    253 			
    254 			long long nn = atoll(t.c_str());
    255 			if (nn % 25 == 0)
    256 				ans = min(ans, cur);
    257 		}
    258 	}
    259 	
    260 	if (ans == INF)
    261 		ans = -1;
    262 		
    263 	cout << ans << endl;
    264 	
    265 	return 0;
    266 }
    267 ```
    268 
    269 [988F - Rain and Umbrellas](/contest/988/problem/F "Codeforces Round 486 (Div. 3)")
    270 
    271 **Tutorial**
    272 
    273 Tutorial is loading...
    274 
    275 **Solution (Vovuh)**
    276 
    277 ```
    278 #include <bits/stdc++.h>
    279 
    280 using namespace std;
    281 
    282 const int INF = 1000 * 1000 * 1000;
    283 
    284 int main() {
    285 #ifdef _DEBUG
    286 	freopen("input.txt", "r", stdin);
    287 //	freopen("output.txt", "w", stdout);
    288 #endif
    289 	
    290 	int a, n, m;
    291 	cin >> a >> n >> m;
    292 	vector<int> rain(a + 1);
    293 	vector<pair<int, int>> umb(a + 1, make_pair(INF, -1));
    294 	vector<int> costs(m);
    295 	
    296 	for (int i = 0; i < n; ++i) {
    297 		int l, r;
    298 		cin >> l >> r;
    299 		for (int j = l; j < r; ++j)
    300 			rain[j] = 1;
    301 	}
    302 	
    303 	for (int i = 0; i < m; ++i) {
    304 		int x, p;
    305 		cin >> x >> p;
    306 		costs[i] = p;
    307 		umb[x] = min(umb[x], make_pair(p, i));
    308 	}
    309 	
    310 	vector<vector<int>> dp(a + 1, vector<int>(m + 1, INF));
    311 	dp[0][m] = 0;
    312 	for (int i = 0; i < a; ++i) {
    313 		for (int j = 0; j <= m; ++j) {
    314 			if (dp[i][j] == INF)
    315 				continue;
    316 			if (rain[i] == 0)
    317 				dp[i + 1][m] = min(dp[i + 1][m], dp[i][j]);
    318 			if (j < m)
    319 				dp[i + 1][j] = min(dp[i + 1][j], dp[i][j] + costs[j]);
    320 			if (umb[i].first != INF)
    321 				dp[i + 1][umb[i].second] = min(dp[i + 1][umb[i].second], dp[i][j] + umb[i].first);
    322 		}
    323 	}
    324 	
    325 	int ans = INF;
    326 	for (int i = 0; i <= m; ++i)
    327 		ans = min(ans, dp[a][i]);
    328 	if (ans == INF)
    329 		ans = -1;
    330 	cout << ans << endl;
    331 	
    332 	return 0;
    333 }
    334 ```
    335 
    336 **Solution (step_by_step)**
    337 
    338 ```
    339 //#pragma comment(linker, "/stack:200000000")
    340 //#pragma GCC optimize("Ofast")
    341 //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
    342 //#pragma GCC optimize("unroll-loops")
    343  
    344 #include <stdio.h>
    345 #include <bits/stdc++.h>
    346  
    347 #define uint unsigned int
    348 #define ll long long
    349 #define ull unsigned long long
    350 #define ld long double
    351 #define rep(i, l, r) for (int i = l; i < r; i++)
    352 #define repb(i, r, l) for (int i = r; i > l; i--)
    353 #define sz(a) (int)a.size()
    354 #define fi first
    355 #define se second
    356 #define mp(a, b) make_pair(a, b)
    357  
    358 using namespace std;
    359  
    360 inline void setmin(int &x, int y) { if (y < x) x = y; }
    361 inline void setmax(int &x, int y) { if (y > x) x = y; }
    362 inline void setmin(ll &x, ll y) { if (y < x) x = y; }
    363 inline void setmax(ll &x, ll y) { if (y > x) x = y; }
    364  
    365 const int N = 2001;
    366 const int inf = (int)1e9 + 1;
    367 const ll big = (ll)1e18 + 1;
    368 const int P = 239;
    369 const int MOD = (int)1e9 + 7;
    370 const int MOD1 = (int)1e9 + 9;
    371 const double eps = 1e-9;
    372 const double pi = atan2(0, -1);
    373 const int ABC = 26;
    374 
    375 struct Line
    376 {
    377     ll k, b;
    378     Line() {}
    379     Line(ll k, ll b) : k(k), b(b) {}
    380     ll val(ll x) { return k * x + b; }
    381 };
    382 
    383 int cnt_v;
    384 Line tree[N * 4];
    385 
    386 void build(int n)
    387 {
    388     cnt_v = 1;
    389     while (cnt_v < n)
    390         cnt_v <<= 1;
    391     rep(i, 0, cnt_v * 2 - 1)
    392         tree[i] = Line(0, inf);
    393 }
    394 
    395 void upd(int x, int lx, int rx, int l, int r, Line line)
    396 {
    397     if (lx >= r || l >= rx)
    398         return;
    399     else if (lx >= l && rx <= r)
    400     {
    401         int m = (lx + rx) / 2;
    402         if (line.val(m) < tree[x].val(m))
    403             swap(tree[x], line);
    404         if (rx - lx == 1)
    405             return;
    406         if (line.val(lx) < tree[x].val(lx))
    407             upd(x * 2 + 1, lx, (lx + rx) / 2, l, r, line);
    408         else
    409             upd(x * 2 + 2, (lx + rx) / 2, rx, l, r, line);
    410     }
    411     else
    412     {
    413         upd(x * 2 + 1, lx, (lx + rx) / 2, l, r, line);
    414         upd(x * 2 + 2, (lx + rx) / 2, rx, l, r, line);
    415     }
    416 }
    417 
    418 ll get(ll p)
    419 {
    420     int x = p + cnt_v - 1;
    421     ll res = tree[x].val(p);
    422     while (x > 0)
    423     {
    424         x = (x - 1) / 2;
    425         setmin(res, tree[x].val(p));
    426     }
    427     return res;
    428 }
    429 
    430 int add[N];
    431 int best[N];
    432 
    433 ll dp[N];
    434 
    435 int main()
    436 {
    437     //freopen("a.in", "r", stdin);
    438     //freopen("a.out", "w", stdout);
    439     ios_base::sync_with_stdio(0);
    440     cin.tie(0);
    441     cout.precision(20);
    442     cout << fixed;
    443     //ll TL = 0.95 * CLOCKS_PER_SEC;
    444     //clock_t time = clock();
    445     int L, n, m;
    446     cin >> L >> n >> m;
    447 
    448     rep(i, 0, n)
    449     {
    450         int l, r;
    451         cin >> l >> r;
    452         add[l]++;
    453         add[r]--;
    454     }
    455     rep(i, 1, L + 1)
    456         add[i] += add[i - 1];
    457 
    458     fill(best, best + L + 1, inf);
    459     rep(i, 0, m)
    460     {
    461         int x, p;
    462         cin >> x >> p;
    463         setmin(best[x], p);
    464     }
    465 
    466     // dp[i] + best[i] * (j - i) = best[i] * j + (dp[i] - best[i] * i)
    467     build(L + 1);
    468     fill(dp, dp + L + 1, inf);
    469     dp[0] = 0;
    470     upd(0, 0, cnt_v, 0 + 1, cnt_v, Line(best[0], dp[0] - best[0] * 0));
    471     rep(i, 1, L + 1)
    472     {
    473         dp[i] = get(i);
    474         if (add[i - 1] == 0)
    475             setmin(dp[i], dp[i - 1]);
    476         upd(0, 0, cnt_v, i + 1, cnt_v, Line(best[i], dp[i] - best[i] * i));
    477     }
    478     cout << (dp[L] != inf ? dp[L] : -1) << "\n";
    479     return 0;
    480 }
    481 ```