Bài toán chia bánh

Whis1 · February 3, 2020, 6:39am

Dạ e chào cả nhà ạ.
E vào vấn đề chính luôn là e có 1 bài toán là làm thế nào để chia bánh cho mọi người ai cũng có phần, mỗi miếng bánh được cắt ra sao cho miếng bánh đó có thể tích miếng bánh đó có thể tích là lớn nhất, mỗi miếng bánh mọi người nhận được có thể tích như nhau không quan trọng hình dáng cắt ra như nào. Sao cho phần dư còn lại của mỗi chiếc bánh là nhỏ nhất!
dưới đây là ví dụ minh hoạ:
ví dụ, có 4 cái bánh chia cho 8 người, kích cỡ miếng bánh khác nhau( ý e là có bánh to và có cái bánh nhỏ) làm sao chia số bánh đó cho mọi người mỗi người 1 miếng và khối lượng mà mỗi người nhận dc như nhau
banh

noname00 · February 2, 2020, 9:44am

Đáp số = tổng thể tích bánh / số người, dư = 0

Có lẽ chỉ cần đơn giản vậy thôi

anon12276517 · February 2, 2020, 9:54am

Có yêu cầu thể tích phải là số nguyên không bạn ??
Nếu không thì đáp số là

x = tổng thể tích.
y = số người
n = thể tích mỗi bánh

n = (float) x/y;

Nếu như yêu cầu thể tích phải là số nguyên thì sẽ là

n = Math.floor(x/y);
==> Mod = x - n*y;

Whis1 · February 2, 2020, 10:49am

ý e là lấy tổng số bánh đó chia cho 8 người, mỗi người dc 1 phần bánh như nhau sao cho chỗ dư bánh là nhỏ nhất, mỗi người chỉ dc 1 miếng bánh, ví dụ như lấy miếng bánh to nhất chia hết miếng bánh đó, rồi lấy cái bánh tiếp theo…
sao cho đủ 8 người là dc, và làm thế nào để mỗi người 1 miếng không ai tị ai

anon12276517 · February 2, 2020, 10:52am

Cho 1 case với số liệu cụ thể đi bạn @@

SITUVN.gcd · February 2, 2020, 11:38am

Là có nhiều cái bánh? Hay chỉ có 1 miếng bánh to? Miếng bánh không cân đối?
Đề rối quá vậy!

qloved · February 3, 2020, 1:05am

Keyword quan trọng trong đề: không quan trọng hình dạng => có thể cắt thành mọi hình dạng => phần dư luôn là 0. Chia đều bánh cho mỗi người thôi cần gì chia nữa.
Nếu giới hạn hình dạng thì mới có việc mà tính chứ

Whis1 · February 3, 2020, 6:35am

có nhiều cái bánh chia cho nhiều người, làm sao để mọi người có dc miếng bánh to nhất có thể, nhưng chỉ dc phép mỗi người 1 miếng

Whis1 · February 3, 2020, 6:37am

ví dụ của e là 4 cái bánh hình tròn, vì sợ mọi người tị nhau bánh to và bánh nhỏ nên chia sao cho mỗi người dc miếng bánh như nhau ( thể tích như nhau còn hình dạng khi cắt thì như nào cũng dc) sao cho phần dư còn lại là nhỏ nhất

anon12276517 · February 3, 2020, 7:04am

Thì lấy số bánh chia số người là được mà nhỉ ??
Vd: 4 cái bánh, 8 người
==> mỗi người được 4/8 = 1/2 cái bánh, dư 0

noname00 · February 3, 2020, 8:53am

Theo như bạn nói thì ví dụ trên có đáp số là

người 1 có cả cái bánh V = 1
người 2 và 3 chia đôi cái bánh V = 2
người 4, 5, 6 chia 3 cái bánh V = 3
người 7, 8 mỗi người lấy 1/4 cái bánh V = 4

Tổng quát: có n miếng a[1], a[2],…, a[n] và m người.

Đặt s = a[1] + a[2] + … + a[n].

Giả sử mỗi người nhận lượng bánh có thể tích là v.

Số miếng cắt ra phải đủ cho m người, tức là $P(v) = \sum{\left \lfloor \frac{a[i]}{v} \right \rfloor}\geq m$
Tổng phần dư sau khi chia là $R(v)=\left(\sum{a[i]}\right) - mv$ , R(v) phải không âm.

Nhận xét:

$v=\frac{\sum{a[i]}}{m}=\frac{s}{m} \rightarrow R(v)=0 \rightarrow v_{max}=\frac{s}{m}$
P(v), R(v) là hàm giảm.

-> Dùng binary search chọn v trong khoảng $\left[0, \frac{s}{m}\right]$ thoả mãn P(v) >= m. Nếu đề cần v nguyên thì ta lấy floor(v) để ra đáp số cuối cùng.