codeforces-scrape

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

1333.md (6658B)


      1 Source: https://codeforces.com/blog/entry/75802
      2 
      3 I hope you liked problems!
      4 
      5 Sorry for incorrect placement of problems. I had to do swap(E, F).
      6 
      7 Tutorial is loading...
      8 
      9 **Solution C++**
     10 
     11 ```
     12 #include <bits/stdc++.h>
     13 
     14 using namespace std;
     15 
     16 void solve() {
     17     int n, m; cin >> n >> m;
     18     string black_row(m, 'B');
     19     vector<string> result(n, black_row);
     20     result[0][0] = 'W';
     21     for (int i = 0; i < n; ++i) {
     22         cout << result[i] << '\n';
     23     }
     24 }
     25 
     26 int main() {
     27     int t; cin >> t;
     28     while(t--) solve();
     29 }
     30 ```
     31 
     32 Tutorial is loading...
     33 
     34 **Solution C++**
     35 
     36 ```
     37 #include <bits/stdc++.h>
     38 
     39 using namespace std;
     40 
     41 void solve() {
     42     int n; cin >> n;
     43     vector<int> a(n), b(n);
     44     for (int i = 0; i < n; ++i) {
     45         cin >> a[i];
     46     }
     47     for (int i = 0; i < n; ++i) {
     48         cin >> b[i];
     49     }
     50     vector<int> good(2, 0);
     51     for (int i = 0; i < n; ++i) {
     52         if (a[i] > b[i] && !good[0]) {
     53             cout << "NO\n";
     54             return;
     55         } else if (a[i] < b[i] && !good[1]) {
     56             cout << "NO\n";
     57             return;
     58         }
     59         if (a[i] == -1) good[0] = 1;
     60         if (a[i] == 1) good[1] = 1;
     61     }
     62     cout << "YES\n";
     63 }
     64 
     65 int main() {
     66     int t; cin >> t;
     67     while(t--) {
     68         solve();
     69     }
     70 }
     71 ```
     72 
     73 Tutorial is loading...
     74 
     75 **Solution C++**
     76 
     77 ```
     78 #include <bits/stdc++.h>
     79 
     80 using namespace std;
     81 
     82 int main() {
     83     int n; cin >> n;
     84     vector<long long> prefix(n + 1, 0);
     85     for (int i = 0; i < n; ++i) {
     86         int x; cin >> x;
     87         prefix[i + 1] = prefix[i] + x;
     88     }
     89     int begin = 0, end = 0;
     90     long long ans = 0;
     91     set<long long> s = {0};
     92     while(begin < n) {
     93         while(end < n && !s.count(prefix[end + 1])) {
     94             ++end;
     95             s.insert(prefix[end]);
     96         }
     97         ans += end - begin;
     98         s.erase(prefix[begin]);
     99         ++begin;
    100     }
    101     cout << ans << endl;
    102 }
    103 ```
    104 
    105 Tutorial is loading...
    106 
    107 **Solution C++**
    108 
    109 ```
    110 #include <bits/stdc++.h>
    111 
    112 using namespace std;
    113 
    114 int n, k;
    115 
    116 vector<int> find_steps(const vector<int>& a) {
    117     vector<int> steps;
    118     for (int i = 0; i < n - 1; ++i) {
    119         if (a[i] == 1 && a[i + 1] == 0) steps.push_back(i);
    120     }
    121     return steps;
    122 }
    123 
    124 int main() {
    125     cin >> n >> k;
    126     string s; cin >> s;
    127     vector<int> a(n);
    128     for (int i = 0; i < n; ++i) a[i] = (s[i] == 'L') ? 0 : 1;
    129     int maxi = 0, mini = 0;
    130     int cnt = 0;
    131     int last = -1;
    132     for (int i = n - 1; i >= 0; --i) {
    133         if (a[i] == 0) {
    134             ++cnt;
    135         } else {
    136             if (cnt == 0) continue;
    137             maxi += cnt;
    138             mini = max(cnt, last + 1);
    139             last = mini;
    140         }
    141     }
    142     if (k < mini || k > maxi) {
    143         cout << -1;
    144         return 0;
    145     }
    146     bool is_min = false;
    147     vector<int> have_step;
    148     for (int i = 0; i < k; ++i) {
    149         if (!is_min) {
    150             auto steps = find_steps(a);
    151             cout << min(int(steps.size()), maxi - k + i + 1) << ' ';
    152             int cur = 0;
    153             while (k - i - 1 < maxi && cur < steps.size()) {
    154                 cout << steps[cur] + 1 << ' ';
    155                 a[steps[cur]] = 0;
    156                 a[steps[cur] + 1] = 1;
    157                 ++cur;
    158                 --maxi;
    159             }
    160             if (maxi == k - i - 1) {
    161                 is_min = true;
    162                 have_step = find_steps(a);
    163             }
    164         } else {
    165             int v = have_step.back();
    166             have_step.pop_back();
    167             cout << "1 " << v + 1;
    168             a[v] = 0;
    169             a[v + 1] = 1;
    170             if (v > 0 && a[v - 1] == 1) {
    171                 have_step.push_back(v - 1);
    172             }
    173             if (v + 2 < n && a[v + 2] == 0) {
    174                 have_step.push_back(v + 1);
    175             }
    176         }
    177         cout << '\n';
    178     }
    179 }
    180 ```
    181 
    182 Tutorial is loading...
    183 
    184 **Solution C++**
    185 
    186 ```
    187 #include <bits/stdc++.h>
    188 
    189 using namespace std;
    190 
    191 int main() {
    192     int n; cin >> n;
    193     if (n < 3) {
    194         cout << -1;
    195         return 0;
    196     }
    197     vector<int> solution = {
    198         1, 3, 4, 8, 2, 7, 9, 5, 6
    199     };
    200     vector<vector<int>> table(n, vector<int>(n, 0));
    201     int cur = 1;
    202     for (int i = 0; i < n - 3; ++i) {
    203         if (i & 1) {
    204             for (int j = n - 1; j >= 0; --j) {
    205                 table[i][j] = cur;
    206                 ++cur;
    207             }
    208         } else {
    209             for (int j = 0; j < n; ++j) {
    210                 table[i][j] = cur;
    211                 ++cur;
    212             }
    213         }
    214     }
    215     if ((n - 3) & 1) {
    216         for (int j = n - 1; j >= 0; --j) {
    217             if (j & 1) {
    218                 for (int i = n - 3; i < n; ++i) {
    219                     if (j > 2) {
    220                         table[i][j] = cur;
    221                         ++cur;
    222                     } else {
    223                         table[i][j] = solution[(2 - j) * 3 + i - n + 3] + n * n - 9;
    224                     }
    225                 }
    226             } else {
    227                 for (int i = n - 1; i >= n - 3; --i) {
    228                     if (j > 2) {
    229                         table[i][j] = cur;
    230                         ++cur;
    231                     } else {
    232                         table[i][j] = solution[(2 - j) * 3 + n - 1 - i] + n * n - 9;
    233                     }
    234                 }
    235             }
    236         }
    237     } else {
    238         for (int j = 0; j < n; ++j) {
    239             if (j & 1) {
    240                 for (int i = n - 1; i >= n - 3; --i) {
    241                     if (j < n - 3) {
    242                         table[i][j] = cur;
    243                         ++cur;
    244                     } else {
    245                         table[i][j] = solution[(j - n + 3) * 3 + n - 1 - i] + n * n - 9;
    246                     }
    247                 }
    248             } else {
    249                 for (int i = n - 3; i < n; ++i) {
    250                     if (j < n - 3) {
    251                         table[i][j] = cur;
    252                         ++cur;
    253                     } else {
    254                         table[i][j] = solution[(j - n + 3) * 3 + i - n + 3] + n * n - 9;
    255                     }
    256                 }
    257             }
    258         }
    259     }
    260     for (int i = 0; i < n; ++i) {
    261         for (int j = 0; j < n; ++j) {
    262             cout << table[i][j] << ' ';
    263         }
    264         cout << '\n';
    265     }
    266 }
    267 ```
    268 
    269 Tutorial is loading...
    270 
    271 **Solution C++**
    272 
    273 ```
    274 #include <bits/stdc++.h>
    275 
    276 using namespace std;
    277 
    278 vector<int> max_div;
    279 
    280 void eratosthenes(int limit) {
    281     max_div.assign(limit + 1, 0);
    282     max_div[0] = limit + 10;
    283     max_div[1] = 1;
    284     for (int i = 2; i <= limit; ++i) {
    285         if (max_div[i]) continue;
    286         for (int j = i; j <= limit; j += i) {
    287             if (max_div[j]) continue;
    288             max_div[j] = j / i;
    289         }
    290     }
    291 }
    292 
    293 int main() {
    294     int n; cin >> n;
    295     eratosthenes(n);
    296     sort(max_div.begin(), max_div.end());
    297     for (int i = 1; i < n; ++i) {
    298         cout << max_div[i] << ' ';
    299     }
    300 }
    301 ```