Nguồn đề bài: http://www.spoj.com/PTIT/problems/BCNEPER/
1. Đề bài BCNEPER spoj
Trong bài này, bạn hãy viết chương trình nhận vào một chuỗi (có thể khá dài) các ký tự số và đưa ra màn hình hoán vị kế tiếp của các ký tự số đó (với ý nghĩa là hoán vị có giá trị lớn hơn tiếp theo nếu ta coi chuỗi đó là một giá trị số nguyên).
Chú ý: Các ký tự số trong dãy có thể trùng nhau.
Ví dụ:
123 -> 132
279134399742 -> 279134423799
Cũng có trường hợp sẽ không thể có hoán vị kế tiếp. Ví dụ như khi đầu vào là chuỗi 987.
Dữ liệu vào
Dòng đầu tiên ghi số nguyên t là số bộ test (1 ≤ t ≤ 1000). Mỗi bộ test có một dòng, đầu tiên là số thứ tự bộ test, một dấu cách, sau đó là chuỗi các ký tự số, tối đa 80 phần tử.
Dữ liệu ra
Với mỗi bộ test hãy đưa ra một dòng gồm thứ tự bộ test, một dấu cách, tiếp theo đó là hoán vị kế tiếp hoặc chuỗi “BIGGEST” nếu không có hoán vị kế tiếp.
Ví dụ
Input:
3
1 123
2 279134399742
3 987 Output:
1 132
2 279134423799
3 BIGGEST
2. Hướng dẫn BCNEPER spoj PTIT – Hoán vị kế tiếp
– Gọi S[i] là phần tử thứ i dãy số.
– gọi vt là vị trí đầu tiên làm cho số tại đó nhỏ hơn số phía sau nó khi xét từ cuối dãy trở về đầu
VD: 5 4 1 2 0 thì vt là 3, do số S[3]=1 nhỏ hơn s[4]=2.
tuy nhiên nếu không tìm được vt nào thỏa mản thì số này chính là số lớn nhất, write “BIGGEST” và kết thúc.
– Tìm số đầu tiên lớn hơn số S[vt] khi xét từ cuối dãy về vt. gọi vị trí của số này là vt1.
– Đổi chỗ vt1 và vt
sau đó ghi ra các số từ 1->vt. và ghi các số còn lại theo chiều ngược lại từ length(s) trở về vt+1.
3. Code Tham khảo BCNEPER spoj PTIT – Hoán vị kế tiếp
const fi='';
type data=longint;
var
f:text;
s:string;
test:data;
procedure xuli;
var i,j,vt,vt1,k:data;
c:char;
begin
vt:=0;
for i:=length(s)-1 downto 1 do
if not (s[i]>=s[i+1]) then
begin
vt:=i;
break;
end;
if vt=0 then
begin
write('BIGGEST');
exit;
end;
vt1:=0;
for i:=length(s) downto vt do
if s[i]>s[vt] then
begin
vt1:=i;
break;
end;
if vt1=0 then vt1:=vt;
c:=s[vt];
s[vt]:=s[vt1];
s[vt1]:=c;
for i:=1 to vt do
write(s[i]);
for i:=length(s) downto vt+1 do
write(s[i]);
end;
procedure docfile;
var i,j:data;
c:char;
z:data;
begin
assign(f,fi); reset(f);
readln(f,test);
for i:=1 to test do
begin
read(f,z); read(f,c);
readln(f,s);
write(i,' ');
xuli;
writeln;
end;
close(f);
end;
begin
docfile;
end.
