Codeforces Round #513 ----- my attempt

Правка en7, от Obsidius, 2018-10-04 17:50:40

A

It's a easy problem. At first you must find out the number of the '8', because all of the phone numbers are began with a '8', so the number of '8' is the max of the phone numbers. Then one of the number contains about 11 different numbers. So the answer is:

min(int(number of '8'), n / 11);

my codes:

#pragma G++ optimize (2)
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <string>
#define INF 0x3f3f3f3f
#define NO 30005
#define MO 100005
typedef long long ll;
//by Oliver
using namespace std;
ll read()
{
	char ch = ' ', last;
	ll ans = 0;
	while (ch < '0' || ch > '9')
		last = ch, ch = getchar();
	while (ch >= '0' && ch <= '9')
		ans = ans * 10 + int(ch - '0'), ch = getchar();
	if (last == '-')
		return -ans;
	return ans;
}
void write(ll x)
{
	if (x >= 10)
		write(x / 10);
	putchar(x % 10 + '0');
}
//head

int n, a[NO], cnt;
//variable

void init()
{
	n = read();
	for (int i = 1; i <= n; i++)
	{
		char x;
		cin >> x;
		a[i] = x - '0';
		cnt += (a[i] == 8);
	}
}
//functions

int main()
{
	init();
	cout << min(cnt, n / 11) << endl;
	return 0;
}
//main

B

If you want to get the most sum of the all digit, you must make the most amount of '9'. So the first number can have the most number of '9'. For example: 100 => 99, 12312 => 9999. Then we just have to get the digit-sum of the rest. The sum of then is the answer. But what if the number is 999? No problem, it can just divided to 998 and 1, it's the same answer as 999 and 0.

my codes:

#pragma G++ optimize (2)
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <string>
#define INF 0x3f3f3f3f
#define NO 30005
#define MO 100005
typedef long long ll;
//by Oliver
using namespace std;
ll read()
{
	char ch = ' ', last;
	ll ans = 0;
	while (ch < '0' || ch > '9')
		last = ch, ch = getchar();
	while (ch >= '0' && ch <= '9')
		ans = ans * 10 + int(ch - '0'), ch = getchar();
	if (last == '-')
		return -ans;
	return ans;
}
void write(ll x)
{
	if (x >= 10)
		write(x / 10);
	putchar(x % 10 + '0');
}
//head

ll n, ans, cnt, tot;
//variable

void init()
{
	n = read();
}
//functions

int main()
{
	init();
	cnt = 9;
	while (cnt < n)
		cnt *= 10, cnt += 9, tot++;
	cnt -= 9, cnt /= 10;
	ans += 9 * tot;
	n -= cnt;
	while (n)
	{
		ans += n % 10;
		n /= 10;
	}
	cout << ans << endl;
	return 0;
}
//main


C

This problem is also not so hard. During the contest, I have already known, that the answer is to get the product of two continued sequences' sum, and time them and get the max of (lena * lenb).

Because:

But I haven't find out that we just need to

get the min of every continued sequence and time it.

by this way is the time enough. (O(n^2))

my codes:

#pragma G++ optimize (2)
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <string>
#define INF 0x3f3f3f3f
#define NO 2005
#define MO 100005
typedef long long ll;
//by Oliver
using namespace std;
ll read()
{
	char ch = ' ', last;
	ll ans = 0;
	while (ch < '0' || ch > '9')
		last = ch, ch = getchar();
	while (ch >= '0' && ch <= '9')
		ans = ans * 10 + int(ch - '0'), ch = getchar();
	if (last == '-')
		return -ans;
	return ans;
}
void write(ll x)
{
	if (x >= 10)
		write(x / 10);
	putchar(x % 10 + '0');
}
//head

ll n, m, a[NO], b[NO], prea[NO], preb[NO], x, A[NO], B[NO], ans;
//variable

void init()
{
	n = read(), m = read();
	for (int i = 1; i <= n; i++)
		a[i] = read(), prea[i] = prea[i - 1] + a[i];
	for (int j = 1; j <= m; j++)
		b[j] = read(), preb[j] = preb[j - 1] + b[j];
	x = read();
}
//functions

int main()
{
	init();
	memset(A, INF, sizeof(A));
	memset(B, INF, sizeof(B));
	for (int i = 1; i <= n; i++)
		for (int j = i; j <= n; j++)
		{
			ll sum = prea[j] - prea[i] + a[i];
			if (sum <= x)
				A[j - i + 1] = min(A[j - i + 1], sum);
		}
	for(int i = 1; i <= m; i++)
		for (int j = i; j <= m; j++)
		{
			ll sum = preb[j] - preb[i] + b[i];
			if(sum <= x)
				B[j - i + 1] = min(B[j - i + 1], sum);
		}
	for (ll i = 1; i <= n; i++)
		for (ll j = 1; j <= m; j++)
			if (A[i] * B[j] <= x)
				ans = max(ans, i * j);
	cout << ans << endl;
	return 0;
}
//main


D

During the contest, I have ignored that the guest can make any number of circle. So I failed once and once. Now is this problem very easy. because for each place the smallest left and smallest right is the best.

Because if another right get the left one, the smallest right one must get another left one. At this case is the sum bigger than before.

So we only need to sort the both left and right, and make them together.

But why can every left and right get together? for example, there are l[1~n] and r[1~n]. they are sorted. Of course we can let l[1] and r[1] together. Then the right side is r[i], we can let l[i] here, then we get r[j] at right side, and so on. There is for sure a time that right side and the left side is a pair. That means the circle is over. We can start then with another circle. By this way, all the guest can sit in some circles.

my codes:

#pragma G++ optimize (2)
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <string>
#define INF 0x3f3f3f3f
#define NO 100005
#define MO 100005
typedef long long ll;
//by Oliver
using namespace std;
ll read()
{
	char ch = ' ', last;
	ll ans = 0;
	while (ch < '0' || ch > '9')
		last = ch, ch = getchar();
	while (ch >= '0' && ch <= '9')
		ans = ans * 10 + int(ch - '0'), ch = getchar();
	if (last == '-')
		return -ans;
	return ans;
}
void write(ll x)
{
	if (x >= 10)
		write(x / 10);
	putchar(x % 10 + '0');
}
//head

ll n, l[NO], r[NO], ans;
//variable

void init()
{
	n = read();
	for (int i = 1; i <= n; i++)
		l[i] = read(), r[i] = read();
	sort(l + 1, l + n + 1);
	sort(r + 1, r + n + 1);
}
//functions

int main()
{
	init();
	for (int i = 1; i <= n; i++)
		ans += max(l[i], r[i]);
	ans += n;
	cout << ans << endl;
	return 0;
}
//main

the problems

Теги attempts

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en7 Английский Obsidius 2018-10-04 17:50:40 0 (published)
en6 Английский Obsidius 2018-10-04 17:42:48 52
en5 Английский Obsidius 2018-10-04 17:40:17 10
en4 Английский Obsidius 2018-10-04 17:39:23 69
en3 Английский Obsidius 2018-10-04 17:25:40 1914
en2 Английский Obsidius 2018-10-04 17:07:05 1932
en1 Английский Obsidius 2018-10-04 16:41:48 2669 Initial revision (saved to drafts)