codeforces-scrape

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

1838.md (5734B)


      1 Source: https://codeforces.com/blog/entry/116995
      2 
      3 [1838A - Blackboard List](/contest/1838/problem/A "Codeforces Round 877 (Div. 2)")
      4 
      5 **Solution**
      6 
      7 Tutorial is loading...
      8 
      9 **Code**
     10 
     11 ```
     12 #include <bits/stdc++.h>
     13 using namespace std;
     14 
     15 int main() {
     16 
     17     int t; cin >> t;
     18     for(int tc = 1; tc <= t; ++tc) {
     19 
     20         int n; cin >> n;
     21         int mn = INT_MAX, mx = INT_MIN;
     22 
     23         for(int i = 0; i < n; ++i) {
     24             int x; cin >> x;
     25             mn = min(mn, x);
     26             mx = max(mx, x);
     27         }
     28 
     29         if(mn < 0) cout << mn << '\n';
     30         else cout << mx << '\n';
     31     }
     32 }
     33 ```
     34 
     35 [1838B - Minimize Permutation Subarrays](/contest/1838/problem/B "Codeforces Round 877 (Div. 2)")
     36 
     37 **Solution**
     38 
     39 Tutorial is loading...
     40 
     41 **Code**
     42 
     43 ```
     44 #include <bits/stdc++.h>
     45 using namespace std;
     46 #define N 200010
     47 
     48 int idx[N];
     49 
     50 int main() {
     51 
     52     int t; cin >> t;
     53     for(int tc = 1; tc <= t; ++tc) {
     54 
     55         int n; cin >> n;
     56 
     57         for(int i = 1; i <= n; ++i) {
     58             int x; cin >> x;
     59             idx[x] = i;
     60         }
     61 
     62         if(idx[n] < min(idx[1], idx[2])) {
     63             cout << idx[n] << ' ' << min(idx[1], idx[2]) << '\n';
     64         } else if(idx[n] > max(idx[1], idx[2])) {
     65             cout << idx[n] << ' ' << max(idx[1], idx[2]) << '\n';
     66         } else {
     67             cout << idx[1] << ' ' << idx[2] << '\n';
     68         }
     69     }
     70 }
     71 ```
     72 
     73 [1838C - No Prime Differences](/contest/1838/problem/C "Codeforces Round 877 (Div. 2)")
     74 
     75 **Solution**
     76 
     77 Tutorial is loading...
     78 
     79 **Code**
     80 
     81 ```
     82 #include <bits/stdc++.h>
     83 using namespace std;
     84 
     85 int main() {
     86 
     87     int t; cin >> t;
     88     for(int tc = 1; tc <= t; ++tc) {
     89 
     90         int n, m; cin >> n >> m;
     91 
     92         for(int i = 0; i < n; ++i) {
     93             for(int j = 0; j < m; ++j) {
     94                 if(i % 2 == 0) cout << (n / 2 + i / 2) * m + j + 1 << ' ';
     95                 else cout << (i / 2) * m + j + 1 << ' ';
     96             }
     97             cout << '\n';
     98         }
     99     }
    100 }
    101 ```
    102 
    103 [1838D - Bracket Walk](/contest/1838/problem/D "Codeforces Round 877 (Div. 2)")
    104 
    105 **Solution**
    106 
    107 Tutorial is loading...
    108 
    109 **Code**
    110 
    111 ```
    112 #include <bits/stdc++.h>
    113 using namespace std;
    114 
    115 int main() {
    116 
    117     int n, q; string s;
    118     cin >> n >> q >> s;
    119 
    120     set<int> a;
    121 
    122     for(int i = 1; i <= n; ++i)
    123         if((i % 2) != (s[i - 1] == '('))
    124             a.insert(i);
    125 
    126     while(q--) {
    127         int i; cin >> i;
    128 
    129         if(a.count(i)) a.erase(i);
    130         else a.insert(i);
    131 
    132         if(n % 2) cout << "NO\n";
    133         else if(a.size() && (*a.begin() % 2 || !(*a.rbegin() % 2))) cout << "NO\n";
    134         else cout << "YES\n";
    135     }
    136 }
    137 ```
    138 
    139 [1838E - Count Supersequences](/contest/1838/problem/E "Codeforces Round 877 (Div. 2)")
    140 
    141 **Solution**
    142 
    143 Tutorial is loading...
    144 
    145 **Code**
    146 
    147 ```
    148 #include <bits/stdc++.h>
    149 using namespace std;
    150 
    151 typedef long long int ll;
    152 
    153 ll M = 1000000007;
    154 
    155 ll pw(ll a, ll p) { return p ? pw(a * a % M, p / 2) * (p & 1 ? a : 1) % M : 1; }
    156 
    157 ll inv(ll a) { return pw(a, M - 2); }
    158 
    159 int main() {
    160 
    161     ll t; cin >> t;
    162     for(ll tc = 1; tc <= t; ++tc) {
    163 
    164         ll n, m, k, ai;
    165         cin >> n >> m >> k;
    166         for(ll i = 0; i < n; ++i) cin >> ai;
    167 
    168         ll ans = pw(k, m), mCi = 1;
    169 
    170         for(ll i = 0; i < n; ++i) {
    171             ans = (ans + M - mCi * pw(k - 1, m - i) % M) % M;
    172             mCi = mCi * (m - i) % M * inv(i + 1) % M;
    173         }
    174 
    175         cout << ans << '\n';
    176     }
    177 }
    178 ```
    179 
    180 [1838F - Stuck Conveyor](/contest/1838/problem/F "Codeforces Round 877 (Div. 2)")
    181 
    182 **Solution**
    183 
    184 Tutorial is loading...
    185 
    186 **Code**
    187 
    188 ```
    189 #include <bits/stdc++.h>
    190 using namespace std;
    191 
    192 char grid[110][110];
    193 int n;
    194 vector<pair<int, int>> snake;
    195 map<pair<int, int>, char> getChar = {
    196     {{1, 0}, 'v'},
    197     {{-1, 0}, '^'},
    198     {{0, 1}, '>'},
    199     {{0, -1}, '<'}
    200 };
    201 
    202 pair<pair<int, int>, char> getBeltAndDir(pair<int, int> p) {
    203     if(p.first == -1) return {p, 'X'};
    204     pair<int, int> q = p;
    205 
    206     if(p.first == 0) q.first++;
    207     if(p.second == 0) q.second++;
    208     if(p.first > n) q.first--;
    209     if(p.second > n) q.second--;
    210 
    211     return {q, getChar[{p.first - q.first, p.second - q.second}]};
    212 }
    213 
    214 pair<pair<int, int>, char> query(int idx) {
    215 
    216     cout << "? " << snake[idx].first << ' ' << snake[idx].second << endl;
    217 
    218     for(int i = 1; i <= n; ++i) {
    219         for(int j = 1; j <= n; ++j)
    220             cout << grid[i][j];
    221         cout << endl;
    222     }
    223 
    224     int i, j; cin >> i >> j;
    225 
    226     return getBeltAndDir({i, j});
    227 }
    228 
    229 void fillGrid() {
    230     for(int i = 0; i < n * n; ++i) {
    231         int dx = snake[i + 1].first - snake[i].first;
    232         int dy = snake[i + 1].second - snake[i].second;
    233 
    234         grid[snake[i].first][snake[i].second] = getChar[{dx, dy}];
    235     }
    236 }
    237 
    238 int main() {
    239     cin >> n;
    240 
    241     for(int i = 1; i <= n; ++i)
    242         if(i % 2 == 0)
    243             for(int j = n; j >= 1; --j)
    244                 snake.emplace_back(i, j);
    245         else
    246             for(int j = 1; j <= n; ++j)
    247                 snake.emplace_back(i, j);
    248 
    249     snake.emplace_back(n + 1, (n % 2 ? n : 1));
    250     fillGrid();
    251 
    252     auto ans = query(0);
    253 
    254     if(ans.second != 'X') {
    255 
    256         snake.pop_back();
    257         reverse(snake.begin(), snake.end());
    258         snake.emplace_back(0, 1);
    259         fillGrid();
    260 
    261         ans = query(0);
    262     }
    263 
    264     if(ans.second == 'X') {
    265 
    266         int id = 0;
    267         for(int j = 13; j >= 0; --j)
    268             if(id + (1 << j) < n * n && query(id + (1 << j)).second == 'X')
    269                 id += (1 << j);
    270 
    271         ans.first = snake[id];
    272 
    273         for(int i = 1; i <= n; ++i)
    274             for(int j = 1; j <= n; ++j)
    275                 if(i < ans.first.first) grid[i][j] = '^';
    276                 else if(i > ans.first.first) grid[i][j] = 'v';
    277                 else grid[i][j] = j < ans.first.second ? '<' : '>';
    278             
    279         ans.second = query(id).second;
    280     }
    281 
    282     cout << "! " << ans.first.first << ' ' << ans.first.second << ' ' << ans.second << endl;
    283 }
    284 ```