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 a[SUB]1[/SUB], a[SUB]2[/SUB], ..., a[SUB]n[/SUB]
(các số nằm trên một dòng cách nhau bởi một dấu cách a[SUB]i[/SUB] ≤ 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: 
   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.
 
T

tengiday

Happy life
- Đầu tiên mảng 's' là integral array; s là tổng các số a[1] + ... + a. 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.
 
Sửa lần cuối:
T

tengiday

Happy life
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.
 
N

ngoclinhqbinh

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ả
 
T

tengiday

Happy life
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.
 
G

gunshot9x

ý 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)
 
Đăng nhập bằng tài khoản VFO hoặc Google

Bài viết mới nhất

Thống kê

Chủ đề
100,682
Bài viết
467,464
Thành viên
339,836
Thành viên mới nhất
fgbfsggoo88

Bài viết được quan tâm nhiều

Top