Nguồn đề bài: http://www.spoj.com/PTIT/problems/PTIT123C/
Nội dung bài viết
1. Đề bài PTIT123C PTIT 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 PTIT spoj
– Bài này có thể làm theo nhiều cách, với mình thì các bạn sort mảng A, và sort luôn thứ tự của nó. sau đó có thể dùng mảng dd để lấy kết quả.
3. Code tham khảo PTIT123C 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 | 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. |
Bài viết liên quan
- PTIT016D spoj PTIT- ACM PTIT 2016 D – Biểu thức
- P157PROE spoj PTIT – ROUND 7E – Kim cương
- P157PROA spoj PTIT – ROUND 7A – Số may mắn
- PTIT127C spoj ptit- Bố trí phòng họp
- PTIT123C spoj PTIT – chứng khoán
- P146PROC spoj PTIT – ROUND 6C – Bút màu
- P133SUMF spoj PTIT – cấp số cộng
- BCTELEPH spoj PTIT – Danh sách điện thoại nhất quán
- BCMARA spoj PTIT – Chạy đua marathon
- BCCOW spoj PTIT – Đi xem phim