Cần giúp đỡ giải bài toán chia kẹo

#1

Anh Danh có rất nhiều em gái nuôi. Các em gái nuôi của anh Danh rất thích ăn kẹo. Anh Danh có 3 loại kẹo với 3 màu lần lượt là đỏ, vàng, xanh. Anh Danh phải chia kẹo cho các em gái dễ thương của mình. Tuy nhiên các em gái rất kiêu kì và hay làm nũng. Vì vậy anh Danh phải chia kẹo cho các em theo quy tắc sau. Mỗi em gái nuôi chỉ nhận 3 viên kẹo cùng màu hoặc 3 viên kẹo khác màu nhau. Nói cách khác, anh Danh phải chia hoặc là 3 viên đỏ, hoặc 3 viên vàng, hoặc 3 viên xanh, hoặc 1 đỏ 1 vàng 1 xanh cho một em gái của mình. Biết rằng anh Danh có d viên kẹo đỏ, v viên kẹo vàng và x viên kẹo xanh. Hãy tính xem anh Danh có thể chia kẹo cho tối đa bao nhiêu em gái nuôi với chừng đó viên kẹo…

Dữ liệu vào: Ba số d, v, x tương tứng số kẹo đỏ vàng xanh (0 < d, v, x <= 1000000000)

Dữ liệu ra: Số lượng tối đa các em gái nuôi được anh Danh chia kẹo.

#2

mình nghĩ kết qủa sẽ là thế này
t = min(d,v,x);
n = t + (d - t)/3 + (v - t)/3 + (x - t)/3

1 Like
#3

hinh nhu sai roi, neu 3, 5, 5 sẽ là 4, còn cái cua bạn là 3 :slight_smile::slight_smile:

#4

thử

s = d/3 + v/3 + x/3;
d %= 3;
v %= 3;
x %= 3;

còn lại biện luận cho 27 trường hợp cho d,v,x:
if trong 3 số (d,v,x) có 2 số là (0,0) hay (0,1) thì ko làm gì cả (16 trường hợp)
else if trong 3 số (d,v,x) có 1 số là 1 thì s += 1 (7 trường hợp)
else if trong 3 số (d,v,x) có số 1 số 0 thì s += 1 (3 trường hợp)
else if (d,v,x) == (2,2,2) thì s += 2 (1 trường hợp)

cách này là đầu tiên chia 3 viên kẹo cùng màu cho tới khi ko còn chia được nữa, thì d,v,x còn lại từ 0-2 viên mỗi loại màu. Nếu còn 0,2,2 thì ta có thể lấy lại 3 viên kẹo cùng màu để thành 3,2,2, chia được cho 2 người, bỏ 1 người => s += 1. Nếu còn 0,0,2 chẳng hạn thì dù có lấy lại thành 3,3,2 thì thêm 2 nhưng mất 2 nên khỏi làm. Cứ thế lý luận cho các trường hợp còn lại.

ko biết chứng minh nó đúng hay sai, chạy thử đúng thì xong, còn sai tính tiếp :stuck_out_tongue:

2 Likes
#5

cam on bạn nha, để mình test thử :grinning:

#6

Đang ngủ thì nghĩ ra cách làm này không biết đúng không :yum:

long ChiaKeo(long d, long v,long x){
	long max_chia=(d+v+x)/3;
	d-=max_chia;
	v-=max_chia;
	x-=max_chia;
	long a[]={d,v,x};//Lưu vào mảng cho dễ xử lý
	while(max_chia>0&&!(a[0]>=0&&a[1]>=0&&a[2]>=0)){
		SortArr(a);//Sap xep giam dan
		while(max_chia>0&&a[0]<2&&a[1]<1&&a[2]<0){
			max_chia--;
			a[0]++;
			a[1]++;
			a[2]++;
		}
		a[0]-=2;
		a[1]++;
		a[2]++;
	}
	return max_chia;
}

Ý tưởng:
+Tìm số lượng chia tối đa không quan tâm tới điều kiện. Coi như số lượng đó là số kẹo từng màu trung bình phải mất. => Cách chia mỗi loại 1 viên
+Trừ số kẹo từng loại cho số trên.
+Giờ tiến hành chia kẹo lại (lấy thằng dư bù cho thằng thiếu) điều kiện dừng: đến khi nào không còn loại kẹo nào âm.

  • Chuyển cách chia mỗi loại 1 viên thành 1 loại 3 viên => số lần chia vẫn không thay đổi
  • Mỗi loại kẹo + 1
  • Xét loại kẹo còn nhiều nhất.=> tiến hành lấy 3 viên kẹo của thằng này .
  • Xét trường hợp nếu chia hoài vẫn còn thằng âm thì giảm max_chia xuống đồng thời tăng số kẹo mỗi loại lên 1.
1 Like
#7

3, 5, 5 làm sao ra được 4 -_-

#8 
1 1 1
1 1 1
0 0 3
0 3 0
-----
2 5 5

4 đó

1 Like
#10

3,5,5 chứ có phải 2,5,5 đâu :grin:

#11

của a là 2, 5, 5… trường hợp 3, 5, 5 cơ mà a @@

#12

Cơ mà nếu 3,5,5 thì đáp án vẫn là 4

1 1 1
1 1 1
0 0 3
0 3 0
1 0 0
--------
3 5 5

Mình làm xong bài này, tưởng hoàn hảo cho đến khi nhìn lại comment của bạn @tntxtnt, vấn đề trở nên phức tạp rồi

#13

Dư cũng được thì phải mà. Chứ đâu nhất thiết d + v + x phải chia hết cho 3

2 Likes
#14

B1: Tìm số lần chia 3 viên kẹo cùng màu
-Chia lấy phần dư số kẹo từng màu cho 3 sao cho 0<số dư<=3 rồi cộng lại là ra số lần chia 3 viên cùng màu.
B2: Tìm số lần chia 3 viên kẹo khác màu == số dư nhỏ nhất…

#15

Đúng rồi vì số phần kẹo tối đa là tổng số chia 3 :smiley: (2+2) / 3 = 1 (dư) thì thêm 1 người là tối ưu. Trừ {0, 1, 2} là trường hợp đặc biệt.

Bài này ko phức tạp chỗ chia vì 3 người x (1 + 1 + 1) thì cũng như 3 người x 3 mà thôi. Để ý các hoán vị của {0, 1, 2} chỉ cách nhau đúng một phép trừ :smiley: nên rất là chặt chẽ.

null, s1 và s2 tạo thành nhóm hoán vị S3 với s1 x s2 = null.

3 Likes
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?