Các bác cho e ý tưởng làm bài này với ạ : Cho số tự nhiên m và số nguyên s không âm, Tìm số bé nhất và lớn nhất có m chữ số và tổng chữ số bằng s, 1 ≤ m ≤ 100, 0 ≤ s ≤ 900.
Tìm số nhỏ nhất và lớn nhất có thể khi biết số chữ số và tổng các chữ số?
Bạn đã suy nghĩ được gì sau vài tiếng vừa rồi?
https://daynhauhoc.com/t/tim-so-be-nhat-va-lon-nhat-co-m-chu-so-va-tong-chu-so-bang-s/108839
6 Likes
Bạn đã thử nháp ra giấy chưa, làm tay sao thì làm trên máy vậy. 
Đây là những gì mình rút được ra sau khi nháp mất gần một nửa sau của tờ lịch hôm nay. :v
Số cần tìm là n = \overline{a_1a_2a_3\dots a_m} \Rightarrow a_1 + a_2 + a_3 + \dots + a_m = s.
Với số nhỏ nhất:
- Vì n nhỏ nhất nên tạm thời cho a_1 = 1 \Rightarrow n = \overline{1a_2a_3\dots a_m}.
\Rightarrow a_2 + a_3 + \dots + a_m = s - 1 - Cũng do n nhỏ nhất nên ta bắt đầu từ hàng đơn vị đi lên, gán cho a_i là giá trị lớn nhất có thể.
- VD: m = 3, s = 14
\Rightarrow n = \overline{1a_2a_3}
\Rightarrow n = \overline{1a_29}
\Rightarrow n = \overline{149} - Với m chữ số thì s phải nhỏ hơn hoặc bằng m * 9 thì mới tìm được số thỏa mãn.
- s = 0, m \ge 2 cũng không có số thỏa mãn. :v
Với số lớn nhất:
- Tương tự như trên nhưng thay vì làm từ hàng đơn vị thì làm từ hàng cao nhất xuống.
- VD: m = 4, s = 24
\Rightarrow n = \overline{a_1a_2a_3a_2}
\Rightarrow n = \overline{9a_2a_3a_2}
\Rightarrow n = \overline{99a_3a_2}
\Rightarrow n = \overline{996a_2}
\Rightarrow n = \overline{9960}
6 Likes
Ở phần tìm số nhỏ nhất có một vấn đề: Nếu m = 3 và s = 24 thì không thể tìm ra kết qua do số cần tìm là 699 có chữ số đầu tiên là 6 chứ không phải là 1 :V. Ở dạng tổng quát thì cách trên sẽ không sử dụng được nếu s >= 2 * m - 1 :V.
5 Likes
Vậy nên em mới nói như v.
5 Likes
Đảo chuỗi lớn nhất rồi thêm bớt 1 vô chữ số đầu tiên nếu cần là đc :V
6 Likes
Nghĩ ra cách tìm số nhỏ nhất thoả mãn điều kiện rồi, có khả năng là sẽ chạy được hết tất cả các case hợp lệ. Cho n = \overline{a_1a_2a_3\dots a_m}, ta bắt đầu từ hàng thứ m tới hàng chục, gán cho a_i (0 < a_1 <= 9) là giá trị nhỏ nhất có thể sao cho s trừ các số còn lại (a_{i - 1}...a_1) <= 9 * (m - i), sau đó lấy s trừ tổng các chữ số ở các hàng trước là ra.
Ví dụ 1: m = 3, s = 24
- n = \overline{a_1a_2a_3}
- n = \overline{6a_2a_3} (24 - 6 = 18, 18 = 9 * (3 - 1) = 9 * 2)
- n = \overline{69a_3} (24 - 15 = 9, 9 = 9 * (2 - 1) = 9 * 1)
- n = 699 (24 - 15 = 9)
Ví dụ 2: m = 2, s = 14
- n = \overline{a_1a_2}
- n = \overline{5a_2} (14 - 5 = 9, 9 = 9 * 1)
- n = 59 (24 - 15 = 9)
Ví dụ 3: m = 3, s = 2
- n = \overline{a_1a_2a_3}
- n = \overline{1a_2a_3} (a_1 > 0)
- n = \overline{10a_3} (2 - 0 = 2, 2 = 2 * (3 - 2) = 2 * 1)
- n = 101 (2 - 1 = 1)
5 Likes
Làm như v là phải tính toán nhiều hơn á. :v
V là được r a. :v :V
std::string minimum_number(int m, int s) {
if (s > m * 9 || (m > 1 && s == 0)) return "";
std::string a(m, '0');
a[0] = '1', s -= 1;
for (int i = m - 1; i > 0; --i) {
if (s >= 9) a[i] = '9', s -= 9;
else a[i] = s + '0', s = 0;
}
a[0] += s;
return a;
}
6 Likes
Mình viết thêm hàm tìm max:
string find_min_number(int m, int s)
{
if(s > 9*m || (m > 1 && s == 0)) return "Not found";
// detect a[0]
string num(m, '0');
int tmp = s - 9 * (m - 1);
if (tmp < 0) tmp = 1;
num[0] = (tmp + '0');
s -= tmp;
// detect a[i]
for (int i = 1; i < m; i++) {
tmp = s - 9*(m-1-i);
if (tmp < 0) tmp = 0;
num[i] = tmp + '0';
s -= tmp;
}
return num;
}
string find_max_number(int m, int s)
{
if (s > 9 * m || (m > 1 && s == 0)) return "Not found";
string num(m, '0');
for (int i = 0; i < m; i++) {
if (s > 9){
num[i] = 9 + '0';
s -= 9;
}
else {
num[i] = s + '0';
s = 0;
}
}
return num;
}
4 Likes
soành điệu 
#include <iostream>
#include <string>
#include <optional>
#include <algorithm>
auto nmax(int m, int s) -> std::optional<std::string> {
constexpr int kMaxDigit = 9;
std::string result;
for (; s > kMaxDigit; s -= kMaxDigit) {
result += kMaxDigit + '0';
}
if (s != 0) {
result += s + '0';
}
if (result.size() > m) {
return {};
}
while (result.size() < m) {
result += '0';
}
return result;
}
auto nmin(int m, int s) -> std::optional<std::string> {
auto res = nmax(m, s);
if (!res) {
return {};
}
auto& result = *res;
std::reverse(begin(result), end(result));
if (result[0] == '0') {
result[result.find_first_not_of('0')]--;
result[0]++;
}
return result;
}
auto main() -> int {
int m = 0;
int s = 0;
std::cin >> m >> s;
if (auto r = nmax(m, s); r) {
std::cout << "max = " << *r << "\n";
} else {
std::cout << "Can't\n";
}
if (auto r = nmin(m, s); r) {
std::cout << "min = " << *r << "\n";
} else {
std::cout << "Can't\n";
}
}
4 Likes
Cái đầu tiên là phải <=0 chứ bro
số nhỏ nhất (python)
def find_largest_number(n, s):
# Kiểm tra xem có thể tạo số hay không
if s > 9 * n or (s == 0 and n > 1):
return -1 # Không thể tạo số
# Tạo số bằng cách sắp xếp các chữ số giảm dần
number = [0] * n
remaining_sum = s
# Bắt đầu từ chữ số đầu tiên, gán giá trị lớn nhất có thể
number[0] = 1
# Điền các chữ số còn lại từ phải sang trái
for i in range(n - 1, 0, -1):
digit = min(9, remaining_sum)
number[i] = digit
remaining_sum -= digit
return int(''.join(map(str, number)))
# Thử nghiệm
n = int(input('n='))
s = int(input('s='))
result = find_largest_number(n, s)
if result != -1:
print(f"Số lớn nhất có {n} chữ số và tổng các chữ số bằng {s} là: {result}")
else:
print("Không thể tạo số với các giá trị đầu vào đã cho.")
số lớn nhất (Python)
def find_largest_number(n, s):
# Kiểm tra xem có thể tạo số hay không
if s > 9 * n or (s == 0 and n > 1):
return -1 # Không thể tạo số
# Tạo số bằng cách điền các chữ số từ trái sang phải
number = [0] * n
# Đặt giá trị lớn nhất cho chữ số đầu tiên
number[0] = min(9, s)
# Đặt giá trị lớn nhất cho các chữ số còn lại
remaining_sum = s - number[0]
for i in range(1, n):
number[i] = min(9, remaining_sum)
remaining_sum -= number[i]
return int(''.join(map(str, number)))
# Thử nghiệm
n = int(input('n='))
s = int(input('s='))
result = find_largest_number(n, s)
if result != -1:
print(f"Số lớn nhất có {n} chữ số và tổng các chữ số bằng {s} là: {result}")
else:
print("Không thể tạo số với các giá trị đầu vào đã cho.")
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?