[Thuật toán] THÁCH THỨC TOÀN THỂ SINH VIÊN UIT

[anonymous]

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)

Các bạn có thể kiểm tra tính đúng đắn của bài giải bằng cách nộp ở trang http://vn.spoj.pl/problems/LQDDIV/.
"Good luck"

[09520339]

Chắc lại khích để nhờ giải dùm đồ án rồi))

[09520548]

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

[CLB ArtUIT]

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 :-?

[09520548]

Cái site đó nguy cơ bị sập rất cao, tội nghiệp )

[08520604]

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 :-?

Cần , gạch nung trong lò bát quái í :-)

[BiThuDoan]

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.

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.

[10520058]

có tài mà hay khoe là vô dụng

[08520016]

mình thì tài không có nhưng mà gạch đá thì nhiều
Chắc bác cần gạch xây nhà hay xây j j đó mà nghèo không có nên cần thu gom??

[09520157]

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à

[08520206]

DIS ..... like :-"

[11520673]

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[i]);
                b[i]:=a[i];
                tong:=tong+a[i];
                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[i]>b[j] then
                begin
                        z:=b[i];
                        b[i]:=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[i]
               else w2:=w2+b[i];
        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.

input output mình quên câu lệnh r, chịu khó nhập tay nhé!

[07520247]

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ơ.

[09520019]

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.

Đâ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.

[08520604]

chậc , chậc, khổ thân thằng bé , chui vào ổ kiến lửa rồi :-)