P132SUMJ spoj PTIT – SUM2 J – Hoán vị chữ số

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

1. Đề bài P132SUMJ spoj PTIT

Cho trước một số nguyên dương X. Nhiệm vụ của bạn là tìm số nhỏ nhất lớn hơn X, mà có các chữ số giống hệt với X.

Input

Dòng đầu tiên là số nguyên X (1 ≤ X ≤ 999 999).

Chữ số đầu tiên của X luôn khác 0.

Output

In ra đáp số trên một dòng. Nếu không có đáp số, in ra “0”.

Example

Test 1:

Input:

156

Output:

165

Test 2:

Input:

330

Output:

0

Test 3:

Input:

27711

Output:

71127

2. Thuật toán bài P132SUMJ spoj PTIT

Đưa bài toán về dạng quay lui sinh hoán vị. Dễ dàng nhận thấy dãy hoán vị sinh được từ thuật toán quay lui sẽ tăng dần. do đó đầu tiên sắp xếp thứ tự các số từ nhỏ đến lớn. sau đó dùng thuật toán quay lui để tìm kết quả. nếu tìm thấy số lớn hơn số ban đầu thì đó chính là kết quả bài toán.

3. Code tham khảo P132SUMJ spoj PTIT