codeforces-scrape

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

1029.md (5800B)


      1 Source: https://codeforces.com/blog/entry/61439
      2 
      3 [1029A - Many Equal Substrings](/contest/1029/problem/A "Codeforces Round 506 (Div. 3)")
      4 
      5 **Tutorial**
      6 
      7 Tutorial is loading...
      8 
      9 **Solution (Vovuh, O(n^2))**
     10 
     11 ```
     12 #include <bits/stdc++.h>
     13 
     14 using namespace std;
     15 
     16 #define sz(a) int((a).size())
     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, k;
     25 	string t;
     26 	cin >> n >> k >> t;
     27 	
     28 	int cnt = 1;
     29 	int pos = 1;
     30 	string ans = t;
     31 	while (cnt < k) {
     32 		if (pos >= sz(ans)) {
     33 			ans += t;
     34 			++cnt;
     35 		} else {
     36 			bool ok = true;
     37 			int len = 0;
     38 			for (int i = 0; i < sz(t); ++i) {
     39 				if (pos + i >= sz(ans)) break;
     40 				++len;
     41 				if (ans[pos + i] != t[i]) ok = false;
     42 			}
     43 			if (ok) {
     44 				ans += t.substr(len);
     45 				++cnt;
     46 			}
     47 		}
     48 		++pos;
     49 	}
     50 	
     51 	cout << ans << endl;
     52 	
     53 	return 0;
     54 }
     55 ```
     56 
     57 **Solution (Vovuh, prefix-function)**
     58 
     59 ```
     60 #include <bits/stdc++.h>
     61 
     62 using namespace std;
     63 
     64 #define sz(a) int((a).size())
     65 
     66 int main() {
     67 #ifdef _DEBUG
     68 	freopen("input.txt", "r", stdin);
     69 //	freopen("output.txt", "w", stdout);
     70 #endif
     71 	
     72 	int n, k;
     73 	string t;
     74 	cin >> n >> k >> t;
     75 	
     76 	vector<int> p(n);
     77 	for (int i = 1; i < sz(t); ++i) {
     78 		int j = p[i - 1];
     79 		while (j > 0 && t[j] != t[i])
     80 			j = p[j - 1];
     81 		if (t[i] == t[j])
     82 			++j;
     83 		p[i] = j;
     84 	}
     85 	
     86 	int len = sz(t) - p[n - 1];
     87 	
     88 	for (int i = 0; i < k - 1; ++i)
     89 		cout << t.substr(0, len);
     90 	cout << t << endl;
     91 	
     92 	return 0;
     93 }
     94 ```
     95 
     96 [1029B - Creating the Contest](/contest/1029/problem/B "Codeforces Round 506 (Div. 3)")
     97 
     98 **Tutorial**
     99 
    100 Tutorial is loading...
    101 
    102 **Solution (Vovuh)**
    103 
    104 ```
    105 #include <bits/stdc++.h>
    106 
    107 using namespace std;
    108 
    109 int main() {
    110 #ifdef _DEBUG
    111 	freopen("input.txt", "r", stdin);
    112 #endif
    113 
    114 	int n;
    115 	scanf("%d", &n);
    116 	vector<int> a(n);
    117 	for (int i = 0; i < n; ++i)
    118 		scanf("%d", &a[i]);
    119 		
    120 	int ans = 0;
    121 	for (int i = 0; i < n; ++i) {
    122 		int j = i;
    123 		while (j + 1 < n && a[j + 1] <= a[j] * 2)
    124 			++j;
    125 		ans = max(ans, j - i + 1);
    126 		i = j;
    127 	}
    128 	
    129 	printf("%d\n", ans);
    130 }
    131 ```
    132 
    133 [1029C - Maximal Intersection](/contest/1029/problem/C "Codeforces Round 506 (Div. 3)")
    134 
    135 **Tutorial**
    136 
    137 Tutorial is loading...
    138 
    139 **Solution (PikMike)**
    140 
    141 ```
    142 #include <bits/stdc++.h>
    143 
    144 #define forn(i, n) for (int i = 0; i < int(n); i++)
    145 
    146 using namespace std;
    147 
    148 const int N = 300 * 1000 + 13;
    149 const int INF = int(1e9);
    150 
    151 int n;
    152 int prl[N], prr[N], sul[N], sur[N];
    153 int l[N], r[N];
    154 
    155 int main() {
    156 	scanf("%d", &n);
    157 	forn(i, n)
    158 		scanf("%d%d", &l[i], &r[i]);
    159 	
    160 	prl[0] = sul[n] = 0;
    161 	prr[0] = sur[n] = INF;
    162 	
    163 	forn(i, n){
    164 		prl[i + 1] = max(prl[i], l[i]);
    165 		prr[i + 1] = min(prr[i], r[i]);
    166 	}
    167 	
    168 	for (int i = n - 1; i >= 0; --i){
    169 		sul[i] = max(sul[i + 1], l[i]);
    170 		sur[i] = min(sur[i + 1], r[i]);
    171 	}
    172 	
    173 	int ans = 0;
    174 	forn(i, n)
    175 		ans = max(ans, min(prr[i], sur[i + 1]) - max(prl[i], sul[i + 1]));
    176 	printf("%d\n", ans);
    177 	return 0;
    178 }
    179 ```
    180 
    181 [1029D - Concatenated Multiples](/contest/1029/problem/D "Codeforces Round 506 (Div. 3)")
    182 
    183 **Tutorial**
    184 
    185 Tutorial is loading...
    186 
    187 **Solution (PikMike)**
    188 
    189 ```
    190 #include <bits/stdc++.h>
    191 
    192 #define forn(i, n) for (int i = 0; i < int(n); i++)
    193 
    194 typedef long long li;
    195 
    196 using namespace std;
    197 
    198 const int N = 200 * 1000 + 13;
    199 const int LOGN = 11;
    200 
    201 int n, k;
    202 int a[N];
    203 int len[N];
    204 vector<int> rems[LOGN];
    205 int pw[LOGN];
    206 
    207 int main() {
    208 	scanf("%d%d", &n, &k);
    209 	forn(i, n) scanf("%d", &a[i]);
    210 	
    211 	pw[0] = 1;
    212 	forn(i, LOGN - 1)
    213 		pw[i + 1] = pw[i] * 10 % k;
    214 	
    215 	forn(i, n){
    216 		int x = a[i];
    217 		while (x > 0){
    218 			++len[i];
    219 			x /= 10;
    220 		}
    221 		rems[len[i]].push_back(a[i] % k);
    222 	}
    223 	
    224 	forn(i, LOGN)
    225 		sort(rems[i].begin(), rems[i].end());
    226 	
    227 	li ans = 0;
    228 	forn(i, n){
    229 		for (int j = 1; j < LOGN; ++j){
    230 			int rem = (a[i] * li(pw[j])) % k;
    231 			int xrem = (k - rem) % k;
    232 			auto l = lower_bound(rems[j].begin(), rems[j].end(), xrem);
    233 			auto r = upper_bound(rems[j].begin(), rems[j].end(), xrem);
    234 			ans += (r - l);
    235 			if (len[i] == j && (rem + a[i] % k) % k == 0)
    236 				--ans;
    237 		}
    238 	}
    239 	
    240 	printf("%lld\n", ans);
    241 	return 0;
    242 }
    243 ```
    244 
    245 [1029E - Tree with Small Distances](/contest/1029/problem/E "Codeforces Round 506 (Div. 3)")
    246 
    247 **Tutorial**
    248 
    249 Tutorial is loading...
    250 
    251 **Solution (Vovuh)**
    252 
    253 ```
    254 #include <bits/stdc++.h>
    255 
    256 using namespace std;
    257 
    258 const int N = 200 * 1000 + 11;
    259 
    260 int p[N];
    261 int d[N];
    262 vector<int> g[N];
    263 
    264 void dfs(int v, int pr = -1, int dst = 0) {
    265 	d[v] = dst;
    266 	p[v] = pr;
    267 	for (auto to : g[v]) {
    268 		if (to != pr) {
    269 			dfs(to, v, dst + 1);
    270 		}
    271 	}
    272 }
    273 
    274 int main() {
    275 #ifdef _DEBUG
    276 	freopen("input.txt", "r", stdin);
    277 #endif
    278 
    279 	int n;
    280 	scanf("%d", &n);
    281 	for (int i = 0; i < n - 1; ++i) {
    282 		int x, y;
    283 		scanf("%d %d", &x, &y);
    284 		--x, --y;
    285 		g[x].push_back(y);
    286 		g[y].push_back(x);
    287 	}
    288 	
    289 	dfs(0);
    290 	set<pair<int, int>> st;
    291 	for (int i = 0; i < n; ++i) {
    292 		if (d[i] > 2) {
    293 			st.insert(make_pair(-d[i], i));
    294 		}
    295 	}
    296 	
    297 	int ans = 0;
    298 	while (!st.empty()) {
    299 		int v = st.begin()->second;
    300 		v = p[v];
    301 		++ans;
    302 		auto it = st.find(make_pair(-d[v], v));
    303 		if (it != st.end()) {
    304 			st.erase(it);
    305 		}
    306 		for (auto to : g[v]) {
    307 			auto it = st.find(make_pair(-d[to], to));
    308 			if (it != st.end()) {
    309 				st.erase(it);
    310 			}
    311 		}
    312 	}
    313 	
    314 	printf("%d\n", ans);
    315 }
    316 ```
    317 
    318 [1029F - Multicolored Markers](/contest/1029/problem/F "Codeforces Round 506 (Div. 3)")
    319 
    320 **Tutorial**
    321 
    322 Tutorial is loading...
    323 
    324 **Solution (PikMike)**
    325 
    326 ```
    327 #include <bits/stdc++.h>
    328 
    329 #define forn(i, n) for (int i = 0; i < int(n); i++)
    330 
    331 typedef long long li;
    332 
    333 using namespace std;
    334 
    335 const int N = 1000 * 1000;
    336 
    337 int lens[N];
    338 int k;
    339 
    340 li solve(li a, li b){
    341 	k = 0;
    342 	for (li i = 1; i * i <= b; ++i)
    343 		if (b % i == 0)
    344 			lens[k++] = i;
    345 	
    346 	li ans = 2 * (a + b) + 2;
    347 	li x = a + b;
    348 	int l = 0;
    349 	for (li i = 1; i * i <= x; ++i){
    350 		if (x % i == 0){
    351 			while (l + 1 < k && lens[l + 1] <= i)
    352 				++l;
    353 			if (b / lens[l] <= x / i)
    354 				ans = min(ans, (i + x / i) * 2);
    355 		}
    356 	}
    357 	
    358 	return ans;
    359 }
    360 
    361 int main() {
    362 	li a, b;
    363 	scanf("%lld%lld", &a, &b);
    364 	printf("%lld\n", min(solve(a, b), solve(b, a)));
    365 	return 0;
    366 }
    367 ```