codeforces-scrape

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

1796.md (7530B)


      1 Source: https://codeforces.com/blog/entry/113408
      2 
      3 [1796A - Typical Interview Problem](/contest/1796/problem/A "Educational Codeforces Round 144 (Rated for Div. 2)")
      4 
      5 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
      6 
      7 **Tutorial**
      8 
      9 Tutorial is loading...
     10 
     11 **Solution (BledDest)**
     12 
     13 ```
     14 #include <bits/stdc++.h>
     15  
     16 using namespace std;
     17 
     18 int main()
     19 {
     20     string fb;
     21     int cur = 1;
     22     while(fb.size() < 100)
     23     {
     24         if(cur % 3 == 0) fb += "F";
     25         if(cur % 5 == 0) fb += "B";
     26         cur++;
     27     }
     28     int t;
     29     cin >> t;
     30     for(int i = 0; i < t; i++)
     31     {
     32         int k;
     33         cin >> k;
     34         string s;
     35         cin >> s;
     36         cout << (fb.find(s) != string::npos ? "YES" : "NO") << endl;
     37     }
     38 }
     39 ```
     40 
     41 [1796B - Asterisk-Minor Template](/contest/1796/problem/B "Educational Codeforces Round 144 (Rated for Div. 2)")
     42 
     43 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
     44 
     45 **Tutorial**
     46 
     47 Tutorial is loading...
     48 
     49 **Solution (awoo)**
     50 
     51 ```
     52 for _ in range(int(input())):
     53     a = input()
     54     b = input()
     55     if a[0] == b[0]:
     56         print("YES")
     57         print(a[0] + "*")
     58         continue
     59     if a[-1] == b[-1]:
     60         print("YES")
     61         print("*" + a[-1])
     62         continue
     63     for i in range(len(b) - 1):
     64         if (b[i] + b[i + 1]) in a:
     65             print("YES")
     66             print("*" + b[i] + b[i + 1] + "*")
     67             break
     68     else:
     69         print("NO")
     70 ```
     71 
     72 [1796C - Maximum Set](/contest/1796/problem/C "Educational Codeforces Round 144 (Rated for Div. 2)")
     73 
     74 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
     75 
     76 **Tutorial**
     77 
     78 Tutorial is loading...
     79 
     80 **Solution (BledDest)**
     81 
     82 ```
     83 #include <bits/stdc++.h>
     84  
     85 using namespace std;
     86 
     87 int main()
     88 {
     89     int t;
     90     cin >> t;
     91     for(int i = 0; i < t; i++)
     92     {
     93         int l, r;
     94         cin >> l >> r;
     95         int max_size = 1;
     96         while((l << max_size) <= r)
     97             max_size++;
     98         int ans2 = (r / (1 << (max_size - 1)) - l + 1);
     99         if(max_size > 1)
    100             ans2 += (max_size - 1) * max(0, (r / (1 << (max_size - 2)) / 3 - l + 1));
    101         cout << max_size << " " << ans2 << endl;
    102     }
    103 }
    104 ```
    105 
    106 [1796D - Maximum Subarray](/contest/1796/problem/D "Educational Codeforces Round 144 (Rated for Div. 2)")
    107 
    108 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    109 
    110 **Tutorial**
    111 
    112 Tutorial is loading...
    113 
    114 **Solution (Neon)**
    115 
    116 ```
    117 #include <bits/stdc++.h>
    118 
    119 using namespace std;
    120 
    121 using li = long long;
    122 
    123 const int N = 222222;
    124 const int K = 22;
    125 const li INF = 1e18;
    126 
    127 int n, k, x;
    128 int a[N];
    129 li dp[N][K][3];
    130 
    131 int main() {
    132   ios::sync_with_stdio(false); cin.tie(0);
    133   int tc;
    134   cin >> tc;
    135   while (tc--) {
    136     cin >> n >> k >> x;
    137     for (int i = 0; i < n; ++i) cin >> a[i];
    138     for (int i = 0; i <= n; ++i) {
    139       for (int j = 0; j <= k; ++j) { 
    140         for (int t = 0; t < 3; ++t) {
    141           dp[i][j][t] = -INF;
    142         }
    143       }
    144     }
    145     dp[0][0][0] = 0;
    146     for (int i = 0; i < n; ++i) {
    147       for (int j = 0; j <= k; ++j) {
    148         for (int t = 0; t < 3; ++t) {
    149           if (dp[i][j][t] == -INF) continue;
    150           for (int jj = j; jj <= min(k, j + 1); ++jj) {
    151             li add = a[i] + (j == jj ? -x : x);
    152             for (int tt = t; tt < 3; ++tt) {
    153               dp[i + 1][jj][tt] = max(dp[i + 1][jj][tt], dp[i][j][t] + (tt == 1 ? add : 0));
    154             }
    155           }
    156         }
    157       }
    158     }
    159     cout << max(dp[n][k][1], dp[n][k][2]) << '\n';
    160   }
    161 }
    162 ```
    163 
    164 [1796E - Colored Subgraphs](/contest/1796/problem/E "Educational Codeforces Round 144 (Rated for Div. 2)")
    165 
    166 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    167 
    168 **Tutorial**
    169 
    170 Tutorial is loading...
    171 
    172 **Solution (awoo)**
    173 
    174 ```
    175 #include <bits/stdc++.h>
    176  
    177 using namespace std;
    178  
    179 #define forn(i, n) for(int i = 0; i < int(n); i++) 
    180 
    181 vector<vector<int>> g;
    182 vector<multiset<int>> len;
    183 multiset<int> all;
    184 
    185 int getlen(int v){
    186     return len[v].empty() ? 1 : *len[v].begin() + 1;
    187 }
    188 
    189 void init(int v, int p = -1){
    190     for (int u : g[v]) if (u != p){
    191         init(u, v);
    192         len[v].insert(getlen(u));
    193     }
    194     if (int(len[v].size()) > 1){
    195         all.insert(*(++len[v].begin()));
    196     }
    197 }
    198 
    199 int ans;
    200 
    201 void dfs(int v, int p = -1){
    202     ans = max(ans, min(*len[v].begin() + 1, *all.begin()));
    203     
    204     for (int u : g[v]) if (u != p){
    205         if (int(len[v].size()) > 1) all.erase(all.find(*(++len[v].begin())));
    206         len[v].erase(len[v].find(getlen(u)));
    207         if (int(len[v].size()) > 1) all.insert(*(++len[v].begin()));
    208         
    209         if (int(len[u].size()) > 1) all.erase(all.find(*(++len[u].begin())));
    210         len[u].insert(getlen(v));
    211         if (int(len[u].size()) > 1) all.insert(*(++len[u].begin()));
    212         
    213         dfs(u, v);
    214         
    215         if (int(len[u].size()) > 1) all.erase(all.find(*(++len[u].begin())));
    216         len[u].erase(len[u].find(getlen(v)));
    217         if (int(len[u].size()) > 1) all.insert(*(++len[u].begin()));
    218         
    219         if (int(len[v].size()) > 1) all.erase(all.find(*(++len[v].begin())));
    220         len[v].insert(getlen(u));
    221         if (int(len[v].size()) > 1) all.insert(*(++len[v].begin()));
    222     }
    223 }
    224 
    225 int main(){
    226     int t;
    227     scanf("%d", &t);
    228     while (t--){
    229         int n;
    230         scanf("%d", &n);
    231         g.assign(n, {});
    232         forn(i, n - 1){
    233             int v, u;
    234             scanf("%d%d", &v, &u);
    235             --v, --u;
    236             g[v].push_back(u);
    237             g[u].push_back(v);
    238         }
    239         len.assign(n, {});
    240         all.clear();
    241         all.insert(n);
    242         init(0);
    243         ans = 0;
    244         dfs(0);
    245         printf("%d\n", ans);
    246     }
    247 }
    248 ```
    249 
    250 [1796F - Strange Triples](/contest/1796/problem/F "Educational Codeforces Round 144 (Rated for Div. 2)")
    251 
    252 Idea: [Neon](/profile/Neon "Candidate Master Neon") and [adedalic](/profile/adedalic "International Master adedalic")
    253 
    254 **Tutorial**
    255 
    256 Tutorial is loading...
    257 
    258 **Solution (Neon)**
    259 
    260 ```
    261 #include <bits/stdc++.h>
    262  
    263 using namespace std;
    264 
    265 #define sz(a) int((a).size())
    266 
    267 using li = long long;
    268 
    269 const int MAXLEN = 5;
    270 
    271 vector<int> divs(int x) {
    272   vector<int> res;
    273   for (int i = 1; i * i <= x; ++i) {
    274     if (x % i == 0) {
    275       res.push_back(i);
    276       if (i * i != x)
    277         res.push_back(x / i);
    278     }
    279   }
    280   return res;
    281 }
    282 
    283 int main() {
    284   int A, B, N;
    285   cin >> A >> B >> N;
    286 
    287   vector<int> pw(10);
    288   pw[0] = 1;
    289   for (int i = 1; i < 10; ++i) pw[i] = pw[i - 1] * 10;
    290   
    291   int PW = pw[MAXLEN];
    292   set<array<int, 3>> used;
    293   
    294   vector<int> len(PW);
    295   for (int i = 0; i < PW; ++i)
    296     len[i] = sz(to_string(i));
    297   
    298   for (int lenn = 1; lenn <= 9; ++lenn) {
    299     int x = pw[lenn] - 1;
    300     for (int k2 : divs(x)) {
    301       int r = x / k2;
    302       for (int d = 1; d < PW; ++d) {
    303         for (int lenb = len[d]; lenb <= MAXLEN; ++lenb) {
    304           int bg = pw[lenb] - d * li(r) % pw[lenb];
    305           int dd = d / __gcd(d, bg);
    306           int lb = (pw[lenb - 1] + bg - 1) / bg;
    307           int rb = (pw[lenb] - 1) / bg;
    308           for (int g = (lb + dd - 1) / dd * dd; g <= rb; g += dd) {
    309             int b = bg * g;
    310             assert(b % d == 0);
    311             if (b >= B || __gcd(b / d, r) != 1) continue;
    312             int ag = (d * li(r) + bg) / pw[lenb];
    313             li n = b / d * li(k2) * ag;
    314             if (n < N && ag * g < A && __gcd(ag, bg) == 1 && sz(to_string(n)) == lenn) 
    315               used.insert({ag * g, b, n});
    316           }
    317         }
    318       }
    319     }
    320   }
    321   
    322   int res = 0;
    323   for (auto it : used) {
    324     li a = it[0], b = it[1], n = it[2];
    325     int lenn = sz(to_string(n));
    326     int lenb = sz(to_string(b));
    327     res += a * b * pw[lenn] + n * b == a * n * pw[lenb] + a * b;
    328   }
    329   
    330   cout << res << endl;
    331 }
    332 ```