P152PROF PTIT spoj – ROUND 2F – Min max
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 &l ...
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
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 | 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. |
