1497.md (8257B)
1 Source: https://codeforces.com/blog/entry/88677 2 3 We are really sorry to make the round unrated. Anyway, we hope that you enjoyed the problems! 4 5 [1497A - Meximization](/contest/1497/problem/A "Codeforces Round 708 (Div. 2)") 6 7 Idea: [shishyando](/profile/shishyando "Expert shishyando") 8 9 **Tutorial** 10 11 Tutorial is loading... 12 13 **Implementation** 14 15 ``` 16 // один манул 17 #include <bits/stdc++.h> 18 using namespace std; 19 20 int main() { 21 int T; 22 cin >> T; 23 while (T --> 0) { 24 int n; 25 cin >> n; 26 vector<int> a(n); 27 for (int i = 0; i < n; ++i) cin >> a[i]; 28 sort(a.begin(), a.end()); 29 vector<int> b; 30 for (int i = 0; i < n; i++) { 31 if (i == 0 || a[i] != a[i - 1]) { 32 b.emplace_back(a[i]); 33 } 34 } 35 for (int i = 0; i < n; i++) { 36 if (i > 0 && a[i] == a[i - 1]) { 37 b.emplace_back(a[i]); 38 } 39 } 40 for (auto x : b) cout << x << ' '; 41 cout << '\n'; 42 } 43 return 0; 44 cout << "amogus"; 45 } 46 ``` 47 48 [1497B - M-arrays](/contest/1497/problem/B "Codeforces Round 708 (Div. 2)") 49 50 Idea: [Artyom123](/profile/Artyom123 "Master Artyom123") 51 52 **Tutorial** 53 54 Tutorial is loading... 55 56 **Implementation** 57 58 ``` 59 //два манула 60 #include <bits/stdc++.h> 61 using namespace std; 62 63 int main() { 64 int t; 65 cin >> t; 66 while (t--) { 67 int n, m; 68 cin >> n >> m; 69 map<int, int> cnt; 70 while (n--) { 71 int x; 72 cin >> x; 73 cnt[x % m]++; 74 } 75 int ans = 0; 76 for (auto &c : cnt) { 77 if (c.first == 0) ans++; 78 else if (2 * c.first == m) { 79 ans++; 80 } else if (2 * c.first < m || cnt.find(m - c.first) == cnt.end()) { 81 int x = c.second, y = cnt[m - c.first]; 82 ans += 1 + max(0, abs(x - y) - 1); 83 } 84 } 85 cout << ans << '\n'; 86 } 87 return 0; 88 } 89 ``` 90 91 [1497C1 - k-LCM (easy version)](/contest/1497/problem/C1 "Codeforces Round 708 (Div. 2)") 92 93 Idea: [shishyando](/profile/shishyando "Expert shishyando") 94 95 **Tutorial** 96 97 Tutorial is loading... 98 99 **Implementation** 100 101 ``` 102 // три манула 103 #include <bits/stdc++.h> 104 using namespace std; 105 106 int main() { 107 int T; 108 cin >> T; 109 while (T --> 0) { 110 int n, k; 111 cin >> n >> k; 112 if (n % 2) cout << 1 << ' ' << n / 2 << ' ' << n / 2 << '\n'; 113 else if (n % 2 == 0 && n % 4) cout << 2 << ' ' << n / 2 - 1 << ' ' << n / 2 - 1 << '\n'; 114 else cout << n / 2 << ' ' << n / 4 << ' ' << n / 4 << '\n'; 115 } 116 return 0; 117 } 118 ``` 119 120 [1497C2 - k-LCM (hard version)](/contest/1497/problem/C2 "Codeforces Round 708 (Div. 2)") 121 122 Idea: [isaf27](/profile/isaf27 "International Grandmaster isaf27") 123 124 **Tutorial** 125 126 Tutorial is loading... 127 128 **Implementation** 129 130 ``` 131 // четыре манула 132 #include <bits/stdc++.h> 133 using namespace std; 134 135 vector<int> solve3(int n) { 136 if (n % 2 == 1) return {1, n / 2, n / 2}; 137 if (n % 4 == 0) return {n / 2, n / 4, n / 4}; 138 if (n % 2 == 0) return {2, n / 2 - 1, n / 2 - 1}; 139 } 140 141 int main() { 142 int T; 143 cin >> T; 144 while (T --> 0) { 145 int n, k; 146 cin >> n >> k; 147 vector<int> added = solve3(n - k + 3); 148 for (int i = 0; i < k; ++i) { 149 cout << (i <3 ? added[i] : 1) << ' '; // <3 150 } 151 cout << '\n'; 152 } 153 return 0; 154 } 155 ``` 156 157 [1497D - Genius](/contest/1497/problem/D "Codeforces Round 708 (Div. 2)") 158 159 Idea: [shishyando](/profile/shishyando "Expert shishyando") 160 161 **Tutorial** 162 163 Tutorial is loading... 164 165 **Implementation** 166 167 ``` 168 // пять манулов 169 #include <bits/stdc++.h> 170 using namespace std; 171 172 int main() { 173 int T; 174 cin >> T; 175 while (T --> 0) { 176 int n; 177 cin >> n; 178 vector<long long> s(n), tag(n), dp(n, 0); 179 for (int i = 0; i < n; ++i) cin >> tag[i]; 180 for (int i = 0; i < n; ++i) cin >> s[i]; 181 for (int j = 1; j < n; ++j) { 182 for (int i = j - 1; i >= 0; --i) { 183 if (tag[i] == tag[j]) continue; 184 long long dpi = dp[i], dpj = dp[j], p = abs(s[i] - s[j]); 185 dp[i] = max(dp[i], dpj + p); 186 dp[j] = max(dp[j], dpi + p); 187 } 188 } 189 cout << *max_element(dp.begin(), dp.end()) << '\n'; 190 } 191 return 0; 192 } 193 ``` 194 195 [1497E1 - Square-Free Division (easy version)](/contest/1497/problem/E1 "Codeforces Round 708 (Div. 2)") 196 197 Idea: [Artyom123](/profile/Artyom123 "Master Artyom123") 198 199 **Tutorial** 200 201 Tutorial is loading... 202 203 **Implementation** 204 205 ``` 206 // шесть манулов 207 #include <bits/stdc++.h> 208 using namespace std; 209 210 const int MAXA = 1e7; 211 212 vector<int> primes; 213 int mind[MAXA + 1]; 214 215 int main() { 216 217 for (int i = 2; i <= MAXA; ++i) { 218 if (mind[i] == 0) { 219 primes.emplace_back(i); 220 mind[i] = i; 221 } 222 for (auto &x : primes) { 223 if (x > mind[i] || x * i > MAXA) break; 224 mind[x * i] = x; 225 } 226 } 227 228 int T; 229 cin >> T; 230 while (T --> 0) { 231 int n, k; 232 cin >> n >> k; 233 vector<int> a(n, 1); 234 for (int i = 0; i < n; ++i) { 235 int x; 236 cin >> x; 237 int cnt = 0, last = 0; 238 while (x > 1) { 239 int p = mind[x]; 240 if (last == p) { 241 ++cnt; 242 } else { 243 if (cnt % 2 == 1) a[i] *= last; 244 last = p; 245 cnt = 1; 246 } 247 x /= p; 248 } 249 if (cnt % 2 == 1) a[i] *= last; 250 } 251 252 int L = 0, ans = 1; 253 map<int, int> last; 254 for (int i = 0; i < n; ++i) { 255 if (last.find(a[i]) != last.end() && last[a[i]] >= L) { 256 ++ans; 257 L = i; 258 } 259 last[a[i]] = i; 260 } 261 cout << ans << '\n'; 262 } 263 264 return 0; 265 } 266 ``` 267 268 [1497E2 - Square-Free Division (hard version)](/contest/1497/problem/E2 "Codeforces Round 708 (Div. 2)") 269 270 Idea: [isaf27](/profile/isaf27 "International Grandmaster isaf27") 271 272 **Tutorial** 273 274 Tutorial is loading... 275 276 **Implementation** 277 278 ``` 279 // семь манулов 280 #include <bits/stdc++.h> 281 using namespace std; 282 283 const int INF = 1e9 + 1; 284 const int MAXA = 1e7; 285 vector<int> primes; 286 int mind[MAXA + 1]; 287 288 int main() { 289 for (int i = 2; i <= MAXA; ++i) { 290 if (mind[i] == 0) { 291 primes.emplace_back(i); 292 mind[i] = i; 293 } 294 for (auto &x : primes) { 295 if (x > mind[i] || x * i > MAXA) break; 296 mind[x * i] = x; 297 } 298 } 299 vector<int> cnt(MAXA + 1); 300 int t; 301 cin >> t; 302 while (t--) { 303 int n, k; 304 cin >> n >> k; // уже k манулов 305 vector<int> a(n, 1); 306 for (int i = 0; i < n; ++i) { 307 int x; 308 cin >> x; 309 int cnt = 0, last = 0; 310 while (x > 1) { 311 int p = mind[x]; 312 if (last == p) { 313 ++cnt; 314 } else { 315 if (cnt % 2 == 1) a[i] *= last; 316 last = p; 317 cnt = 1; 318 } 319 x /= p; 320 } 321 if (cnt % 2 == 1) a[i] *= last; 322 } 323 vector<vector<int>> mnleft(n, vector<int>(k + 1)); 324 for (int j = 0; j <= k; j++) { 325 int l = n, now = 0; 326 for (int i = n - 1; i >= 0; i--) { 327 while (l - 1 >= 0 && now + (cnt[a[l - 1]] > 0) <= j) { 328 l--; 329 now += (cnt[a[l]] > 0); 330 cnt[a[l]]++; 331 } 332 mnleft[i][j] = l; 333 if (cnt[a[i]] > 1) now--; 334 cnt[a[i]]--; 335 } 336 } 337 vector<vector<int>> dp(n + 1, vector<int>(k + 1, INF)); 338 for (auto &c : dp[0]) c = 0; 339 for (int i = 1; i <= n; i++) { 340 for (int j = 0; j <= k; j++) { 341 if (j > 0) dp[i][j] = dp[i][j - 1]; 342 for (int lst = 0; lst <= j; lst++) { 343 dp[i][j] = min(dp[i][j], dp[mnleft[i - 1][lst]][j - lst] + 1); 344 } 345 } 346 } 347 int ans = INF; 348 for (auto &c : dp.back()) ans = min(ans, c); 349 cout << ans << "\n"; 350 } 351 return 0; 352 } 353 ```