1462.md (6271B)
1 Source: https://codeforces.com/blog/entry/85594 2 3 All problems were created by [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") and developed by me ([Stepavly](/profile/Stepavly "Master Stepavly")) and [Supermagzzz](/profile/Supermagzzz "Master Supermagzzz"). 4 5 [1462A - Favorite Sequence](/contest/1462/problem/A "Codeforces Round 690 (Div. 3)") 6 7 **Editorial** 8 9 Tutorial is loading... 10 11 **Solution** 12 13 ``` 14 #include <bits/stdc++.h> 15 16 using namespace std; 17 18 void solve() { 19 int n; 20 cin >> n; 21 vector<int> v(n); 22 for (int &e : v) { 23 cin >> e; 24 } 25 int left = 0, right = n - 1; 26 vector<int> ans(n); 27 for (int i = 0; i < n; i++) { 28 if (i % 2 == 0) { 29 ans[i] = v[left++]; 30 } else { 31 ans[i] = v[right--]; 32 } 33 } 34 for (int i : ans) { 35 cout << i << " "; 36 } 37 cout << "\n"; 38 } 39 40 int main() { 41 int t; 42 cin >> t; 43 while (t--) { 44 solve(); 45 } 46 } 47 ``` 48 49 [1462B - Last Year's Substring](/contest/1462/problem/B "Codeforces Round 690 (Div. 3)") 50 51 **Editorial** 52 53 Tutorial is loading... 54 55 **Solution** 56 57 ``` 58 #include <bits/stdc++.h> 59 60 using namespace std; 61 62 void solve() { 63 int n; 64 cin >> n; 65 string s; 66 cin >> s; 67 68 for (int i = 0; i <= 4; i++) { 69 if (s.substr(0, i) + s.substr(n - 4 + i, 4 - i) == "2020") { 70 cout << "YES" << endl; 71 return; 72 } 73 } 74 cout << "NO" << endl; 75 } 76 77 int main() { 78 int tests; 79 cin >> tests; 80 while (tests-- > 0) { 81 solve(); 82 } 83 return 0; 84 } 85 ``` 86 87 [1462C - Unique Number](/contest/1462/problem/C "Codeforces Round 690 (Div. 3)") 88 89 **Editorial** 90 91 Tutorial is loading... 92 93 **Solution** 94 95 ``` 96 #include <bits/stdc++.h> 97 98 using namespace std; 99 100 void solve() { 101 int x; 102 cin >> x; 103 vector<int> ans; 104 int sum = 0, last = 9; 105 while (sum < x && last > 0) { 106 ans.push_back(min(x - sum, last)); 107 sum += last; 108 last--; 109 } 110 if (sum < x) { 111 cout << -1 << "\n"; 112 } else { 113 reverse(ans.begin(), ans.end()); 114 for (int i : ans) { 115 cout << i; 116 } 117 cout << "\n"; 118 } 119 } 120 121 int main() { 122 int t; 123 cin >> t; 124 while (t--) { 125 solve(); 126 } 127 } 128 ``` 129 130 [1462D - Add to Neighbour and Remove](/contest/1462/problem/D "Codeforces Round 690 (Div. 3)") 131 132 Problem authors: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov"), [Supermagzzz](/profile/Supermagzzz "Master Supermagzzz"), [Stepavly](/profile/Stepavly "Master Stepavly"). 133 134 **Editorial** 135 136 Tutorial is loading... 137 138 **Solution** 139 140 ``` 141 #include <bits/stdc++.h> 142 using namespace std; 143 144 using ll = long long; 145 146 void solve() { 147 int n; 148 cin >> n; 149 vector<ll> a(n); 150 ll sum = 0; 151 for (ll &x : a) { 152 cin >> x; 153 sum += x; 154 } 155 156 for (int i = n; i >= 1; i--) { 157 if (sum % i == 0) { 158 ll needSum = sum / i; 159 ll curSum = 0; 160 bool ok = true; 161 for (int j = 0; j < n; j++) { 162 curSum += a[j]; 163 if (curSum > needSum) { 164 ok = false; 165 break; 166 } else if (curSum == needSum) { 167 curSum = 0; 168 } 169 } 170 171 if (ok) { 172 cout << n - i << endl; 173 return; 174 } 175 } 176 } 177 } 178 179 int main() { 180 int tests; 181 cin >> tests; 182 while (tests-- > 0) { 183 solve(); 184 } 185 return 0; 186 } 187 ``` 188 189 [1462E1 - Close Tuples (easy version)](/contest/1462/problem/E1 "Codeforces Round 690 (Div. 3)") 190 191 **Editorial** 192 193 Tutorial is loading... 194 195 **Solution** 196 197 ``` 198 #include <bits/stdc++.h> 199 200 using namespace std; 201 using ll = long long; 202 203 void solve() { 204 int n; 205 cin >> n; 206 vector<ll> cnt(n + 1); 207 for (int i = 0; i < n; i++) { 208 int x; 209 cin >> x; 210 cnt[x]++; 211 } 212 ll ans = 0; 213 for (int i = 2; i < n; i++) { 214 ans += cnt[i - 1] * cnt[i] * cnt[i + 1]; 215 } 216 for (int i = 1; i < n; i++) { 217 ans += cnt[i] * (cnt[i] - 1) / 2 * cnt[i + 1]; 218 } 219 for (int i = 2; i <= n; i++) { 220 ans += cnt[i - 1] * cnt[i] * (cnt[i] - 1) / 2; 221 } 222 for (int i = 2; i < n; i++) { 223 ans += cnt[i - 1] * cnt[i + 1] * (cnt[i + 1] - 1) / 2; 224 } 225 for (int i = 2; i < n; i++) { 226 ans += cnt[i + 1] * cnt[i - 1] * (cnt[i - 1] - 1) / 2; 227 } 228 for (int i = 1; i <= n; i++) { 229 ans += cnt[i] * (cnt[i] - 1) * (cnt[i] - 2) / 6; 230 } 231 cout << ans << "\n"; 232 } 233 234 int main() { 235 int t; 236 cin >> t; 237 while (t--) { 238 solve(); 239 } 240 } 241 ``` 242 243 [1462E2 - Close Tuples (hard version)](/contest/1462/problem/E2 "Codeforces Round 690 (Div. 3)") 244 245 **Editorial** 246 247 Tutorial is loading... 248 249 **Solution** 250 251 ``` 252 #include <bits/stdc++.h> 253 254 using namespace std; 255 using ll = long long; 256 257 const int N = 300500; 258 const int mod = 1000000007; 259 ll fact[N]; 260 ll invFact[N]; 261 262 ll fast_pow(ll a, ll p) { 263 ll res = 1; 264 while (p) { 265 if (p % 2 == 0) { 266 a = (a * a) % mod; 267 p /= 2; 268 } else { 269 res = (res * a) % mod; 270 p--; 271 } 272 } 273 return res; 274 } 275 276 ll C(int n, int k) { 277 if (k > n) { 278 return 0; 279 } 280 return fact[n] * invFact[k] % mod * invFact[n - k] % mod; 281 } 282 283 void solve() { 284 int n, m, k; 285 cin >> n >> m >> k; 286 vector<ll> v(n); 287 for (ll &e : v) { 288 cin >> e; 289 } 290 sort(v.begin(), v.end()); 291 ll ans = 0; 292 for (int i = 0; i < n; i++) { 293 int l = i + 1; 294 int r = upper_bound(v.begin(), v.end(), v[i] + k) - v.begin(); 295 ans = (ans + C(r - l, m - 1)) % mod; 296 } 297 cout << ans << "\n"; 298 } 299 300 int main() { 301 fact[0] = invFact[0] = 1; 302 for (int i = 1; i < N; i++) { 303 fact[i] = (fact[i - 1] * i) % mod; 304 invFact[i] = fast_pow(fact[i], mod - 2); 305 } 306 int t; 307 cin >> t; 308 while (t--) { 309 solve(); 310 } 311 } 312 ``` 313 314 [1462F - The Treasure of The Segments](/contest/1462/problem/F "Codeforces Round 690 (Div. 3)") 315 316 **Editorial** 317 318 Tutorial is loading... 319 320 **Solution** 321 322 ``` 323 #include <bits/stdc++.h> 324 325 using namespace std; 326 using ll = long long; 327 328 void solve() { 329 vector<int> L; 330 vector<int> R; 331 int n; 332 cin >> n; 333 vector<pair<int, int>> v(n); 334 for (auto &[l, r] : v) { 335 cin >> l >> r; 336 L.push_back(l); 337 R.push_back(r); 338 } 339 sort(L.begin(), L.end()); 340 sort(R.begin(), R.end()); 341 int ans = n - 1; 342 for (auto [l, r] : v) { 343 int left = lower_bound(R.begin(), R.end(), l) - R.begin(); 344 int right = max(0, n - (int)(upper_bound(L.begin(), L.end(), r) - L.begin())); 345 ans = min(ans, left + right); 346 } 347 cout << ans << "\n"; 348 } 349 350 int main() { 351 int t; 352 cin >> t; 353 while (t--) { 354 solve(); 355 } 356 } 357 ```