题目描述

HXY得到了一些卡片，这些卡片上标有数字0或5。现在她可以选择其中一些卡片排成一列，使得排出的一列数字组成的数最大，且满足被90整除这个条件。同时这个数不能含有前导0，即0不能作为这串数的首位。如果不能排出这样的数，输出“-1”。

输入输出格式

输入格式：

 

第一行，卡片的个数n。

第二行，分别给出了这n个数（只能为数字5或0）。

 

输出格式：

 

仅一行，如果可以排出，则输出这个数。否则输出“-1”。

 

输入输出样例

输入样例#1：

45 0 5 0

输出样例#1：

0

输入样例#2：

115 5 5 5 5 5 5 5 0 5 5

输出样例#2：

5555555550

说明

数据范围：

对于30%的数据，n<=10；

对于20%的数据，仅含数字5；

对于100%的数据，n<=1000。

 

特潘

#include
     
      #include
      
       #include
       
        #include
        
         using namespace std;long long  a,b,n;int dfs(long long tot){    if(a)    a--,dfs(tot*10+5),a++;    if(b)    b--,dfs(tot*10),b++;    if(tot%9==0)    {        cout<
         
          >n;    for(int i=1,x;i<=n;i++)    {        scanf("%d",&x);        if(x==5)    a++;        else b++;    }    if(b==0&&a<9)        {        cout<<-1;        return 0;    }    if(b>0&& a<9)    {        cout<<0;        return 0;    }    if(b>0 && a>=9)    {             for (int i=1;i<=a/9*9;i++) cout<<5;         for (int i=1;i<=b;i++) cout<<0;    }    return 0;}