codeforces-scrape

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

2170.md (8742B)


      1 Source: https://codeforces.com/blog/entry/148798
      2 
      3 [2170A - Maximum Neighborhood](/contest/2170/problem/A "Educational Codeforces Round 185 (Rated for Div. 2)")
      4 
      5 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
      6 
      7 **Tutorial**
      8 
      9 Tutorial is loading...
     10 
     11 **Solution 1 (Neon)**
     12 
     13 ```
     14 #include <bits/stdc++.h>
     15  
     16 using namespace std;
     17  
     18 int dx[] = {-1, 0, 1, 0};
     19 int dy[] = {0, -1, 0, 1};
     20  
     21 int main() {
     22     int t;
     23     cin >> t;
     24     while (t--) {
     25         int n;
     26         cin >> n;
     27         auto get = [&](int x, int y) {
     28             if (x >= 0 && x < n && y >= 0 && y < n) return x * n + y + 1;
     29             return 0;
     30         };
     31         int ans = 0;
     32         for (int i = 0; i < n; ++i) {
     33             for (int j = 0; j < n; ++j) {
     34                 int cur = get(i, j);
     35                 for (int d = 0; d < 4; ++d) cur += get(i + dx[d], j + dy[d]);
     36                 ans = max(ans, cur);
     37             }
     38         }
     39         cout << ans << '\n';
     40     }
     41 }
     42 ```
     43 
     44 **Solution 2 (Neon)**
     45 
     46 ```
     47 #include <bits/stdc++.h>
     48  
     49 using namespace std;
     50  
     51 int main() {
     52   int t;
     53   cin >> t;
     54   while (t--) {
     55     int n;
     56     cin >> n;
     57     int ans = 1;
     58     if (n == 2) ans = 9;
     59     else if (n == 3 || n == 4) ans = 4 * n * n - n - 4;
     60     else if (n > 4) ans = 5 * n * n - 5 * n - 5;
     61     cout << ans << '\n';
     62   }
     63 }
     64 ```
     65 
     66 [2170B - Addition on a Segment](/contest/2170/problem/B "Educational Codeforces Round 185 (Rated for Div. 2)")
     67 
     68 Idea: [FelixArg](/profile/FelixArg "Master FelixArg")
     69 
     70 **Tutorial**
     71 
     72 Tutorial is loading...
     73 
     74 **Solution (FelixArg)**
     75 
     76 ```
     77 #include<bits/stdc++.h>
     78 using namespace std;
     79  
     80 #define int long long
     81  
     82 void solve(){
     83     int n;
     84     cin >> n;
     85     vector<int> a(n);
     86     for (int i = 0; i < n; i++){
     87         cin >> a[i];
     88     }
     89  
     90     int sum = 0;
     91     int cnt_one = 0;
     92  
     93     for (int i = 0; i < n; i++){
     94         if (a[i] > 0){
     95             cnt_one++;
     96         }
     97         sum += a[i];
     98     }
     99  
    100     int sum2 = sum - cnt_one;
    101     int sub = n - 1 - sum2;
    102  
    103     cout << cnt_one - max(0ll, sub) << '\n';
    104 }
    105  
    106 signed main()
    107 {
    108 #ifdef FELIX
    109     auto _clock_start = chrono::high_resolution_clock::now();
    110 #endif
    111     ios_base::sync_with_stdio(false);
    112     cin.tie(0);
    113     cout.tie(0);
    114  
    115     int t = 1;
    116     cin >> t;
    117     while(t--){
    118         solve();
    119     }
    120  
    121 #ifdef FELIX
    122     cerr << "Executed in " << chrono::duration_cast<chrono::milliseconds>(
    123         chrono::high_resolution_clock::now()
    124             - _clock_start).count() << "ms." << endl;
    125 #endif
    126     return 0;
    127 }
    128 ```
    129 
    130 [2170C - Quotient and Remainder](/contest/2170/problem/C "Educational Codeforces Round 185 (Rated for Div. 2)")
    131 
    132 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    133 
    134 **Tutorial**
    135 
    136 Tutorial is loading...
    137 
    138 **Solution (adedalic)**
    139 
    140 ```
    141 #include<bits/stdc++.h>
    142  
    143 using namespace std;
    144  
    145 #define fore(i, l, r) for(int i = int(l); i < int(r); i++)
    146 #define sz(a) int((a).size())
    147  
    148 typedef long long li;
    149  
    150 template<class A> ostream& operator <<(ostream& out, const vector<A> &v) {
    151     fore(i, 0, sz(v)) {
    152         if(i) out << " ";
    153         out << v[i];
    154     }
    155     return out;
    156 }
    157  
    158 const int INF = int(1e9);
    159 const li INF64 = li(1e18);
    160  
    161 inline void solve() {
    162     int n; li k;
    163     cin >> n >> k;
    164     vector<int> q(n), r(n);
    165     fore (i, 0, n)
    166         cin >> q[i];
    167     fore (i, 0, n)
    168         cin >> r[i];
    169     
    170     sort(q.begin(), q.end());
    171     sort(r.begin(), r.end());
    172  
    173     auto check = [&](int cnt) {
    174         fore (i, 0, cnt) {
    175             if (li(q[i] + 1) * (r[cnt - 1 - i] + 1) - 1 > k)
    176                 return false;
    177         }
    178         return true;
    179     };
    180  
    181     int lf = 0, rg = n + 1;
    182     while (rg - lf > 1) {
    183         int mid = (lf + rg) >> 1;
    184         if (check(mid))
    185             lf = mid;
    186         else
    187             rg = mid;
    188     }
    189     cout << lf << endl;
    190 }
    191  
    192 int main() {
    193 #ifdef _DEBUG
    194     freopen("input.txt", "r", stdin);
    195     int tt = clock();
    196 #endif
    197     ios_base::sync_with_stdio(false);
    198     cin.tie(0), cout.tie(0);
    199     cout << fixed << setprecision(15);
    200     
    201     int t = 1; cin >> t;
    202     while (t--) {
    203         solve();
    204         
    205 #ifdef _DEBUG
    206         cerr << "TIME = " << clock() - tt << endl;
    207         tt = clock();
    208 #endif
    209     }
    210     return 0;
    211 }
    212 ```
    213 
    214 [2170D - Almost Roman](/contest/2170/problem/D "Educational Codeforces Round 185 (Rated for Div. 2)")
    215 
    216 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    217 
    218 **Tutorial**
    219 
    220 Tutorial is loading...
    221 
    222 **Solution (BledDest)**
    223 
    224 ```
    225 #include<bits/stdc++.h>
    226 
    227 using namespace std;
    228 
    229 int cost(char c)
    230 {
    231     if(c == 'I') return 1;
    232     return 5;
    233 }
    234 
    235 int eval(string s)
    236 {
    237     int n = s.size();
    238     int ans = 0;
    239     for(int i = 0; i < n; i++)
    240         if(s[i] == 'I' && i + 1 < n && s[i + 1] == 'V')
    241             ans--;
    242         else ans += cost(s[i]);
    243     return ans;    
    244 }
    245 
    246 void solve()
    247 {
    248     int n, q;
    249     cin >> n >> q;
    250     string s;
    251     cin >> s;
    252     int ans = 0;
    253     for(int i = 0; i < n; i++)
    254     {
    255         if(s[i] == 'X')
    256         {
    257             s[i] = 'V';
    258             ans += 5;
    259         }
    260     }
    261     int inc = 0;
    262     int same = 0;
    263     int qcount = 0;
    264     for(int i = 0; i < n; i++)
    265     {
    266         if(s[i] != '?') continue;
    267         int r = i;
    268         while(r < n && s[r] == '?') r++;
    269         int len = r - i;
    270         if(i > 0 && s[i - 1] == 'I') len++;
    271         if(r < n && s[r] == 'V') 
    272         {
    273             inc--;
    274             len++;
    275         }
    276         inc += len / 2;
    277         same += len % 2;
    278         qcount += (r - i);
    279         i = r - 1;        
    280     }
    281     for(int i = 0; i < n; i++)
    282         if(s[i] == '?') s[i] = 'I';
    283     ans += eval(s);
    284     for(int i = 0; i < q; i++)
    285     {
    286         int a, b, c;
    287         cin >> a >> b >> c;
    288         int used_v = max(0, min(b, qcount - c));
    289         int used_x = max(0, qcount - c - b);
    290         int cur = ans;
    291         cur += used_v * 4 + used_x * 9;
    292         int rep = used_v + used_x;
    293         cur -= min(inc, rep) * 2;
    294         rep -= (inc + same);
    295         cur += max(0, rep) * 2;
    296         cout << cur << "\n";  
    297     }
    298 }
    299 
    300 int main()
    301 {
    302     ios_base::sync_with_stdio(0);
    303     cin.tie(0);
    304     int t;
    305     cin >> t;
    306     for(int i = 0; i < t; i++)
    307         solve();
    308 }
    309 ```
    310 
    311 [2170E - Binary Strings and Blocks](/contest/2170/problem/E "Educational Codeforces Round 185 (Rated for Div. 2)")
    312 
    313 Idea: [Roms](/profile/Roms "Master Roms")
    314 
    315 **Tutorial**
    316 
    317 Tutorial is loading...
    318 
    319 **Solution (BledDest)**
    320 
    321 ```
    322 #include<bits/stdc++.h>
    323  
    324 using namespace std;
    325  
    326 const int INF = 1e9;
    327 const int MOD = 998244353;
    328  
    329 int add(int x, int y)
    330 {
    331     x += y;
    332     while(x >= MOD) x -= MOD;
    333     while(x < 0) x += MOD;
    334     return x;
    335 }
    336  
    337 void solve()
    338 {
    339     int n, m;
    340     cin >> n >> m;
    341     vector<int> max_left(n + 1, -1);
    342     for(int i = 0; i < m; i++)
    343     {
    344         int l, r;
    345         cin >> l >> r;
    346         --l;
    347         --r;
    348         max_left[r] = max(max_left[r], l);
    349     }
    350     for(int i = 1; i <= n; i++)
    351         max_left[i] = max(max_left[i], max_left[i - 1]);
    352     vector<int> dp(n + 1);
    353     vector<int> prefsum(n + 2);
    354     dp[0] = 2;
    355     prefsum[1] = 2;
    356     for(int i = 1; i <= n; i++)
    357     {
    358         int j = max_left[i - 1] + 1;
    359         dp[i] = add(prefsum[i], -prefsum[j]);
    360         prefsum[i + 1] = add(prefsum[i], dp[i]);
    361     }
    362     cout << dp[n] << "\n";
    363 }
    364  
    365 int main()
    366 {
    367     ios_base::sync_with_stdio(0);
    368     cin.tie(0);
    369     int t;
    370     cin >> t;
    371     for(int i = 0; i < t; i++) solve();
    372 }
    373 ```
    374 
    375 [2170F - Build XOR on a Segment](/contest/2170/problem/F "Educational Codeforces Round 185 (Rated for Div. 2)")
    376 
    377 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    378 
    379 **Tutorial**
    380 
    381 Tutorial is loading...
    382 
    383 **Solution (BledDest)**
    384 
    385 ```
    386 #include<bits/stdc++.h>
    387  
    388 using namespace std;
    389  
    390 const int B = 13;
    391 const int M = (1 << (B - 1));
    392 const int INF = 1e9;
    393  
    394 int dp[B][M];
    395  
    396 void upd(int& a, int b)
    397 {
    398     if(a < b) a = b;
    399 }
    400  
    401 int main()
    402 {
    403     ios_base::sync_with_stdio(0);
    404     cin.tie(0);
    405     int n;
    406     cin >> n;
    407     vector<int> a(n);
    408     for(int i = 0; i < n; i++) cin >> a[i];
    409     vector<vector<int>> id(n);
    410     int q;
    411     cin >> q;
    412     vector<int> l(q), x(q);
    413     for(int i = 0; i < q; i++)
    414     {
    415         int r;
    416         cin >> l[i] >> r >> x[i];
    417         --l[i];
    418         --r;
    419         id[r].push_back(i);
    420     }
    421     
    422     for(int i = 0; i < B; i++)
    423         for(int j = 0; j < M; j++)
    424             dp[i][j] = -INF;
    425     dp[0][0] = INF;
    426     vector<int> ans(q, 0);
    427     for(int i = 0; i < n; i++)
    428     {
    429         int val = a[i];
    430         upd(dp[1][val], i);
    431         for(int j = 1; j < B - 1; j++)
    432         {
    433             for(int k = 1; k < M; k++)
    434             {
    435                 upd(dp[j + 1][k ^ val], dp[j][k]);
    436             }
    437         }
    438         for(auto qr : id[i])
    439         {
    440             int cur = x[qr];
    441             for(int j = B - 1; j >= 0; j--)
    442                 if(dp[j][cur] >= l[qr])
    443                     ans[qr] = j;
    444         }
    445     }
    446     
    447     for(int i = 0; i < q; i++)
    448         cout << ans[i] << " ";
    449     cout << endl;
    450 }
    451 ```