Nguồn đề bài: http://www.spoj.com/PTIT/problems/PTIT123A/
1. Đề bài PTIT123A PTIT spoj
Cho một danh sách chứa cả các số và các từ. Yêu cầu bạn hãy sắp xếp danh sách này tăng dần sao cho các từ theo thứ tự từ điển, các số theo thứ tự số. Hơn nữa, nếu phần tử thứ n là số thì danh sách sau khi sắp xếp phần tử thứ n cũng phải là số, nếu là từ thì vẫn là từ.
Lưu ý: Các từ chỉ gồm các chữ in thuờng trong bảng chữ cái tiếng Anh.
Input
Gồm nhiều dòng, mỗi dòng là một danh sách. Mỗi phần tử của danh sách cách nhau bởi dấu phẩy (“,”) theo sau là dấu cách, và danh sách được kết thúc bằng dấu chấm (“.”).
Dữ liệu kết thúc bởi dòng chỉ chứa một dấu chấm.
Output
Với mỗi danh sách trong dữ liệu, xuất ra danh sách đã sắp xếp thỏa mãn yêu cầu đề bài (có định dạng như trong dữ liệu).
Example
Input:
0.
banana, strawberry, orange.
banana, strawberry, orange.
10, 8, 6, 4, 2, 0.
x, 30, -20, z, 1000, 1, y.
50, 7, kitten, puppy, 2, orangutan, 52, -100, bird, worm, 7, beetle.
.
Output:
0.
banana, orange, strawberry.
banana, orange, strawberry.
0, 2, 4, 6, 8, 10.
x, -20, 1, y, 30, 1000, z.
-100, 2, beetle, bird, 7, kitten, 7, 50, orangutan, puppy, 52, worm.
2. Hướng dẫn PTIT123A PTIT spoj
– bài này ý tưởng khá đơn giản. lấy số bỏ ra 1 mảng, chữ bỏ ra 1 mảng. đồng thời cũng lưu lại vị trí là ở chữ/số thứ i nào đó thì ban đầu nó là số hay chữ (tạm gọi là mảng dd).
– sau đó sắp xếp mảng số, sắp xếp mảng chữ.
– dựa vào mảng DD, để xuất ra kết quả.
3. Code tham khảo PTIT123A PTIT spoj
const fi='';
nmax=1000000;
type data=longint;
var
f:text;
s:ansistring;
tmp:string;
so:array[0..nmax+1] of data;
chu:array[0..nmax+1] of string;
dd:array[0..nmax+1] of data;
n,nso,nchu:data;
procedure sortSO(l,r: longint);
var
i,j,x,y: longint;
begin
i:=l; j:=r; x:=so[(l+r) div 2];
repeat
while so[i]<x do inc(i);
while x<so[j] do dec(j);
if not(i>j) then
begin
y:=so[i];
so[i]:=so[j];
so[j]:=y;
inc(i); j:=j-1;
end;
until i>j;
if l<j then sortSO(l,j);
if i<r then sortSO(i,r);
end;
procedure sortCHU(l,r: longint);
var
i,j: longint;
x,y:string;
begin
i:=l; j:=r; x:=chu[(l+r) div 2];
repeat
while chu[i]<x do inc(i);
while x<chu[j] do dec(j);
if not(i>j) then
begin
y:=chu[i];
chu[i]:=chu[j];
chu[j]:=y;
inc(i); j:=j-1;
end;
until i>j;
if l<j then sortCHU(l,j);
if i<r then sortCHU(i,r);
end;
procedure xuli;
var i,j,vt,dem,x,er:data;
begin
n:=0;
nso:=0;
nchu:=0;
tmp:='';
for i:=1 to length(s) do
begin
if (s[i]=',') or (s[i]='.') then
begin
inc(n);
if tmp[length(tmp)] in ['0'..'9'] then
begin
dd[n]:=1; // la so
inc(nso);
val(tmp,x,er);
so[nso]:=x;
end
else
begin
dd[n]:=2; // la chu
inc(nchu);
chu[nchu]:=tmp;
end;
continue;
end;
if s[i]=' ' then
begin
tmp:='';
continue;
end;
tmp:=tmp+s[i];
end;
sortso(1,nso);
sortchu(1,nchu);
nso:=0;
nchu:=0;
for i:=1 to n -1 do
if dd[i]=1 then
begin
inc(nso);
write(so[nso],', ');
end
else
begin
inc(nchu);
write(chu[nchu],', ');
end;
if dd[n]=1 then
begin
inc(nso);
write(so[nso],'.');
end
else
begin
inc(nchu);
write(chu[nchu],'.');
end;
writeln;
end;
procedure docfile;
var i,j:data;
begin
assign(f,fi); reset(f);
repeat
readln(f,s);
if s='.' then break;
xuli;
until false;
close(f);
end;
begin
docfile;
end.
