1、

Codeforces-1060A

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 nn 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 nn — the number of cards with digits that you have (1≤n≤1001≤n≤100).

The second line contains a string of nn digits (characters "0", "1", ..., "9") s1,s2,…,sns1,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

题意:

给定n个卡片,从这些卡片中选择某些卡片组成电话号码,需要满足以下条件:

1、长度是 11 位

2、开头必须由 8 组成

3、这些卡片只能使用一次,但是没有必要去使用全部的卡片

思路:

当n< 11 或者不存在8 的时候,是不符合题意的,输出 0

否则

去比较 n最多包括几个 11  and 8 的个数,去较小的一个

CODE

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <map>
#include <cstdlib>
#include <algorithm>
using namespace std;

typedef long long LL;
#define memset(a,n) memset(a,n,sizeof(a))
#define INF 0x3f3f3f3f


int main()
{
    int n;
    char a[102];

    int sum=0;
    scanf("%d",&n);

    getchar();

    for(int i=0;i<n;i++){
        scanf("%c",&a[i]);
        if(a[i]=='8')
            sum++;
    }

    if(n<11||sum==0)
        printf("0\n");
    else
    {
        int x;

        x=n/11;

        printf("%d\n",min(sum,x));
    }

}

 

 

 

 

 

 

 

 

 

5、

Codeforces-712B

Memory is performing a walk on the two-dimensional plane, starting at the origin. He is given a string s with his directions for motion:

  • An 'L' indicates he should move one unit left.
  • An 'R' indicates he should move one unit right.
  • A 'U' indicates he should move one unit up.
  • A 'D' indicates he should move one unit down.

But now Memory wants to end at the origin. 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.

 

题意:

给定字符串,由’R'、‘L’、‘U‘、’D‘ 四个方位组成,Memory 从原点出发,按照字符串走每一步,但是她想回到原点,有个方法可以实现,就是去改动字符串中的某个字母,将它变成能回到起点的字符串,问最少需要改动几个?

例如:

RLUU,是到不了原点的,将’U' 改成‘D’,可以实现回到原点

思路:

1、长度是奇数是不可能回到起点的

2、回到起点说明‘R’‘L'、’U‘’D' 是相互对称的,‘R’的个数应该等于‘L'的个数、’U‘的个数等于’D'的个数

  去判断给定了多少对的‘R’‘L'、’U‘’D',把能形成整数对 ‘R’‘L'、’U‘’D' 的个数去掉(在原个数的基础上减去能形成整数对的个数),剩下的就是需要改配对的,

  也就是需要改变的某几个数

  剩下的数之和除 2——就是需要改变的个数

CODE:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <map>
#include <cstdlib>
#include <algorithm>
using namespace std;

typedef long long LL;
#define memset(a,n) memset(a,n,sizeof(a))
#define INF 0x3f3f3f3f

char s[100000+10];


int main()
{

    int a,aa,b,bb;
    a=0,aa=0,b=0,bb=0;
    scanf("%s",s);

    for(int i=0;i<strlen(s);i++){
        if(s[i]=='R')
            a++;
        if(s[i]=='L')
            aa++;
        if(s[i]=='U')
            b++;
        if(s[i]=='D')
            bb++;
    }

    int sum=0;

    if(strlen(s)%2==1)
    {
        printf("-1\n");
    }

    else
    {
        a=abs(a-aa);
        b=abs(b-bb);
        int ans;
        ans=(a+b)/2;
        printf("%d\n",ans);

    }
}

 

10-06 11:26