Codeforces Round #690 (Div. 3)

原题传送门

题目描述

You are given a positive number xx. Find the smallest positive integer number that has the sum of digits equal to xx and all digits are **distinct** (unique).

Input

The first line contains a single positive integer tt (1≤t≤501≤t≤50) — the number of test cases in the test. Then tt test cases follow.

Each test case consists of a single integer number xx (1≤x≤501≤x≤50).

Output

Output tt answers to the test cases:

  • if a positive integer number with the sum of digits equal to xx and all digits are different exists, print the smallest such number;
  • otherwise print -1.

Example

input

4
1
5
15
50

output

1
5
69
-1

题目分析

题目大意 ：找一个整数，这个整数每一位的和等于所给的x，并且这个整数每一位都不同且这个整数是满足情况的最小值

首先，满足的最大情况是123456789，这几个数字之和为45，那么当x大于45时则直接输出-1。

当x小于45时让个位开始分别是最大的，即.....789，那就从9开始枚举，如果符合情况，那就直接输出结果

AC代码

#include<iostream>
using namespace std;
int main(){
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int t;
    cin >> t;
    while(t--){
        long long ans = 0, sum = 0;
        int x, k = 1;
        bool f = 0;
        cin >> x;
        if(x > 45) cout << -1 << endl;
        else {
            for(int i = 9, j; i ; i--){
                for(j = i; j; j--){
                    if(sum + j == x){
                        ans += j * k;
                        f = 1;
                        break;
                    }
                }
                sum += i;
                if(f) break;
                ans += i * k;
                k *= 10;
            }
            cout << ans << endl;
        }
    }
    return 0;
}