1475.md (6716B)
1 Source: https://codeforces.com/blog/entry/87188 2 3 [1475A - Odd Divisor](/contest/1475/problem/A "Codeforces Round 697 (Div. 3)") 4 5 Problem authors: [Stepavly](/profile/Stepavly "Master Stepavly"), [Supermagzzz](/profile/Supermagzzz "Master Supermagzzz") 6 7 **Editorial** 8 9 Tutorial is loading... 10 11 **Solution** 12 13 ``` 14 #include <bits/stdc++.h> 15 16 using namespace std; 17 using ll = long long; 18 using ld = long double; 19 20 void solve() { 21 ll n; 22 cin >> n; 23 if (n & (n - 1)) { 24 cout << "YES\n"; 25 } else { 26 cout << "NO\n"; 27 } 28 } 29 30 int main() { 31 int t; 32 cin >> t; 33 while (t--) { 34 solve(); 35 } 36 } 37 ``` 38 39 [1475B - New Year's Number](/contest/1475/problem/B "Codeforces Round 697 (Div. 3)") 40 41 Problem author: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 42 43 **Editorial** 44 45 Tutorial is loading... 46 47 **Solution** 48 49 ``` 50 #include <bits/stdc++.h> 51 52 #include <utility> 53 using namespace std; 54 55 using pii = pair<int, int>; 56 57 int main() { 58 int test; 59 cin >> test; 60 while (test-- > 0) { 61 int n; 62 cin >> n; 63 int cnt2021 = n % 2020; 64 int cnt2020 = (n - cnt2021) / 2020 - cnt2021; 65 if (cnt2020 >= 0 && 2020 * cnt2020 + 2021 * cnt2021 == n) { 66 cout << "YES\n"; 67 } else { 68 cout << "NO\n"; 69 } 70 } 71 return 0; 72 } 73 ``` 74 75 [1475C - Ball in Berland](/contest/1475/problem/C "Codeforces Round 697 (Div. 3)") 76 77 Problem authors: [Stepavly](/profile/Stepavly "Master Stepavly"), [Supermagzzz](/profile/Supermagzzz "Master Supermagzzz") 78 79 **Editorial** 80 81 Tutorial is loading... 82 83 **Solution** 84 85 ``` 86 #include <bits/stdc++.h> 87 88 using namespace std; 89 using ll = long long; 90 using ld = long double; 91 92 void solve() { 93 int A, B, k; 94 cin >> A >> B >> k; 95 vector<int> a(A), b(B); 96 vector<pair<int, int>> edges(k); 97 for (auto &[x, y] : edges) { 98 cin >> x; 99 } 100 for (auto &[x, y] : edges) { 101 cin >> y; 102 } 103 for (auto &[x, y] : edges) { 104 x--; 105 y--; 106 a[x]++; 107 b[y]++; 108 } 109 ll ans = 0; 110 for (auto &[x, y] : edges) { 111 ans += k - a[x] - b[y] + 1; 112 } 113 cout << ans / 2 << "\n"; 114 } 115 116 int main() { 117 int t; 118 cin >> t; 119 while (t--) { 120 solve(); 121 } 122 } 123 ``` 124 125 [1475D - Cleaning the Phone](/contest/1475/problem/D "Codeforces Round 697 (Div. 3)") 126 127 Problem authors: [Stepavly](/profile/Stepavly "Master Stepavly"), [Supermagzzz](/profile/Supermagzzz "Master Supermagzzz") 128 129 **Editorial** 130 131 Tutorial is loading... 132 133 **Solution** 134 135 ``` 136 #include <bits/stdc++.h> 137 138 using namespace std; 139 using ll = long long; 140 using ld = long double; 141 142 void solve() { 143 int n, m; 144 cin >> n >> m; 145 vector<int> a, b; 146 vector<int> v(n); 147 for (int &e : v) { 148 cin >> e; 149 } 150 for (int &e : v) { 151 int x; 152 cin >> x; 153 if (x == 1) { 154 a.push_back(e); 155 } else { 156 b.push_back(e); 157 } 158 } 159 sort(a.rbegin(), a.rend()); 160 sort(b.rbegin(), b.rend()); 161 ll curSumA = 0; 162 int r = (int)b.size(); 163 ll curSumB = accumulate(b.begin(), b.end(), 0ll); 164 int ans = INT_MAX; 165 for (int l = 0; l <= a.size(); l++) { 166 while (r > 0 && curSumA + curSumB - b[r - 1] >= m) { 167 r--; 168 curSumB -= b[r]; 169 } 170 if (curSumB + curSumA >= m) { 171 ans = min(ans, 2 * r + l); 172 } 173 if (l != a.size()) { 174 curSumA += a[l]; 175 } 176 } 177 cout << (ans == INT_MAX ? -1 : ans) << "\n"; 178 } 179 180 int main() { 181 int t; 182 cin >> t; 183 while (t--) { 184 solve(); 185 } 186 } 187 ``` 188 189 [1475E - Advertising Agency](/contest/1475/problem/E "Codeforces Round 697 (Div. 3)") 190 191 Problem authors: [Stepavly](/profile/Stepavly "Master Stepavly"), [Supermagzzz](/profile/Supermagzzz "Master Supermagzzz") 192 193 **Editorial** 194 195 Tutorial is loading... 196 197 **Solution** 198 199 ``` 200 #include <bits/stdc++.h> 201 202 using namespace std; 203 using ll = long long; 204 using ld = long double; 205 206 int mod = 1e9 + 7; 207 208 int fast_pow(int a, int p) { 209 int res = 1; 210 while (p) { 211 if (p % 2 == 0) { 212 a = a * 1ll * a % mod; 213 p /= 2; 214 } else { 215 res = res * 1ll * a % mod; 216 p--; 217 } 218 } 219 return res; 220 } 221 222 int fact(int n) { 223 int res = 1; 224 for (int i = 1; i <= n; i++) { 225 res = res * 1ll * i % mod; 226 } 227 return res; 228 } 229 230 int C(int n, int k) { 231 return fact(n) * 1ll * fast_pow(fact(k), mod - 2) % mod * 1ll * fast_pow(fact(n - k), mod - 2) % mod; 232 } 233 234 void solve() { 235 int n, k; 236 cin >> n >> k; 237 vector<int> cnt(n + 1); 238 for (int i = 0; i < n; i++) { 239 int x; 240 cin >> x; 241 cnt[x]++; 242 } 243 for (int i = n; i >= 0; i--) { 244 if (cnt[i] >= k) { 245 cout << C(cnt[i], k) << "\n"; 246 return; 247 } else { 248 k -= cnt[i]; 249 } 250 } 251 cout << 1; 252 } 253 254 int main() { 255 int t; 256 cin >> t; 257 while (t--) { 258 solve(); 259 } 260 } 261 ``` 262 263 [1475F - Unusual Matrix](/contest/1475/problem/F "Codeforces Round 697 (Div. 3)") 264 265 Problem authors: [Stepavly](/profile/Stepavly "Master Stepavly"), [Supermagzzz](/profile/Supermagzzz "Master Supermagzzz") 266 267 **Editorial** 268 269 Tutorial is loading... 270 271 **Solution** 272 273 ``` 274 #include <bits/stdc++.h> 275 using namespace std; 276 277 using pii = pair<int, int>; 278 279 bool check(vector<vector<int>> a, vector<vector<int>> const &b) { 280 int n = (int) a.size(); 281 for (int j = 0; j < n; j++) { 282 if (a[0][j] != b[0][j]) { 283 for (int i = 0; i < n; i++) { 284 a[i][j] ^= 1; 285 } 286 } 287 } 288 for (int i = 0; i < n; i++) { 289 int need_xor = (a[i][0] ^ b[i][0]); 290 for (int j = 1; j < n; j++) { 291 if (need_xor != (a[i][j] ^ b[i][j])) { 292 return false; 293 } 294 } 295 } 296 return true; 297 } 298 299 void solve() { 300 int n; 301 cin >> n; 302 vector<vector<int>> a(n, vector<int>(n)); 303 vector<vector<int>> b(n, vector<int>(n)); 304 for (int i = 0; i < n; i++) { 305 string s; 306 cin >> s; 307 for (int j = 0; j < n; j++) { 308 a[i][j] = s[j] - '0'; 309 } 310 } 311 for (int i = 0; i < n; i++) { 312 string s; 313 cin >> s; 314 for (int j = 0; j < n; j++) { 315 b[i][j] = s[j] - '0'; 316 } 317 } 318 319 for (int times = 0; times < 2; times++) { 320 if (check(a, b)) { 321 cout << "YES\n"; 322 return; 323 } 324 for (int j = 0; j < n; j++) { 325 a[0][j] ^= 1; 326 } 327 } 328 cout << "NO\n"; 329 } 330 331 int main() { 332 int test; 333 cin >> test; 334 while (test-- > 0) { 335 solve(); 336 } 337 return 0; 338 } 339 ``` 340 341 [1475G - Strange Beauty](/contest/1475/problem/G "Codeforces Round 697 (Div. 3)") 342 343 Problem author: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 344 345 **Editorial** 346 347 Tutorial is loading... 348 349 **Solution** 350 351 ``` 352 #include <bits/stdc++.h> 353 using namespace std; 354 355 const int N = (int) 2e5 + 100; 356 357 int dp[N]; 358 int cnt[N]; 359 360 void solve() { 361 int n; 362 cin >> n; 363 fill(dp, dp + N, 0); 364 fill(cnt, cnt + N, 0); 365 for (int i = 0; i < n; i++) { 366 int x; 367 cin >> x; 368 cnt[x]++; 369 } 370 for (int i = 1; i < N; i++) { 371 dp[i] += cnt[i]; 372 for (int j = 2 * i; j < N; j += i) { 373 dp[j] = max(dp[j], dp[i]); 374 } 375 } 376 cout << (n - *max_element(dp, dp + N)) << endl; 377 } 378 379 int main() { 380 int test; 381 cin >> test; 382 while (test-- > 0) { 383 solve(); 384 } 385 return 0; 386 } 387 ```