Đ ề: (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ị. | Đề 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 , GỒM N+1 dòng: Dòng đầu ghi số nguyên dương N (1 mid do inc(i); while t[j].y j; if loi 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 loi then qsorty(t,i,hi); end; {4 điểm} {-----------------------------------------} procedure findminxy(var minxy:xytype); var i:0max_mole; begin qsorty(t,1,n); [(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); [(n+1)div 2].x; end; procedure solve; var i:1max_mole; begin findminxy(minxy); for i:=1 to n do inc(step, abs(t[i]. )+abs(t[i].)); 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}
