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 n<=10⁶. 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.

PTIT123C spoj PTIT – chứng khoán