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

const   fi='';
        nmax=999999;
type    data=longint;
var
        f:text;
        kq,S,A,tmp:string;
        n,sl,i:data;
        dd:array[1..6] of boolean;

procedure sort(l,r: longint);
      var
         i,j: longint;
         y,x:char;
      begin
         i:=l;
         j:=r;
         x:=s[(l+r) div 2];
         repeat
           while s[i]<x do
            inc(i);
           while x<s[j] do
            dec(j);
           if not(i>j) then
             begin
                y:=s[i];
                s[i]:=s[j];
                s[j]:=y;
                inc(i);
                j:=j-1;
             end;
         until i>j;
         if l<j then
           sort(l,j);
         if i<r then
           sort(i,r);
      end;


procedure try;
var     i:data;
begin
        if sl=n then
                begin
                        if kq>a then
                                begin
                                        writeln(kq);
                                        halt;
                                end;

                end
        else
                for i:=1 to n do
                        if not dd[i] then
                                begin
                                        inc(sl);
                                        dd[i]:=true;
                                        kq[sl]:=s[i];
                                        try;
                                        dd[i]:=false;
                                        dec(sl);
                                end;
end;

begin
        assign(f,fi); reset(f);
        readln(f,s);
        close(f);
        n:=length(s);
        a:=s;
        kq:=s;
        sort(1,n);
        for i:=n downto 1 do

                tmp:=tmp+s[i];
        if tmp=a then
                begin
                        writeln(0);
                        halt;
                end;
        fillchar(dd,sizeof(dd),false);
        sl:=0;

        try;
        writeln(0);
end.