codeforces-305A Strange Addition（思维+模拟）

拼搏现实的明天。 2022-06-10 09:22 203阅读 0赞

A. Strange Addition

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

Unfortunately, Vasya can only sum pairs of integers (*a*, *b*), such that for any decimal place at least one number has digit 0 in this place. For example, Vasya can sum numbers 505 and 50, but he cannot sum 1 and 4.

Vasya has a set of *k* distinct non-negative integers *d*1, *d*2, ..., *d**k*.

Vasya wants to choose some integers from this set so that he could sum any two chosen numbers. What maximal number of integers can he choose in the required manner?

Input

The first input line contains integer *k* (1 ≤ *k* ≤ 100) — the number of integers.

The second line contains *k* distinct space-separated integers *d*1, *d*2, ..., *d**k* (0 ≤ *d**i* ≤ 100).

Output

In the first line print a single integer *n* the maximum number of the chosen integers. In the second line print *n* distinct non-negative integers — the required integers.

If there are multiple solutions, print any of them. You can print the numbers in any order.

Examples

input

4
    100 10 1 0

output

4
    0 1 10 100

input

3
    2 70 3

output

2
    2 70

题解：

题意：

给你一堆数字，范围0-100，问最多能有几个数按照要求可以组合在一起，任意输出几个就行，要求如下：比如第一个样例的0可以看成000，1看成001,10看成010，这些随意组合都可以使得3位中每一位至少有一个0，又比如50和25就不行，因为50就是050,25就是025，他们的个位没有0，不能组合

思路：

很容易分析出0-100间这样的数最多有4个，0符合，100符合，然后两个可以是一个个位数和一个能被10整除的两位数，或者如果给的数字中没有个位，就可以拿一个任意的两位数，还有就是如果输出了一个不能被10整除的两位数的话，就不能再输出两位数和一位数了（想想），就是这种思路，如果觉得绕就仔细想想

代码：

#include<algorithm>
    #include<iostream>
    #include<cstring>
    #include<stdio.h>
    #include<math.h>
    #include<string>
    #include<stdio.h>
    #include<queue>
    #include<stack>
    #include<map>
    #include<vector>
    #include<deque>
    using namespace std;
    #define lson k*2
    #define rson k*2+1
    #define M (t[k].l+t[k].r)/2
    #define INF 1008611111
    int a[10];//存要输出的数字
    int vis[105];//看0-100间出现的情况
    int main()
    {
        int i,j,n,x,num=0,tag1=0,tag2=0;
        scanf("%d",&n);
        memset(vis,0,sizeof(vis));
        for(i=0;i<n;i++)
        {
            scanf("%d",&x);
            vis[x]=1;
        }
        if(vis[0])//如果0出现了直接加0
        {
            a[num]=0;
            num++;
        }
        if(vis[100])//100出现了直接加100
        {
            a[num]=100;
            num++;
        }
        for(i=1;i<=9;i++)//如果出现个位直接加上
        {
            if(vis[i])
            {
                a[num]=i;
                num++;
                tag1=1;//打上一个tag1，不能和不能被10整除的两位数同时出现
                break;
            }
        }
        for(i=1;i<=9;i++)//如果能被10整除的两位出现了直接加上一个
    
        {
            if(vis[i*10])
            {
                a[num]=i*10;
                tag2=1;//要打一个tag2，防止两位的不能整除的数和该数同时出现
                num++;
                break;
            }
        }
        if(!tag1&&!tag2)//如果没有以上两种情况才可以找一个不能被10整除的两位数
        {
            for(i=11;i<=99;i++)
            {
                if(i%10==0)
                    continue;
                if(vis[i])
                {
                    a[num]=i;
                    num++;
                    break;
                }
            }
        }
        printf("%d\n",num);
        printf("%d",a[0]);
        for(i=1;i<num;i++)
            printf(" %d",a[i]);
        printf("\n");
        return 0;
    }