codeforces-scrape

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

1624.md (7953B)


      1 Source: https://codeforces.com/blog/entry/98942
      2 
      3 [1624A - Plus One on the Subset](/contest/1624/problem/A "Codeforces Round 764 (Div. 3)")
      4 
      5 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
      6 
      7 **Tutorial**
      8 
      9 Tutorial is loading...
     10 
     11 **Solution**
     12 
     13 ```
     14 #include <bits/stdc++.h>
     15 
     16 using namespace std;
     17 
     18 typedef long long ll;
     19 
     20 #define forn(i, n) for (int i = 0; i < int(n); i++)
     21 
     22 void solve() {
     23     int n;
     24     cin >> n;
     25     int a[n];
     26     for (int i = 0; i < n; ++i) {
     27         cin >> a[i];
     28     }
     29     int MIN = INT_MAX;
     30     int MAX = INT_MIN;
     31     for (int i = 0; i < n; ++i) {
     32         MIN = min(MIN, a[i]);
     33         MAX = max(MAX, a[i]);
     34     }
     35     cout << MAX - MIN << '\n';
     36 }
     37 int main() {
     38     int tests;
     39     cin >> tests;
     40     forn(tt, tests) {
     41         solve();
     42     }
     43 }
     44 ```
     45 
     46 [1624B - Make AP](/contest/1624/problem/B "Codeforces Round 764 (Div. 3)")
     47 
     48 Idea: [ibraevdmitriy](/profile/ibraevdmitriy "Master ibraevdmitriy")
     49 
     50 **Tutorial**
     51 
     52 Tutorial is loading...
     53 
     54 **Solution**
     55 
     56 ```
     57 #include<bits/stdc++.h>
     58 
     59 using namespace std;
     60 
     61 void solveTest() {
     62     int a, b, c;
     63     cin >> a >> b >> c;
     64 
     65     int new_a = b - (c - b);
     66     if(new_a >= a && new_a % a == 0 && new_a != 0) {
     67         cout << "YES\n";
     68         return;
     69     }
     70 
     71     int new_b = a + (c - a)/2;
     72     if(new_b >= b && (c-a)%2 == 0 && new_b % b == 0 && new_b != 0) {
     73         cout << "YES\n";
     74         return;
     75     }
     76 
     77     int new_c = a + 2*(b - a);
     78     if(new_c >= c && new_c % c == 0 && new_c != 0) {
     79         cout << "YES\n";
     80         return;
     81     }
     82 
     83     cout << "NO\n";
     84     return;
     85 }
     86 
     87 int main() {
     88     ios_base::sync_with_stdio(false);
     89     cin.tie(0); cout.tie(0);
     90     int tt;
     91     cin >> tt;
     92     while(tt--)
     93         solveTest();
     94     return 0;
     95 }
     96 ```
     97 
     98 [1624C - Division by Two and Permutation](/contest/1624/problem/C "Codeforces Round 764 (Div. 3)")
     99 
    100 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
    101 
    102 **Tutorial**
    103 
    104 Tutorial is loading...
    105 
    106 **Solution**
    107 
    108 ```
    109 #include<bits/stdc++.h>
    110 using namespace std;
    111 
    112 void solve(){
    113     int n;
    114     cin >> n;
    115     vector<int>a(n), used(n + 1, false);
    116     for(auto &i : a) cin >> i;
    117     sort(a.begin(), a.end(), [] (int a, int b) {
    118         return a > b;
    119     });
    120     bool ok = true;
    121     for(auto &i : a){
    122         int x = i;
    123         while(x > n or used[x])  x /= 2;
    124         if(x > 0) used[x] = true;
    125         else ok = false;
    126     }
    127     cout << (ok ? "YES" : "NO") << '\n';
    128 
    129 }
    130 
    131 int main(){
    132     ios_base :: sync_with_stdio(false);
    133     cin.tie(nullptr);
    134     int t;
    135     cin >> t;
    136     while(t--){
    137         solve();
    138     }
    139     return 0;
    140 }
    141 ```
    142 
    143 [1624D - Palindromes Coloring](/contest/1624/problem/D "Codeforces Round 764 (Div. 3)")
    144 
    145 Idea: [ibraevdmitriy](/profile/ibraevdmitriy "Master ibraevdmitriy")
    146 
    147 **Tutorial**
    148 
    149 Tutorial is loading...
    150 
    151 **Solution**
    152 
    153 ```
    154 #include <iostream>
    155 #include <vector>
    156 #include <stack>
    157 #include <algorithm>
    158 
    159 using namespace std;
    160 
    161 typedef long long ll;
    162 const int MAX_N = 2e5;
    163 
    164 int main(int argc, char* argv[]) {
    165     int t;
    166     cin >> t;
    167     for (int _ = 0; _ < t; ++_) {
    168         int n, k;
    169         string s;
    170         cin >> n >> k >> s;
    171         vector<int> cnt(26);
    172         for (char c : s) {
    173             cnt[c - 'a']++;
    174         }
    175         int cntPairs = 0, cntOdd = 0;
    176         for (int c : cnt) {
    177             cntPairs += c / 2;
    178             cntOdd += c % 2;
    179         }
    180         int ans = 2 * (cntPairs / k);
    181         cntOdd += 2 * (cntPairs % k);
    182         if (cntOdd >= k) {
    183             ans++;
    184         }
    185         cout << ans << '\n';
    186     }
    187 }
    188 ```
    189 
    190 [1624E - Masha-forgetful](/contest/1624/problem/E "Codeforces Round 764 (Div. 3)")
    191 
    192 Idea: [Aris](/profile/Aris "Candidate Master Aris")
    193 
    194 **Tutorial**
    195 
    196 Tutorial is loading...
    197 
    198 **Solution**
    199 
    200 ```
    201 #include <bits/stdc++.h>
    202 
    203 using namespace std;
    204 
    205 #define forn(i, n) for (int i = 0; i < int(n); i++)
    206 #define sz(v) (int)v.size()
    207 
    208 const int N = 1e4;
    209 map<string, bool> have;
    210 map<string, tuple<int,int,int>> pos;
    211 
    212 void solve() {
    213     int n, m; cin >> n >> m;
    214     vector<bool> dp(m+1, false);
    215     vector<int> pr(m+1);
    216     vector<string> cache;
    217     dp[0] = true;
    218 
    219     forn(i, n) {
    220         string s; cin >> s;
    221         forn(j, m) {
    222             string t;
    223             t += s[j];
    224             for(int k = 1; k <= 2; k++) {
    225                 if (k + j >= m) break;
    226                 t += s[j+k];
    227 
    228                 if (!have[t]) {
    229                     have[t] = true;
    230                     pos[t] = make_tuple(j, j+k, i);
    231                     cache.push_back(t);
    232                 }
    233             }
    234         }
    235     }
    236 
    237     string s; cin >> s;
    238     forn(i, m) {
    239         string t;
    240         t += s[i];
    241         for (int k = 1; k <= 2; k++) {
    242             if (i - k < 0) break;
    243             t = s[i-k] + t;
    244             if (have[t] && dp[i-k]) {
    245                 dp[i+1] = true;
    246                 pr[i+1] = i-k;
    247             }
    248             if (dp[i+1]) break;
    249         }
    250     }
    251     for (string t : cache) {
    252         have[t] = false;
    253     }
    254 
    255     if (!dp[m]) {
    256         cout << "-1\n";
    257         return;
    258     }
    259     vector<tuple<int,int,int>> ans;
    260 
    261     for (int k = m; k > 0; ) {
    262         int p = pr[k];
    263         string t = s.substr(p, k - p);
    264         ans.emplace_back(pos[t]);
    265         k = p;
    266     }
    267 
    268     cout << sz(ans) << '\n';
    269     reverse(ans.begin(), ans.end());
    270     for (auto [l,r,i] : ans) cout << l+1 << ' ' << r+1 << ' ' << i+1 << '\n';
    271 }
    272 
    273 int main() {
    274     int t;
    275     cin >> t;
    276 
    277     forn(tt, t) {
    278         solve();
    279     }
    280 }
    281 ```
    282 
    283 [1624F - Interacdive Problem](/contest/1624/problem/F "Codeforces Round 764 (Div. 3)")
    284 
    285 Idea: [Vladosiya](/profile/Vladosiya "Expert Vladosiya")
    286 
    287 **Tutorial**
    288 
    289 Tutorial is loading...
    290 
    291 **Solution**
    292 
    293 ```
    294 #include <bits/stdc++.h>
    295 
    296 #define int long long
    297 #define mp make_pair
    298 #define x first
    299 #define y second
    300 #define all(a) (a).begin(), (a).end()
    301 #define rall(a) (a).rbegin(), (a).rend()
    302 
    303 typedef long double ld;
    304 typedef long long ll;
    305 
    306 using namespace std;
    307 
    308 mt19937 rnd(143);
    309 
    310 const int inf = 1e10;
    311 const int M = 998244353;
    312 const ld pi = atan2(0, -1);
    313 const ld eps = 1e-4;
    314 
    315 signed main(){
    316     int n;
    317     cin >> n;
    318     int l = 1, r = n;
    319     int div = 0;
    320     while(r - l > 1){
    321         int mid = (r + l) / 2;
    322         cout << "+ "<< n - mid << endl;
    323         int d;
    324         cin >> d;
    325         if(d > div)l = mid;
    326         else r = mid;
    327         l = (l + n - mid) % n;
    328         r = (r + n - mid) % n;
    329         if(r == 0) r = n;
    330         div = d;
    331     }
    332     cout << "! " << div * n + l;
    333     return 0;
    334 }
    335 ```
    336 
    337 [1624G - MinOr Tree](/contest/1624/problem/G "Codeforces Round 764 (Div. 3)")
    338 
    339 Idea: [Vladosiya](/profile/Vladosiya "Expert Vladosiya")
    340 
    341 **Tutorial**
    342 
    343 Tutorial is loading...
    344 
    345 **Solution**
    346 
    347 ```
    348 #include <bits/stdc++.h>
    349 
    350 #define int long long
    351 #define mp make_pair
    352 #define x first
    353 #define y second
    354 #define all(a) (a).begin(), (a).end()
    355 #define rall(a) (a).rbegin(), (a).rend()
    356 
    357 typedef long double ld;
    358 typedef long long ll;
    359 
    360 using namespace std;
    361 
    362 mt19937 rnd(143);
    363 
    364 const int inf = 1e9;
    365 const int M = 998244353;
    366 const ld pi = atan2(0, -1);
    367 const ld eps = 1e-4;
    368 
    369 int n, cur;
    370 vector<vector<pair<int, int>>> sl;
    371 
    372 void dfs(int v, vector<bool> &used){
    373     used[v] = true;
    374     for(auto e: sl[v]){
    375         int u = e.x, w = e.y;
    376         if(!used[u] && (cur | w) == cur){
    377             dfs(u, used);
    378         }
    379     }
    380 }
    381 
    382 void cnt(int pw){
    383     if(pw < 0) return;
    384     int d = (ll) 1 << pw;
    385     cur -= d;
    386     vector<bool> used(n);
    387     dfs(0, used);
    388     for(bool b: used){
    389         if(!b) {
    390             cur += d;
    391             break;
    392         }
    393     }
    394     cnt(pw - 1);
    395 }
    396 
    397 void solve() {
    398     int m;
    399     cin >> n >> m;
    400     sl.assign(n, vector<pair<int, int>>(0));
    401     for(int i = 0; i < m; ++i){
    402         int u, v, w;
    403         cin >> u >> v >> w;
    404         --u, --v;
    405         sl[u].emplace_back(v, w);
    406         sl[v].emplace_back(u, w);
    407     }
    408     cur = 1;
    409     int bit = 0;
    410     for(; cur < inf; bit++){
    411         cur = 2 * cur + 1;
    412     }
    413     cnt(bit);
    414     cout << cur;
    415 }
    416 
    417 bool multi = true;
    418 
    419 signed main() {
    420     int t = 1;
    421     if (multi) {
    422         cin >> t;
    423     }
    424     for (; t != 0; --t) {
    425         solve();
    426         cout << "\n";
    427     }
    428     return 0;
    429 }
    430 ```