kết quả từ 1 tới 7 trên 7

Y tuong bai toan nay nhu the nao? ai giup voi

  1. #1
    Ðến Từ
    Quảng Bình
    Thành Viên Thứ: 377431
    Giới tính: Nam
    Bài gửi
    16

    Y tuong bai toan nay nhu the nao? ai giup voi

    Bài 2. Trò chơi với băng số (8 điểm) File bài làm DIV.PAS
    Cho một băng số gồm n số nguyên dương, mỗi số được viết trên một ô. Hãy cắt băng số này thành nhiều đoạn nhất sao cho tổng các phần tử trong các đoạn là bằng nhau.
    Dữ liệu vào: DIV.INP + Dòng đầu ghi n (n ≤ 1000)
    + Dòng tiếp theo ghi n số nguyên dương a1, a2, ..., an
    (các số nằm trên một dòng cách nhau bởi một dấu cách ai ≤ 1000)
    Dữ liệu ra: DIV.OUT Ghi K là số đoạn cần chia.

    10 2 6 2 5 2 1 2


    10

    2 6 2

    5 2 1 2


    Ví dụ:



    DIV.INP DIV.OUT Giải thích
    8
    10 2 6 2 5 2 1 2
    3
    Đoạn 1: 10
    Đoạn 2: 2 + 6 + 2 =10
    Đoạn 3: 5 + 2 + 1 + 2 = 10

    HTML Code:
       tfi='DIV.INP';
       tfo='DIV.OUT';
    var n: longint;
        a, s: array[0..1001] of longint;
        res: longint;
     
    function ok(t: longint): boolean;
    var i,u,tong: longint;
    begin
       tong:=0;
       for i:=1 to n do if a[i]<>0 then
          begin
             tong:=tong+a[i];
             if tong=t then tong:=0;
          end;
       exit(tong=0);
    end;
    procedure main;
    var j,u,i,k,t: longint;
    begin
       assign(input,tfi); reset(input);
       assign(output,tfo); rewrite(output);
       read(n);
       for i:=1 to n do read(a[i]);
       s[0]:=0;
       for i:=1 to n do s[i]:=s[i-1]+a[i];
       for k:=n downto 1 do if s[n] mod k=0 then
          begin
             t:=s[n] div k;
             if ok(t) then
                begin
                   res:=k;
                   break;
                end;
          end;
       writeln(res);
       close(input); close(output);
    end;
     
    BEGIN
       main;
    END.
    Quick reply to this message Trả lời       


  2. #2
    Ðến Từ
    TP. Hồ Chí Minh
    Thành Viên Thứ: 56897
    Giới tính: Nam
    Bài gửi
    881

    Reply: Y tuong bai toan nay nhu the nao? ai giup voi

    - Đầu tiên mảng 's' là integral array; s[i] là tổng các số a[1] + ... + a[i]. Có nghĩa rằng s[n] là tổng tất cả các số trong dãy. Nhiệm vụ của mảng này để tránh tính tổng lại nhiều lần. Tuy nhiên, mảng s trong đoạn code trên là vô dụng, bạn thấy chỉ dùng đc mỗi s[n].
    - k là số đoạn chia đc. Với k = n tức là chia nguyên mảng ra thành n đoạn. Như vậy để đảm bảo chia đc thì s[n] chia hết cho k.
    - Giả sử s[n] chia hết cho k, thì mỗi đoạn phải có tổng là t := s[n] div k. Tiếp theo là kiểm tra xem nguyên mảng a có thể chia thành từng đoạn con với mỗi đoạn con có tổng là t hay không.
    - Function ok sẽ kiểm tra mảng 'a' đc chia thành nhiều đoạn con có tổng t. Cách làm là cộng lần lượt các phần tử cho tới khi 'tong = t', khi đó reset biến 'tong' lại về 0. Nếu như ko chia đc thì sẽ còn dư lại phần cuối và biến 'tong' sẽ khác 0.
    Độ phức tạp của thuật toán O(n^2), vừa đúng với giới hạn của dữ liệu.
    LCD: 13.3" 1920x1080 IPS
    CPU: Intel i7 - 4700MQ (2.4 GHz - 3.4 GHz)
    GPU: Nvidia GTX 765m with GDDR5 2GB
    RAM: 2x8GB G.Skill 2133
    HDD: Samsung SSD 850 Pro 512 GB
    2 kg.

  3. #3
    Ðến Từ
    Quảng Bình
    Thành Viên Thứ: 377431
    Giới tính: Nam
    Bài gửi
    16

    Reply: Y tuong bai toan nay nhu the nao? ai giup voi

    vậy bài này có cách nào khác để độ phức tạp nhỏ hơn ko ban

  4. #4
    Ðến Từ
    TP. Hồ Chí Minh
    Thành Viên Thứ: 56897
    Giới tính: Nam
    Bài gửi
    881

    Reply: Y tuong bai toan nay nhu the nao? ai giup voi

    Nếu số đoạn fixed thì có thể làm còn O(n log n) được. Nhưng bài này số đoạn cũng là một biến nên mình không nghĩ là có thể làm nhanh hơn được.

  5. #5
    Ðến Từ
    Quảng Bình
    Thành Viên Thứ: 377431
    Giới tính: Nam
    Bài gửi
    16

    Reply: Y tuong bai toan nay nhu the nao? ai giup voi

    vậy bạn ơi. có cách làm nào khác dễ hiểu hơn không chứ đọc code đó lên minh không hiểu giải thuật như thế nào cả

  6. #6
    Ðến Từ
    TP. Hồ Chí Minh
    Thành Viên Thứ: 56897
    Giới tính: Nam
    Bài gửi
    881

    Reply: Y tuong bai toan nay nhu the nao? ai giup voi

    Mình thấy viết như thế cũng được lắm rồi. Bạn có thể xem như: giả sử ta chia thành k đoạn (mỗi đoạn cần có tổng là t), sau đó kiểm tra xem có chia mảng a thành từng đoạn có tổng t đc hay không.

  7. #7
    Ðến Từ
    Hà Nội
    Thành Viên Thứ: 358027
    Bài gửi
    1.720

    Reply: Y tuong bai toan nay nhu the nao? ai giup voi

    ý tưởng như sau:

    vòng lặp tính tổng k phần tử đầu tiên và thực hiện công việc sau

    vòng lặp đầu tiên index = 0, doan = 1, tong_xet = 10 (index nhớ ví trí phần tử đang xét, tong_xet la tổng n phần tử đầu tiên)

    xét từ index + 1, tính tong_doan (tong_doan là tổng n phần tử tiếp theo)

    nếu tong_doan > tong_xet bỏ qua vòng lặp tính tổng k phần tử đầu tiên này, xét tổng k phần tử đầu tiên tiếp theo

    nếu tong_doan < tong_xet mà index < n - 1, thì cộng tiếp phần tử tiếp theo và xét tiếp tong_doan

    nếu tong_doan = tong_xet mà index < n - 1, thì doan tăng 1, tong_doan = 0, index tang 1 và xét tiếp tong_doan

    nếu tong_doan = tong_xet mà index = n - 1, thì doan tăng 1, đưa ra kết quả

    VD cho dễ hiểu

    a[0] = 10
    a[1] = 2
    a[2] = 6
    a[3] = 2
    a[4] = 5
    a[5] = 2
    a[6] = 1
    a[7] = 2

    lặp 1: index = 0, tong_xet = 10, doan = 1

    tong_doan = 2 < 10 (index = 1)
    tong_doan = 2 + 6 < 10 (index = 2)
    tong_doan = 2 + 6 + 2 = 10, doan = 2 (index = 3 < 7 => tong_doan = 0)

    tong_doan = 5 < 10 (index = 4)
    tong_doan = 5 + 2 < 10 (index = 5)
    tong_doan = 5 + 2 + 1 < 10 (index = 6)
    tong_doan = 5 + 2 + 1 + 2 = 10, doan = 3 (index = 7 = 7 => nhớ doan)

    10 | 2 6 2 | 5 2 1 2

    lặp 2: index = 1, tong_xet = 10 + 2 = 12, doan = 1

    tong_doan = 6 < 12 (index = 2)
    tong_doan = 6 + 2 < 12 (index = 3)
    tong_doan = 6 + 2 + 5 > 12 (index = 4 < 7 => bỏ qua vòng lặp này, xét tổng k phần tử đầu tiên tiếp theo)

    lặp 3: index = 2, tong_xet = 10 + 2 + 6 = 18, doan = 1

    tong_doan = 2 < 18 (index = 3)
    tong_doan = 2 + 5 < 18 (index = 4)
    tong_doan = 2 + 5 + 2 < 18 (index = 5)
    tong_doan = 2 + 5 + 2 + 1 < 18 (index = 6)
    tong_doan = 2 + 5 + 2 + 1 + 2 < 18, (index = 7 = 7 => bỏ qua)

    lặp 4: index = 3, tong_xet = 10 + 2 + 6 + 2 = 20, doan = 1

    tong_doan = 5 < 20 (index = 4)
    tong_doan = 5 + 2 < 20 (index = 5)
    tong_doan = 5 + 2 + 1 < 12 (index = 6)
    tong_doan = 5 + 2 + 1 + 2 < 20, (index = 7 = 7 => bỏ qua)

    cứ như vậy đến hết, xét các doan nhớ, lấy max ta được 3 đoạn ứng với vòng lặp đầu tiên

    Để giảm bớt số vòng lặp tổng k phần tử đầu tiên giúp giảm bớt trường hợp phải xét thì chỉ cần xét đến vị trí k sao cho S(n) - S(k) > S(k)