Đặt trạm phủ sóng - Olympic 30/4/2015 tin học 10

bài giải, thuật toán bài olympic 30-4 môn tin học lớp 10, kì thi olympic lần thứ 21 tại chuyên Lê Hồng Phong TP. Hồ Chí Minh

Nội dung bài viết

1. Đề bài Olympic 30/4/2015 tin học 10
2. Hướng dẫn Olympic 30/4/2015 tin học 10
3. Code tham khảo

1. Đề bài Olympic 30/4/2015 tin học 10

Nhà cung cấp dịch vụ viễn thông Mobi đã khảo sát số lượng người sẽ dùng dịch vụ trên một con đường thẳng mới được xây dựng và đánh dấu lại những vị trí trên con đường này. Đầu con đường được đánh tọa độ bắt đầu từ 0. Tại vị trí có tọa độ X (đơn vị chiều dài) có số lượng người sẽ sử dụng dịch vụ là Y. Trước mắt, nhà cung cấp dịch vụ cần đặt một trạm phát sóng có bán kính phủ sóng là K đơn vị chiều dài để phủ sóng cho một số người sử dụng dịch vụ trên con đường này.

Yêu cầu: Bạn hãy xác định vị trí đặt trạm phát sóng sao cho trạm có thể phục vụ được số lượng người sử dụng nhiều nhất có thể.

Dữ liệu: cho trong file văn bản MOBI.INP có cấu trúc như sau:

Dòng đầu tiên ghi hai số nguyên N và K (0<N ≤10⁶, 0<K≤2*10⁶), trong đó N là số điểm dân cư đã được đánh dấu, K là bán kính phủ sóng của trạm.
Trong N dòng tiếp theo, dòng thứ i (i=1..N) ghi hai số nguyên X[i] và Y[i] cho biết tại vị trí X[i] có số lượng người dùng là Y[i] (0≤ X[i] ≤10⁶, 0≤Y[i] ≤10⁴). Các số trên cùng dòng viết cách nhau ít nhất một dấu cách.

Kết quả: Ghi ra file văn bản MOBI.OUT một số nguyên cho biết số người dùng nhiều nhất sẽ được phục vụ.

Ví dụ:

MOBI.INP

MOBI.OUT

Giải thích

4 3

7 4

15 10

2 2

1 5

Chọn vị trí trạm tại X=4. Như vậy có thể phủ sóng đến các vị trí có toạ độ 1, 2, 7. Số lượng người sử dụng lớn nhất là 11.

2. Hướng dẫn Olympic 30/4/2015 tin học 10

đọc file vào mảng Y, với Y[i] là số lượng người dùng tại tọa độ i.
tạo biến S, là tổng của Y[1]->Y[2*k]. cập nhập KQ.
dần dần tịnh tiến sang bên phải…
for i:=1 to 10^6-2*k do
{
S:=S-y[i-1];
S:=S+y[i+k*2];
cập nhật KQ dựa trên S.
}
DPT(10^6).

Tham khảo thêm lời giải của Ban tổ chức Olympic 30/4:

lời giải của Ban tổ chức Olympic 30/4 môn tin học

3. Code tham khảo

Đây là code tham khảo của mình viết :v nếu có sai sót các bạn vui lòng comment dưới đây

const   fi='MOBI.INP';
        fo='MOBI.OUT';
        nmax=1000000;
type    data=longint;
var
        f:text;
        Y:array[0..4*nmax+2] of data;
        x,n,k,S,res,i:data;

begin
        assign(f,fi); reset(f);
        readln(f,n,k);
        fillchar(y,sizeof(y),0);
        for i:=1 to n do
                readln(f,x,y[x]);
        close(f);
        s:=0;
        for i:=0 to 2*k do
                s:=s+y[i];
        res:=s;
        for i:=1 to nmax-2*k do
                begin
                        s:=s-Y[i-1];
                        s:=s+y[i+2*k];
                        if res<s then res:=s;
                end;
        assign(f,fo); rewrite(f);
        writeln(f,res);
        close(f);
end.

const fi='MOBI.INP';

fo='MOBI.OUT';

nmax=1000000;

type data=longint;

var

f:text;

Y:array[0..4*nmax+2] of data;

x,n,k,S,res,i:data;

begin

assign(f,fi); reset(f);

readln(f,n,k);

fillchar(y,sizeof(y),0);

for i:=1 to n do

readln(f,x,y[x]);

close(f);

s:=0;

for i:=0 to 2*k do

s:=s+y[i];

res:=s;

for i:=1 to nmax-2*k do

begin

s:=s-Y[i-1];

s:=s+y[i+2*k];

if res<s then res:=s;

end;

assign(f,fo); rewrite(f);

writeln(f,res);

close(f);

end.

2 thoughts on “Đặt trạm phủ sóng – Olympic 30/4/2015 tin học 10”

unmatched Tài Nguyễn says:
4 Tháng Tám, 2016 at 17:34
ý tưởng hk hay 🙂
Trả lời
- admin says:
  4 Tháng Tám, 2016 at 19:19
  Bạn mình luận vớ vẩn quá. Độ phức tạp O(n) mà bảo chưa hay? Nếu bạn nghĩ có cách nào tối ưu và hay hơn thì nói xem?
  Trả lời

Đặt trạm phủ sóng – Olympic 30/4/2015 tin học 10

1. Đề bài Olympic 30/4/2015 tin học 10

2. Hướng dẫn Olympic 30/4/2015 tin học 10

3. Code tham khảo

Bài viết liên quan

2 thoughts on “Đặt trạm phủ sóng – Olympic 30/4/2015 tin học 10”

Trả lời Hủy