1154.md (7821B)
1 Source: https://codeforces.com/blog/entry/66586 2 3 [1154A - Restoring Three Numbers](/contest/1154/problem/A "Codeforces Round 552 (Div. 3)") 4 5 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 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 vector<int> a(4); 25 for (int i = 0; i < 4; ++i) { 26 cin >> a[i]; 27 } 28 sort(a.begin(), a.end()); 29 cout << a[3] - a[0] << " " << a[3] - a[1] << " " << a[3] - a[2] << endl; 30 31 return 0; 32 } 33 ``` 34 35 [1154B - Make Them Equal](/contest/1154/problem/B "Codeforces Round 552 (Div. 3)") 36 37 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 38 39 **Tutorial** 40 41 Tutorial is loading... 42 43 **Solution** 44 45 ``` 46 #include <bits/stdc++.h> 47 48 using namespace std; 49 50 int main() { 51 #ifdef _DEBUG 52 freopen("input.txt", "r", stdin); 53 // freopen("output.txt", "w", stdout); 54 #endif 55 56 int n; 57 cin >> n; 58 vector<int> a(n); 59 for (int i = 0; i < n; ++i) { 60 cin >> a[i]; 61 } 62 sort(a.begin(), a.end()); 63 a.resize(unique(a.begin(), a.end()) - a.begin()); 64 if (a.size() > 3) { 65 cout << -1 << endl; 66 } else { 67 if (a.size() == 1) { 68 cout << 0 << endl; 69 } else if (a.size() == 2) { 70 if ((a[1] - a[0]) % 2 == 0) { 71 cout << (a[1] - a[0]) / 2 << endl; 72 } else { 73 cout << a[1] - a[0] << endl; 74 } 75 } else { 76 if (a[1] - a[0] != a[2] - a[1]) { 77 cout << -1 << endl; 78 } else { 79 cout << a[1] - a[0] << endl; 80 } 81 } 82 } 83 84 return 0; 85 } 86 ``` 87 88 [1154C - Gourmet Cat](/contest/1154/problem/C "Codeforces Round 552 (Div. 3)") 89 90 Idea: [le.mur](/profile/le.mur "Unrated, le.mur") 91 92 **Tutorial** 93 94 Tutorial is loading... 95 96 **Solution** 97 98 ``` 99 #include <bits/stdc++.h> 100 101 using namespace std; 102 103 int main() { 104 #ifdef _DEBUG 105 freopen("input.txt", "r", stdin); 106 // freopen("output.txt", "w", stdout); 107 #endif 108 109 vector<int> a(3); 110 cin >> a[0] >> a[1] >> a[2]; 111 112 vector<int> idx({0, 1, 2, 0, 2, 1, 0}); 113 114 int full = min({a[0] / 3, a[1] / 2, a[2] / 2}); 115 a[0] -= full * 3; 116 a[1] -= full * 2; 117 a[2] -= full * 2; 118 119 int ans = 0; 120 for (int start = 0; start < 7; ++start) { 121 int day = start; 122 vector<int> b = a; 123 int cur = 0; 124 while (b[idx[day]] > 0) { 125 --b[idx[day]]; 126 day = (day + 1) % 7; 127 ++cur; 128 } 129 ans = max(ans, full * 7 + cur); 130 } 131 132 cout << ans << endl; 133 134 return 0; 135 } 136 ``` 137 138 [1154D - Walking Robot](/contest/1154/problem/D "Codeforces Round 552 (Div. 3)") 139 140 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 141 142 **Tutorial** 143 144 Tutorial is loading... 145 146 **Solution** 147 148 ``` 149 #include<bits/stdc++.h> 150 151 using namespace std; 152 153 int a, b, maxa; 154 155 void use_battery(int s) 156 { 157 if(s == 1) a = min(a + 1, maxa); 158 --b; 159 } 160 161 void use_accum() 162 { 163 --a; 164 } 165 166 int main() 167 { 168 int ans = 0; 169 int n; 170 cin >> n >> b >> a; 171 maxa = a; 172 vector<int> s(n); 173 for(int i = 0; i < n; i++) cin >> s[i]; 174 for(int i = 0; i < n; i++) 175 { 176 if(a == 0 && b == 0) 177 break; 178 else if(a == 0) 179 use_battery(s[i]); 180 else if(b == 0) 181 use_accum(); 182 else if(s[i] == 1 && a < maxa) 183 use_battery(s[i]); 184 else use_accum(); 185 ans++; 186 } 187 cout << ans << endl; 188 } 189 ``` 190 191 [1154E - Two Teams](/contest/1154/problem/E "Codeforces Round 552 (Div. 3)") 192 193 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 194 195 **Tutorial** 196 197 Tutorial is loading... 198 199 **Solution** 200 201 ``` 202 #include <bits/stdc++.h> 203 204 using namespace std; 205 206 int main() { 207 #ifdef _DEBUG 208 freopen("input.txt", "r", stdin); 209 // freopen("output.txt", "w", stdout); 210 #endif 211 212 int n, k; 213 cin >> n >> k; 214 vector<pair<int, int>> a(n); 215 for (int i = 0; i < n; ++i) { 216 cin >> a[i].first; 217 a[i].second = i; 218 } 219 220 sort(a.rbegin(), a.rend()); 221 queue<int> q; 222 for (int i = 0; i < n; ++i) { 223 q.push(a[i].second); 224 } 225 226 set<int> idx; 227 for (int i = 0; i < n; ++i) { 228 idx.insert(i); 229 } 230 string ans(n, '0'); 231 int who = 0; 232 while (!idx.empty()) { 233 while (!idx.count(q.front())) { 234 q.pop(); 235 } 236 int pos = q.front(); 237 q.pop(); 238 239 vector<int> add; 240 auto it = idx.find(pos); 241 for (int i = 0; i <= k; ++i) { 242 add.push_back(*it); 243 if (it == idx.begin()) break; 244 --it; 245 } 246 it = next(idx.find(pos)); 247 for (int i = 0; i < k; ++i) { 248 if (it == idx.end()) break; 249 add.push_back(*it); 250 ++it; 251 } 252 for (auto it : add) { 253 idx.erase(it); 254 ans[it] = '1' + who; 255 } 256 who ^= 1; 257 } 258 259 cout << ans << endl; 260 261 return 0; 262 } 263 ``` 264 265 [1154F - Shovels Shop](/contest/1154/problem/F "Codeforces Round 552 (Div. 3)") 266 267 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 268 269 **Tutorial** 270 271 Tutorial is loading... 272 273 **Solution** 274 275 ``` 276 #include <bits/stdc++.h> 277 278 using namespace std; 279 280 const int INF = 1e9; 281 282 int main() { 283 #ifdef _DEBUG 284 freopen("input.txt", "r", stdin); 285 // freopen("output.txt", "w", stdout); 286 #endif 287 288 int n, m, k; 289 cin >> n >> m >> k; 290 vector<int> a(n); 291 for (int i = 0; i < n; ++i) { 292 cin >> a[i]; 293 } 294 295 sort(a.begin(), a.end()); 296 a.resize(k); 297 reverse(a.begin(), a.end()); 298 299 vector<int> offers(k + 1); 300 for (int i = 0; i < m; ++i) { 301 int x, y; 302 cin >> x >> y; 303 if (x <= k) { 304 offers[x] = max(offers[x], y); 305 } 306 } 307 308 vector<int> pref(k + 1); 309 for (int i = 0; i < k; ++i) { 310 pref[i + 1] = pref[i] + a[i]; 311 } 312 313 vector<int> dp(k + 1, INF); 314 dp[0] = 0; 315 for (int i = 0; i < k; ++i) { 316 dp[i + 1] = min(dp[i + 1], dp[i] + a[i]); 317 for (int j = 1; j <= k; ++j) { 318 if (offers[j] == 0) continue; 319 if (i + j > k) break; 320 dp[i + j] = min(dp[i + j], dp[i] + pref[i + j - offers[j]] - pref[i]); 321 } 322 } 323 324 cout << dp[k] << endl; 325 326 return 0; 327 } 328 ``` 329 330 [1154G - Minimum Possible LCM](/contest/1154/problem/G "Codeforces Round 552 (Div. 3)") 331 332 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 333 334 **Tutorial** 335 336 Tutorial is loading... 337 338 **Solution** 339 340 ``` 341 #include <bits/stdc++.h> 342 343 using namespace std; 344 345 const int INF = 1e9; 346 const int N = 10 * 1000 * 1000 + 11; 347 348 int n; 349 vector<int> a; 350 351 int mind[N]; 352 353 pair<int, int> mins[N]; 354 vector<pair<int, int>> divs; 355 356 void build_sieve() { 357 vector<int> pr; 358 mind[0] = mind[1] = 1; 359 for (int i = 2; i < N; ++i) { 360 if (mind[i] == 0) { 361 pr.push_back(i); 362 mind[i] = i; 363 } 364 for (int j = 0; j < int(pr.size()) && pr[j] <= mind[i] && i * pr[j] < N; ++j) { 365 mind[i * pr[j]] = pr[j]; 366 } 367 } 368 } 369 370 void add_to_mins(int curd, int idx) { 371 if(mins[curd].first == -1) 372 mins[curd].first = idx; 373 else if(mins[curd].second == -1) 374 mins[curd].second = idx; 375 } 376 377 void rec(int pos, int curd, int idx) { 378 if (pos == int(divs.size())) { 379 add_to_mins(curd, idx); 380 return; 381 } 382 int curm = 1; 383 for (int i = 0; i <= divs[pos].second; ++i) { 384 rec(pos + 1, curd * curm, idx); 385 curm *= divs[pos].first; 386 } 387 } 388 389 void add(int idx) { 390 int value = a[idx]; 391 divs.clear(); 392 while (value > 1) { 393 int d = mind[value]; 394 if (!divs.empty() && divs.back().first == d) { 395 ++divs.back().second; 396 } else { 397 divs.push_back(make_pair(d, 1)); 398 } 399 value /= d; 400 } 401 rec(0, 1, idx); 402 } 403 404 int main() { 405 #ifdef _DEBUG 406 freopen("input.txt", "r", stdin); 407 // freopen("output.txt", "w", stdout); 408 #endif 409 410 cin >> n; 411 a.resize(n); 412 for (int i = 0; i < n; ++i) { 413 cin >> a[i]; 414 } 415 for(int i = 0; i < N; i++) 416 mins[i] = make_pair(-1, -1); 417 build_sieve(); 418 419 vector<pair<int, int> > vals; 420 for(int i = 0; i < n; i++) 421 vals.push_back(make_pair(a[i], i)); 422 sort(vals.begin(), vals.end()); 423 for (int i = 0; i < n; ++i) { 424 if(i > 1 && vals[i].first == vals[i - 2].first) continue; 425 add(vals[i].second); 426 } 427 428 long long l = INF * 1ll * INF; 429 int ansi = -1, ansj = -1; 430 for (int i = 1; i < N; ++i) { 431 pair<int, int> idxs = mins[i]; 432 if (idxs.second == -1) continue; 433 long long curl = a[idxs.first] * 1ll * a[idxs.second] / i; 434 if (l > curl) { 435 l = curl; 436 ansi = min(idxs.first, idxs.second); 437 ansj = max(idxs.first, idxs.second); 438 } 439 } 440 441 cout << ansi + 1 << " " << ansj + 1 << endl; 442 443 return 0; 444 } 445 ```