02/10/2018, 14:31
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 ...
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.
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 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 | 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. |
