Tối ưu bài toán tìm số nhỏ nhất có n chữ số khi cho trước tổng các chữ số

[Nguyen_Tam]

Tìm số M nhỏ nhất có n chữ số (2<=n<=9) có tổng các chữ số bằng s (0<=s<=100)

Ae ai có cách tối ưu thuật toán ko ạ. Em làm cách này nếu n > 5 và s là mấy số lớn thì nó chạy lâu quá.

#include <bits/stdc++.h>
using namespace std;
int tcs (int x)
{
    int y=0;
    while (x>0)
     {
     >   int r=x%10;
         y=y+r;
         x/=10;
     }
     return y;
}
int dcs(int x)
{
     int d=0;
     while (x>0)
    {
         d++;
         x/=10;
    }
    return d;
}
int main()
{
     int n,s;
     cout << "N=";
     cin >> n;
     cout << "S=";
     cin >> s;
     int y=s;
     while (y>0)
     {
       if (tcs(y)==s&&dcs(y)==n)
         {
             cout << "M=" << y;
             return 0;
         }
         y++;
     }
     return 0;
}

[noname00 (HK boy)]

Bây giờ bạn phải đánh giá bằng toán học thôi.

1. Nếu 9 * n < s thì bài toán vô nghiệm.

2. Nếu chơi tham lam một chút, bạn cố gắng nhét nhiều chữ số 9 vào cuối số M nhất có thể thì bạn có thể nhét tối đa bao nhiêu chữ số 9? Bạn thử làm với ví dụ n = 5 và s = 31.