Announcement

Collapse
No announcement yet.

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

Collapse
X
 
  • Filter
  • Time
  • Show
Clear All
new posts

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

    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"

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

    Comment


    • #3
      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
      Không có gì là không thể nếu chúng ta có lòng tin.
      http://gabrielbl.com

      Comment


      • #4
        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 :-?

        Comment


        • #5
          Cái site đó nguy cơ bị sập rất cao, tội nghiệp )
          Không có gì là không thể nếu chúng ta có lòng tin.
          http://gabrielbl.com

          Comment


          • #6
            Originally posted by CLB ArtUIT View Post
            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 í :-)
            Amat Victoria Curam.

            ------
            Ping me at me@toan.mobi

            Comment


            • #7
              Originally posted by anonymous View Post
              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.
              Last edited by toannv; 25-10-2011, 23:29.
              :happy:SỐNG TRONG MÁI NHÀ UIT, BẠN HÃY NHỚ :happy:
              1. Chấp hành pháp luật, tuân thủ nội quy; 2. Tích cực học tập, chủ động nghiên cứu
              3. Đi học đúng giờ, trang phục lịch sự; 4. Nhớ xếp hàng và đừng chen lấn
              5. Sống có trách nhiệm và biết sẻ chia; 6. Giữ gìn tài sản chung như tài sản của chính bạn
              7. Sử dụng tài sản, thời gian hiệu quả; 8. Khiêm tốn, lễ phép, hòa nhã, thân thiện
              9. Không xả rác để không nhặt rác; 10. Văn minh, lịch sự dù trên lớp học, diễn đàn hay mạng xã hội

              Comment


              • #8
                có tài mà hay khoe là vô dụng
                Be different and always different
                http://archlinuxvn.org/
                http://theslinux.org
                http://lab.infosec.xyz

                Comment


                • #9
                  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??

                  Im a british accent lover

                  Comment


                  • #10
                    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à

                    Comment


                    • #11
                      DIS ..... like :-"

                      Comment


                      • #12
                        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.
                        Code:
                        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é!
                        Last edited by 11520673; 26-10-2011, 03:29.

                        Comment


                        • #13
                          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ơ.

                          Comment


                          • #14
                            Originally posted by anonymous View Post
                            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.
                            Last edited by 09520019; 26-10-2011, 09:57.
                            Khoảng cách giữa bạn và ước mơ của bạn là bao xa ?

                            Comment


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

                              ------
                              Ping me at me@toan.mobi

                              Comment

                              LHQC

                              Collapse
                              Working...
                              X