//
you're reading...
00 - Chủ đề chung

Xếp lịch công việc – Bài tập 0


Bài 0: (Lịch trực )


Giả sử trong một phiên làm việc từ thời điểm 0 đến thời điểm T=8640000, một trung tâm tính toán phải thực hiện N chương trình, chương trình i thực hiện từ thời điểm A[i] đến thời điểm B[i], 0 A[i]B[i] <T.
1. Cho trước một đoạn thời gian [P1, Q1]. Hãy xét xem tại mọi thời điểm của đoạn đó luôn có chương trình chạy hay không?
2. Cho trước một đoạn thời gian [R1, S1]. Hãy xét xem liệu tại mọi thời điểm của đoạn đó luôn không có chương trình chạy hay không?
3. Hãy tìm đoạn thời gian [P, Q] dài nhất sao cho tại mọi điểm của nó luôn có chương trình chạy.
4. Hãy tìm đoạn thời gian [R, S] dài nhất sao cho tại mọi điểm của nó đều không có chương trình chạy.
Dữ liệu vào được cho bởi file văn bản INP.BL trong đó dòng thứ nhất ghi số nguyên dương N 200. Dòng thứ i+1 (1 i N) ghi hai số nguyên không âm A[i] và B[i]. Dòng thứ N+2 ghi hai số nguyên không âm P1, Q1 ( P1 Q1). Dòng thứ N+3 ghi hai số nguyên không âm R1, S1 (R1 S1)
Kết quả ghi ra file văn bản OUT.BL: dòng thứ nhất ghi 1 hoặc 0 tuỳ thuộc kết quả cụ thể (tìm được thì ghi số 1, không tìm được thì ghi số 0). Dòng thứ hai cũng ghi 1 hoặc 0 theo nghĩa trên. Dòng thứ ba ghi hai số P, Q. Dòng thứ tư ghi hai số R, S.
Ví dụ:
INP.BL
5
1000 10000
2000 30000
20000 100000
200000 500000
8000000 8500000
1000 100000
0 1000
OUT.BL
1
0
8000000 8500000
500001 7999999

Hướng dẫn: Dùng mảng A một chiều (mỗi phần tử là một record gồm 2 trường: thời điểm đầu và thời điểm cuối của mỗi chương trình). Sắp tăng mảng A theo thời điểm đầu của mỗi chương trình. Sau đó duyệt mảng A để tạo mảng B (cùng kiểu mảng A) lưu các đoạn gồm các thời điểm liên tiếp có chương trình, và tạo mảng C để lưu các đoạn gồm các thời điểm liên tiếp không có chương trình nào. Dựa vào các mảng B và C dẫn ra kết luận thích hợp.


Chương trình bài 0


const T = 8640000;
max = 1000;
fi = ‘xl00.inp’;
fo = ‘xl00.out’;
type re = record d,c: longint end;
m1 = array[1..max] of re;
var a,b,c : m1;
f : text;
n,sd,sr : integer;
p,q,r,s : longint;
procedure docf;
begin {Đọc file input lấy giá trị N, mảng A(N), giá trị các biến p, q, r, s} end;
procedure sap;
begin
{Sắp tăng mảng A theo theo khoá là thời điểm đầu của mỗi chương trình }
end;
procedure tao_b_c; {b chứa các đoạn làm liên tục. C chứa các đoạn không có chương trình}
var i,j: integer; cuoi: longint;
begin
sd := 1;
i := 1;
b[sd].d := a[i].d;
cuoi := a[i].c;
while i<n do
begin
if a[i+1].d>cuoi+1 then
begin
b[sd].c := cuoi;
inc(sd);
b[sd].d := a[i+1].d;
cuoi := a[i+1].c;
inc(i);
end
else
begin
if a[i+1].c>cuoi then cuoi:= a[i+1].c;
inc(i);
end;
end;
b[sd].c:= cuoi;
sr:= 1;
if b[1].d <> 0 then
begin
c[sr].d:= 0;
c[sr].c:= b[1].d-1;
inc(sr);
end;
i:= 2;
while i<=sd do
begin
c[sr].d:= b[i-1].c+1;
c[sr].c:= b[i].d-1;
inc(sr);
inc(i);
end;
if b[sd].c<T then
begin
c[sr].d:= b[sd].c+1;
c[sr].c:= T;
end;
end;
procedure caua;
var i: integer;
begin
for i:=1 to sd do
if (b[i].d<=p) and (q<=b[i].c) then
begin
writeln(f,1);
exit;
end;
writeln(f,0);
end;
procedure caub;
var i: integer;
begin
for i:=1 to sr do
if (c[i].d<=r) and (s<=c[i].c) then
begin
writeln(f,1);
exit;
end;
writeln(f,0);
end;
procedure cauc;
var ld,lc,lmax: longint;
i : integer;
begin
lmax:= -1;
for i:=1 to sd do
if (b[i].c-b[i].d)>lmax then
begin
lmax:= b[i].c-b[i].d;
ld := b[i].d;
lc := b[i].c;
end;
writeln(f,ld,’ ‘,lc);
end;
procedure caud;
var ld,lc,lmax: longint;
i : integer;
begin
lmax:= -1;
for i:=1 to sr do
if (c[i].c-c[i].d)>lmax then
begin
lmax:= c[i].c-c[i].d;
ld := c[i].d;
lc := c[i].c;
end;
writeln(f,ld,’ ‘,lc);
end;
BEGIN
docf;
sap;
tao_b_c;
assign(f,fo);
rewrite(f);
caua;
caub;
cauc;
caud;
close(f);
END.

About pascalteacher

Trang thông tin Toán học và Tin học

Thảo luận

Chưa có phản hồi.

Gửi phản hồi

Mời bạn điền thông tin vào ô dưới đây hoặc kích vào một biểu tượng để đăng nhập:

WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com Log Out / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Log Out / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Log Out / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Log Out / Thay đổi )

Connecting to %s

Các tác giả

Tháng Mười 2016
M T W T F S S
« Sep   Nov »
 12
3456789
10111213141516
17181920212223
24252627282930
31  

NCT Computer

Flickr Photos

A bellezza di a natura (C☺rsica)

Southern White-faced Owl D75_5752.jpg

2016 Lake Yamanaka winter Fuji

More Photos

Thống kê

  • 78,768 lượt xem

%d bloggers like this: