P152PROF PTIT spoj - ROUND 2F - Min max

Nguồn đề bài: http://www.spoj.com/PTIT/problems/P152PROF/

Nội dung bài viết

1. Đề bài P152PROF PTIT spoj
2. Hướng dẫn P152PROF PTIT spoj
3. code tham khảo P152PROF PTIT spoj

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.

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;

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.

P152PROF PTIT spoj – ROUND 2F – Min max

1. Đề bài P152PROF PTIT spoj

Input

Output

Example

2. Hướng dẫn P152PROF PTIT spoj

3. code tham khảo P152PROF PTIT spoj

Bài viết liên quan

Trả lời Hủy