codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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 ```