codeforces-scrape

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

708.md (6499B)


      1 Source: https://codeforces.com/blog/entry/46763
      2 
      3 Tutorial is loading...
      4 
      5 **Code**
      6 
      7 ```
      8 int main() {
      9   int n, b, d;
     10   std::cin >> n >> b >> d;
     11 
     12   int current_size = 0;
     13   int result = 0;
     14   int x;
     15   for (; n > 0; --n) {
     16     std::cin >> x;
     17     if (x > b) {
     18       continue;
     19     }
     20     current_size += x;
     21     if (current_size > d) {
     22       ++result;
     23       current_size = 0;
     24     }
     25   }
     26 
     27   std::cout << result << "\n";
     28   return 0;
     29 }
     30 ```
     31 
     32 Tutorial is loading...
     33 
     34 **Code**
     35 
     36 ```
     37 const int MAXN = 100000;
     38 
     39 int x[MAXN];
     40 
     41 int main() {
     42   int n, A;
     43   scanf("%d %d", &n, &A);
     44   if (n == 1) {
     45     printf("0\n");
     46     return 0;
     47   }
     48   for (int i = 0; i < n; i++) {
     49     scanf("%d", &x[i]);
     50   }
     51   int first_max = -2e6;
     52   int second_max = -2e6;
     53   int first_min = 2e6;
     54   int second_min = 2e6;
     55 
     56   for (int i = 0; i < n; i++) {
     57     if (x[i] > second_max) {
     58       second_max = x[i];
     59       if (second_max > first_max) {
     60         swap(second_max, first_max);
     61       }
     62     }
     63     if (x[i] < second_min) {
     64       second_min = x[i];
     65       if (second_min < first_min) {
     66         swap(second_min, first_min);
     67       }
     68     }
     69   }
     70   printf("%d\n", min(first_max - second_min + min(abs(A - first_max), abs(A - second_min)),
     71                      second_max - first_min + min(abs(A - second_max), abs(A - first_min))));
     72 
     73   return 0;
     74 }
     75 ```
     76 
     77 Tutorial is loading...
     78 
     79 **Code**
     80 
     81 ```
     82 void solve() {
     83   string s;
     84   cin >> s;
     85   for (int i = 0; i < s.length(); ++i) {
     86     if (s[i] == 'a') {
     87       continue;
     88     }
     89     int j = i + 1;
     90     while (j < s.length() && s[j] != 'a') {
     91       ++j;
     92     }
     93     for (int r = i; r < j; ++r) {
     94       --s[r];
     95     }
     96     cout << s << "\n";
     97     return;
     98   }
     99 
    100   s.back() = 'z';
    101   cout << s << "\n";
    102 
    103 }
    104 ```
    105 
    106 Tutorial is loading...
    107 
    108 **Code**
    109 
    110 ```
    111 void imp() {
    112   cout << "Impossible\n";
    113   exit(0);
    114 }
    115 
    116 ll invtriange(ll x) {
    117   ll l = 1, r = 1000000;
    118   while (r - l > 1) {
    119     ll m = (l + r) / 2;
    120     if (m * (m - 1) / 2 > x) r = m;
    121     else l = m;
    122   }
    123   if (l * (l - 1) / 2 != x) {
    124     imp();
    125   }
    126   return l;
    127 }
    128 
    129 int main() {
    130   vvl a(2, vl(2));
    131   for (int i = 0; i < 2; ++i) for (int j = 0; j < 2; ++j) {
    132     cin >> a[i][j];
    133   }
    134   if (a[0][0] + a[0][1] + a[1][0] + a[1][1] == 0) {
    135     cout << "0\n";
    136     return 0;
    137   }
    138   ll c0 = invtriange(a[0][0]);
    139   ll c1 = invtriange(a[1][1]);
    140   if (a[0][0] == 0 || a[1][1] == 0) {
    141     if (a[0][1] + a[1][0] == 0) {
    142       if (c0 == 1) c0 = 0;
    143       if (c1 == 1) c1 = 0;
    144       cout << string(c0, '0') << string(c1, '1');
    145       return 0;
    146     }
    147   }
    148   if (c0 * c1 != a[0][1] + a[1][0]) {
    149     imp();
    150   }
    151   string s(c0 + c1, '0');
    152   for (int i = 0; i < s.size(); ++i) {
    153     if (c0 == 0 || a[0][1] < c1) {
    154       s[i] = '1';
    155       a[1][0] -= c0;
    156       --c1;
    157     } else {
    158       a[0][1] -= c1;
    159       --c0;
    160     }
    161   }
    162   cout << s << endl;
    163   return 0;
    164 }
    165 ```
    166 
    167 Tutorial is loading...
    168 
    169 **Code**
    170 
    171 ```
    172 int n;
    173 vector<vector<int>> g;
    174 vector<int> cnt;
    175 
    176 int min_mx = 1e9;
    177 int center = -1;
    178 
    179 void dfs(int v, int p) {
    180 	cnt[v] = 1;
    181 	int mx = 0;
    182 	for (int to : g[v]) {
    183 		if (to == p) {
    184 			continue;
    185 		}
    186 		dfs(to, v);
    187 		cnt[v] += cnt[to];
    188 		mx = max(mx, cnt[to]);
    189 	}
    190 	mx = max(mx, n - cnt[v]);
    191 	if (mx < min_mx) {
    192 		min_mx = mx;
    193 		center = v;
    194 	}
    195 }
    196 
    197 vector<pair<int, int>> subtrees;
    198 vector<int> ans;
    199 
    200 void dfs1(int v, int p, int sum_other, int prev) {
    201 	if (sum_other <= n / 2) {
    202 		ans[v] = 1;
    203 	}
    204 	for (int i = 0; i < 2 && i < subtrees.size(); ++i) {
    205 		if (subtrees[i].second == prev) {
    206 			continue;
    207 		}
    208 		if (n - cnt[v] - subtrees[i].first <= n / 2) {
    209 			ans[v] = 1;
    210 		}
    211 	}
    212 	for (int to : g[v]) {
    213 		if (to == p) {
    214 			continue;
    215 		}
    216 		dfs1(to, v, sum_other, prev);
    217 	}
    218 }
    219 
    220 void solve() {
    221 	cin >> n;
    222 	g.resize(n);
    223 	cnt.assign(n, 0);
    224 	for (int i = 1; i < n; ++i) {
    225 		int a, b;
    226 		cin >> a >> b;
    227 		--a; --b;
    228 		g[a].push_back(b);
    229 		g[b].push_back(a);
    230 	}
    231 	dfs(0, 0);
    232 
    233 	assert(center != -1);
    234 	ans.assign(n, 0);
    235 	ans[center] = 1;
    236 	dfs(center, center);
    237 	int sum_all = 0;
    238 	for (int to : g[center]) {
    239 		subtrees.emplace_back(cnt[to], to);
    240 		sum_all += cnt[to];
    241 	}
    242 	sort(all(subtrees));
    243 	reverse(all(subtrees));
    244 
    245 	for (int to : g[center]) {
    246 		dfs1(to, center, n - cnt[to], to);
    247 	}
    248 
    249 	for (int i = 0; i < n; ++i) {
    250 		cout << ans[i] << ' ';
    251 	}
    252 	cout << "\n";
    253 
    254 }
    255 ```
    256 
    257 Tutorial is loading...
    258 
    259 **Code**
    260 
    261 ```
    262 class FixFlow {
    263 public:
    264 	void solve(std::istream& in, std::ostream& out) {
    265 		int n, m;
    266 		in >> n >> m;
    267 		int s = n;
    268 		int t = n + 1;
    269 		MinCostFlow<int, int> flow(n + 2);
    270 		vector<int> balance(n);
    271 		int INF = 1000000000;
    272 		flow.addEdge((size_t) (n - 1), 0, INF, 0);
    273 
    274 		int defaultAnswer = 0;
    275 		for (int i: range(m)) {
    276 			int a, b, c, f;
    277 			in >> a >> b >> c >> f;
    278 			--a, --b;
    279 			balance[a] += f;
    280 			balance[b] -= f;
    281 			if (f <= c) {
    282 				flow.addEdge(a, b, c - f, 1);
    283 				flow.addEdge(a, b, INF, 2);
    284 				flow.addEdge(b, a, f, 1);
    285 			} else {
    286 				// f > c
    287 				defaultAnswer += f - c;
    288 				flow.addEdge(a, b, INF, 2);
    289 				flow.addEdge(b, a, f - c, 0);
    290 				flow.addEdge(b, a, c, 1);
    291 			}
    292 		}
    293 
    294 		int sumB = 0;
    295 		for (int i: range(n)) {
    296 			if (balance[i] > 0) {
    297 				flow.addEdge(i, t, balance[i], 0);
    298 				sumB += balance[i];
    299 			} else {
    300 				flow.addEdge(s, i, -balance[i], 0);
    301 			}
    302 		}
    303 
    304 		auto res = flow.findFlow(s, t, MinCostMaxFlowStrategy());
    305 		assert(res.flow == sumB);
    306 		out << res.cost + defaultAnswer << "\n";
    307 	}
    308 };
    309 ```
    310 
    311 Tutorial is loading...
    312 
    313 **Code**
    314 
    315 ```
    316 class MAI {
    317 public:
    318 	void solve(std::istream& in, std::ostream& out) {
    319 		int N, m;
    320 		int a, b;
    321 		int k;
    322 		in >> N >> m >> a >> b >> k;
    323 		using Z = ZnConst<1000000007>;
    324 		Z p = Z::valueOf(a) / b;
    325 		Z q = 1 - p;
    326 
    327 		// dp[r'] = sum l < r <= r' d[l][r]
    328 		vector<Z> dp(m + 1, Z());
    329 		dp[m] = 1;
    330 
    331 		vector<Z> powersP(k + 1), powersQ(k + 1);
    332 		powersP[0] = powersQ[0] = 1;
    333 		for (int i: range(k)) {
    334 			powersP[i + 1] = powersP[i] * p;
    335 			powersQ[i + 1] = powersQ[i] * q;
    336 		}
    337 
    338 		vector<Z> fact = factorials<Z>(k + 1);
    339 		vector<Z> invfact = fact;
    340 		for (auto& x: invfact) {
    341 			x = 1 / x;
    342 		}
    343 
    344 		auto get_p_one_side = [&](int l) {
    345 			if (l > k) {
    346 				return Z();
    347 			}
    348 			return powersP[l] * powersQ[k - l] * fact[k] * invfact[l] * invfact[k - l];
    349 		};
    350 
    351 		for (int iter: range(N)) {
    352 			vector<Z> dp_one(m + 1, Z());
    353 			Z sumPl, sumPlDpl;
    354 
    355 			for (int r: inclusiveRange(m)) {
    356 				//new_d[l][r] = p[l] * p[n - r] * (have_something - dp[l] - dp[n - r])
    357 				Z have_something = dp.back();
    358 				dp_one[r] = get_p_one_side(m - r) * (
    359 						have_something * sumPl - sumPlDpl - sumPl * dp[m - r]
    360 				);
    361 				sumPl += get_p_one_side(r);
    362 				sumPlDpl += get_p_one_side(r) * dp[r];
    363 			}
    364 
    365 			for (int i: range(m)) {
    366 				dp_one[i + 1] += dp_one[i];
    367 			}
    368 
    369 			dp = move(dp_one);
    370 		}
    371 
    372 		out << dp.back();
    373 	}
    374 };
    375 ```