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 ```