Đề Thi Học Sinh Giỏi Môn Tin Học-Khối 12

Chia sẻ: Hoang Duc | Ngày: | Loại File: DOC | Số trang:4

Thêm vào BST

Báo xấu

376
lượt xem 117
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Đ ề: (Thang điểm 20) N con bọ được bố trí rải rác ngẫu nhiên trên các nút của một lưới ô vuông mà mỗi cạnh ô vuông bằng đơn vị.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Đề Thi Học Sinh Giỏi Môn Tin Học-Khối 12

Đề Thi Học Sinh Giỏi Môn Tin Học-Khối 12 Đ ề: (Thang điểm 20) N con bọ được bố trí rải rác ngẫu nhiên trên các nút của một lưới ô vuông mà mỗi cạnh ô vuông bằng đơn vị. Mỗi nút của lưới ô vuông được xác định bởi cặp tọa độ nguyên (x,y). Các con bọ có thể di chuyên lên, xuống trái, phải mỗi lần một đơn v ị (tương ứng với việc thay đổi các hoành độ hay trung độ 1 hay – 1 đ ơn v ị. Các con b ọ di chuyên sao cho cuối cùng chúng đứng thành đường thẳng nằm ngang, con bọ nọ cạnh con bọ kia: lúc đó các vị trí của các con bọ là (x,y), (x+1,y),….,(x+n-1,y v ới x,y nào đó. Giá trị nguyên của x, y cũng như thứ tự các con bọ là tùy ý. Yêu cầu: Tìm số lần di chuyển ít nhất để đạt được thỏa mãng yêu cầu trên. tại mỗi nút của lưới ô vuông không thể có hơn một con bọ tại cùng một thời điểm. Dữ liệu vào: Ghi trên file MOLE.INP, GỒM N+1 dòng: Dòng đầu ghi số nguyên dương N (1
Đáp án: const fi='mole.inp'; fo='mole.out'; max_mole=10000; vocuc=maxlongint; type maxxy=-10000..10000; xytype= record x,y:maxxy; end; molexy=array[1..max_mole] of xytype; var n,minpos:0..max_mole; t: molexy; minxy:xytype; step:longint; {2 điểm} {-------------------------------} procedure readdata(filename:string); var f:text; i:integer; begin assign(f,filename); reset(f);readln(f,n); for i:=1 to n do readln(f,t[i].x,t[i].y); close(f); end; {3 điểm} {-------------------------------} procedure swap (var a,b:xytype); var tmp:xytype; begin tmp:=a; a:=b;b:=tmp; end; {2 điểm} {------------------------------} procedure qsorty(var t:molexy; lo,hi:integer); var i,j,mid:integer; begin i:=lo;j:=hi;mid:=t[(lo+hi)div 2].y; repeat while t[i].y> mid do inc(i); while t[j].y
if ij; if lo< j then qsorty(t,lo,j); if hi>i then qsorty(t,i,hi); end; {4 điểm} {-------------------------------------------} procedure qsortx(var t:molexy; lo,hi:integer); var i,j,mid:integer; begin i:=lo;j:=hi;mid:=t[(lo+hi)div 2].x; repeat while t[i].x> mid do inc(i); while t[j].y >mid do dec(j); if ij; if lo< j then qsortx(t,lo,j); if hi>i then qsorty(t,i,hi); end; {4 điểm} {-----------------------------------------} procedure findminxy(var minxy:xytype); var i:0..max_mole; begin qsorty(t,1,n); minxy.y:=t[(n+1)div 2].y; qsortx(t,1,n); for i:=0 to n-1 do dec(t[i+1].x,i); qsortx(t,1,n); minxy.x:=t[(n+1)div 2].x; end; procedure solve; var i:1..max_mole; begin findminxy(minxy); for i:=1 to n do inc(step, abs(t[i].x-minxy.x )+abs(t[i].y- minxy.y)); end; {3 điểm}
{-----------------------------} procedure output; var f: text; begin assign(f,fo); rewrite(f); write(f,step); close(f); end; BEGIN readdata(fi); solve; output; END. {2 điểm}