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
