codeforces-scrape

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

1743.md (9034B)


      1 Source: https://codeforces.com/blog/entry/108153
      2 
      3 [1743A - Password](/contest/1743/problem/A "Educational Codeforces Round 137 (Rated for Div. 2)")
      4 
      5 Idea: [fcspartakm](/profile/fcspartakm "Candidate Master fcspartakm")
      6 
      7 **Tutorial**
      8 
      9 Tutorial is loading...
     10 
     11 **Solution 1 (awoo)**
     12 
     13 ```
     14 for _ in range(int(input())):
     15 	n = int(input())
     16 	a = set(map(int, input().split()))
     17 	ans = 0
     18 	for i in range(10000):
     19 		num = str(i)
     20 		num = (4 - len(num)) * '0' + num
     21 		used = set(num)
     22 		if len(used) != 2:
     23 			continue
     24 		d1 = int(used.pop())
     25 		d2 = int(used.pop())
     26 		if (not d1 in a) and (not d2 in a) and num.count(num[0]) == 2:
     27 			ans += 1
     28 	print(ans)
     29 ```
     30 
     31 **Solution 2 (fcspartakm)**
     32 
     33 ```
     34 #include <bits/stdc++.h>
     35 
     36 using namespace std;
     37 
     38 int n;
     39 
     40 inline void read() {	
     41     cin >> n;
     42     int x;
     43     for (int i = 0; i < n; ++i)
     44         cin >> x;
     45 }
     46 
     47 inline int fac(int n) {
     48     int res = 1;
     49     for (int i = 2; i <= n; i++) {
     50         res *= i;
     51     }
     52     return res;
     53 }
     54 
     55 inline int c(int n, int k) {
     56     return fac(n) / fac(k) / fac(n - k);
     57 }
     58 
     59 inline void solve() {
     60     cout << c(10 - n, 2) * c(4, 2) << endl;
     61 }
     62 
     63 int main () {
     64     int t;
     65     cin >> t;
     66     while (t--){
     67         read();
     68         solve();
     69     }
     70 }
     71 ```
     72 
     73 [1743B - Permutation Value](/contest/1743/problem/B "Educational Codeforces Round 137 (Rated for Div. 2)")
     74 
     75 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
     76 
     77 **Tutorial**
     78 
     79 Tutorial is loading...
     80 
     81 **Solution (BledDest)**
     82 
     83 ```
     84 #include <bits/stdc++.h>
     85  
     86 using namespace std;
     87 
     88 void solve() 
     89 {
     90     int n;
     91     cin >> n;
     92     cout << 1;
     93     for(int i = n; i >= 2; i--)
     94         cout << " " << i;
     95     cout << endl;
     96 }
     97 
     98 int main()
     99 {
    100     int t;
    101     cin >> t;
    102     for(int i = 0; i < t; i++)
    103         solve();
    104 }
    105 ```
    106 
    107 [1743C - Save the Magazines](/contest/1743/problem/C "Educational Codeforces Round 137 (Rated for Div. 2)")
    108 
    109 Idea: [fcspartakm](/profile/fcspartakm "Candidate Master fcspartakm")
    110 
    111 **Tutorial**
    112 
    113 Tutorial is loading...
    114 
    115 **Solution (awoo)**
    116 
    117 ```
    118 for _ in range(int(input())):
    119 	n = int(input())
    120 	s = '0' + input()
    121 	a = [0] + list(map(int, input().split()))
    122 	ans = 0
    123 	i = 0
    124 	while i <= n:
    125 		mn = a[i]
    126 		sm = a[i]
    127 		j = i + 1
    128 		while j <= n and s[j] == '1':
    129 			mn = min(mn, a[j])
    130 			sm += a[j]
    131 			j += 1
    132 		ans += sm - mn
    133 		i = j
    134 	print(ans)
    135 ```
    136 
    137 [1743D - Problem with Random Tests](/contest/1743/problem/D "Educational Codeforces Round 137 (Rated for Div. 2)")
    138 
    139 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    140 
    141 **Tutorial**
    142 
    143 Tutorial is loading...
    144 
    145 **Solution (BledDest)**
    146 
    147 ```
    148 #include<bits/stdc++.h>
    149 
    150 using namespace std;
    151 
    152 char buf[1000043];
    153 
    154 string normalize(const string& v)
    155 {
    156     int cnt = 0;
    157     while(cnt < v.size() && v[cnt] == '0') cnt++;
    158     if(cnt == v.size()) return "0";
    159     return v.substr(cnt, int(v.size()) - cnt);
    160 }
    161 
    162 string operator |(const string& a, const string& b)
    163 {
    164     int sz = max(a.size(), b.size());
    165     string ans(sz, '0');
    166     for(int i = 0; i < a.size(); i++)
    167         if(a[i] == '1') ans[i + sz - int(a.size())] = '1';
    168     for(int i = 0; i < b.size(); i++)
    169         if(b[i] == '1') ans[i + sz - int(b.size())] = '1';    
    170     return normalize(ans);
    171 }
    172 
    173 bool better(const string& a, const string& b)
    174 {
    175     if(a.size() != b.size()) return a.size() > b.size();
    176     return a > b;
    177 }
    178 
    179 int main()
    180 {
    181     int n;
    182     scanf("%d", &n);
    183     string s;
    184     scanf("%s", buf);
    185     s = buf;
    186     string ans = s | s;
    187     int pos1 = s.find("1");
    188     if(pos1 != string::npos)
    189     {
    190         int pos2 = s.find("0", pos1);
    191         if(pos2 != string::npos)
    192         {
    193             int cur = pos1;
    194             int not_needed = 0;
    195             while(true)
    196             {                
    197                 if(cur == n || (s[cur] == '1' && cur > pos2)) break;
    198                 string nw = s | s.substr(pos1, n - pos1 - not_needed);
    199                 if(better(nw, ans)) ans = nw;
    200                 cur++;
    201                 not_needed++;
    202             }
    203         }
    204     }
    205     puts(ans.c_str());
    206 }
    207 ```
    208 
    209 [1743E - FTL](/contest/1743/problem/E "Educational Codeforces Round 137 (Rated for Div. 2)")
    210 
    211 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    212 
    213 **Tutorial**
    214 
    215 Tutorial is loading...
    216 
    217 **Solution (awoo)**
    218 
    219 ```
    220 #include <bits/stdc++.h>
    221 
    222 #define forn(i, n) for (int i = 0; i < int(n); i++)
    223 
    224 using namespace std;
    225 
    226 const long long INF64 = 1e18;
    227 
    228 int main() {
    229 	vector<int> ps(2);
    230 	vector<long long> ts(2);
    231 	int h, s;
    232 	forn(i, 2) scanf("%d%lld", &ps[i], &ts[i]);
    233 	scanf("%d%d", &h, &s);
    234 	long long ans = INF64;
    235 	vector<long long> dp(h + 1, INF64);
    236 	dp[0] = 0;
    237 	forn(i, h) for (int j = 1; j <= h - i; ++j) forn(k, 2){
    238 		int ni = min((long long)h, i + j * (ps[k] - s) + j * ts[k] / ts[k ^ 1] * (ps[k ^ 1] - s));
    239 		if (ni == h)
    240 			ans = min(ans, dp[i] + j * ts[k]);
    241 		if (j * ts[k] >= ts[k ^ 1]){
    242 			ni = min((long long)h, i + (j - 1) * (ps[k] - s) + (j * ts[k] / ts[k ^ 1] - 1) * (ps[k ^ 1] - s) + (ps[0] + ps[1] - s));
    243 			dp[ni] = min(dp[ni], dp[i] + j * ts[k]);
    244 		}
    245 	}
    246 	ans = min(ans, dp[h]);
    247 	printf("%lld\n", ans);
    248 }
    249 ```
    250 
    251 [1743F - Intersection and Union](/contest/1743/problem/F "Educational Codeforces Round 137 (Rated for Div. 2)")
    252 
    253 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    254 
    255 **Tutorial**
    256 
    257 Tutorial is loading...
    258 
    259 **Solution (BledDest)**
    260 
    261 ```
    262 #include<bits/stdc++.h>
    263 
    264 using namespace std;
    265 
    266 const int N = 300043;
    267 
    268 typedef array<int, 2> vec;
    269 typedef array<vec, 2> mat;
    270 
    271 const int MOD = 998244353;
    272 
    273 mat operator*(const mat& a, const mat& b)
    274 {
    275     mat c;
    276     for(int i = 0; i < 2; i++)
    277         for(int j = 0; j < 2; j++)
    278             c[i][j] = 0;
    279     for(int i = 0; i < 2; i++)
    280         for(int j = 0; j < 2; j++)
    281             for(int k = 0; k < 2; k++)
    282                 c[i][k] = (a[i][j] * 1ll * b[j][k] + c[i][k]) % MOD;
    283     return c;
    284 }
    285 
    286 mat ZERO = {vec({3, 0}), vec({1, 2})};
    287 mat ONE = {vec({1, 2}), vec({1, 2})};
    288 
    289 mat t[4 * N];
    290 
    291 void recalc(int v)
    292 {
    293     t[v] = t[v * 2 + 1] * t[v * 2 + 2];    
    294 }
    295 
    296 void build(int v, int l, int r)
    297 {
    298     if(l == r - 1)
    299     {            
    300         t[v] = ZERO;                       
    301     }
    302     else
    303     {
    304         int m = (l + r) / 2;
    305         build(v * 2 + 1, l, m);
    306         build(v * 2 + 2, m, r);
    307         recalc(v);               
    308     }
    309 }
    310 
    311 void upd(int v, int l, int r, int pos, int val)
    312 {
    313     if(l == r - 1)
    314     {
    315         if(val == 0) t[v] = ZERO;
    316         else t[v] = ONE;
    317     }
    318     else
    319     {
    320         int m = (l + r) / 2;
    321         if(pos < m) upd(v * 2 + 1, l, m, pos, val);
    322         else upd(v * 2 + 2, m, r, pos, val);
    323         recalc(v);
    324     }
    325 }
    326 
    327 int main()
    328 {
    329     ios_base::sync_with_stdio(0);
    330     cin.tie(0);
    331     int n;
    332     cin >> n;
    333     vector<vector<pair<int, int>>> v(N);
    334     for(int i = 0; i < n; i++)
    335     {
    336         int l, r;
    337         cin >> l >> r;
    338         v[l].push_back(make_pair(1, i));
    339         v[r + 1].push_back(make_pair(0, i));
    340     }    
    341     build(0, 0, n - 1);
    342     int cur = 0;
    343     int ans = 0;
    344     for(int i = 0; i <= 300000; i++)
    345     {
    346         for(auto x : v[i])
    347         {
    348             if(x.second == 0) cur = x.first;
    349             else upd(0, 0, n - 1, x.second - 1, x.first);
    350         }
    351         ans = (ans + t[0][cur][1]) % MOD;
    352     }
    353     cout << ans << endl;
    354 }
    355 ```
    356 
    357 [1743G - Antifibonacci Cut](/contest/1743/problem/G "Educational Codeforces Round 137 (Rated for Div. 2)")
    358 
    359 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    360 
    361 **Tutorial**
    362 
    363 Tutorial is loading...
    364 
    365 **Solution (BledDest)**
    366 
    367 ```
    368 #include<bits/stdc++.h>
    369 
    370 using namespace std;
    371 
    372 const int MOD = 998244353;
    373 
    374 int add(int x, int y)
    375 {
    376     x += y;
    377     while(x >= MOD) x -= MOD;
    378     while(x < 0) x += MOD;
    379     return x;
    380 }
    381 
    382 int sub(int x, int y)
    383 {
    384     return add(x, MOD - y);
    385 }
    386 
    387 int expected(int mask)
    388 {
    389     if(mask & 2) return 0;
    390     return 1;
    391 }
    392 
    393 int last_bit(int x)
    394 {
    395     if(x == 0) return -1;
    396     return x - (x & (x - 1));
    397 }
    398 
    399 bool go(int& a, int x)
    400 {
    401     if(expected(a) != x)
    402     {
    403         a = 1 << x;
    404         return false;    
    405     }
    406     a ^= (1 << x);
    407     while(true)
    408     {
    409         int b = last_bit(a);
    410         int c = last_bit(a - b);
    411         if(c == 2 * b) a += b;
    412         else break;
    413     }
    414     return true;
    415 }
    416 
    417 bool is_fib(int a)
    418 {
    419     return a == last_bit(a);
    420 }
    421 
    422 vector<pair<int, int>> go(const vector<pair<int, int>>& a, int x)
    423 {
    424     vector<pair<int, int>> nw;
    425     for(auto b : a)
    426     {
    427         int cost = b.first;
    428         int seqn = b.second;
    429         if(go(seqn, x)) nw.push_back(make_pair(cost, seqn));
    430     }
    431     return nw;
    432 }
    433 
    434 int main()
    435 {
    436     ios_base::sync_with_stdio(0);
    437     cin.tie(0);
    438     int last = 1, sum = 1;
    439     vector<pair<int, int>> w;
    440     int n;
    441     cin >> n;
    442     for(int i = 0; i < n; i++)
    443     {
    444         string s;
    445         cin >> s;
    446         for(auto x : s)
    447         {
    448             int c = x - '0';
    449             int ndp = sub(sum, last);
    450             w = go(w, c);
    451             for(int j = 0; j < w.size(); j++)
    452             {
    453                 if(is_fib(w[j].second))
    454                     ndp = sub(ndp, w[j].first);
    455             }
    456             if(c == 1) w.push_back(make_pair(last, 2));
    457             sum = add(sum, ndp);
    458             last = ndp;
    459             assert(w.size() <= 60);
    460         }
    461         cout << last << endl;
    462     }
    463 }
    464 ```