codeforces-scrape

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

1294.md (6255B)


      1 Source: https://codeforces.com/blog/entry/73274
      2 
      3 Thanks to [Rox](/profile/Rox "Candidate Master Rox") and [_overrated_](/profile/_overrated_ "Master _overrated_") for help with problem ideas and preparation!
      4 
      5 [1294A - Collecting Coins](/contest/1294/problem/A "Codeforces Round 615 (Div. 3)")
      6 
      7 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
      8 
      9 **Tutorial**
     10 
     11 Tutorial is loading...
     12 
     13 **Solution**
     14 
     15 ```
     16 #include <bits/stdc++.h>
     17 
     18 using namespace std;
     19 
     20 int main() {
     21 #ifdef _DEBUG
     22 	freopen("input.txt", "r", stdin);
     23 //	freopen("output.txt", "w", stdout);
     24 #endif
     25 	
     26 	int q;
     27 	cin >> q;
     28 	for (int i = 0; i < q; ++i) {
     29 		int a[3], n;
     30 		cin >> a[0] >> a[1] >> a[2] >> n;
     31 		sort(a, a + 3);
     32 		n -= 2 * a[2] - a[1] - a[0];
     33 		if (n < 0 || n % 3 != 0) {
     34 			cout << "NO" << endl;
     35 		} else {
     36 			cout << "YES" << endl;
     37 		}
     38 	}
     39 	
     40 	return 0;
     41 }
     42 ```
     43 
     44 [1294B - Collecting Packages](/contest/1294/problem/B "Codeforces Round 615 (Div. 3)")
     45 
     46 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
     47 
     48 **Tutorial**
     49 
     50 Tutorial is loading...
     51 
     52 **Solution**
     53 
     54 ```
     55 #include <bits/stdc++.h>
     56 
     57 using namespace std;
     58 
     59 int main() {
     60 #ifdef _DEBUG
     61 	freopen("input.txt", "r", stdin);
     62 //	freopen("output.txt", "w", stdout);
     63 #endif
     64     int t;
     65     cin >> t;
     66     
     67     for (int tt = 0; tt < t; tt++) {
     68      	int n;
     69     	cin >> n;
     70     	vector<pair<int, int>> a(n);
     71     	for (int i = 0; i < n; ++i) {
     72     		cin >> a[i].first >> a[i].second;
     73     	}
     74     	sort(a.begin(), a.end());
     75     	pair<int, int> cur = make_pair(0, 0);
     76     	string ans;
     77     	bool ok = true;
     78     	for (int i = 0; i < n; ++i) {
     79     		int r = a[i].first - cur.first;
     80     		int u = a[i].second - cur.second;
     81     		if (r < 0 || u < 0) {
     82     			cout << "NO" << endl;
     83     			ok = false;
     84     			break;
     85     		}
     86     		ans += string(r, 'R');
     87     		ans += string(u, 'U');
     88     		cur = a[i];
     89     	}
     90     	
     91     	if (ok)
     92     	    cout << "YES" << endl << ans << endl;
     93    }
     94 
     95 	return 0;
     96 }
     97 ```
     98 
     99 [1294C - Product of Three Numbers](/contest/1294/problem/C "Codeforces Round 615 (Div. 3)")
    100 
    101 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
    102 
    103 **Tutorial**
    104 
    105 Tutorial is loading...
    106 
    107 **Solution**
    108 
    109 ```
    110 #include <bits/stdc++.h>
    111 
    112 using namespace std;
    113 
    114 int main() {
    115 #ifdef _DEBUG
    116 	freopen("input.txt", "r", stdin);
    117 //	freopen("output.txt", "w", stdout);
    118 #endif
    119 	
    120 	int q;
    121 	cin >> q;
    122 	for (int i = 0; i < q; ++i) {
    123 		int n;
    124 		cin >> n;
    125 		set<int> used;
    126 		for (int i = 2; i * i <= n; ++i) {
    127 			if (n % i == 0 && !used.count(i)) {
    128 				used.insert(i);
    129 				n /= i;
    130 				break;
    131 			}
    132 		}
    133 		for (int i = 2; i * i <= n; ++i) {
    134 			if (n % i == 0 && !used.count(i)) {
    135 				used.insert(i);
    136 				n /= i;
    137 				break;
    138 			}
    139 		}
    140 		if (int(used.size()) < 2 || used.count(n) || n == 1) {
    141 			cout << "NO" << endl;
    142 		} else {
    143 			cout << "YES" << endl;
    144 			used.insert(n);
    145 			for (auto it : used) cout << it << " ";
    146 			cout << endl;
    147 		}
    148 	}
    149 	
    150 	return 0;
    151 }
    152 ```
    153 
    154 [1294D - MEX maximizing](/contest/1294/problem/D "Codeforces Round 615 (Div. 3)")
    155 
    156 Idea: [vovuh](/profile/vovuh "Master vovuh")
    157 
    158 **Tutorial**
    159 
    160 Tutorial is loading...
    161 
    162 **Solution**
    163 
    164 ```
    165 #include <bits/stdc++.h>
    166 
    167 using namespace std;
    168 
    169 int main() {
    170 #ifdef _DEBUG
    171 	freopen("input.txt", "r", stdin);
    172 //	freopen("output.txt", "w", stdout);
    173 #endif
    174 	
    175 	int q, x;
    176 	cin >> q >> x;
    177 	vector<int> mods(x);
    178 	
    179 	set<pair<int, int>> vals;
    180 	for (int i = 0; i < x; ++i) {
    181 		vals.insert(make_pair(mods[i], i));
    182 	}
    183 	
    184 	for (int i = 0; i < q; ++i) {
    185 		int cur;
    186 		cin >> cur;
    187 		cur %= x;
    188 		vals.erase(make_pair(mods[cur], cur));
    189 		++mods[cur];
    190 		vals.insert(make_pair(mods[cur], cur));
    191 		cout << vals.begin()->first * x + vals.begin()->second << endl;
    192 	}
    193 	
    194 	return 0;
    195 }
    196 ```
    197 
    198 [1294E - Obtain a Permutation](/contest/1294/problem/E "Codeforces Round 615 (Div. 3)")
    199 
    200 Idea: [vovuh](/profile/vovuh "Master vovuh")
    201 
    202 **Tutorial**
    203 
    204 Tutorial is loading...
    205 
    206 **Solution**
    207 
    208 ```
    209 #include <bits/stdc++.h>
    210 
    211 using namespace std;
    212 
    213 int main() {
    214 #ifdef _DEBUG
    215 	freopen("input.txt", "r", stdin);
    216 //	freopen("output.txt", "w", stdout);
    217 #endif
    218 	
    219 	int n, m;
    220 	cin >> n >> m;
    221 	vector<vector<int>> a(n, vector<int>(m));
    222 	for (int i = 0; i < n; ++i) {
    223 		for (int j = 0; j < m; ++j) {
    224 			cin >> a[i][j];
    225 			--a[i][j];	
    226 		}
    227 	}
    228 	
    229 	long long ans = 0;
    230 	for (int j = 0; j < m; ++j) {
    231 		vector<int> cnt(n);
    232 		for (int i = 0; i < n; ++i) {
    233 			if (a[i][j] % m == j) {
    234 				int pos = a[i][j] / m;
    235 				if (pos < n) {
    236 					++cnt[(i - pos + n) % n];
    237 				}
    238 			}
    239 		}
    240 		int cur = n - cnt[0];
    241 		for (int i = 1; i < n; ++i) {
    242 			cur = min(cur, n - cnt[i] + i);
    243 		}
    244 		ans += cur;
    245 	}
    246 	
    247 	cout << ans << endl;
    248 	
    249 	return 0;
    250 }
    251 ```
    252 
    253 [1294F - Three Paths on a Tree](/contest/1294/problem/F "Codeforces Round 615 (Div. 3)")
    254 
    255 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
    256 
    257 **Tutorial**
    258 
    259 Tutorial is loading...
    260 
    261 **Solution**
    262 
    263 ```
    264 #include <bits/stdc++.h>
    265 
    266 using namespace std;
    267 
    268 #define x first
    269 #define y second
    270 
    271 vector<int> p;
    272 vector<vector<int>> g;
    273 
    274 pair<int, int> dfs(int v, int par = -1, int dist = 0) {
    275 	p[v] = par;
    276 	pair<int, int> res = make_pair(dist, v);
    277 	for (auto to : g[v]) {
    278 		if (to == par) continue;
    279 		res = max(res, dfs(to, v, dist + 1));
    280 	}
    281 	return res;
    282 }
    283 
    284 int main() {
    285 #ifdef _DEBUG
    286 	freopen("input.txt", "r", stdin);
    287 //	freopen("output.txt", "w", stdout);
    288 #endif
    289 	
    290 	int n;
    291 	cin >> n;
    292 	p = vector<int>(n);
    293 	g = vector<vector<int>>(n);
    294 	for (int i = 0; i < n - 1; ++i) {
    295 		int x, y;
    296 		cin >> x >> y;
    297 		--x, --y;
    298 		g[x].push_back(y);
    299 		g[y].push_back(x);	
    300 	}
    301 	
    302 	
    303 	pair<int, int> da = dfs(0);
    304 	pair<int, int> db = dfs(da.y);
    305 	vector<int> diam;
    306 	int v = db.y;
    307 	while (v != da.y) {
    308 		diam.push_back(v);
    309 		v = p[v];
    310 	}
    311 	diam.push_back(da.y);
    312 	
    313 	if (int(diam.size()) == n) {
    314 		cout << n - 1 << " " << endl << diam[0] + 1 << " " << diam[1] + 1 << " " << diam.back() + 1 << endl;
    315 	} else {
    316 		queue<int> q;
    317 		vector<int> d(n, -1);
    318 		for (auto v : diam) {
    319 			d[v] = 0;
    320 			q.push(v);
    321 		}
    322 		while (!q.empty()) {
    323 			int v = q.front();
    324 			q.pop();
    325 			for (auto to : g[v]) {
    326 				if (d[to] == -1) {
    327 					d[to] = d[v] + 1;
    328 					q.push(to);
    329 				}
    330 			}
    331 		}
    332 		pair<int, int> mx = make_pair(d[0], 0);
    333 		for (int v = 1; v < n; ++v) {
    334 			mx = max(mx, make_pair(d[v], v));
    335 		}
    336 		cout << int(diam.size()) - 1 + mx.x << endl << diam[0] + 1 << " " << mx.y + 1 << " " << diam.back() + 1 << endl;
    337 	}
    338 	
    339 	return 0;
    340 }
    341 ```