A. Phone Numbers
Description
Let’s call a string a phone number if it has length 11 and fits the pattern “8xxxxxxxxxx”, where each “x” is replaced by a digit.
For example, “80123456789” and “80000000000” are phone numbers, while “8012345678” and “79000000000” are not.
You have n cards with digits, and you want to use them to make as many phone numbers as possible. Each card must be used in at most one phone number, and you don’t have to use all cards. The phone numbers do not necessarily have to be distinct.
Input
The first line contains an integer n — the number of cards with digits that you have (1≤n≤100).
The second line contains a string of n digits (characters “0”, “1”, …, “9”) s1,s2,…,sn. The string will not contain any other characters, such as leading or trailing spaces.
Output
If at least one phone number can be made from these cards, output the maximum number of phone numbers that can be made. Otherwise, output 0.
Sample Input
Input
11
00000000008
Output
1
Input
22
0011223344556677889988
Output
2
Input
11
31415926535
Output
0
Hint
In the first example, one phone number, “8000000000”, can be made from these cards.
In the second example, you can make two phone numbers from the cards, for example, “80123456789” and “80123456789”.
In the third example you can’t make any phone number from the given cards.
题意：问你能组成多少个电话号码 像8xxxxxxxxxx的，给你n个卡片，每个卡片只能用一次或者不用
分析：不用考虑电话号码里具体的排列
1：如果给出的卡片没有8或者卡片数量小于11,直接输出0
2：t=卡片数除以11，如果t的数量大于号码为8的卡片的数量，则输出8的数量，否则输出t
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <string>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <vector>
typedef long long LL;
using namespace std;
int main()
{
int n,sum=0,sum1=0;
char a[110];
while(cin>>n)
{
for(int i=0; i<n; i++)
{
cin>>a[i];
}
for(int i=0; i<n; i++)
{
if(a[i]=='8')
{
sum++;
}
}
sum1=n/11;
cout<<min(sum,sum1)<<endl;
}
return 0;
}
B. Maximum Sum of Digits
Description
You are given a positive integer n.
Let S(x) be sum of digits in base 10 representation of x,for example, S(123)=1+2+3=6, S(0)=0.
Your task is to find two integers a,b, such that 0≤a,b≤n, a+b=n and S(a)+S（b) is the
largest possible among all such pairs.
Input
The only line of input contains an integer
n (1≤n≤1012).
Output
Print largest S(a)+S(b) among all pairs of integers a,b, such that 0≤a,b≤n and a+b=n.
Sample Input
Input
35
Output
17
Input
10000000000
Output
91
In the first example, you can choose, for example, a=17 and b=18, so that S(17)+S(18）=1+7+1+8=17. It can be shown that it is impossible to get a larger answer.
In the second test example, you can choose, for example, a=5000000001 and b=
4999999999, with S(5000000001)+S(4999999999)=91. It can be shown that it is impossible to get a larger answer.
题意：给一个数字n，拆分成两个数字之和，然后把两个数字拆分成单个数字，然后单个数字相加，然后求出最大的和。
思路：尽可能构造出9的数字，如果是三位数我们最多构造两个99，然后剩下的n-99得出另一个数字。
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <string>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <vector>
typedef long long LL;
using namespace std;
int main()
{
LL n;
LL sum=0,t=0,x;
cin>>n;
x=n;
while(x)
{
t++;
x/=10;
}
for(int i=1;i<t;i++)
{
sum=sum*10+9;
}
LL ans=9*(t-1);
LL temp=n-sum;
while(temp)
{
ans+=temp%10;
temp/=10;
}
cout<<ans<<endl;
return 0;
}
C. Memory and De-Evolution
Description
Memory is now interested in the de-evolution of objects, specifically triangles. He starts with an equilateral triangle of side length x, and he wishes to perform operations to obtain an equilateral triangle of side length y.
In a single second, he can modify the length of a single side of the current triangle such that it remains a non-degenerate triangle (triangle of positive area). At any moment of time, the length of each side should be integer.
What is the minimum number of seconds required for Memory to obtain the equilateral triangle of side length y?
Input
The first and only line contains two integers x and y (3 ≤ y < x ≤ 100 000) — the starting and ending equilateral triangle side lengths respectively.
Output
Print a single integer — the minimum number of seconds required for Memory to obtain the equilateral triangle of side length y if he starts with the equilateral triangle of side length x.
Sample Input
Input
6 3
Output
4
Input
8 5
Output
3
Input
22 4
Output
6
Hint
In the first sample test, Memory starts with an equilateral triangle of side length 6 and wants one of side length 3. Denote a triangle with sides a, b, and c as (a, b, c). Then, Memory can do .
In the second sample test, Memory can do .
In the third sample test, Memory can do:
.
解题思路:
【题意】现有边长为x的等边三角形,Memory想要将其变成边长为y的等边三角形
现规定Memory每秒能够改变一条边的大小,但要保证改变后的三条边仍能构成一个三角形
问,最少需要多少时间才能变为边长为y的等边三角形
【类型】贪心,逆推【分析】
一开始,正常人的想法就是如何改变边长为x的等边三角形的边,使得其变为边长为y的等边三角形
但是在不断尝试过程中,就会发现,貌似不是非常好处理
根据定理"三角形两边之和大于第三边,两边之差小于第三边"
就很难确定最初应该把x减少为多少合适,如果减少太多,势必会使得另外两条边减少速度过慢
(22,22,22)→(4,22,22)→(4,19,22)→(4,19,16)→(4,13,16)→(4,13,10)→(4,7,10)→(4,7,4)→(4,4,4)
但如果减少太少,同样会影响速率
应该是个怎么样的度,总是把握不好
这时,把问题反过来想想,发现有出路
减法控制不好,相对来说加法就简单得多
为了尽快使y->x,那每秒都要使得y增加得尽可能多
所以每次选取最短边,将其变为另两条边之和-1(“三角形两边之和大于第三边”)
直到三条边都大于等于x为止
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <string>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <vector>
typedef long long LL;
using namespace std;
int main()
{
int x,y;
while(~scanf("%d%d",&x,&y))
{
int a[3],cnt=0;
a[0]=a[1]=a[2]=y;
while(1)
{
if((a[0]==x&&a[1]==x&&a[2]==x))
break;
cnt++;
a[0]=a[1],a[1]=a[2];
a[2]=min(x,a[0]+a[1]-1);
}
printf("%d\n",cnt);
}
return 0;
}
B. Memory and Trident
. To do this, he has a special trident. This trident can replace any character in s with any of ‘L’, ‘R’, ‘U’, or ‘D’. However, because he doesn’t want to wear out the trident, he wants to make the minimum number of edits possible. Please tell Memory what is the minimum number of changes he needs to make to produce a string that, when walked, will end at the origin, or if there is no such string.
Input
The first and only line contains the string s (1 ≤ |s| ≤ 100 000) — the instructions Memory is given.
Output
If there is a string satisfying the conditions, output a single integer — the minimum number of edits required. In case it’s not possible to change the sequence in such a way that it will bring Memory to to the origin, output -1.
Sample Input
Input
RRU
Output
-1
Input
UDUR
Output
1
Input
RUUR
Output
2
Hint
In the first sample test, Memory is told to walk right, then right, then up. It is easy to see that it is impossible to edit these instructions to form a valid walk.
In the second sample test, Memory is told to walk up, then down, then up, then right. One possible solution is to change s to “LDUR”. This string uses 1 edit, which is the minimum possible. It also ends at the origin.
题意：
给定字符串，由’Ｒ’、‘Ｌ’、‘Ｕ‘、’Ｄ‘ 四个方位组成，Ｍemory 从原点出发，按照字符串走每一步，但是她想回到原点，有个方法可以实现，就是去改动字符串中的某个字母，将它变成能回到起点的字符串，问最少需要改动几个？
简洁的来说就是给个字符串，改变最小字母次数然后回到原点。
例如：
ＲＬＵＵ，是到不了原点的，将’Ｕ’ 改成‘Ｄ’，可以实现回到原点
思路：
１、长度是奇数是不可能回到起点的
２、回到起点说明‘Ｒ’‘L’、’Ｕ‘’Ｄ’ 是相互对称的，‘Ｒ’的个数应该等于‘L’的个数、’Ｕ‘的个数等于’Ｄ’的个数
去判断给定了多少对的‘Ｒ’‘L’、’Ｕ‘’Ｄ’，把能形成整数对 ‘Ｒ’‘L’、’Ｕ‘’Ｄ’ 的个数去掉（在原个数的基础上减去能形成整数对的个数），剩下的就是需要改配对的，
也就是需要改变的某几个数
剩下的数之和除 ２——就是需要改变的个数
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <string>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <vector>
typedef long long LL;
using namespace std;
int main()
{
int x,y;
while(~scanf("%d%d",&x,&y))
{
int a[3],cnt=0;
a[0]=a[1]=a[2]=y;
while(1)
{
if((a[0]==x&&a[1]==x&&a[2]==x))
break;
cnt++;
a[0]=a[1],a[1]=a[2];
a[2]=min(x,a[0]+a[1]-1);
}
printf("%d\n",cnt);
}
return 0;
}