Codeforces Round #204: Jeff and Digits

90の倍数の条件は

• 各桁の数字の和が、9の倍数
• 最後の桁が 0

を満たすことである。

よって

• 5 は 「9 の倍数」分使えるだけ使う
• 0 は 全部使う
• ただし、使える 5 がない場合は "0000..0" とせず "0" を返し、0 がない場合は強制的に -1 を返す。

namespace Codeforces {
    public class _352A {
        public static void Main(string[] args) {
            int n = int.Parse(Console.ReadLine());
            var a = Console.ReadLine().Split().Select(int.Parse).ToArray();
            int n0 = a.Where(v => v == 0).Count();
            int n5 = a.Where(v => v == 5).Count();
            String ans = new String('5', n5 / 9 * 9) + new String('0', n0);
            if (ans == "" || n0 == 0) ans = "-1";
            else if (!ans.Contains('5')) ans = "0";
            Console.WriteLine(ans);
        }
    }
}