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 ...
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
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 | 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. |
