codeforces-scrape

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

1886.md (9174B)


      1 Source: https://codeforces.com/blog/entry/121255
      2 
      3 [1886A - Sum of Three](/contest/1886/problem/A "Educational Codeforces Round 156 (Rated for Div. 2)")
      4 
      5 Idea: [fcspartakm](/profile/fcspartakm "Candidate Master fcspartakm")
      6 
      7 **Tutorial**
      8 
      9 Tutorial is loading...
     10 
     11 **Solution (fcspartakm)**
     12 
     13 ```
     14 #include <bits/stdc++.h>
     15 
     16 using namespace std;
     17 
     18 int n;
     19 
     20 inline void read() {
     21 	cin >> n;
     22 }
     23 
     24 inline void solve() {
     25 	for (int x = 1; x <= 20; x++) {
     26 	    for (int y = 1; y <= 20; y++) {
     27 	        if (x + y >= n || x == y) continue;
     28 	        int z = n - x - y;
     29 	        if (z == x || z == y) continue;
     30 	        if (x % 3 == 0 || y % 3 == 0 || z % 3 == 0) {
     31 	            continue;
     32 	        }
     33 	        puts("YES");
     34 	        cout << x << ' ' << y << ' ' << z << endl;
     35 	        return;
     36 	    }
     37 	}
     38 	puts("NO");
     39 }
     40 
     41 int main () {
     42     int t;
     43     cin >> t;
     44     while (t--){
     45         read();
     46         solve();
     47     }
     48 }
     49 ```
     50 
     51 [1886B - Fear of the Dark](/contest/1886/problem/B "Educational Codeforces Round 156 (Rated for Div. 2)")
     52 
     53 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
     54 
     55 **Tutorial**
     56 
     57 Tutorial is loading...
     58 
     59 **Solution (Neon)**
     60 
     61 ```
     62 #include <bits/stdc++.h>
     63  
     64 using namespace std;
     65  
     66 int main() {
     67   auto dist = [](int x1, int y1, int x2, int y2) {
     68     return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
     69   };
     70  
     71   int t;
     72   cin >> t;
     73   while (t--) {
     74     int px, py, ax, ay, bx, by;
     75     cin >> px >> py >> ax >> ay >> bx >> by;
     76     double pa = dist(px, py, ax, ay), pb = dist(px, py, bx, by);
     77     double oa = dist(0, 0, ax, ay), ob = dist(0, 0, bx, by);
     78     double ab = dist(ax, ay, bx, by);
     79     double ans = 1e9;
     80     ans = min(ans, max(pa, oa));
     81     ans = min(ans, max(pb, ob));
     82     ans = min(ans, max({ab / 2, pa, ob}));
     83     ans = min(ans, max({ab / 2, pb, oa}));
     84     cout << setprecision(10) << fixed << ans << '\n';
     85   }
     86 }
     87 ```
     88 
     89 [1886C - Decreasing String](/contest/1886/problem/C "Educational Codeforces Round 156 (Rated for Div. 2)")
     90 
     91 Idea: [Roms](/profile/Roms "Master Roms")
     92 
     93 **Tutorial**
     94 
     95 Tutorial is loading...
     96 
     97 **Solution (Roms)**
     98 
     99 ```
    100 #include <bits/stdc++.h>
    101 
    102 using namespace std;
    103 
    104 const int N = 200000;
    105 
    106 int t;
    107 
    108 int main() {
    109     cin >> t;
    110     for (int tc = 0; tc < t; ++tc) {
    111         string s;
    112         long long pos;
    113         cin >> s >> pos;
    114         --pos;
    115         
    116         int curLen = s.size();
    117         vector <char> st;
    118         bool ok = pos < curLen;
    119         s += '$';
    120         
    121         for (auto c : s) {
    122             while (!ok && st.size() > 0 && st.back() > c) {
    123                 pos -= curLen;
    124                 --curLen;
    125                 st.pop_back();
    126                 
    127                 if(pos < curLen) 
    128                     ok = true;
    129             }
    130             st.push_back(c);
    131         }
    132         
    133         cout << st[pos];
    134     }
    135     return 0;
    136 }
    137 ```
    138 
    139 [1886D - Monocarp and the Set](/contest/1886/problem/D "Educational Codeforces Round 156 (Rated for Div. 2)")
    140 
    141 Idea: [Roms](/profile/Roms "Master Roms")
    142 
    143 **Tutorial**
    144 
    145 Tutorial is loading...
    146 
    147 **Solution (Roms)**
    148 
    149 ```
    150 #include <bits/stdc++.h>
    151 
    152 using namespace std;
    153 
    154 const int MOD = 998244353;
    155 
    156 const int N = 300009;
    157 
    158 int bp(int a, int n) {
    159     int res = 1;
    160     while(n > 0) {
    161         if (n & 1)
    162             res = (res * 1LL * a) % MOD;
    163         a = (a * 1LL * a) % MOD;
    164         n >>= 1;
    165     }
    166     return res;
    167 }
    168 
    169 int n, m;
    170 string s;
    171 int inv[N];
    172 
    173 void upd(int &res, int x) {
    174     res = (res * 1LL * x) % MOD;
    175 }
    176 
    177 int main() {
    178     inv[1] = 1;
    179     for (int i = 2; i < N; ++i){
    180 	    inv[i] = bp(i, MOD - 2);
    181     }
    182     
    183     cin >> n >> m >> s;
    184     
    185     int res = 1, k = n;
    186     bool isZero = false;
    187     for (int i = 0; i < s.size(); ++i) 
    188         if (s[i] == '?') {
    189             if (i == 0) {
    190                 isZero = true;
    191             } else {
    192                 upd(res, i);
    193             }
    194         }
    195     
    196     cout << (isZero? 0 : res) << endl;
    197     
    198     for(int i = 0; i < m; ++i) {
    199         int pos;
    200         char c;
    201         cin >> pos >> c;
    202         --pos;
    203         
    204         if (s[pos] == '?' && (c == '<' || c == '>')) {
    205             if (pos == 0)
    206                 isZero = false;
    207             else
    208                 upd(res, inv[pos]);
    209         } else if ((s[pos] == '<' || s[pos] == '>') && c == '?') {
    210             if (pos == 0)
    211                 isZero = true;
    212             else
    213                 upd(res, pos);
    214         }
    215         
    216         s[pos] = c;
    217         cout << (isZero? 0 : res) << endl;
    218     }
    219     return 0;
    220 }
    221 ```
    222 
    223 [1886E - I Wanna be the Team Leader](/contest/1886/problem/E "Educational Codeforces Round 156 (Rated for Div. 2)")
    224 
    225 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    226 
    227 **Tutorial**
    228 
    229 Tutorial is loading...
    230 
    231 **Solution (awoo)**
    232 
    233 ```
    234 #include <bits/stdc++.h>
    235  
    236 #define forn(i, n) for (int i = 0; i < int(n); i++)
    237  
    238 using namespace std;
    239  
    240 int main() {
    241 	int n, m;
    242 	scanf("%d%d", &n, &m);
    243 	vector<int> a(n), b(m);
    244 	forn(i, n) scanf("%d", &a[i]);
    245 	forn(i, m) scanf("%d", &b[i]);
    246 	vector<int> ord(n);
    247 	iota(ord.begin(), ord.end(), 0);
    248 	sort(ord.begin(), ord.end(), [&a](int i, int j){
    249 		return a[i] > a[j];
    250 	});
    251 	vector<vector<int>> mn(m, vector<int>(n + 2));
    252 	forn(i, m){
    253 		int r = 0;
    254 		forn(l, n + 2){
    255 			r = min(n + 1, max(r, l + 1));
    256 			while (r <= n && a[ord[r - 1]] * (r - l) < b[i]) ++r;
    257 			mn[i][l] = r;
    258 		}
    259 	}
    260 	vector<int> dp(1 << m, n + 1);
    261 	dp[0] = 0;
    262 	vector<int> p(1 << m, -1);
    263 	forn(mask, 1 << m) forn(i, m) if (!((mask >> i) & 1) && dp[mask | (1 << i)] > mn[i][dp[mask]]){
    264 		dp[mask | (1 << i)] = mn[i][dp[mask]];
    265 		p[mask | (1 << i)] = mask;
    266 	}
    267 	int mask = (1 << m) - 1;
    268 	if (dp[mask] > n){
    269 		puts("NO");
    270 		return 0;
    271 	}
    272 	puts("YES");
    273 	vector<vector<int>> ans(n);
    274 	forn(_, m){
    275 		int i = __builtin_ctz(mask ^ p[mask]);
    276 		for (int j = dp[p[mask]]; j < dp[mask]; ++j)
    277 			ans[i].push_back(ord[j]);
    278 		mask = p[mask];
    279 	}
    280 	forn(i, m){
    281 		printf("%d", int(ans[i].size()));
    282 		for (int x : ans[i]) printf(" %d", x + 1);
    283 		puts("");
    284 	}
    285 	return 0;
    286 }
    287 ```
    288 
    289 [1886F - Diamond Theft](/contest/1886/problem/F "Educational Codeforces Round 156 (Rated for Div. 2)")
    290 
    291 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    292 
    293 **Tutorial**
    294 
    295 Tutorial is loading...
    296 
    297 **Solution (Neon)**
    298 
    299 ```
    300 #include <bits/stdc++.h>
    301  
    302 using namespace std;
    303  
    304 const int N = 3003;
    305  
    306 int n;
    307 int k[4];
    308 vector<int> a[4];
    309  
    310 struct segtree {
    311   int sz;
    312   int tot;
    313   vector<int> t, p;
    314   
    315   segtree(int sz) : sz(sz) {
    316     tot = 0;
    317     t = vector<int>(4 * sz);
    318     p = vector<int>(4 * sz);
    319     build(0, 0, sz);
    320   }
    321   
    322   void build(int v, int l, int r) {
    323     if (l + 1 == r) {
    324       t[v] = -l;
    325       return;
    326     }
    327     int m = (l + r) / 2;
    328     build(v * 2 + 1, l, m);
    329     build(v * 2 + 2, m, r);
    330     t[v] = max(t[v * 2 + 1], t[v * 2 + 2]);
    331   }
    332   
    333   void push(int v) {
    334     if (p[v] == 0) return;
    335     if (v + 1 < 2 * sz) {
    336       t[v * 2 + 1] += p[v];
    337       p[v * 2 + 1] += p[v];
    338       t[v * 2 + 2] += p[v];
    339       p[v * 2 + 2] += p[v];
    340       p[v] = 0;
    341     }
    342   } 
    343   
    344   void upd(int v, int l, int r, int L, int R, int x) {
    345     if (L >= R) return;
    346     if (l == L && r == R) {
    347       t[v] += x;
    348       p[v] += x;
    349       return;
    350     }
    351     push(v);
    352     int m = (l + r) / 2;
    353     upd(v * 2 + 1, l, m, L, min(m, R), x);
    354     upd(v * 2 + 2, m, r, max(L, m), R, x);
    355     t[v] = max(t[v * 2 + 1], t[v * 2 + 2]);
    356   }
    357   
    358   void upd(int pos, int x) { 
    359     tot += x;
    360     upd(0, 0, sz, max(0, pos), sz, x);
    361   }
    362   
    363   int get(int v, int l, int r, int L, int R) {
    364     if (L >= R) return -1e9;
    365     if (l == L && r == R) return t[v];
    366     push(v);
    367     int m = (l + r) / 2;
    368     return max(
    369       get(v * 2 + 1, l, m, L, min(m, R)),
    370       get(v * 2 + 2, m, r, max(L, m), R)
    371     );
    372   }
    373   
    374   int get(int L) {
    375     return get(0, 0, sz, max(0, L), sz);
    376   }
    377   
    378   int getBad(int v, int l, int r) {
    379     if (t[v] <= 0) return -1;
    380     if (l + 1 == r) return l;
    381     push(v);
    382     int m = (l + r) / 2;
    383     if (t[v * 2 + 1] > 0) {
    384       return getBad(v * 2 + 1, l, m);
    385     } else {
    386       return getBad(v * 2 + 2, m, r);
    387     }
    388   }
    389   
    390   int getBad() {
    391     return getBad(0, 0, sz);
    392   }
    393 };  
    394  
    395 int main() {
    396   cin >> n;
    397   int sz = 1;
    398   for (int i = 0; i < n; ++i) {
    399     int t, s;
    400     cin >> t >> s;
    401     a[t].push_back(s);
    402     sz = max(sz, s + 1);
    403   }
    404   for (int t = 1; t < 4; ++t) {
    405     sort(a[t].begin(), a[t].end());
    406     k[t] = a[t].size();
    407   }
    408   reverse(a[2].begin(), a[2].end());
    409   int ans = 1e4;
    410   for (int len = 1; len <= k[2] + k[3] + 1; ++len) {
    411     segtree L(sz), R(sz);
    412     multiset<int> used;
    413     for (int x : a[1]) L.upd(x, +1);
    414     for (int x : a[2]) R.upd(x, +1);
    415     for (int x : a[3]) {
    416       L.upd(x - len, +1);
    417       if (L.t[0] <= 0) {
    418         used.insert(x - len);
    419       } else {
    420         L.upd(x - len, -1);
    421         L.upd(x, +1);
    422         R.upd(x, +1);
    423       }
    424     }
    425     for (int i = 0; i <= k[2]; ++i) {
    426       if (L.t[0] <= 0 && R.t[0] <= 0 && R.tot + 1 <= len)
    427         ans = min(ans, n + (k[3] - (int)used.size()) + 2); 
    428       if (i == k[2]) break;
    429       R.upd(a[2][i], -1);
    430       L.upd(a[2][i] - len, +1);
    431       int pos;
    432       while ((pos = L.getBad()) != -1) {
    433         auto it = used.upper_bound(pos);
    434         if (it == used.begin()) break;
    435         --it;
    436         L.upd(*it, -1);
    437         L.upd(*it + len, +1);
    438         R.upd(*it + len, +1);
    439         used.erase(it);
    440       }
    441     }
    442   }
    443   if (ans == 1e4) ans = -1;
    444   cout << ans << '\n';
    445 }
    446 ```