codeforces-scrape

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

913.md (17652B)


      1 Source: https://codeforces.com/blog/entry/56992
      2 
      3 Here is the tutorial of Hello 2018. Enjoy!
      4 
      5 **Modular Exponentiation**
      6 
      7 Problem writer: [tourist](/profile/tourist "Legendary Grandmaster tourist")
      8 
      9 Tutorial is loading...
     10 
     11 **Solution**
     12 
     13 ```
     14 #include <bits/stdc++.h>
     15 
     16 using namespace std;
     17 
     18 int main() {
     19   int n, m;
     20   scanf("%d %d", &n, &m);
     21   printf("%d\n", n >= 31 ? m : m % (1 << n));
     22   return 0;
     23 }
     24 ```
     25 
     26 **Christmas Spruce**
     27 
     28 Problem writer: [budalnik](/profile/budalnik "Grandmaster budalnik")
     29 
     30 Tutorial is loading...
     31 
     32 **C++ solution**
     33 
     34 ```
     35 #include <bits/stdc++.h>
     36 
     37 using namespace std;
     38 
     39 int main() {
     40   int n;
     41   cin >> n;
     42   vector<int> p(n), deg(n);
     43   for (int i = 1; i < n; i++) {
     44     cin >> p[i];
     45     p[i]--;
     46     deg[p[i]]++;
     47   }
     48   vector<int> sons_leaves(n);
     49   for (int i = 0; i < n; i++) {
     50     if (deg[i] == 0) {
     51       sons_leaves[p[i]]++;
     52     }
     53   }
     54   for (int i = 0; i < n; i++) {
     55     if (deg[i] > 0 && sons_leaves[i] < 3) {
     56       puts("No");
     57       return 0;
     58     }
     59   }
     60   puts("Yes");
     61   return 0;
     62 }
     63 ```
     64 
     65 **Python solution**
     66 
     67 ```
     68 n = int(input())
     69 p = [int(input()) - 1 for _ in range(n - 1)]
     70 leafs = list(filter(lambda x: not x in p, range(n)))
     71 lp = [x for i, x in enumerate(p) if i + 1 in leafs]
     72 x = min(lp.count(k) for k in p)
     73 print("Yes" if x >= 3 else "No")
     74 ```
     75 
     76 **Party Lemonade**
     77 
     78 Problem writer: [tourist](/profile/tourist "Legendary Grandmaster tourist")
     79 
     80 Tutorial is loading...
     81 
     82 **Solution**
     83 
     84 ```
     85 #include <bits/stdc++.h>
     86 
     87 using namespace std;
     88 
     89 int main() {
     90   int n, L;
     91   scanf("%d %d", &n, &L);
     92   vector<int> c(n);
     93   for (int i = 0; i < n; i++) {
     94     scanf("%d", &c[i]);
     95   }
     96   for (int i = 0; i < n - 1; i++) {
     97     c[i + 1] = min(c[i + 1], 2 * c[i]);
     98   }
     99   long long ans = (long long) 4e18;
    100   long long sum = 0;
    101   for (int i = n - 1; i >= 0; i--) {
    102     int need = L / (1 << i);
    103     sum += (long long) need * c[i];
    104     L -= need << i;
    105     ans = min(ans, sum + (L > 0) * c[i]);
    106   }
    107   cout << ans << endl;
    108   return 0;
    109 }
    110 ```
    111 
    112 **Too Easy Problems**
    113 
    114 Problem writer: [tourist](/profile/tourist "Legendary Grandmaster tourist")
    115 
    116 Tutorial is loading...
    117 
    118 **Solution with binary search**
    119 
    120 ```
    121 #include <bits/stdc++.h>
    122 
    123 using namespace std;
    124 
    125 int main() {
    126   int n, T;
    127   scanf("%d %d", &n, &T);
    128   vector<int> a(n), t(n);
    129   for (int i = 0; i < n; i++) {
    130     scanf("%d %d", &a[i], &t[i]);
    131   }
    132   vector<int> res;
    133   int low = 0, high = n;
    134   while (low < high) {
    135     int mid = (low + high + 1) >> 1;
    136     vector< pair<int,int> > e;
    137     for (int i = 0; i < n; i++) {
    138       if (a[i] >= mid) {
    139         e.emplace_back(t[i], i);
    140       }
    141     }
    142     sort(e.begin(), e.end());
    143     bool ok = false;
    144     if ((int) e.size() >= mid) {
    145       int sum = 0;
    146       for (int i = 0; i < mid; i++) {
    147         sum += e[i].first;
    148       }
    149       if (sum <= T) {
    150         ok = true;
    151         res.resize(mid);
    152         for (int i = 0; i < mid; i++) {
    153           res[i] = e[i].second;
    154         }
    155       }
    156     }
    157     if (ok) {
    158       low = mid;
    159     } else {
    160       high = mid - 1;
    161     }
    162   }
    163   int sz = (int) res.size();
    164   printf("%d\n%d\n", sz, sz);
    165   for (int i = 0; i < sz; i++) {
    166     if (i > 0) {
    167       putchar(' ');
    168     }
    169     printf("%d", res[i] + 1);
    170   }
    171   printf("\n");
    172   return 0;
    173 }
    174 ```
    175 
    176 **Solution with set**
    177 
    178 ```
    179 #include <bits/stdc++.h>
    180 
    181 using namespace std;
    182 
    183 int main() {
    184   int n, T;
    185   scanf("%d %d", &n, &T);
    186   vector< vector< pair<int, int> > > at(n + 1);
    187   for (int i = 0; i < n; i++) {
    188     int foo, bar;
    189     scanf("%d %d", &foo, &bar);
    190     at[foo].emplace_back(bar, i);
    191   }
    192   vector<int> res;
    193   set< pair<int, int> > s;
    194   int sum = 0;
    195   for (int k = n; k > 0; k--) {
    196     for (auto &p : at[k]) {
    197       sum += p.first;
    198       s.emplace(p);
    199     }
    200     while ((int) s.size() > k) {
    201       sum -= (--s.end())->first;
    202       s.erase(--s.end());
    203     }
    204     if ((int) s.size() == k && sum <= T) {
    205       for (auto &p : s) {
    206         res.push_back(p.second);
    207       }
    208       break;
    209     }
    210   }
    211   int sz = (int) res.size();
    212   printf("%d\n%d\n", sz, sz);
    213   for (int i = 0; i < sz; i++) {
    214     if (i > 0) {
    215       putchar(' ');
    216     }
    217     printf("%d", res[i] + 1);
    218   }
    219   printf("\n");
    220   return 0;
    221 }
    222 ```
    223 
    224 **Logical Expression**
    225 
    226 Problem writer: [budalnik](/profile/budalnik "Grandmaster budalnik")
    227 
    228 Tutorial is loading...
    229 
    230 **Solution 1**
    231 
    232 ```
    233 #include <iostream>
    234 #include <set>
    235 #include <vector>
    236 #include <string>
    237 
    238 using namespace std;
    239 
    240 bool ls(const string& a, const string& b) {
    241 	if (a.length() == b.length()) return a < b;
    242 	return a.length() < b.length();
    243 }
    244 
    245 struct Expression {
    246 	int p, t;
    247 	string e;
    248 
    249 	Expression(string _e, int t_, int _p) : e(_e), t(t_), p(_p) {}
    250 
    251 	bool operator < (const Expression& ex) const {
    252 		if (ex.e == e) {
    253 			if (t != ex.t) {
    254 				return t < ex.t;
    255 			}
    256 			return p < ex.p;
    257 		}
    258 		return ls(e, ex.e);
    259 	}
    260 };
    261 
    262 set<Expression> q;
    263 
    264 const int FULL = 0xff;
    265 const vector<int> B = {1, 2, 4, 8, 16, 32, 64, 128};
    266 const int X_TABLE = B[4] + B[5] + B[6] + B[7];
    267 const int Y_TABLE = B[2] + B[3] + B[6] + B[7];
    268 const int Z_TABLE = B[1] + B[3] + B[5] + B[7];
    269 
    270 string dp[1 << 8][3];
    271 
    272 void add(int pr, const string& s, int mask) {
    273 	if (dp[mask][pr].empty() || ls(s, dp[mask][pr])) {
    274 		dp[mask][pr] = s;
    275 		Expression e(s, mask, pr);
    276 		q.insert(e);
    277 	}
    278 }
    279 
    280 int main() {
    281 	add(2, "x", X_TABLE);
    282 	add(2, "y", Y_TABLE);
    283 	add(2, "z", Z_TABLE);
    284 	while (!q.empty()) {
    285 		auto e = *q.begin();
    286 		q.erase(q.begin());
    287 
    288 		if (e.p == 2) {
    289 			add(2, "!" + e.e, ~e.t & FULL);
    290 			add(1, e.e, e.t);
    291 		}
    292 
    293 		if (e.p == 1) {
    294 			for (int mask = 0; mask < FULL; ++mask) {
    295 				if (!dp[mask][2].empty()) {
    296 					add(1, dp[mask][2] + "&" + e.e, mask & e.t);
    297 					add(1, e.e + "&" + dp[mask][2], mask & e.t);
    298 				}
    299 			}
    300 			add(2, "(" + e.e + ")", e.t);
    301 			add(0, e.e, e.t);
    302 		}
    303 
    304 		if (e.p == 0) {
    305 			for (int mask = 0; mask < FULL; ++mask) {
    306 				for (int pr = 1; pr <= 2; ++pr) {
    307 					if (!dp[mask][pr].empty()) {
    308 						add(0, dp[mask][pr] + "|" + e.e, mask | e.t);
    309 						add(0, e.e + "|" + dp[mask][pr], mask | e.t);
    310 					}
    311 				}
    312 			}
    313 			add(2, "(" + e.e + ")", e.t);
    314 		}
    315 	}
    316 
    317 	
    318 	int n;
    319 	cin >> n;
    320 	while (n--) {
    321 		string s;
    322 		cin >> s;
    323 		int mask = 0;
    324 		for (int i = 0; i < 8; ++i) {
    325 			if (s[i] == '1') {
    326 				mask |= (1 << i);
    327 			}
    328 		}
    329 
    330 		cout << dp[mask][0] << endl;
    331 	}
    332 
    333 	return 0;
    334 }
    335 ```
    336 
    337 **Solution 2**
    338 
    339 ```
    340 #include <bits/stdc++.h>
    341 
    342 using namespace std;
    343 
    344 string res[256][3];
    345 bool changed;
    346 
    347 void update(string &a, string &b) {
    348   if (a == "" || (b.length() < a.length() || (b.length() == a.length() && b < a))) {
    349     changed = true;
    350     a = b;
    351   }
    352 }
    353 
    354 int main() {
    355   res[(1 << 4) + (1 << 5) + (1 << 6) + (1 << 7)][0] = "x";
    356   res[(1 << 2) + (1 << 3) + (1 << 6) + (1 << 7)][0] = "y";
    357   res[(1 << 1) + (1 << 3) + (1 << 5) + (1 << 7)][0] = "z";
    358   changed = true;
    359   while (changed) {
    360     changed = false;
    361     for (int i = 0; i < 256; i++) {
    362       for (int j = 0; j < 3; j++) {
    363         if (res[i][j] == "") {
    364           continue;
    365         }
    366         { // op == 0
    367           string s = res[i][j];
    368           if (j > 0) {
    369             s = "(" + s + ")";
    370           }
    371           s = "!" + s;
    372           update(res[i ^ 255][0], s);
    373         }
    374         for (int ii = 0; ii < 256; ii++) {
    375           for (int jj = 0; jj < 3; jj++) {
    376             if (res[ii][jj] == "") {
    377               continue;
    378             }
    379             for (int op = 1; op <= 2; op++) {
    380               string s = res[i][j];
    381               if (j > op) {
    382                 s = "(" + s + ")";
    383               }
    384               string t = res[ii][jj];
    385               if (jj > op) {
    386                 t = "(" + t + ")";
    387               }
    388               string w = s + (op == 1 ? '&' : '|') + t;
    389               update(res[op == 1 ? (i & ii) : (i | ii)][op], w);
    390             }
    391           }
    392         }
    393       }
    394     }
    395   }
    396   int tt;
    397   cin >> tt;
    398   while (tt--) {
    399     string z;
    400     cin >> z;
    401     int mask = 0;
    402     for (int i = 0; i < 8; i++) {
    403       mask |= (z[i] - '0') << i;
    404     }
    405     string best = "";
    406     for (int j = 0; j < 3; j++) {
    407       update(best, res[mask][j]);
    408     }
    409     cout << best << endl;
    410   }
    411   return 0;
    412 }
    413 ```
    414 
    415 **Strongly Connected Tournament**
    416 
    417 Problem writer: [YakutovDmitriy](/profile/YakutovDmitriy "International Master YakutovDmitriy")
    418 
    419 Tutorial is loading...
    420 
    421 **Solution**
    422 
    423 ```
    424 #include <bits/stdc++.h>
    425 
    426 using namespace std;
    427 
    428 const int md = 998244353;
    429 
    430 inline void add(int &a, int b) {
    431   a += b;
    432   if (a >= md) a -= md;
    433 }
    434 
    435 inline void sub(int &a, int b) {
    436   a -= b;
    437   if (a < 0) a += md;
    438 }
    439 
    440 inline int mul(int a, int b) {
    441   return (int) ((long long) a * b % md);
    442 }
    443 
    444 inline int power(int a, long long b) {
    445   int res = 1;
    446   while (b > 0) {
    447     if (b & 1) {
    448       res = mul(res, a);
    449     }
    450     a = mul(a, a);
    451     b >>= 1;
    452   }
    453   return res;
    454 }
    455 
    456 inline int inv(int a) {
    457   return power(a, md - 2);
    458 }
    459 
    460 int main() {
    461   int n, P, Q;
    462   cin >> n >> P >> Q;
    463   int p = mul(P, inv(Q));
    464   vector< vector<int> > p_win(n + 1, vector<int>(n + 1, 0));
    465   p_win[0][0] = 1;
    466   for (int i = 0; i < n; i++) {
    467     for (int j = 0; j <= i; j++) {
    468       add(p_win[i + 1][j], mul(p_win[i][j], power(p, j)));
    469       add(p_win[i + 1][j + 1], mul(p_win[i][j], power((1 - p + md) % md, i - j)));
    470     }
    471   }
    472   vector<int> p_strong(n + 1);
    473   for (int i = 1; i <= n; i++) {
    474     p_strong[i] = 1;
    475     for (int j = 1; j < i; j++) {
    476       sub(p_strong[i], mul(p_strong[j], p_win[i][j]));
    477     }
    478   }
    479   vector<int> res(n + 1);
    480   res[1] = 0;
    481   for (int i = 2; i <= n; i++) {
    482     res[i] = 0;
    483     for (int j = 1; j < i; j++) {
    484       int coeff = mul(p_strong[j], p_win[i][j]);
    485       int games = (res[j] + res[i - j]) % md;
    486       add(games, j * (j - 1) / 2 + j * (i - j));
    487       add(res[i], mul(coeff, games));
    488     }
    489     add(res[i], mul(i * (i - 1) / 2, p_strong[i]));
    490     res[i] = mul(res[i], inv((1 - p_strong[i] + md) % md));
    491   }
    492   cout << res[n] << endl;
    493   return 0;
    494 }
    495 ```
    496 
    497 **Power Substring**
    498 
    499 Problem writer: [YakutovDmitriy](/profile/YakutovDmitriy "International Master YakutovDmitriy")
    500 
    501 Tutorial is loading...
    502 
    503 **Python solution**
    504 
    505 ```
    506 def dlog(x, n):
    507   bigMod = 5 ** n
    508   ans = [None, 0, 1, 3, 2][x % 5]
    509   val = 2 ** ans % bigMod
    510   mod, phi = 5, 4
    511   phiVal = 2 ** phi % bigMod
    512   for i in range(2, n + 1):
    513     nextMod = mod * 5
    514     while val % nextMod != x % nextMod:
    515       val = val * phiVal % bigMod
    516       ans += phi
    517     phi *= 5
    518     phiVal = (phiVal *
    519               phiVal % bigMod *
    520               phiVal % bigMod *
    521               phiVal % bigMod *
    522               phiVal % bigMod)
    523     mod = nextMod
    524   return ans
    525 
    526 def main():
    527   inp = input()
    528   n = len(inp)
    529   a = int(inp)
    530   for m in range(n + 1):
    531     l = a * 10 ** m
    532     x, mod = l, 2 ** (n + m)
    533     if x % mod != 0:
    534       x += mod - x % mod
    535     if x % 5 == 0:
    536       x += mod
    537     if x < l + 10 ** m:
    538       assert x % mod == 0 and x % 5 != 0
    539       x = x // mod
    540       mod = 5 ** (n + m)
    541       print(n + m + dlog(x % mod, n + m))
    542       return
    543   assert False
    544 
    545 if __name__ == '__main__':
    546   cnt = int(input())
    547   for i in range(cnt):
    548     main()
    549 ```
    550 
    551 **C++ solution**
    552 
    553 ```
    554 #include <bits/stdc++.h>
    555 
    556 using namespace std;
    557 
    558 inline long long mul(long long a, long long b, long long md) {
    559   long long res = 0;
    560   while (b > 0) {
    561     if (b & 1) {
    562       res += a; if (res >= md) res -= md;
    563     }
    564     a += a; if (a >= md) a -= md;
    565     b >>= 1;
    566   }
    567   return res;
    568 }
    569 
    570 inline long long power(long long a, long long b, long long md) {
    571   long long res = 1;
    572   while (b > 0) {
    573     if (b & 1) {
    574       res = mul(res, a, md);
    575     }
    576     a = mul(a, a, md);
    577     b >>= 1;
    578   }
    579   return res;
    580 }
    581 
    582 int main() {
    583   int tt;
    584   cin >> tt;
    585   while (tt--) {
    586     long long a;
    587     cin >> a;
    588     int n = (int) to_string(a).length();
    589     for (int m = 0; ; m++) {
    590       long long b = (-a) & ((1LL << (n + m)) - 1);
    591       if ((a + b) % 5 == 0) {
    592         b += (1LL << (n + m));
    593       }
    594       if ((b == 0 && m == 0) || (int) to_string(b).length() <= m) {
    595         long long c = (a + b) >> (n + m);
    596         long long t = vector<long long>{-1, 0, 1, 3, 2}[c % 5];
    597         long long p5 = 5;
    598         for (int i = 1; i < n + m; i++) {
    599           while (power(2, t, p5 * 5) != c % (p5 * 5)) {
    600             t += p5 / 5 * 4;
    601           }
    602           p5 *= 5;
    603         }
    604         t += n + m;
    605         cout << t << endl;
    606         break;
    607       }
    608       a *= 10;
    609     }
    610   }
    611   return 0;
    612 }
    613 ```
    614 
    615 **Don't Exceed**
    616 
    617 Problem writer: [tourist](/profile/tourist "Legendary Grandmaster tourist")
    618 
    619 Tutorial is loading...
    620 
    621 **O(n^5) solution**
    622 
    623 ```
    624 #include <bits/stdc++.h>
    625 
    626 using namespace std;
    627 
    628 const int md = 998244353;
    629 
    630 inline void add(int &a, int b) {
    631   a += b;
    632   if (a >= md) a -= md;
    633 }
    634 
    635 inline void sub(int &a, int b) {
    636   a -= b;
    637   if (a < 0) a += md;
    638 }
    639 
    640 inline int mul(int a, int b) {
    641   return (int) ((long long) a * b % md);
    642 }
    643 
    644 inline int power(int a, long long b) {
    645   int res = 1;
    646   while (b > 0) {
    647     if (b & 1) {
    648       res = mul(res, a);
    649     }
    650     a = mul(a, a);
    651     b >>= 1;
    652   }
    653   return res;
    654 }
    655 
    656 inline int inv(int a) {
    657   return power(a, md - 2);
    658 }
    659 
    660 const int N = 77;
    661 
    662 int C[N][N];
    663 
    664 typedef vector<int> poly;
    665 
    666 poly integrate(poly a) {
    667   poly b = {0};
    668   for (int i = 0; i < (int) a.size(); i++) {
    669     b.push_back(mul(a[i], inv(i + 1)));
    670   }
    671   return b;
    672 }
    673 
    674 void sub(poly &a, poly b) {
    675   while (a.size() < b.size()) {
    676     a.push_back(0);
    677   }
    678   for (int i = 0; i < (int) b.size(); i++) {
    679     sub(a[i], b[i]);
    680   }
    681 }
    682 
    683 poly plug(poly a, int delta) {
    684   // a(x + delta)
    685   poly b(a.size(), 0);
    686   for (int i = 0; i < (int) a.size(); i++) {
    687     for (int j = 0; j <= i; j++) {
    688       add(b[j], mul(a[i], mul(C[i][j], power(delta, i - j))));
    689     }
    690   }
    691   return b;
    692 }
    693 
    694 int eval(poly a, int x) {
    695   int res = 0;
    696   for (int i = (int) a.size() - 1; i >= 0; i--) {
    697     res = mul(res, x);
    698     add(res, a[i]);
    699   }
    700   return res;
    701 }
    702 
    703 const int COEFF = 1000000;
    704 
    705 int main() {
    706   for (int i = 0; i < N; i++) {
    707     for (int j = 0; j < N; j++) {
    708       C[i][j] = (j == 0 ? 1 : (i == 0 ? 0 : (C[i - 1][j] + C[i - 1][j - 1]) % md));
    709     }
    710   }
    711   int n;
    712   cin >> n;
    713   vector<int> x(n), fracs;
    714   for (int i = 0; i < n; i++) {
    715     double foo;
    716     cin >> foo;
    717     x[i] = (int) (foo * COEFF + 0.5);
    718     fracs.push_back(x[i] % COEFF);
    719   }
    720   fracs.push_back(0);
    721   sort(fracs.begin(), fracs.end());
    722   fracs.resize(unique(fracs.begin(), fracs.end()) - fracs.begin());
    723   int cnt = (int) fracs.size();
    724   vector<int> point(n * cnt + 1);
    725   for (int i = 0; i <= n * cnt; i++) {
    726     point[i] = mul(i / cnt * COEFF + fracs[i % cnt], inv(COEFF));
    727   }
    728   vector<int> cut(n);
    729   for (int i = 0; i < n; i++) {
    730     cut[i] = (int) (find(point.begin(), point.end(), mul(x[i], inv(COEFF))) - point.begin());
    731   }
    732   vector<poly> a(n * cnt);
    733   for (int i = 0; i < n * cnt; i++) {
    734     a[i] = {i < min(cnt, cut[0]) ? 1 : 0};
    735   }
    736   for (int id = 1; id < n; id++) {
    737     for (int i = 0; i < n * cnt; i++) {
    738       a[i] = integrate(a[i]);
    739     }
    740     for (int i = n * cnt - 1; i >= 0; i--) {
    741       sub(a[i][0], eval(a[i], point[i]));
    742       for (int j = i - 1; j >= i - cnt && j >= 0; j--) {
    743         add(a[i][0], eval(a[j], point[j + 1]));
    744         if (j > i - cnt) {
    745           sub(a[i][0], eval(a[j], point[j]));
    746         } else {
    747           sub(a[i], plug(a[i - cnt], md - 1));
    748         }
    749       }
    750     }
    751     for (int i = cut[id]; i < n * cnt; i++) {
    752       a[i] = {0};
    753     }
    754   }
    755   int ans = 0;
    756   for (int i = 0; i < n * cnt; i++) {
    757     poly b = integrate(a[i]);
    758     add(ans, eval(b, point[i + 1]));
    759     sub(ans, eval(b, point[i]));
    760   }
    761   printf("%d\n", ans);
    762   return 0;
    763 }
    764 ```
    765 
    766 **O(n^4) solution**
    767 
    768 ```
    769 #include <bits/stdc++.h>
    770 
    771 using namespace std;
    772 
    773 const int md = 998244353;
    774 
    775 inline void add(int &a, int b) {
    776   a += b;
    777   if (a >= md) a -= md;
    778 }
    779 
    780 inline void sub(int &a, int b) {
    781   a -= b;
    782   if (a < 0) a += md;
    783 }
    784 
    785 inline int mul(int a, int b) {
    786   return (int) ((long long) a * b % md);
    787 }
    788 
    789 inline int power(int a, long long b) {
    790   int res = 1;
    791   while (b > 0) {
    792     if (b & 1) {
    793       res = mul(res, a);
    794     }
    795     a = mul(a, a);
    796     b >>= 1;
    797   }
    798   return res;
    799 }
    800 
    801 inline int inv(int a) {
    802   return power(a, md - 2);
    803 }
    804 
    805 typedef vector<int> poly;
    806 
    807 poly integrate(poly a) {
    808   poly b = {0};
    809   for (int i = 0; i < (int) a.size(); i++) {
    810     b.push_back(mul(a[i], inv(i + 1)));
    811   }
    812   return b;
    813 }
    814 
    815 void sub(poly &a, poly b) {
    816   while (a.size() < b.size()) {
    817     a.push_back(0);
    818   }
    819   for (int i = 0; i < (int) b.size(); i++) {
    820     sub(a[i], b[i]);
    821   }
    822 }
    823 
    824 int eval(poly a, int x) {
    825   int res = 0;
    826   for (int i = (int) a.size() - 1; i >= 0; i--) {
    827     res = mul(res, x);
    828     add(res, a[i]);
    829   }
    830   return res;
    831 }
    832 
    833 const int COEFF = 1000000;
    834 
    835 int main() {
    836   int n;
    837   cin >> n;
    838   vector<int> x(n), fracs;
    839   for (int i = 0; i < n; i++) {
    840     double foo;
    841     cin >> foo;
    842     x[i] = (int) (foo * COEFF + 0.5);
    843     fracs.push_back(x[i] % COEFF);
    844   }
    845   fracs.push_back(0);
    846   sort(fracs.begin(), fracs.end());
    847   fracs.resize(unique(fracs.begin(), fracs.end()) - fracs.begin());
    848   int cnt = (int) fracs.size();
    849   vector<int> point(n * cnt + 1);
    850   for (int i = 0; i <= n * cnt; i++) {
    851     point[i] = i / cnt * COEFF + fracs[i % cnt];
    852   }
    853   vector<int> cut(n);
    854   for (int i = 0; i < n; i++) {
    855     cut[i] = (int) (find(point.begin(), point.end(), x[i]) - point.begin());
    856   }
    857   vector<int> sz(n * cnt);
    858   for (int i = 0; i < n * cnt; i++) {
    859     sz[i] = mul((point[i + 1] - point[i] + md) % md, inv(COEFF));
    860   }
    861   vector<poly> a(n * cnt);
    862   vector<int> sum(n * cnt);
    863   for (int i = 0; i < n * cnt; i++) {
    864     a[i] = i < min(cnt, cut[0]) ? vector<int>{0, 1} : vector<int>{0};
    865     sum[i] = a[i].size() == 1 ? 0 : sz[i];
    866   }
    867   for (int id = 1; id < n; id++) {
    868     for (int i = n * cnt - 1; i >= 0; i--) {
    869       if (i >= cut[id]) {
    870         a[i] = {0};
    871         sum[i] = 0;
    872       } else {
    873         for (int j = i - 1; j >= i - cnt && j >= 0; j--) {
    874           add(a[i][0], sum[j]);
    875         }
    876         if (i - cnt >= 0) {
    877           sub(a[i], a[i - cnt]);
    878         }
    879         a[i] = integrate(a[i]);
    880         sum[i] = eval(a[i], sz[i]);
    881       }
    882     }
    883   }
    884   int ans = 0;
    885   for (int i = 0; i < n * cnt; i++) {
    886     add(ans, sum[i]);
    887   }
    888   printf("%d\n", ans);
    889   return 0;
    890 }
    891 ```