Phân công công việc

[dongbo]

Một phần mềm nhỏ đã được người phân tích thiết kế chia làm n công đoạn và giao cho 2 lập trình viên thực hện. Mỗi lập trình viên sẽ lần lượt viết các đoạn mã chương trình được giao một cách tuần tự và tiến hành song với lập trình viên còn lại.
Trong 2 lập trình viên, có 1 người chuyên lập trình Pascal và một người chuyên lập trình C++. Sau khi viết xong các đoạn chương trình, họ sẽ dịch dưới dạng các thư viện liên kết ngoài và sau đó chỉ cần lắp ráp lại là xong. Tuy nhiên, có những công đoạn mà lập trình viên Pascal viết nhanh hơn và cũng có những đoạn viết chậm hơn lập trình viên C++.
Có n công đoạn. Cho biết thời gian dự kiến đẻ lập trình viên Pascal viết đoạn thứ i là pi phút, người lập trình viết đoạn thứ j là cj phút. Hãy phân công mỗi đoạn cho đúng một người viết để thời gian hoàn thành phần mềm là nhanh nhất.
(n≤100, pi,cj≤30000)

Dữ liệu: File SOFTWARE.INP:
- Dòng 1 chứa n.
- Dòng 2 chứa các số từ p1đến pn.
- Dòng 3 chứa các số từ c1 đến cn.
Kết quả: File SOFTWARE.OUT:
- Dòng 1 ghi thời gian ngắn nhất để hoàn thành phần mềm.
- Dòng 2 ghi số hiệu các công đoạn giao cho lập trình viên Pascal.
- Dòng 3 ghi số hiệu các công đoạn giao cho lập trình viên C++.

Ví dụ:

SOFTWARE.INP
6
10 100 30 50 50 80
100 30 40 40 60 90

SOFTWARE.OUT
130
1 3 6
2 4 5

[Farmer_Boy]

Hình như cái test đó bị sai rồi thì phải, phải là 230 chứ, nhưng nhỏ nhất là 220

[Farmer_Boy]

Có phải như vậy không nhỉ:


program phancong;
var
a,b:array [1..100] of integer;
n,i,c,v:byte;
f:text;
tong:integer;
begin
assign(f,'software.inp');reset(f);
readln(f,n);
for i:=1 to n do
read(f,a[i]);
readln(f);
for i:=1 to n do
read(f,b[i]);
tong:=0;
c:=0;
v:=0;
for i:=1 to n do
if a[i]<b[i] then
begin
tong:=tong+a[i];
inc(c);
a[c]:=i;
end
else begin
tong:=tong+b[i];
inc(v);
b[v]:=i;
end;
close(f);
assign(f,'software.out');rewrite(f);
writeln(f,tong);
for i:=1 to c do
write(f,a[i],' ');
writeln(f);
for i:=1 to v do
write(f,b[i],' ');
close(f);
end.

[auauau97]

Có phải như vậy không nhỉ:


program phancong;
var
a,b:array [1..100] of integer;
n,i,c,v:byte;
f:text;
tong:integer;
begin
assign(f,'software.inp');reset(f);
readln(f,n);
for i:=1 to n do
read(f,a[i]);
readln(f);
for i:=1 to n do
read(f,b[i]);
tong:=0;
c:=0;
v:=0;
for i:=1 to n do
if a[i]<b[i] then
begin
tong:=tong+a[i];
inc(c);
a[c]:=i;
end
else begin
tong:=tong+b[i];
inc(v);
b[v]:=i;
end;
close(f);
assign(f,'software.out');rewrite(f);
writeln(f,tong);
for i:=1 to c do
write(f,a[i],' ');
writeln(f);
for i:=1 to v do
write(f,b[i],' ');
close(f);
end.
bài này của bạn khá hay.
bạn có thể nói thêm 1 chút về thuật toán không ?
thanks

[Farmer_Boy]

bài này của bạn khá hay.
bạn có thể nói thêm 1 chút về thuật toán không ?
thanks

Đơn giản thôi, sau khi nhập 2 mảng a và b xong, cho i chạy từ 1 -> n, so sánh a[i] và b[i] với nhau. Nếu a[i] nhỏ hơn thì cộng vào biến tổng và ngược lại, đồng thời lưu i vào mảng a hoặc b với 2 biến c và v để khỏi cần tạo thêm mảng khác, sau đó in ra

[dongbo]

Bạn hiểu nhầm đề rồi bạn ơi. Hai người làm song song và độc lập với nhau nên thời gian hoàn thành phần mềm đó là thời gian của người làm xong sau cùng. Không đơn giản là chỉ chọn thời gian hoàn thành công đoạn ngắn nhất mà giao cho người đó làm mà phải phân phối cho thời gian người nào làm nhiều hơn mà nhỏ nhất nữa. Trên ví dụ trên, 130 phút là tổng thời gian của lập trình viên Pascal hoàn thành sau lập trình viên C++ (110 phút) và cũng là thời gian hoàn thành phần mềm.

[Farmer_Boy]

Nếu vậy thì phải là 120 chứ

[Farmer_Boy]

Sặc bạn chép cái đề bị sai rồi, ở chỗ cái test dòng thứ 3 của file input phần tử thứ 2 là 30 chứ không phải là 10.

Vào link này để xem đề đúng: http://www.scribd.com/doc/60317245/88/T%C6%AF-DUY-KI-U-UC
Trang 98

[haplinhavxt]

Bài này thì QHĐ thôi, không cần bàn nhiều!

[xuperman]

cái test ví dụ của bạn sao không khớp với đề bài nhỉ, mình cộng tới cộng lui đâu có ra 130. bạn cộng thử coi, hay là mình hiểu sai cái đề.

[xuperman]

Hình như cái test đó bị sai rồi thì phải, phải là 230 chứ, nhưng nhỏ nhất là 220

ý của bạn hình như giống thuật toán con kiến bò trên tháp.
Nhưng mà đâu có đúng trong trường hợp này vì trong khi anh thợ Pascal viết module 1 thì anh thợ Cplus củng viết module2.

..@@~@@~!@ ..mà như vậy theo ví dụ trên mình cộng lại không ra 130 mà chỉ ra 120 à -->mâu thuẫn với tác giả--> nghi ngỡ lẫn nhau-->nghi ngờ bản thân-->chẳng hiểu.

[dongbo]

Chân thành xin lỗi các bạn. Đã edit. :) Mọi người cùng bàn thuật toán nhé. Thanks.

[Farmer_Boy]

Thôi, kêu anh haplinhavxt viết code QHĐ ra là xong ngay

[ThangA3]

nói cho nhìu làm gì post code lên cho nhanh, nói mồm thỳ ai mà chả nói đc, chỉ có viết đc code mới thể hiện đc đẳng cấp

[xuperman]

nói cho nhìu làm gì post code lên cho nhanh, nói mồm thỳ ai mà chả nói đc, chỉ có viết đc code mới thể hiện đc đẳng cấp

Ông này nói thấy ghét. có tài giỏi thì post code có thời gian thực thi tốt nhất lên đi.
Người ta đưa ra bài toán để phân tích và trao đổi qua lại để tìm ra cách giải quyết chứ post code lên làm mịa gì. chủ yếu là khả năng phân tích giải thuật chứ lấy cái code làm mịa gì.

[ThangA3]

tui thấy code của famer thế là đc rồi, tui nói là nói cái code QHĐ của haplinh ak (vì tui nghĩ bài này ko cần xài QHĐ).
P/s: mọi thứ phải mang tính thực tiễn, cách tốt nhất để kiểm tra 1 thuật toán đúng hay ko là viết ra code rùi đem đi test. thế thôi chứ tui cũng chẳng có ý gì hết

[HGMinh95]

tui thấy code của famer thế là đc rồi, tui nói là nói cái code QHĐ của haplinh ak (vì tui nghĩ bài này ko cần xài QHĐ).
P/s: mọi thứ phải mang tính thực tiễn, cách tốt nhất để kiểm tra 1 thuật toán đúng hay ko là viết ra code rùi đem đi test. thế thôi chứ tui cũng chẳng có ý gì hết
Vậy bài này dùng cách nào?

[ThangA3]

đó là 1 ẩn số........... trong các ẩn số

[Farmer_Boy]

đó là 1 ẩn số........... trong các ẩn số

Nguy hiểm thật, code của mình thực ra vẫn chưa dc, tìm thời gian ít nhất chứ không phải cái nào ít hơn là dùng cái đó, bài này của thầy Hoàng ra trong bộ bài tập của thầy, có link ở trên đó mọi người

[xuperman]

Trời ơi, lâu rồi mà chưa ai có cách để giải bài này à. Tui cũng pó tay