2091.md (6238B)
1 Source: https://codeforces.com/blog/entry/141047 2 3 And here is the Editorial! 4 5 We hope you liked the problems. Thanks everyone! 6 7 **\[^-^]/** 8 9 Don't forget to praise the sun! 10 11 [2091A - Olympiad Date](/contest/2091/problem/A "Codeforces Round 1013 (Div. 3)") 12 13 **Tutorial** 14 15 Tutorial is loading... 16 17 **Solution** 18 19 ``` 20 #include <iostream> 21 22 using namespace std; 23 24 void solve() { 25 int n; 26 cin >> n; 27 int cnt[10] = {}; 28 bool f = 0; 29 30 for (int i = 0; i < n; i++) { 31 int dig; 32 cin >> dig; 33 cnt[dig]++; 34 if (cnt[0] >= 3 && cnt[1] >= 1 && cnt[2] >= 2 && 35 cnt[3] >= 1 && cnt[5] >= 1 && !f) { 36 cout << i + 1 << endl; 37 f = 1; 38 } 39 } 40 if (!f) cout << 0 << endl; 41 } 42 43 int main() { 44 int t; 45 cin >> t; 46 while (t--) { 47 solve(); 48 } 49 } 50 ``` 51 52 [2091B - Team Training](/contest/2091/problem/B "Codeforces Round 1013 (Div. 3)") 53 54 **Tutorial** 55 56 Tutorial is loading... 57 58 **Solution** 59 60 ``` 61 #include <iostream> 62 #include <algorithm> 63 64 using namespace std; 65 66 void solve() { 67 int n, x; 68 cin >> n >> x; 69 int a[n]; 70 for (int i = 0; i < n; i++) { 71 cin >> a[i]; 72 } 73 sort(a, a + n); 74 reverse(a, a + n); 75 76 int ans = 0; 77 for (int i = 0, cnt = 1; i < n; i++, cnt++) { 78 if (a[i] * cnt >= x) { 79 ans++; 80 cnt = 0; 81 } 82 } 83 cout << ans << endl; 84 } 85 86 int main() { 87 int t; 88 cin >> t; 89 while (t--) { 90 solve(); 91 } 92 } 93 ``` 94 95 [2091C - Combination Lock](/contest/2091/problem/C "Codeforces Round 1013 (Div. 3)") 96 97 **Tutorial** 98 99 Tutorial is loading... 100 101 **Solution** 102 103 ``` 104 #include <iostream> 105 106 using namespace std; 107 108 void solve() { 109 int n; 110 cin >> n; 111 if (n % 2 == 0) { 112 cout << -1 << endl; 113 return; 114 } 115 for (int i = n; i > 0; i--) { 116 cout << i << ' '; 117 } 118 cout << endl; 119 } 120 121 int main() { 122 int t = 1; 123 cin >> t; 124 while (t--) 125 solve(); 126 } 127 ``` 128 129 [2091D - Place of the Olympiad](/contest/2091/problem/D "Codeforces Round 1013 (Div. 3)") 130 131 **Tutorial** 132 133 Tutorial is loading... 134 135 **Solution** 136 137 ``` 138 #include <iostream> 139 140 using namespace std; 141 142 void solve() { 143 long long n, m, k, l, r, mid; 144 cin >> n >> m >> k; 145 l = 0, r = m; 146 147 while (l + 1 < r) { 148 mid = (l + r) / 2; 149 if ((m / (mid + 1) * mid + m % (mid + 1)) * n >= k) { 150 r = mid; 151 } else { 152 l = mid; 153 } 154 } 155 156 cout << r << endl; 157 } 158 159 int main() { 160 int t = 1; 161 cin >> t; 162 while (t--) { 163 solve(); 164 } 165 166 } 167 ``` 168 169 [2091E - Interesting Ratio](/contest/2091/problem/E "Codeforces Round 1013 (Div. 3)") 170 171 **Tutorial** 172 173 Tutorial is loading... 174 175 **Solution** 176 177 ``` 178 #include <iostream> 179 180 using namespace std; 181 182 const int MAXN = 10000001; 183 bool prime[MAXN]; 184 185 void solve() { 186 int n, ans = 0; 187 cin >> n; 188 189 for (int i = 2; i <= n; i++) { 190 if (prime[i]) { 191 ans += n / i; 192 } 193 } 194 195 cout << ans << endl; 196 } 197 198 int main() { 199 for (int i = 0; i < MAXN; i++) prime[i] = 1; 200 prime[0] = prime[1] = 0; 201 for (int i = 2; i * i < MAXN; i++) { 202 if (!prime[i]) continue; 203 for (int j = i * i; j < MAXN; j += i) 204 prime[j] = 0; 205 } 206 207 int t; 208 cin >> t; 209 while (t--) { 210 solve(); 211 } 212 } 213 ``` 214 215 [2091F - Igor and Mountain](/contest/2091/problem/F "Codeforces Round 1013 (Div. 3)") 216 217 **Tutorial** 218 219 Tutorial is loading... 220 221 **Solution** 222 223 ``` 224 #include <iostream> 225 226 using namespace std; 227 228 const int MAXN = 2010; 229 const int MOD = 998244353; 230 231 string s[MAXN]; 232 int dp[MAXN][MAXN][2]; 233 long long sdp[MAXN][MAXN][2]; 234 235 int n, m, d; 236 237 long long getsum(int x, int y1, int y2, int f) { 238 long long res = sdp[x][y2][f]; 239 if (y1) res -= sdp[x][y1 - 1][f]; 240 return res; 241 } 242 243 int get(int i, int j, int f) { 244 if (s[i][j] != 'X') return 0; 245 long long res = 0; 246 if (i == n - 1) res++; 247 248 if (!f) { 249 res += getsum(i, max(0, j - d), 250 min(m - 1, j + d), 1); 251 res -= dp[i][j][1]; 252 } 253 254 if (i < n - 1) { 255 res += getsum(i + 1, max(0, j - d + 1), 256 min(m - 1, j + d - 1), 0); 257 } 258 259 return res % MOD; 260 } 261 262 void solve() { 263 264 cin >> n >> m >> d; 265 for (int i = 0; i < n; i++) { 266 cin >> s[i]; 267 } 268 for (int i = n - 1; i >= 0; i--) { 269 for (int f = 1; f >= 0; f--) { 270 for (int j = 0; j < m; j++) { 271 sdp[i][j][f] = dp[i][j][f] = get(i, j, f); 272 } 273 for (int j = 1; j < m; j++) { 274 sdp[i][j][f] += sdp[i][j - 1][f]; 275 } 276 } 277 } 278 279 long long ans = 0; 280 for (int j = 0; j < m; j++) { 281 ans += dp[0][j][0]; 282 } 283 284 cout << ans % MOD << endl; 285 286 } 287 288 int main() { 289 int t; 290 cin >> t; 291 while (t--) { 292 solve(); 293 } 294 } 295 ``` 296 297 [2091G - Gleb and Boating](/contest/2091/problem/G "Codeforces Round 1013 (Div. 3)") 298 299 **Tutorial** 300 301 Tutorial is loading... 302 303 **Solution** 304 305 ``` 306 #include <iostream> 307 #include <vector> 308 309 using namespace std; 310 311 int s, k, p; 312 vector<bool> was1, was2; 313 314 void bfs() { 315 vector<int> v; 316 for (int i = 0; i < s; i++) { 317 if (was1[i]) 318 v.push_back(i); 319 } 320 321 int q = 0; 322 while (q < v.size()) { 323 int x = v[q++]; 324 int y = x + p * k; 325 if (y >= 0 && y <= s && !was1[y]) { 326 was1[y] = 1; 327 v.push_back(y); 328 } 329 } 330 } 331 332 void solve() { 333 cin >> s >> k; 334 if (s % k == 0) { 335 cout << k << endl; 336 return; 337 } 338 if (s > k * k) { 339 cout << max(1, k - 2) << endl; 340 return; 341 } 342 343 was1.resize(s + 1); 344 was2.resize(s + 1); 345 for (int i = 0; i <= s; i++) { 346 was1[i] = was2[i] = 0; 347 } 348 349 p = 1; 350 was1[k] = 1; 351 while (1) { 352 bfs(); 353 if (was1[s]) { 354 cout << k << endl; 355 return; 356 } 357 k = max(k - 1, 1); 358 p *= -1; 359 for (int i = 0; i <= s; i++) { 360 was2[i] = 0; 361 } 362 for (int i = 0; i < s; i++) { 363 if (was1[i]) { 364 if (i + p * k >= 0 && i + p * k <= s) { 365 was2[i + p * k] = 1; 366 } 367 } 368 } 369 swap(was1, was2); 370 } 371 372 } 373 374 int main() { 375 int t; 376 cin >> t; 377 while (t--) { 378 solve(); 379 } 380 } 381 ```