codeforces-scrape

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

1613.md (8746B)


      1 Source: https://codeforces.com/blog/entry/97467
      2 
      3 [1613A - Long Comparison](/contest/1613/problem/A "Educational Codeforces Round 118 (Rated for Div. 2)")
      4 
      5 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
      6 
      7 **Tutorial**
      8 
      9 Tutorial is loading...
     10 
     11 **Solution (awoo)**
     12 
     13 ```
     14 #include <bits/stdc++.h>
     15  
     16 using namespace std;
     17  
     18 int main(){
     19 	int t;
     20 	cin >> t;
     21 	while (t--){
     22 		long long x1, x2;
     23 		int p1, p2;
     24 		cin >> x1 >> p1 >> x2 >> p2;
     25 		int mn = min(p1, p2);
     26 		p1 -= mn;
     27 		p2 -= mn;
     28 		if (p1 >= 7)
     29 			cout << ">" << endl;
     30 		else if (p2 >= 7)
     31 			cout << "<" << endl;
     32 		else{
     33 			for (int i = 0; i < p1; ++i) x1 *= 10;
     34 			for (int i = 0; i < p2; ++i) x2 *= 10;
     35 			if (x1 < x2)
     36 				cout << "<" << endl;
     37 			else if (x1 > x2)
     38 				cout << ">" << endl;
     39 			else
     40 				cout << "=" << endl;
     41 		}
     42 	}
     43 }
     44 ```
     45 
     46 [1613B - Absent Remainder](/contest/1613/problem/B "Educational Codeforces Round 118 (Rated for Div. 2)")
     47 
     48 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
     49 
     50 **Tutorial**
     51 
     52 Tutorial is loading...
     53 
     54 **Solution (Neon)**
     55 
     56 ```
     57 #include <bits/stdc++.h>
     58 
     59 using namespace std;
     60 
     61 int main() {
     62   int t;
     63   cin >> t;
     64   while (t--) {
     65     int n;
     66     cin >> n;
     67     vector<int> a(n);
     68     for (int &x : a) cin >> x;
     69     int mn = *min_element(a.begin(), a.end());
     70     for (int i = 0, k = 0; k < n / 2; ++i) if (a[i] != mn) {
     71       cout << a[i] << ' ' << mn << '\n';
     72       k += 1;
     73     }
     74   }
     75 }
     76 ```
     77 
     78 [1613C - Poisoned Dagger](/contest/1613/problem/C "Educational Codeforces Round 118 (Rated for Div. 2)")
     79 
     80 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
     81 
     82 **Tutorial**
     83 
     84 Tutorial is loading...
     85 
     86 **Solution (Neon)**
     87 
     88 ```
     89 #include <bits/stdc++.h>
     90 
     91 using namespace std;
     92 
     93 using li = long long;
     94 
     95 int main() {
     96   int t;
     97   cin >> t;
     98   while (t--) {
     99     int n;
    100     li h;
    101     cin >> n >> h;
    102     vector<li> a(n);
    103     for (li &x : a) cin >> x;
    104     li l = 1, r = 1e18;
    105     while (l <= r) {
    106       li m = (l + r) / 2;
    107       li sum = m;
    108       for (int i = 0; i < n - 1; ++i) 
    109         sum += min(m, a[i + 1] - a[i]);
    110       if (sum < h) l = m + 1;
    111       else r = m - 1;
    112     }
    113     cout << r + 1 << '\n';
    114   }
    115 }
    116 ```
    117 
    118 [1613D - MEX Sequences](/contest/1613/problem/D "Educational Codeforces Round 118 (Rated for Div. 2)")
    119 
    120 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    121 
    122 **Tutorial**
    123 
    124 Tutorial is loading...
    125 
    126 **Solution (Neon)**
    127 
    128 ```
    129 #include <bits/stdc++.h>
    130 
    131 using namespace std;
    132 
    133 const int MOD = 998244353;
    134 
    135 int add(int x, int y) {
    136   x += y;
    137   if (x >= MOD) x -= MOD;
    138   return x;
    139 }
    140 
    141 int main() {
    142   int t;
    143   scanf("%d", &t);
    144   while (t--) {
    145     int n;
    146     scanf("%d", &n);
    147     vector<int> dp1(n + 2), dp2(n + 2);
    148     dp1[0] = 1;
    149     while (n--) {
    150       int x;
    151       scanf("%d", &x);
    152       dp1[x + 1] = add(dp1[x + 1], dp1[x + 1]);
    153       dp1[x + 1] = add(dp1[x + 1], dp1[x]);
    154       if (x > 0) dp2[x - 1] = add(dp2[x - 1], dp2[x - 1]);
    155       if (x > 0) dp2[x - 1] = add(dp2[x - 1], dp1[x - 1]);
    156       dp2[x + 1] = add(dp2[x + 1], dp2[x + 1]);
    157     }
    158     int ans = 0;
    159     for (int x : dp1) ans = add(ans, x);
    160     for (int x : dp2) ans = add(ans, x);
    161     printf("%d\n", add(ans, MOD - 1));
    162   }
    163 }
    164 ```
    165 
    166 [1613E - Crazy Robot](/contest/1613/problem/E "Educational Codeforces Round 118 (Rated for Div. 2)")
    167 
    168 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    169 
    170 **Tutorial**
    171 
    172 Tutorial is loading...
    173 
    174 **Solution (awoo)**
    175 
    176 ```
    177 #include <bits/stdc++.h>
    178 
    179 #define forn(i, n) for (int i = 0; i < int(n); i++)
    180 
    181 using namespace std;
    182 
    183 struct cell{
    184 	int x, y;
    185 };
    186 
    187 int dx[] = {-1, 0, 1, 0};
    188 int dy[] = {0, 1, 0, -1};
    189 
    190 int main() {
    191 	int t;
    192 	cin >> t;
    193 	while (t--){
    194 		int n, m;
    195 		cin >> n >> m;
    196 		vector<string> s(n);
    197 		int lx = -1, ly = -1;
    198 		forn(i, n){
    199 			cin >> s[i];
    200 			forn(j, m) if (s[i][j] == 'L'){
    201 				lx = i;
    202 				ly = j;
    203 			}
    204 		}
    205 		auto in = [&](int x, int y){
    206 			return 0 <= x && x < n && 0 <= y && y < m;
    207 		};
    208 		vector<vector<int>> d(n, vector<int>(m, 0));
    209 		forn(x, n) forn(y, m) if (s[x][y] == '.'){
    210 			forn(i, 4){
    211 				int nx = x + dx[i];
    212 				int ny = y + dy[i];
    213 				d[x][y] += in(nx, ny) && s[nx][ny] != '#';
    214 			}
    215 		}
    216 		queue<cell> q;
    217 		vector<vector<char>> used(n, vector<char>(m, 0));
    218 		q.push({lx, ly});
    219 		used[lx][ly] = true;
    220 		while (!q.empty()){
    221 			int x = q.front().x;
    222 			int y = q.front().y;
    223 			q.pop();
    224 			forn(i, 4){
    225 				int nx = x + dx[i];
    226 				int ny = y + dy[i];
    227 				if (!in(nx, ny) || s[nx][ny] == '#' || used[nx][ny]) continue;
    228 				--d[nx][ny];
    229 				if (d[nx][ny] <= 1){
    230 					used[nx][ny] = true;
    231 					q.push({nx, ny});
    232 				}
    233 			}
    234 		}
    235 		forn(i, n){
    236 			forn(j, m) if (s[i][j] == '.' && used[i][j])
    237 				s[i][j] = '+';
    238 			cout << s[i] << "\n";
    239 		}
    240 	}
    241 	return 0;
    242 }
    243 ```
    244 
    245 [1613F - Tree Coloring](/contest/1613/problem/F "Educational Codeforces Round 118 (Rated for Div. 2)")
    246 
    247 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    248 
    249 **Tutorial**
    250 
    251 Tutorial is loading...
    252 
    253 **Solution (BledDest)**
    254 
    255 ```
    256 #include <bits/stdc++.h>
    257 
    258 using namespace std;
    259 
    260 #define forn(i, n) for (int i = 0; i < int(n); ++i)
    261 #define fore(i, l, r) for (int i = int(l); i < int(r); ++i)
    262 #define sz(a) int((a).size())
    263 
    264 const int MOD = 998244353;
    265 
    266 struct Mint
    267 {
    268   int val;
    269 
    270   bool operator==(const Mint& other)
    271   {
    272     return val == other.val;
    273   }
    274 
    275   Mint operator+(const Mint& other)
    276   {
    277     int res = val + other.val;
    278     while(res >= MOD) res -= MOD;
    279     while(res < 0) res += MOD;
    280     return Mint(res);
    281   }
    282 
    283   Mint operator-(const Mint& other)
    284   {
    285     int res = val - other.val;
    286     while(res >= MOD) res -= MOD;
    287     while(res < 0) res += MOD;
    288     return Mint(res);  
    289   }
    290 
    291   Mint operator*(const Mint& other)
    292   {
    293     return Mint((val * 1ll * other.val) % MOD);
    294   }
    295 
    296   Mint pow(int y)
    297   {
    298     Mint z(1);
    299     Mint x(val);
    300     while(y > 0)
    301     {
    302       if(y % 2 == 1) z = z * x;
    303       x = x * x;
    304       y /= 2;
    305     }
    306     return z;
    307   }
    308 
    309   Mint operator/(const Mint& other)
    310   {
    311     return Mint(val) * Mint(other.val).pow(MOD - 2);
    312   }
    313 
    314   Mint() {
    315       val = 0;
    316   };
    317   Mint(int x)
    318   {
    319     while(x >= MOD) x -= MOD;
    320     while(x < 0) x += MOD;
    321     val = x;
    322   };
    323 };
    324 
    325 ostream& operator<<(ostream& out, const Mint& x)
    326 {
    327   return out << x.val;
    328 }
    329 
    330 const int g = 3;
    331 const int LOGN = 19;
    332 
    333 vector<Mint> w[LOGN];
    334 vector<int> rv[LOGN];
    335 
    336 void prepare() {
    337   Mint wb = Mint(g).pow((MOD - 1) / (1 << LOGN));
    338   forn(st, LOGN - 1) {
    339     w[st].assign(1 << st, 1);
    340     Mint bw = wb.pow(1 << (LOGN - st - 1));
    341     Mint cw = 1;
    342     forn(k, 1 << st) {
    343       w[st][k] = cw;
    344       cw = cw * bw;
    345     }
    346   }
    347   forn(st, LOGN) {
    348     rv[st].assign(1 << st, 0);
    349     if (st == 0) {
    350       rv[st][0] = 0;
    351       continue;
    352     }
    353     int h = (1 << (st - 1));
    354     forn(k, 1 << st)
    355       rv[st][k] = (rv[st - 1][k & (h - 1)] << 1) | (k >= h);
    356   }
    357 }
    358 
    359 void ntt(vector<Mint> &a, bool inv) {
    360   int n = sz(a);
    361   int ln = __builtin_ctz(n);
    362   forn(i, n) {
    363     int ni = rv[ln][i];
    364     if (i < ni) swap(a[i], a[ni]);
    365   }
    366   forn(st, ln) {
    367     int len = 1 << st;
    368     for (int k = 0; k < n; k += (len << 1)) {
    369       fore(pos, k, k + len){
    370         Mint l = a[pos];
    371         Mint r = a[pos + len] * w[st][pos - k];
    372         a[pos] = l + r;
    373         a[pos + len] = l - r;
    374       }
    375     }
    376   }
    377   if (inv) {
    378     Mint rn = Mint(n).pow(MOD - 2);
    379     forn(i, n) a[i] = a[i] * rn;
    380     reverse(a.begin() + 1, a.end());
    381   }
    382 }
    383 
    384 vector<Mint> mul(vector<Mint> a, vector<Mint> b) {
    385   int cnt = 1 << (32 - __builtin_clz(sz(a) + sz(b) - 1));
    386   a.resize(cnt);
    387   b.resize(cnt);
    388   ntt(a, false);
    389   ntt(b, false);
    390   vector<Mint> c(cnt);
    391   forn(i, cnt) c[i] = a[i] * b[i];
    392   ntt(c, true);
    393   return c;
    394 }
    395 
    396 vector<Mint> norm(vector<Mint> a)
    397 {
    398   while(a.size() > 1 && a.back() == Mint(0))
    399     a.pop_back();
    400   return a;
    401 }
    402 
    403 const int N = 250043;
    404 vector<int> G[N];
    405 int d[N];
    406 
    407 Mint fact[N * 2];
    408 Mint rev[N * 2];
    409 
    410 void dfs(int x, int p)
    411 {
    412   if(p != x) d[p]++;
    413   for(auto y : G[x]) if(y != p) dfs(y, x);
    414 }
    415 
    416 Mint C(int n, int k)
    417 {
    418   return fact[n] * rev[k] * rev[n - k];
    419 }
    420 
    421 int main()
    422 {
    423   prepare();
    424   fact[0] = Mint(1);
    425   for(int i = 1; i < N * 2; i++) fact[i] = fact[i - 1] * i;
    426   for(int i = 0; i < N * 2; i++) rev[i] = Mint(1) / fact[i];
    427   int n;
    428   scanf("%d", &n);
    429   for(int i = 0; i < n - 1; i++)
    430   {
    431     int x, y;
    432     scanf("%d %d", &x, &y);
    433     --x;
    434     --y;
    435     G[x].push_back(y);
    436     G[y].push_back(x);  
    437   }
    438   dfs(0, 0);
    439   vector<vector<Mint>> cur;
    440   for(int i = 0; i < n; i++)
    441     if(d[i] > 0)
    442       cur.push_back(vector<Mint>({Mint(1), Mint(d[i])}));
    443   while(cur.size() > 1)
    444   {
    445     vector<vector<Mint>> ncur;
    446     for(int i = 0; i + 1 < cur.size(); i += 2)
    447       ncur.push_back(norm(mul(cur[i], cur[i + 1])));
    448     if(cur.size() % 2 == 1) ncur.push_back(cur.back());
    449     cur = ncur;  
    450   }
    451   Mint ans = 0;
    452   for(int i = 0; i < cur[0].size(); i++)
    453   {
    454     if(i % 2 == 0) ans = ans + cur[0][i] * fact[n - i];
    455     else ans = ans - cur[0][i] * fact[n - i];
    456   }
    457   cout << ans << endl;
    458 }
    459 ```