Codeforces Round #273 (Div. 2)_html/css_WEB-ITnose

Codeforces Round #273 (Div. 2)

Question link

A: Sign in, just judge whether the sum is a multiple of 5, pay attention to the case of 0

B : The maximum value is to put 1 ball in each set first, and throw the rest into one set. The minimum value is to divide it equally as much as possible

C: If the three kinds of balls from small to large are a, b, c, then if (a b) 2 <= c, the obvious answer is a b, because c will definitely be leftover. If (a b)2 > c, the optimal (a b c) / 3 can definitely be constructed , because you can certainly use a and b to eliminate c, and control a and b to have a 2-fold relationship or eliminate a pile and make the remaining two piles as similar as possible.

D: dp, first calculate the maximum height h, and then treat each column from 1 to h as an item. You need to select a few of them to form r and find the number of situations. This can be solved with the 01 backpack

Code:

A:

#include <cstdio>#include <cstring>int c, sum = 0;int main() {	for (int i = 0; i < 5; i++) {		scanf("%d", &c);		sum += c;	}	if (sum == 0 || sum % 5) printf("-1\n");	else printf("%d\n", sum / 5);	return 0;}

B:

#include <cstdio>#include <cstring>typedef long long ll;ll n, m;int main() {	scanf("%lld%lld", &n, &m);	ll yu = n - m + 1;	ll Max = yu * (yu - 1) / 2;	yu = n % m;	ll sb = n / m;	ll sbb = sb + 1;	ll Min = 0;	if (sbb % 2) {		Min += yu * (sbb - 1) / 2 * sbb;	} else Min += yu * sbb / 2 * (sbb - 1);	if (sb % 2) {		Min += (m - yu) * (sb - 1) / 2 * sb;	} else Min += (m - yu) * sb / 2 * (sb - 1);	printf("%lld %lld\n", Min, Max);	return 0;}

C:

#include <cstdio>#include <cstring>#include <algorithm>using namespace std;typedef long long ll;ll a[3], ans = 0;int main() {	for (ll i = 0; i < 3; i++)		scanf("%lld", &a[i]);	sort(a, a + 3);	if ((a[0] + a[1]) * 2 >= a[2]) printf("%lld\n", (a[0] + a[1] + a[2]) / 3);	else printf("%lld\n", a[0] + a[1]);	return 0;}

D:

#include <cstdio>#include <cstring>#include <algorithm>using namespace std;typedef long long ll;const int N = 200005;const ll MOD = 1000000007;ll r, g;int n;ll dp[N];int main() {	scanf("%lld%lld", &r, &g);	if (r > g) swap(r, g);	ll sum = 0;	for (int i = 1; ;i++) {		sum += i;		if (sum >= r + g) {			if (sum > r + g) {				sum -= i;				i--;			}			n = i;			break;		}	}	dp[0] = 1;	for (int i = 1; i <= n; i++) {		for (int j = r; j >= i; j--) {			dp[j] = dp[j] + dp[j - i];			if (dp[j] > MOD) dp[j] -= MOD;		}	}	ll sb = 0;	for (int i = 0; i <= r + g - sum; i++) {		if (r < i) break;		sb = (dp[r - i] + sb) % MOD;	}	printf("%lld\n", sb);	return 0;}