P152PROF PTIT spoj – ROUND 2F – Min max

Contact for work: 096.1014.106 (Mr. Tiến)

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

 

Trả lời

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *