PTIT123A PTIT spoj – Sắp xếp 2
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 ...
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
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 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 | 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. |
