Sau khi xem qua một số bài tập thuật toán được post trên forum của trường UIT, mình thấy trình độ các bạn còn non kém quá. Không biết UIT các bạn có nhân tài thuật toán nào không. Nhân đây, mình “mạn phép” post 1 bài sau đây. Hi vọng UIT có người giải được.
Giới hạn thời gian: 1s
Ngôn ngữ: C++, Java, Pascal.
Cho N người(2≤N≤32) ,mỗi người có một số ai(1 ≤ ai ≤ 10^9) được gọi là độ tin cậy
Cần phân chia n người này vào 2 tập sao cho:
Mỗi người thuộc đúng một tập
Chênh lệch tổng độ tin cậy của 2 phần là bé nhất
Input
Dòng đầu chứa số nguyên N
Dòng tiếp theo chứa N số : số thứ i là độ tin cậy của người thứ i
Output
Ghi ra hai số u và v với u là độ chênh lệch nhỏ nhất và v là số cách phân chia
Example
Input:
5
1 5 6 7 8
Output:
1 3
Chú thích : Độ chênh lệch ít nhất của 2 phần là 1
Có 3 cách phân chia .3 cách phân chia nhóm 1 là (3,5) ,(1,3,4)
và (1,2,5)
Không biết trình độ bạn thế nào nhưng cách nói chuyện và đặt tiêu đề của bạn thì thấy rõ bạn là một con người tự cao tự đại. Nên nhớ núi cao có núi còn cao hơn. Bó tay một con người :|. Đề nghị các bạn UIT không giải mà cứ gạch đá chủ topic vào
[QUOTE=CLB ArtUIT;18941]Quảng cáo cho cái site http://vn.spoj.pl/problems/LQDDIV/. chứ j đâu mà … anh em có cần gạch chất lượng cao ko :-?[/QUOTE]
Cần , gạch nung trong lò bát quái í
[QUOTE=anonymous;18931]Sau khi xem qua một số bài tập thuật toán được post trên forum của trường UIT, mình thấy trình độ các bạn còn non kém quá. Không biết UIT các bạn có nhân tài thuật toán nào không. Nhân đây, mình “mạn phép” post 1 bài sau đây. Hi vọng UIT có người giải được.
[/QUOTE]
Do bên UIT “giấu hàng ở” http://forum.uit.edu.vn/forums/74-Thuat-toan-OLP nên bên ngoài hok thấy được.
Đề nghị các bạn giải 1-2 chứ không nên có lời lẻ không hay.
*Giang hồ *cũng nên múa vài đường quyền để tự giới thiệu.
các bác không hiểu gì hết , bạn ấy đang PR cho trang http://vn.spoj.pl/problems/LQDDIV/ gồm toàn những thằng dở hơi rảnh đời chuyên khoe khoang tụ tập ấy mà
Thường thì những bài mình nghĩ ra cách làm ít khi nào là bài khó, bài này mình cũng nghĩ ra 1 cách bạn coi thử đúng hay k?
Tìm độ chênh lệch nhỏ nhất:sắp xếp các số theo thứ tự tăng, rồi đặt số lớn nhất vào một trong hai tập. Sau đó, đặt số tiếp theo vào tập đang có tổng bé hơn, tiếp tục cho đến khi tất cả các số được xét.Ta đc 2 phần, lấy abs hiệu 2 phần ra độ chênh lệch nhỏ nhất.
Sau cùng đệ quy tìm tất cả các tổ hợp phù hợp có độ chlech pé nhất r đếm số trường hợp in ra.
program test;
var
a,b,c:array[0..33] of integer;
tong,n,chlmin,s,dem,so:integer;
{-------------------------------------------}
procedure nhap;
var
i:integer;
begin
writeln('Nhap n: ');
readln(n);
tong:=0;
writeln('Nhap mang: ');
for i:=0 to n-1 do
begin
readln(a*);
b*:=a*;
tong:=tong+a*;
end;
end;
{----------------------------------------------}
procedure xeptagdan;
var
i,j,z:integer;
begin
for i:=0 to n-2 do
for j:=i+1 to n-1 do
if b*>b[j] then
begin
z:=b*;
b*:=b[j];
b[j]:=z;
end;
end;
{--------------------------------------------}
procedure chenhlechmin;
var
w1,w2,i:integer;
begin
w1:=b[n-1];
w2:=0;
for i:=n-2 downto 0 do
if w1<w2 then w1:=w1+b*
else w2:=w2+b*;
chlmin:=abs(w1-w2);
end;
{--------------------------------------------------}
{------------------------------------------------------}
procedure xuly(m:integer);
var
j:longint;
begin
for j:=m to n-1 do
if s+a[j]<=so then
begin
s:=s+a[j];
if s=so then inc(dem)
else if j<n-1 then xuly(j+1);
s:=s-a[j];
end;
end;
{------------------------------------------}
begin
nhap;
s:=0;
dem:=0;
xeptagdan;
chenhlechmin;
so:=(tong-chlmin)div 2;
xuly(0);
writeln('Ket qua');
writeln(chlmin,' ',dem);
readln;
end.
Bài này là quy hoạch động thuần túy mà. Chính xác là đề kiểm tra lần 2 môn Phân tích và thiết kế thuật toán của khoa CS.
Mà đề ra không chỉ 32 đâu. 100 cơ.
[QUOTE=anonymous;18931]Sau khi xem qua một số bài tập thuật toán được post trên forum của trường UIT, mình thấy trình độ các bạn còn non kém quá. Không biết UIT các bạn có nhân tài thuật toán nào không. Nhân đây, mình “mạn phép” post 1 bài sau đây. Hi vọng UIT có người giải được.
[/QUOTE]
Đây là bài tập cơ bản, nếu bạn gọi đây là 1 bài để thử nhân tài thì trình bạn còn non lắm. Thân
Độ phức tạp bài này là O(m * 2^m ), với m = n / 2
Các kỹ thuật sử dụng: QHĐ trạng thái & tìm kiếm nhị phân
Mình chỉ giải bài này với 1 đk: Hãy là quân tử đứng trong sáng. Mình không biết bạn là ai, tên gì, ở đâu. Và bạn đã làm được bài này chưa ? ;))
(bài này trong đk bình thường code 1h là maximum, trong đk phòng thi Olympic code 30’)
Như trường ĐHKHTN ấy, giao hữu rất là thân thiện, mặc dù đội KHTN rất là mạnh nhưng 2 bên đều giao hữu thân thiện, biết nhau, chứ ko phải cái loại chui vào trường khác post bài thách thức nhau như vậy.
Cách forum UIT của các bạn làm việc rất là không minh bạch, tài khoản Anonymous mình dùng để mở topic này đã bị khóa chức năng post bài nên bất đắc dĩ mình phải đăng ký tài khoản Anonymous1 để trao đổi với các bạn (tức là Anonymous1 = Anonymous).
Mình rất hoan nghênh tinh thần bạn 11520673 - Lâm Thị Mỹ Tú là người đầu tiên đã đưa ra đáp án. Bạn đã sử dụng thuật toán tham lam và đệ quy nhưng :
a. Thuật toán tham lam trong trường hợp này là không chính xác.
b. Dùng đệ quy trong bài này sẽ bị quá thời gian cho phép.
Xem ra các bạn vẫn chưa đủ “trình độ” để accept bài này, các bạn code xong thì gửi lên VOJ, nếu accept thì xem như đã làm xong.
Đối với các bạn thích gạch đá, mình không hiểu tại sao các bạn không xem đó là một thách thức và nghĩ ra cách giải quyết mà thay vào đó các bạn lại nói những điều vô ích, thiếu tính xây dựng. UIT đã chấp nhận bước ra sân chơi lớn đồng nghĩa với việc phải đón nhận thách thức mới, từ chối giải quyết thách thức các bạn đã từ chối tiến bộ.
@Bạn Châu : đây là proof
Khi nào bạn Accept hãy nói chuyện với mình.
Đôi lời gửi UITers.
[QUOTE=anonymous1;19017]Chào các bạn,
Mình có 3 vấn đề muốn chia sẻ :
Cách forum UIT của các bạn làm việc rất là không minh bạch, tài khoản Anonymous mình dùng để mở topic này đã bị khóa chức năng post bài nên bất đắc dĩ mình phải đăng ký tài khoản Anonymous1 để trao đổi với các bạn (tức là Anonymous1 = Anonymous).
Mình rất hoan nghênh tinh thần bạn 11520673 - Lâm Thị Mỹ Tú là người đầu tiên đã đưa ra đáp án. Bạn đã sử dụng thuật toán tham lam và đệ quy nhưng :
a. Thuật toán tham lam trong trường hợp này là không chính xác.
b. Dùng đệ quy trong bài này sẽ bị quá thời gian cho phép.
Xem ra các bạn vẫn chưa đủ “trình độ” để accept bài này, các bạn code xong thì gửi lên VOJ, nếu accept thì xem như đã làm xong.
Đối với các bạn thích gạch đá, mình không hiểu tại sao các bạn không xem đó là một thách thức và nghĩ ra cách giải quyết mà thay vào đó các bạn lại nói những điều vô ích, thiếu tính xây dựng. UIT đã chấp nhận bước ra sân chơi lớn đồng nghĩa với việc phải đón nhận thách thức mới, từ chối giải quyết thách thức các bạn đã từ chối tiến bộ.
@Bạn Châu : đây là proof
Khi nào bạn Accept hãy nói chuyện với mình.
Đôi lời gửi UITers.[/QUOTE]
xin lỗi không biết trình độ bạn đến đâu nhưng kiểu nói người khác còn non thì hình như hơi tự đại quá mức
bạn code giỏi vậy cho mình hỏi vài câu nhé ( dù hơi gà )
1.trình biên dịch làm gì đầu tiên khi bắt đấu biên dịch.
2.trong quá trình biên dịch, trình biên dịch sẽ thêm vào cái gì và trong khi thực thi gọi các thư viện, chúng sẽ được “nhét” vào đâu
mình còn gà lắm mong bạn thông cảm
[QUOTE=anonymous1;19017]Chào các bạn,
Mình có 3 vấn đề muốn chia sẻ :
Cách forum UIT của các bạn làm việc rất là không minh bạch, tài khoản Anonymous mình dùng để mở topic này đã bị khóa chức năng post bài nên bất đắc dĩ mình phải đăng ký tài khoản Anonymous1 để trao đổi với các bạn (tức là Anonymous1 = Anonymous).
Mình rất hoan nghênh tinh thần bạn 11520673 - Lâm Thị Mỹ Tú là người đầu tiên đã đưa ra đáp án. Bạn đã sử dụng thuật toán tham lam và đệ quy nhưng :
a. Thuật toán tham lam trong trường hợp này là không chính xác.
b. Dùng đệ quy trong bài này sẽ bị quá thời gian cho phép.
Xem ra các bạn vẫn chưa đủ “trình độ” để accept bài này, các bạn code xong thì gửi lên VOJ, nếu accept thì xem như đã làm xong.
Đối với các bạn thích gạch đá, mình không hiểu tại sao các bạn không xem đó là một thách thức và nghĩ ra cách giải quyết mà thay vào đó các bạn lại nói những điều vô ích, thiếu tính xây dựng. UIT đã chấp nhận bước ra sân chơi lớn đồng nghĩa với việc phải đón nhận thách thức mới, từ chối giải quyết thách thức các bạn đã từ chối tiến bộ.
@Bạn Châu : đây là proof
Khi nào bạn Accept hãy nói chuyện với mình.
Đôi lời gửi UITers.[/QUOTE]
sang nhà người ta thì (Đối với người lịch sự, có học) đầu tiên là phải giới thiệu đôi lời về bản thân mình đã chứ. rồi có thách thức cũng chẳng sao. ít ra cũng phải cho cái thông tin tên gì, học trường nào!
tự nhiên sang chưa nói gì đã phán câu như thánh sống ~> “Sau khi xem qua một số bài tập thuật toán được post trên forum của trường UIT, mình thấy trình độ các bạn còn non kém quá”
thử hỏi với forum trường bạn thì có gạch đá không? bạn là tài khoản ngoài trường thì không xem hết được các box trong forum này đâu.
Sao nhiều người thích nói lý với “ếch ngồi đáy giếng” nhỉ?Hắn ta còn không truy nhập vào những phần chính, để biết là mình vào đó đọc không được mà vẫn phán bừa như thế thì đủ hiểu rồi…
mình thì tài không có nhưng mà gạch đá thì nhiều
