Fence

[ngtrhieu0011]

Dì Poly giao cho Tom một nhiệm vụ quan trọng là sơn lại các thanh gỗ ở hàng rào sau nhà. Các tấm gỗ làm hàng rào đã được sơn từ trước, nhưng lâu ngày, một số tấm bị bong sơn. Tôm phải sơn lại những tấm này. Hàng rào rất dài nên dì Poly đã cho chở đến một thùng sơn lớn dặt ở đầu hàng rào, cách thanh gỗ đầu tiên đúng 1 foot. Các thanh gỗ trên hàng rào cũng được đóng cách nhau đúng 1 foot. Thùng sơn rất nặng nên không thể di chuyển được. Tôm được trang bị một xô đựng sơn và một chổi quét. Nếu đổ sơn đầy xô thì có thể quét được k thanh (1 ≤ k ≤ 100). Bất cứ lúc nào Tôm cũng có thể xách xô về lấy sơn ở thùng. Sơn xong Tôm phải mang xô và chổi sơn về đặt trả cạnh thùng. Hàng rào được dựng từ n thanh gỗ đánh số từ 1 đến n (1 ≤ n ≤109), trên đó có m đoạn bị bong sơn (1 ≤ m ≤ 50). Các đoạn này không giao nhau. Đoạn thứ i được xác định bởi vị trí li của thanh bên trái và vị trí ri của thanh bên phải (1 ≤ l[i] ≤ r[i] ≤n).Với đoạn thứ i, cần phải sơn các thanh l[i], l[i+1], . . ., r[i].

Yêu cầu: Hãy xác định chiều dài quãng đường tối thiểu Tôm phải đi để hoàn thành nhiệm vụ dì Poly đã giao.

Dữ liệu: Vào từ file văn bản FENCE.INP, gồm nhiều bộ dữ liệu, mỗi bộ cho trên một nhóm dòng:
• Dòng đầu tiên chứa hai số nguyên n, k,
• Dòng thứ hai chứa số nguyên m,
• Dòng thứ i trong m dòng sau chứa hai số nguyên l[i], r[i].

Kết quả: Đưa ra file văn bản FENCE.OUT, kết quả mỗi test đưa ra trên một dòng dưới dạng một số nguyên.

Ví dụ:
FENCE.INP
10 2
2
8 10
3 5
15 5
3
2 4
6 8
10 12
FENCE.OUT
44
36


Bài này rất dễ làm, các bạn làm thử nhé ^^

[=========> Bổ sung bài viết <=========]

gợi ý: đi ngược từ n về 1

[nhat_truong]

Cách 1:

Dùng mảng đánh dấu P: P[i]=True nghĩa là thanh gỗ thứ i cần sơn lại
Duyệt từ cuối lên đầu, cộng các vị trí cần đi đến vào KQ.
Do cần đi ngược lại thùng sơn nên cần nhân KQ với 2.

VD:
10 2
2
8 10
3 5
KQ:=(10+8+4)*2=44



Program Fence;
Const fi = 'fence.inp';
fo = 'fence.out';
max = 60000;
Var P: array [1..max] of Boolean;
f, g: Text;
n, k, m, KQ: Longint;

Procedure Enter;
Var i, j, x, y: Longint;
Begin
Fillchar(P,SizeOf(P),False);
Readln(f,n,k);
Readln(f,m);
For i:=1 to m do
Begin
Readln(f,x,y);
For j:=x to y do P[j]:=True;
End;
End;

Procedure Solution;
Var i, l, j: Longint;
Begin
KQ:=0;
For i:=max downto 1 do
If P[i] then
Begin
KQ:=KQ+i*2;
j:=i; l:=0;
While (l<k) and (j>0) do
Begin
If P[j] then
Begin
P[j]:=False;
inc(l);
End;
dec(j);
End;
End;
End;


BEGIN
Assign(f,fi); Reset(f);
Assign(g,fo); Rewrite(g);
While not(eof(f)) do
Begin
Enter;
Solution;
Writeln(g,KQ);
End;
Close(f); Close(g);
END.



Cách 2:

Dùng mảng P lưu các vị trí cần sơn.
Sắp xếp lại mảng P thành dãy giảm.
Duyệt từ đầu đến cuối mảng P, cộng các vị trí cần sơn vào KQ.
Tương tự, cần nhân KQ với 2.

VD: Ví dụ ở trên
Dãy P: 8 9 10 3 4 5
Dãy P sau khi sắp xếp: 10 9 8 5 4 3
KQ=(10+8+4)*2=44



Program Fence;
Const fi = 'fence.inp';
fo = 'fence.out';
max = 30000;
Var P: array [1..max] of Integer;
f, g: Text;
n, k, m, l, KQ: Longint;

Procedure Enter;
Var i, j, x, y: Longint;
Begin
Fillchar(P,SizeOf(P),False);
Readln(f,n,k);
Readln(f,m);
l:=0;
For i:=1 to m do
Begin
Readln(f,x,y);
For j:=x to y do
Begin
inc(l);
P[l]:=j;
End;
End;
End;

Procedure Sort;
Var i, j, t: Longint;
Begin
For j:=l downto 2 do
For i:=1 to j-1 do
If P[i]<P[i+1] then
Begin
t:=P[i];
P[i]:=P[i+1];
P[i+1]:=t;
End;
End;


Procedure Solution;
Var i: Longint;
Begin
KQ:=0;
For i:=1 to l do
If (i-1) mod k = 0 then inc(KQ,P[i]);
KQ:=KQ*2;
End;

BEGIN
Assign(f,fi); Reset(f);
Assign(g,fo); Rewrite(g);
While not(eof(f)) do
Begin
Enter;
Sort;
Solution;
Writeln(g,KQ);
End;
Close(f); Close(g);
END.

[ngtrhieu0011]

Đúng rồi đó anh ^^
Bài này chỉ là vét đơn thuần, chỉ khó ở chỗ ta vét từ đâu thôi

[bld]

lúc đầu cũng nghĩ thế , nhưng thấy như vậy hóa ra đề này dễ quá , nên ko dám post , a hieu vào xem d/s đi
ah vậy còn đi từ dưới lên (1..n) , cũng đúng mà ?

[ngtrhieu0011]

bld thử post code bài này lên xem nào?

[bld]

code à ..
nói ngắn gọn dc ko a , đủ thì thêm vào tí xíu

đọc n,k,m
đọc các l , r
sắp xếp lại , phân thành các đoạn độ dài k(đoạn đầu thiếu cũng được), lấy chỉ số của phần tử cuối & đầu mỗi đoạn , cộng lại

có điều phải cộng thêm khoảng cách giữa các chỉ số nữa

cụ thể

8 9 10 3 4 5 1
sắp lại 10 9 8 5 4 3 1
phân các đoạn (10 9) (8 5) (4 3) (1) (0) vì phải về cuối
tổng các chỉ số đầu & cuối mỗi đoạn
10+9+8+5+4+3+1+1=41
công với hiệu 41+(10-9)+(8-5)+(4-3)+(1-1)= 46

[elnino_020993]

bld xem lại, kq bài 1


8 9 10 3 4 5 1
sắp lại 10 9 8 5 4 3 1
phân các đoạn (10 9) (8 5) (4 3) (1) (0) vì phải về cuối
tổng các chỉ số đầu & cuối mỗi đoạn
10+9+8+5+4+3+1+1=41
công với hiệu 41+(10-9)+(8-5)+(4-3)+(1-1)= 46

kq = 44 mà
anh lại có ý tưởng khác cơ,
dựa trên chu kì, có code nà, cùng sửa nha:


const fi='FENCE.INP';
fo='FENCE.OUT';
var f:text;
n,m,k,s,kq:longint;
a:array[0..109] of boolean;
procedure docfile;
var x,y,i,j:longint;
begin
assign(f,fi);
reset(f);
readln(f,n,k);
readln(f,m);
s:=0;
for i:=1 to m do
begin
readln(f,x,y);
for j:=x to y do a[j]:=true;
s:=s+y-x+1;
end;
close(f);
end;

function tim(i,j:longint):longint;
var k,dem:longint;
begin
dem:=0;
k:=i;
repeat
inc(k);
if a[k] then inc(dem);
until dem=j;
tim:=k;
end;

procedure xuly;
var p,q,i,j,x,y:longint;
begin
p:=s mod k;
q:=s div k;
if p=0 then
begin
p:=k;
dec(q);
end;
x:=tim(0,p);
y:=x;
i:=1;
while i<=q do
begin
j:=tim(x,k);
y:=y+x+j;
x:=j;
inc(i);
end;
kq:=y+j;
end;

procedure ghifile;
begin
assign(f,fo);
rewrite(f);
writeln(f,kq);
close(f);
end;

begin
docfile;
xuly;
ghifile;
end.


[=========> Bổ sung bài viết <=========]

mà bạn ngtrhieu0011 sinh năm 93, bằng tuổi mình àh

[ngtrhieu0011]

bài bạn elnino có bộ phức tạp N^2, xét về thời gian thì bài này chỉ cần N tuyến tính là ok

[elnino_020993]

trên thực tế, bài mình tương đương với việc chạy 1 for từ 1 đến N đấy bạn
bạn xem lại đi

[ngtrhieu0011]

uhm, mình hiểu, tại cái function tìm của bạn làm bài toán lên N^2
nhưng với giới hạn bài toàn này thì code đó AC dc

[bld]

bld xem lại, kq bài 1

kq = 44 mà

đâu có , test của e là test khác mà , có thêm số 1 vào nữa , bỏ nó đi cũng ra 44 a à

[nhat_truong]

lúc đầu cũng nghĩ thế , nhưng thấy như vậy hóa ra đề này dễ quá , nên ko dám post , a hieu vào xem d/s đi
ah vậy còn đi từ dưới lên (1..n) , cũng đúng mà ?

Duyệt từ 1 đến n sẽ ko được kq tối ưu đâu bạn.

VD:
P: 10 9 8 5 4 3 2, k=2
KQ=(10+8+4+2)*2=48

Nếu duyệt xuôi:
P: 2 3 4 5 8 9 10. k=2
KQ=(3+5+9+10)*2=54

[ngtrhieu0011]

bài này tối ưu khi duyệt ngược... ^^, độ phức tạp thuật toán khi này là O(N) là quá chuẩn rồi ^^

[bld]

dĩ nhiên đi lộn xộn ko theo thứ tự là chết , chỉ có 2 cách ngược và xuôi , số thanh gỗ cần sơn là ko đổi nên số thanh dư (mod k) giống nhau , chỉ có điều nếu đi xuôi thì các thanh này ở cuối , còn đi ngược thì các thanh này ở đầu , gần hơn , nên đi ngược là tối ưu ...

[elnino_020993]

đi ngược xử lý sẽ tối ưu hơn phải công nhận thế
nhưng ko có nghĩa là ko xuôi được,
nếu duyệt xuôi thì ta bắt đầu từ cái hàng rào thứ (n mod k), nhỉ ;)

[ngtrhieu0011]

Program Fence;

Const Fin = 'Fence.Inp';
Fou = 'Fence.Out';
MaxArr = 100;

Type Arr = Array [0..MaxArr] of Longint;

Var Fi, Fo : Text;
A : Arr;
n, m, k : Longint;
Sum : Int64;
{================================================= ==================}
Procedure Input;

Var i : Longint;

Begin
Readln(Fi, n,k);
Readln(Fi, m);
For i:=1 to m do
Readln(Fi, A[2*i], A[2*i -1]);
End;
{================================================= ==================}
Procedure {Bubble}Sort;

Var i,j,Temp : Longint;

Begin
For i:=1 to 2*m-1 do
For j:=i+1 to 2*m do
If A[i] < A[j] then
Begin
Temp := A[i];
A[i] := A[j];
A[j] := Temp;
End;
End;
{================================================= ==================}
Procedure Process;

Var i,j,y : Longint;
Fl : Boolean;

Begin
Sort;

Sum := 0;
i := 1;
y := k;
While i <= m*2 do
Begin
If A[i] - A[i+1] +1 <= y
Then
Begin
If y = k then Sum := Sum + A[i];
y := y - A[i] + A[i+1] -1;
i := i+2;
End
Else
Begin
If y = k then Sum := Sum + A[i];
A[i] := A[i] -y;
y := k;
End;
End;

Sum := Sum*2;
End;
{================================================= ==================}
Begin
Assign(Fi, Fin);
Reset(Fi);
Assign(Fo, Fou);
Rewrite(Fo);
While not Eof(Fi) do
Begin
Input;
Process;
Writeln(Fo, Sum);
End;
Close(Fi);
Close(Fo);
End.