02/10/2018, 14:41
PTIT123C spoj PTIT – chứng khoán
Nguồn đề bài: http://www.spoj.com/PTIT/problems/PTIT123C/ 1. Đề bài PTIT123C spoj Cho trước lịch sử giao dịch của một mã chứng khoán trong n ngày. Hãy xác định k1 ngày có giá thấp nhất và k2 ngày có giá cao nhất. Input Mỗi bộ test gồm 2 dòng Dòng 1 ghi 3 số n, k1, k2 với ...
Nguồn đề bài: http://www.spoj.com/PTIT/problems/PTIT123C/
1. Đề bài PTIT123C spoj
Cho trước lịch sử giao dịch của một mã chứng khoán trong n ngày. Hãy xác định k1 ngày có giá thấp nhất và k2 ngày có giá cao nhất.
Input
Mỗi bộ test gồm 2 dòng
- Dòng 1 ghi 3 số n, k1, k2 với n<=106. k1+k2<=n và k1,k2<=100.
- Dòng tiếp theo ghi n số nguyên theo thứ tự là giá của mã chứng khoán trong n ngày liên tiếp.
- Bộ test cuối cùng chứa 3 số 0
Output
Với mỗi bộ test, ghi ra màn hình 3 dòng gồm:
- Dòng 1 ghi số thứ tự bộ test
- Dòng 2 ghi k1 ngày có giá thấp nhất theo thứ tự các ngày tăng dần. Nếu có nhiều danh sách cho kết quả giống nhau thì chọn danh sách thấp nhất theo thứ tự từ điển.
- Dòng 3 ghi k2 ngày có giá cao nhất theo thứ tự các ngày giảm dần. Nếu có nhiều danh sách cho kết quả giống nhau thì chọn danh sách cao nhất theo thứ tự từ điển.
Example
Input:
10 3 2
1 2 3 4 5 6 7 8 9 10
10 3 2
10 9 8 7 6 5 4 3 2 1
0 0 0
Output:
Case 1
1 2 3
10 9
Case 2
8 9 10
2 1
2. Hướng dẫn PTIT123C spoj PTIT
– sắp xếp A[i], nếu có nhiều giá trị A[i] bằng nhau, ưu tiên giá trị có chỉ số ban đầu nhỏ hơn.
– Xuất ra k1 số đầu tiên, và k2 số cuối cùng theo yêu cầu bài toán
3. Code tham khảo PTIT123C spoj PTIT
const fi=';
nmax=1000000;
type data=longint;
dulieu=record
tt,c:data;
end;
var
f:text;
n,k1,k2:data;
a:array[0..nmax] of dulieu;
dd:array[0..nmax+1] of data;
procedure sort(l,r: longint);
var
i,j,x,y: longint;
z:dulieu;
begin
i:=l;
j:=r;
x:=a[(l+r) div 2].c;
y:=a[(l+r) div 2].tt;
repeat
while (a[i].c<x) OR ((a[i].c=x) and (a[i].tt<y)) do inc(i);
while (x<a[j].c) or ((x=a[j].c) and (y<a[j].tt)) do dec(j);
if not(i>j) then
begin
z:=a[i];
a[i]:=a[j];
a[j]:=z;
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 xuli;
var i,j:data;
begin
fillchar(dd,sizeof(dd),0);
sort(1,n);
for i:=1 to k1 do
dd[a[i].tt]:=1;
for i:=n-k2+1 to n do
dd[a[i].tt]:=2;
for i:=1 to nmax do
if dd[i]= 1 then
write(i,' ');
writeln;
for i:=nmax downto 1 do
if dd[i]=2 then
write(i,' ');
writeln;
end;
procedure nhap;
var i,j,x,count:data;
begin
count:=0;
assign(f,fi); reset(f);
repeat
readln(f,n,k1,k2);
if (n=0) and (k1=0) and (k2=0) then
break;
inc(count);
writeln('Case ',count);
for i:=1 to n do
begin
read(f,a[i].c);
a[i].tt:=i;
end;
readln(f);
xuli;
until false;
close(f);
end;
begin
nhap;
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 86 87 | const fi='; nmax=1000000; type data=longint; dulieu=record tt,c:data; end; var f:text; n,k1,k2:data; a:array[0..nmax] of dulieu; dd:array[0..nmax+1] of data; procedure sort(l,r: longint); var i,j,x,y: longint; z:dulieu; begin i:=l; j:=r; x:=a[(l+r) div 2].c; y:=a[(l+r) div 2].tt; repeat while (a[i].c<x) OR ((a[i].c=x) and (a[i].tt<y)) do inc(i); while (x<a[j].c) or ((x=a[j].c) and (y<a[j].tt)) do dec(j); if not(i>j) then begin z:=a[i]; a[i]:=a[j]; a[j]:=z; 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 xuli; var i,j:data; begin fillchar(dd,sizeof(dd),0); sort(1,n); for i:=1 to k1 do dd[a[i].tt]:=1; for i:=n-k2+1 to n do dd[a[i].tt]:=2; for i:=1 to nmax do if dd[i]= 1 then write(i,' '); writeln; for i:=nmax downto 1 do if dd[i]=2 then write(i,' '); writeln; end; procedure nhap; var i,j,x,count:data; begin count:=0; assign(f,fi); reset(f); repeat readln(f,n,k1,k2); if (n=0) and (k1=0) and (k2=0) then break; inc(count); writeln('Case ',count); for i:=1 to n do begin read(f,a[i].c); a[i].tt:=i; end; readln(f); xuli; until false; close(f); end; begin nhap; end. |
