Đề 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<= n <=10000), chỉ số con bọ. Trên dòng thứ i+1 (1<=i <=n), chứa hai số nguyên x[i], y[i] (-10000<=x[i],y[i]) <=10000), cách nhau một khoảng trắng, chỉ hoàng độ và trung độ của con bọ thứ i. Dữ liệu ra: Ghi trên file MOLE.OUT, gồm 1 dòng, chỉ số nguyên chỉ số bước di chuyển ít nhất cần thực hiện. Ví dụ: MOLE.INP MOLE.OUT 3 1 0 2 4 3 2 4 Đá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 <mid do dec(j); if i<=j then begin swap(t[i],t[j]); inc(i); dec(j); end; until i>j; 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 i<=j then begin swap(t[i],t[j]); inc(i); dec(j); end; until i>j; 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}