BCJABUKE spoj – Nhặt táo

Nguồn đề bài: http://www.spoj.com/PTIT/problems/BCJABUKE/

1. Đề bài BCJABUKE spoj PTIT

Mirko vừa tìm thấy 1 trò chơi điện tử cũ. Màn hình của game chia thành N cột. Ở dưới của màn hình , có 1 con thuyên chứa trong M côt (M<N). Người chơi có thê di chuyên thuyên sang trái hoặc phải, nhưng phải trong phạm vi của màn hình. Ban đâu, thuyên ở M côt bên trái nhât của màn hình.

Những quả táo sẽ rơi từ phía trên của màn hình. Môi quả bắt đâu rơi ở đâu trên của môt côt, và rơi xuông phía dưới của màn hình. Quả tiêp theo rơi sau khi quả trước đó chạm đáy.

Nhiêm vụ của bạn là tìm cách di chuyên ngắn nhât đê có thê lây tât cả trái táo.

Dữ liệu:

Dòng đâu chứa 2 sô nguyên N và M (1<=M<=N<=10).

Dòng 2 chứa sô nguyên J (1<=J<=20), sô trái táo rơi.

J dòng sau là thứ tự các côt của các quả táo sẽ rơi.

Kết quả:

Dòng chứa sô nguyên duy nhât là sô di chuyên bé nhât đê lây tât cả trái táo.

Example
Input:
5 1
3
1
5
3

Output:
6
Input:
5 2
3
1
5
3
Output:
4

2. Hướng dẫn BCJABUKE spoj

– Đây là bài toán duyệt

– Tạo 2 biến quản lí vị trí đầu và cuối của con thuyền.

– mỗi lần đọc vào cột mà quả táo sẽ rơi, bạn tính xem quả táo đó có nằm trong khoảng của con thuyền không? nếu có thì không làm gì hết (tức là con thuyền ở vị trí đó thì sẽ nhặt dc táo). ngược lại bạn phải tìm cách dịch chuyển con thuyền Vừa đủ để nhặt được quả táo thông qua vị trí đầu cuối của con thuyền.

3. Code tham khảo BCJABUKE spoj

const   fi='';
        nmax=10;
type    data=longint;
var
        f:text;
        dau,cuoi,n,m,test,k,s:data;

function min(a,b:data):data;
begin
        if a<b then exit(a);
        exit(b);
end;

procedure xuli;
var     i,j,x,tinh:data;
begin
        assign(f,fi); reset(f);
        readln(f,n,m);
        readln(f,test);
        s:=0;
        dau:=1; cuoi:=m;
        for i:=1 to test do
                begin
                        readln(f,x);
                        if (x>=dau) and (x<=cuoi) then
                                continue
                        else
                                begin
                                        tinh:=min(abs(x-dau),abs(x-cuoi));
                                        s:=s+tinh;
                                        if x < dau then
                                                begin
                                                        dau:=dau-tinh;
                                                        cuoi:=cuoi-tinh;
                                                end
                                        else
                                                if x>cuoi then
                                                        begin
                                                                dau:=dau+tinh;
                                                                cuoi:=cuoi+tinh;
                                                        end;
                                end;
                        end;
        write(s);
        close(f);
end;

begin
        xuli;
end.