codeforces 352A Jeff and Digits

​​點選打開連結​​

A. Jeff and Digits

time limit per test

memory limit per test

input

output

n

Jeff must make the number without leading zero. At that, we assume that number 0 doesn't contain any leading zeroes. Jeff doesn't have to use all the cards.

Input

n (1 ≤ n ≤ 103). The next line contains n integers a1, a2, ..., an (ai or ai). Number ai represents the digit that is written on the i-th card.

Output

In a single line print the answer to the problem — the maximum number, divisible by 90. If you can't make any divisible by 90 number from the cards, print -1.

Examples

Copy

4

5 0 5 0

Copy

Copy

11
5 5 5 5 5 5 5 5 0 5 5      

Copy

5555555550

Note

0.

5555555550, it is a multiple of 90.

#include<bits/stdc++.h>  
using namespace std;  
typedef long long ll;  
const int inf = 0x3f3f3f3f;  
int main()   
{  
    // freopen("in.txt","r",stdin);
    int n;
    int s[1000+5];
    int a=0,b=0;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>s[i];
        if(s[i]==5)
            a++;
    }
    b=n-a;
    a/=9;
    if(a!=0&&b!=0)
    {
        for(int i=0;i<a;i++)
            printf("555555555");
        for(int i=0;i<b;i++)
            printf("0");
        printf("\n");
    }
    else
    {
        if(b==0)
            printf("-1\n");
        else
            printf("0\n");
    }
    return 0;  
}