Nguồn đề bài: http://www.spoj.com/PTIT/problems/P152PROF/
1. Đề bài P152PROF PTIT spoj
Cho số tự nhiên m và số nguyên s không âm. Nhiệm vụ của bạn là tìm số bé nhất và lớn nhất có m chữ số và tổng chữ số bằng s.
Input
Dòng đầu gồm 2 số m và s (1 ≤ m ≤ 100, 0 ≤ s ≤ 900).
Output
In ra kết quả của bài toán.
Số đầu tiên là số bé nhất, số thứ hai là số lớn nhất. Nếu không có đáp án in ra “-1 -1”.
Example
Input:
2 15
Output:
69 96
2. Hướng dẫn P152PROF PTIT spoj
Mình sẽ hướng dẫn các bạn giải từng tình huống sau:
– Nếu m=1 và s=0 thì kết quả là “0 0”.
– Tiếp tục, dễ dàng nhận thấy khi s=0 hoặc s>9*m thì kết quả sẽ cho ra một số vô nghĩa nên lúc này kết quả sẽ là “-1 -1”.
– Tìm số lớn nhất có tổng các chữ số bằng S:
+ Ưu tiên điền các số lớn nhất còn có thể điền vào các vị trí đầu tiên. các số lớn nhất đó có thể là [0..9] và nó phụ thuộc vào S còn lại, mỗi lần điền như vậy cập nhật lại s còn lại. khi điền hết thì cho những số cuối cùng chưa điền bằng 0. Nhận thấy với cách làm này ta luôn thu được 1 số có nghĩa vì các số 0 luôn ở phía sau.
– Tìm số nhỏ nhất có tổng các chữ số bằng S:
+ việc tìm số nhỏ nhất có thể dựa trên kết quả của số lớn nhất đã tìm được ở trên.
+ ở đây rất dễ sai vì nó còn xét đến chữ số có nghĩa. bạn dễ dàng nhận thấy nếu lật ngược kết quả lớn nhất tìm được ở trên thì sẽ cho ra số nhỏ nhất (và khả năng có chữ số vô nghĩa).
+ Cách xử lí: Nếu chữ số đầu tiên sau khi lật ngược xâu kết quả lớn nhất mà bằng 0 thì mình sẽ cho nó bằng 1. và đi tìm 1 vị trí khác có chữ số khác 0, giảm nó xuống 1 đơn vị là xong.
– Xuất ra KQ bài toán
3. code tham khảo P152PROF PTIT spoj
const fi='';
nmax=100;
type data=longint;
var
f:text;
m,s:data;
A:array[0..nmax+1] of data;
procedure xuli;
var i,j,stam:data;
begin
if (m=1) and (s=0) then
begin
writeln('0 0');
exit;
end;
if (s>9*m) or (s=0) then
begin
writeln('-1 -1');
exit;
end;
// tim so nho nhat.
stam:=s;
for i:=1 to m do a[i]:=0;
for i:=m downto 1 do
begin
for j:=9 downto 0 do
if stam-j>=0 then
begin
a[i]:=j;
stam:=stam-j;
break;
end;
if a[i]=0 then break;
end;
if a[1]=0 then
begin
A[1]:=1;
for j:=2 to m do
if a[j]<>0 then
begin
a[j]:=a[j]-1;
break;
end;
end;
for i:=1 to m do
write(a[i]);
write(' ');
// tim so lon nhat.
stam:=s;
for i:=1 to m do A[i]:=0;
for i:=1 to m do
begin
for j:=9 downto 0 do
if stam-j>=0 then
begin
A[i]:=j;
stam:=stam-j;
break;
end;
if A[i]=0 then break;
end;
for i:=1 to m do
write(a[i]);
end;
begin
assign(f,fi); reset(f); readln(f,m,s); close(f);
xuli;
end.
