1165.md (6511B)
1 Source: https://codeforces.com/blog/entry/67041 2 3 [1165A - Remainder](/contest/1165/problem/A "Codeforces Round 560 (Div. 3)") 4 5 Idea: [vovuh](/profile/vovuh "Candidate Master vovuh") 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 n, x, y; 25 string s; 26 cin >> n >> x >> y >> s; 27 28 int ans = 0; 29 for (int i = n - x; i < n; ++i) { 30 if (i == n - y - 1) ans += s[i] != '1'; 31 else ans += s[i] != '0'; 32 } 33 34 cout << ans << endl; 35 36 return 0; 37 } 38 ``` 39 40 [1165B - Polycarp Training](/contest/1165/problem/B "Codeforces Round 560 (Div. 3)") 41 42 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 43 44 **Tutorial** 45 46 Tutorial is loading... 47 48 **Solution** 49 50 ``` 51 #include <bits/stdc++.h> 52 53 using namespace std; 54 55 int main() { 56 #ifdef _DEBUG 57 freopen("input.txt", "r", stdin); 58 // freopen("output.txt", "w", stdout); 59 #endif 60 61 int n; 62 cin >> n; 63 vector<int> a(n); 64 for (int i = 0; i < n; ++i) { 65 cin >> a[i]; 66 } 67 sort(a.begin(), a.end()); 68 69 int pos = 1; 70 for (int i = 0; i < n; ++i) { 71 if (a[i] >= pos) ++pos; 72 } 73 74 cout << pos - 1 << endl; 75 76 return 0; 77 } 78 ``` 79 80 [1165C - Good String](/contest/1165/problem/C "Codeforces Round 560 (Div. 3)") 81 82 Idea: [BledDest](/profile/BledDest "Grandmaster BledDest") 83 84 **Tutorial** 85 86 Tutorial is loading... 87 88 **Solution** 89 90 ``` 91 #include<bits/stdc++.h> 92 93 using namespace std; 94 95 string s; 96 int n; 97 string res; 98 99 int main() 100 { 101 cin >> n >> s; 102 for(int i = 0; i < n; i++) 103 { 104 if(res.size() % 2 == 0 || res.back() != s[i]) 105 res.push_back(s[i]); 106 } 107 if(res.size() % 2 == 1) res.pop_back(); 108 cout << n - int(res.size()) << endl << res << endl; 109 return 0; 110 } 111 ``` 112 113 [1165D - Almost All Divisors](/contest/1165/problem/D "Codeforces Round 560 (Div. 3)") 114 115 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 116 117 **Tutorial** 118 119 Tutorial is loading... 120 121 **Solution** 122 123 ``` 124 #include <bits/stdc++.h> 125 126 using namespace std; 127 128 int main() { 129 #ifdef _DEBUG 130 freopen("input.txt", "r", stdin); 131 // freopen("output.txt", "w", stdout); 132 #endif 133 134 int t; 135 cin >> t; 136 for (int i = 0; i < t; ++i) { 137 138 int n; 139 cin >> n; 140 vector<long long> d(n); 141 for (int i = 0; i < n; ++i) { 142 cin >> d[i]; 143 } 144 sort(d.begin(), d.end()); 145 long long x = d[0] * d[n - 1]; 146 147 vector<long long> dd; 148 for (int i = 2; i * 1ll * i <= x; ++i) { 149 if (x % i == 0) { 150 dd.push_back(i); 151 if (i != x / i) { 152 dd.push_back(x / i); 153 } 154 } 155 } 156 sort(dd.begin(), dd.end()); 157 158 if (dd == d) { 159 cout << x << endl; 160 } else { 161 cout << -1 << endl; 162 } 163 } 164 165 return 0; 166 } 167 ``` 168 169 [1165E - Two Arrays and Sum of Functions](/contest/1165/problem/E "Codeforces Round 560 (Div. 3)") 170 171 Idea: [vovuh](/profile/vovuh "Candidate Master vovuh") 172 173 **Tutorial** 174 175 Tutorial is loading... 176 177 **Solution** 178 179 ``` 180 #include <bits/stdc++.h> 181 182 using namespace std; 183 184 const int MOD = 998244353; 185 186 int main() { 187 #ifdef _DEBUG 188 freopen("input.txt", "r", stdin); 189 // freopen("output.txt", "w", stdout); 190 #endif 191 192 int n; 193 cin >> n; 194 vector<int> a(n), b(n); 195 for (int i = 0; i < n; ++i) { 196 cin >> a[i]; 197 } 198 for (int i = 0; i < n; ++i) { 199 cin >> b[i]; 200 } 201 202 sort(b.begin(), b.end()); 203 vector<pair<long long, int>> val(n); 204 for (int i = 0; i < n; ++i) { 205 val[i].first = (i + 1) * 1ll * (n - i) * a[i]; 206 val[i].second = i; 207 } 208 sort(val.rbegin(), val.rend()); 209 int ans = 0; 210 for (int i = 0; i < n; ++i) { 211 ans = (ans + (val[i].first % MOD * 1ll * b[i]) % MOD) % MOD; 212 } 213 cout << ans << endl; 214 215 return 0; 216 } 217 ``` 218 219 [1165F1 - Microtransactions (easy version)](/contest/1165/problem/F1 "Codeforces Round 560 (Div. 3)") 220 221 Idea: [BledDest](/profile/BledDest "Grandmaster BledDest") 222 223 **Tutorial** 224 225 Tutorial is loading... 226 227 **Solution** 228 229 ``` 230 #include <bits/stdc++.h> 231 232 using namespace std; 233 234 int n, m; 235 vector<int> k; 236 vector<pair<int, int>> q(1001); 237 238 bool can(int day) { 239 vector<int> lst(n, -1); 240 for (int i = 0; i < m; ++i) { 241 if (q[i].first <= day) { 242 lst[q[i].second] = max(lst[q[i].second], q[i].first); 243 } 244 } 245 vector<vector<int>> off(1001); 246 for (int i = 0; i < n; ++i) { 247 if (lst[i] != -1) { 248 off[lst[i]].push_back(i); 249 } 250 } 251 vector<int> need = k; 252 int cur_money = 0; 253 for (int i = 0; i <= day; ++i) { 254 ++cur_money; 255 if (i > 1000) continue; 256 for (auto it : off[i]) { 257 if (cur_money >= need[it]) { 258 cur_money -= need[it]; 259 need[it] = 0; 260 } else { 261 need[it] -= cur_money; 262 cur_money = 0; 263 break; 264 } 265 } 266 } 267 return accumulate(need.begin(), need.end(), 0) * 2 <= cur_money; 268 } 269 270 int main() { 271 #ifdef _DEBUG 272 freopen("input.txt", "r", stdin); 273 // freopen("output.txt", "w", stdout); 274 #endif 275 276 cin >> n >> m; 277 k = vector<int>(n); 278 for (int i = 0; i < n; ++i) { 279 cin >> k[i]; 280 } 281 for (int i = 0; i < m; ++i) { 282 cin >> q[i].first >> q[i].second; 283 --q[i].first; 284 --q[i].second; 285 } 286 287 for (int l = 0; l <= 2000; ++l) { 288 if (can(l)) { 289 cout << l + 1 << endl; 290 return 0; 291 } 292 } 293 294 assert(false); 295 296 return 0; 297 } 298 ``` 299 300 [1165F2 - Microtransactions (hard version)](/contest/1165/problem/F2 "Codeforces Round 560 (Div. 3)") 301 302 Idea: [BledDest](/profile/BledDest "Grandmaster BledDest") 303 304 **Tutorial** 305 306 Tutorial is loading... 307 308 **Solution** 309 310 ``` 311 #include <bits/stdc++.h> 312 313 using namespace std; 314 315 int n, m; 316 vector<int> k; 317 vector<pair<int, int>> q(200001); 318 319 bool can(int day) { 320 vector<int> lst(n, -1); 321 for (int i = 0; i < m; ++i) { 322 if (q[i].first <= day) { 323 lst[q[i].second] = max(lst[q[i].second], q[i].first); 324 } 325 } 326 vector<vector<int>> off(200001); 327 for (int i = 0; i < n; ++i) { 328 if (lst[i] != -1) { 329 off[lst[i]].push_back(i); 330 } 331 } 332 vector<int> need = k; 333 int cur_money = 0; 334 for (int i = 0; i <= day; ++i) { 335 ++cur_money; 336 if (i > 200000) continue; 337 for (auto it : off[i]) { 338 if (cur_money >= need[it]) { 339 cur_money -= need[it]; 340 need[it] = 0; 341 } else { 342 need[it] -= cur_money; 343 cur_money = 0; 344 break; 345 } 346 } 347 } 348 return accumulate(need.begin(), need.end(), 0) * 2 <= cur_money; 349 } 350 351 int main() { 352 #ifdef _DEBUG 353 freopen("input.txt", "r", stdin); 354 // freopen("output.txt", "w", stdout); 355 #endif 356 357 cin >> n >> m; 358 k = vector<int>(n); 359 for (int i = 0; i < n; ++i) { 360 cin >> k[i]; 361 } 362 for (int i = 0; i < m; ++i) { 363 cin >> q[i].first >> q[i].second; 364 --q[i].first; 365 --q[i].second; 366 } 367 368 int l = 0, r = 400000; 369 while (r - l > 1) { 370 int mid = (l + r) >> 1; 371 if (can(mid)) r = mid; 372 else l = mid; 373 } 374 375 for (int i = l; i <= r; ++i) { 376 if (can(i)) { 377 cout << i + 1 << endl; 378 return 0; 379 } 380 } 381 382 assert(false); 383 384 return 0; 385 } 386 ```