codeforces-scrape

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

1283.md (5186B)


      1 Source: https://codeforces.com/blog/entry/72592
      2 
      3 All problems were proposed by Mikhail [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") Mirzayanov.
      4 
      5 [1283A - Minutes Before the New Year](/contest/1283/problem/A "Codeforces Round 611 (Div. 3)")
      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 	int q;
     25 	scanf("%d", &q);
     26 	for (int i = 0; i < q; ++i) {
     27 		int h, m;
     28 		scanf("%d %d", &h, &m);
     29 		printf("%d\n", 1440 - h * 60 - m);
     30 	}
     31 	
     32 	return 0;
     33 }
     34 ```
     35 
     36 [1283B - Candies Division](/contest/1283/problem/B "Codeforces Round 611 (Div. 3)")
     37 
     38 **Tutorial**
     39 
     40 Tutorial is loading...
     41 
     42 **Solution**
     43 
     44 ```
     45 #include <bits/stdc++.h>
     46 
     47 using namespace std;
     48 
     49 int main() {
     50 #ifdef _DEBUG
     51 	freopen("input.txt", "r", stdin);
     52 //	freopen("output.txt", "w", stdout);
     53 #endif
     54 	
     55 	int q;
     56 	cin >> q;
     57 	for (int i = 0; i < q; ++i) {
     58 		int n, k;
     59 		cin >> n >> k;
     60 		int full = n - n % k;
     61 		full += min(n % k, k / 2);
     62 		cout << full << endl;
     63 	}
     64 	
     65 	return 0;
     66 }
     67 ```
     68 
     69 [1283C - Friends and Gifts](/contest/1283/problem/C "Codeforces Round 611 (Div. 3)")
     70 
     71 **Tutorial**
     72 
     73 Tutorial is loading...
     74 
     75 **Solution**
     76 
     77 ```
     78 #include <bits/stdc++.h>
     79 
     80 using namespace std;
     81 
     82 int main() {
     83 #ifdef _DEBUG
     84 	freopen("input.txt", "r", stdin);
     85 //	freopen("output.txt", "w", stdout);
     86 #endif
     87 	
     88 	int n;
     89 	cin >> n;
     90 	vector<int> f(n);
     91 	vector<int> in(n), out(n);
     92 	for (int i = 0; i < n; ++i) {
     93 		cin >> f[i];
     94 		--f[i];
     95 		if (f[i] != -1) {
     96 			++out[i];
     97 			++in[f[i]];
     98 		}
     99 	}
    100 	
    101 	vector<int> loops;
    102 	for (int i = 0; i < n; ++i) {
    103 		if (in[i] == 0 && out[i] == 0) {
    104 			loops.push_back(i);
    105 		}
    106 	}
    107 	if (loops.size() == 1) {
    108 		int idx = loops[0];
    109 		for (int i = 0; i < n; ++i) {
    110 			if (in[i] == 0 && i != idx) {
    111 				f[idx] = i;
    112 				++out[idx];
    113 				++in[i];
    114 				break;
    115 			}
    116 		}
    117 	} else if (loops.size() > 1) {
    118 		for (int i = 0; i < int(loops.size()); ++i) {
    119 			int cur = loops[i];
    120 			int nxt = loops[(i + 1) % int(loops.size())];
    121 			f[cur] = nxt;
    122 			++out[cur];
    123 			++in[nxt];
    124 		}
    125 	}
    126 	loops.clear();
    127 	vector<int> ins, outs;
    128 	for (int i = 0; i < n; ++i) {
    129 		if (in[i] == 0) ins.push_back(i);
    130 		if (out[i] == 0) outs.push_back(i);
    131 	}
    132 	assert(ins.size() == outs.size());
    133 	for (int i = 0; i < int(outs.size()); ++i) {
    134 		f[outs[i]] = ins[i];
    135 	}
    136 	
    137 	for (int i = 0; i < n; ++i) {
    138 		cout << f[i] + 1 << " ";
    139 	}
    140 	cout << endl;
    141 	
    142 	return 0;
    143 }
    144 ```
    145 
    146 [1283D - Christmas Trees](/contest/1283/problem/D "Codeforces Round 611 (Div. 3)")
    147 
    148 **Tutorial**
    149 
    150 Tutorial is loading...
    151 
    152 **Solution**
    153 
    154 ```
    155 #include <bits/stdc++.h>
    156 
    157 using namespace std;
    158 
    159 mt19937 rnd(time(NULL));
    160 
    161 int main() {
    162 #ifdef _DEBUG
    163 	freopen("input.txt", "r", stdin);
    164 //	freopen("output.txt", "w", stdout);
    165 #endif
    166 	
    167 	int n, m;
    168 	cin >> n >> m;
    169 	vector<int> x(n);
    170 	for (int i = 0; i < n; ++i) {
    171 		cin >> x[i];
    172 	}
    173 	queue<int> q;
    174 	map<int, int> d;
    175 	for (int i = 0; i < n; ++i) {
    176 		d[x[i]] = 0;
    177 		q.push(x[i]);
    178 	}
    179 	long long ans = 0;
    180 	vector<int> res;
    181 	while (!q.empty()) {
    182 		if (int(res.size()) == m) break;
    183 		int cur = q.front();
    184 		q.pop();
    185 		if (d[cur] != 0) {
    186 			ans += d[cur];
    187 			res.push_back(cur);
    188 		}
    189 		if (!d.count(cur - 1)) {
    190 			d[cur - 1] = d[cur] + 1;
    191 			q.push(cur - 1);
    192 		}
    193 		if (!d.count(cur + 1)) {
    194 			d[cur + 1] = d[cur] + 1;
    195 			q.push(cur + 1);
    196 		}
    197 	}
    198 	cout << ans << endl;
    199 	shuffle(res.begin(), res.end(), rnd);
    200 	for (auto it : res) cout << it << " ";
    201 	cout << endl;
    202 	
    203 	return 0;
    204 }
    205 ```
    206 
    207 [1283E - New Year Parties](/contest/1283/problem/E "Codeforces Round 611 (Div. 3)")
    208 
    209 **Tutorial**
    210 
    211 Tutorial is loading...
    212 
    213 **Solution**
    214 
    215 ```
    216 #include <bits/stdc++.h>
    217 
    218 #define forn(i, n) for (int i = 0; i < int(n); i++)
    219 
    220 using namespace std;
    221 
    222 int n;
    223 vector<int> a, cnt;
    224 
    225 int solvemin(){
    226 	int res = 0;
    227 	forn(i, n){
    228 		if (!cnt[i]) continue;
    229 		++res;
    230 		i += 2;
    231 	}
    232 	return res;
    233 }
    234 
    235 int solvemax(){
    236 	int res = 0;
    237 	int dist = 2;
    238 	bool right = false;
    239 	forn(i, n){
    240 		if (!cnt[i]){
    241 			++dist;
    242 			continue;
    243 		}
    244 		int j = i - 1;
    245 		int sum = 0;
    246 		while (j + 1 < n && cnt[j + 1]){
    247 			++j;
    248 			sum += cnt[j];
    249 		}
    250 		res += (j - i + 1);
    251 		if (sum > j - i + 1 && (!right || dist > 1)){
    252 			--sum;
    253 			++res;
    254 		}
    255 		right = false;
    256 		if (sum > j - i + 1){
    257 			right = true;
    258 			++res;
    259 		}
    260 		i = j;
    261 		dist = 0;
    262 	}
    263 	return res;
    264 }
    265 
    266 int main() {
    267 	scanf("%d", &n);
    268 	a.resize(n);
    269 	cnt.resize(n + 1);
    270 	forn(i, n){
    271 		scanf("%d", &a[i]);
    272 		++cnt[a[i] - 1];
    273 	}
    274 	printf("%d %d\n", solvemin(), solvemax());
    275 	return 0;
    276 }
    277 ```
    278 
    279 [1283F - DIY Garland](/contest/1283/problem/F "Codeforces Round 611 (Div. 3)")
    280 
    281 **Tutorial**
    282 
    283 Tutorial is loading...
    284 
    285 **Solution**
    286 
    287 ```
    288 #define _CRT_SECURE_NO_WARNINGS
    289 
    290 #include<cstdio>
    291 #include<vector>
    292 #include<algorithm>
    293 
    294 using namespace std;
    295 
    296 int main()
    297 {
    298 	int n;
    299 	scanf("%d", &n);
    300 	vector<int> a(n - 1);
    301 	for (int i = 0; i < n - 1; i++)
    302 	{
    303 		scanf("%d", &a[i]);
    304 		a[i]--;
    305 	}
    306 	int root = a[0];
    307 	int last = -1;
    308 	vector<int> used(n, 0);
    309 	printf("%d\n", root + 1);
    310 	int cur = n - 1;
    311 	for (int i = 0; i < n - 1; i++)
    312 	{
    313 		used[a[i]] = 1;
    314 		while (used[cur])
    315 			cur--;
    316 		if (i == n - 2 || used[a[i + 1]])
    317 		{
    318 			printf("%d %d\n", a[i] + 1, cur + 1);
    319 			used[cur] = 1;
    320 		}
    321 		else
    322 			printf("%d %d\n", a[i + 1] + 1, a[i] + 1);
    323 	}
    324 	return 0;
    325 }
    326 ```