Bài toán C++: Đổi màu bi sao cho số lượng bi 3 màu bằng nhau

#1

Em cần giúp đỡ bài toán này ạ
Cho 1 vector A gồm số lượng của 3 màu bi ( xanh, đỏ, vàng). Tìm số lần tối thiểu để đổi màu bi sao cho 3 màu có số lượng bằng nhau, biết rằng :

  • Mỗi lần đổi chỉ đổi 2 bi màu bất kì ( 2 bi cùng màu hoặc 2 bi khác màu) thành 2 bi có màu muốn đổi.
  • Nếu không đổi được return -1.
    Ví dụ : A = {1,4,4} kq là 1 ( Đổi 1 vàng, 1 đỏ thành 2 xanh).
    A={1,1,4} kq =2 ( Đổi 1 vàng 1 xanh thành 2 đỏ ( 3,0,3). Sau đỏ đổi 1 đỏ, 1 vàng lấy 2 xanh).
    A={1,0,4} kq=-1 vì không tìm ra được cách đổi.
    Với A[i] <= 10^9
#2

Bạn có thể tham khảo và sử dụng giải thuật tìm kiếm A* cho bài toán này.
Đầu tiên xây dựng tập không gian mẫu bao gồm tất cả các phép toán có thể xảy ra.
Áp dụng các phép toán vào trạng thái hiện tại.
Kiểm tra và đánh giá trạng thái so với Goal.
Ví dụ:
A = {1, 4, 4}
Các phép toán mình có thể có:

  • Đổi sang 2 bi xanh
  • Đổi sang 2 bi vàng
  • Đổi sang 2 bi đỏ
    Các tham số mình có thể có:
  • 2 bi xanh
  • 2 bi đỏ
  • 2 bi vàng
  • 1 bi xanh, 1 bi đỏ
  • 1 bi xanh, 1 bi vàng
  • 1 bi vàng, 1 bi đỏ
    Goal của mình:A = {3, 3, 3}
2 Likes
#3

N<=10^9 chạy không nổi đâu :slight_smile:

4 Likes
#4

Đây là cách làm của tôi (java):

 private static int doiMau(int mauXanh, int mauDo, int mauVang) {
    	int count = 0, a = 0, xanhThieu = 0, doThieu = 0, vangThieu = 0, tongThieu = 0;
    	if ((mauXanh + mauDo + mauVang) % 3 !=0 ) {
    		return count = -1;
    	}
    	a = (mauXanh + mauDo + mauVang) / 3;
    	if (a > mauXanh) xanhThieu = a - mauXanh;
    	if (a > mauDo) doThieu = a - mauDo;
    	if (a > mauVang) vangThieu = a - mauVang;

		tongThieu = xanhThieu + doThieu + vangThieu;
		if (tongThieu % 2 != 0) return count = -1;
		count = (xanhThieu / 2) + (doThieu / 2) + (vangThieu / 2);

		xanhThieu %= 2;
		doThieu %= 2;
		vangThieu %= 2;
    	if (xanhThieu > 0 || doThieu > 0||vangThieu > 0 ) {
    		count += 2;
    	}
    	return count;
	}
3 Likes
#6

Giả sử nếu ta có
A = {1, 6, 5}
==> a=4
xanhThieu = 3
doThieu = 0
vangThieu = 0
==> tongThieu = 3 ==> return -1

Trong khi
(0) A = {1, 6, 5} <== 1 xanh + 1 vàng => 2 đỏ
(1) A = {0, 8, 4} <== 2 đỏ => 2 xanh
(2) A = {2, 6, 4} <== 2 đỏ => 2 xanh
(3) A = {4, 4, 4} <== GOAL

2 Likes
#7

[1, 6, 5] -> [3, 5, 4] -> (vẫn OK) [4, 4, 4]

2 Likes
#8

Uh, khi làm tôi thử [3, 5, 4] tưởng k đổi được. Tôi sai rồi =)))

#9

[3, 5, 4] sao ra [4, 4, 4] được ?

#10

[3, 5, 4] :point_right: [2, 4, 6] :point_right: [4, 4, 4]. :slight_smile:

Về cơ bản thì cứ chia hết cho 3 là chuyển được. :slight_smile:

2 Likes
#11

246 sau thành 444 được :V :V

1 Like
#12

Bốc hai thằng từ 6 sang hai thằng 2. :slight_smile:

Đề nó chỉ bảo bốc 2 bi, không phân biệt màu. :slight_smile:

4 Likes
#13

hèn gì, ko đọc kĩ đề bài :V

2 Likes
#14

gọi 3 số là x y z, tổng x+y+z chia hết cho 3, đặt k=(x+y+z)/3
gọi x là màu có số lượng bi bé nhất. Nếu k và x cùng chẵn hoặc lẻ, ta đổi 2 bi từ 2 màu khác tới khi x = k. Tiếp tục đổi từ màu y thành z hoặc z thành y là cân bằng. Nesu x và k ko cùng chẵn hoặc cùng lẻ, ta đổi 1 viên x thành y hoặc z cho cùng dấu, rồi làm như khi x và k cùng chẵn/lẻ.
vậy lúc nào cũng giải được nếu x+y+z chia hết cho 3 :V

quan trọng là tìm cách ngắn nhất :V

4 Likes
#15

Nếu tổng thiếu là n thì số lần đổi tối thiểu là [n/2]+1. Kmttq xét hai trường hợp

  • (+, +, -) áp dụng AB -> CC rồi dùng AA -> CC, nếu còn dư 1 thì AC -> CC. Dễ thấy đây là tối ưu.
  • (-, -, +) CC -> AA sau đó CC -> BB rồi nếu còn dư thì CA -> BB. Như trên.

Đề bài có thể siết lại như sau:

  • A + B -> 2C
  • B + C -> 2A
  • A + C -> 2B
4 Likes
#16

Đổi đoạn này

Thành

// tongThieu = xanhThieu + doThieu + vangThieu;
// if (tongThieu % 2 != 0) return count = -1;
count = (xanhThieu / 2) + (doThieu / 2) + (vangThieu / 2);

xanhThieu %= 2;
doThieu %= 2;
vangThieu %= 2;

// if (xanhThieu > 0 || doThieu > 0||vangThieu > 0 ) {
//    	count += 2;
// }
tongThieu = xanhThieu + doThieu + vangThieu;
//tongThieu chỉ có thể = 1 hoặc bằng 2.
// TH1: tổng thiếu = 1 là trường hợp: thiếu 1 xanh, thừa 1 đỏ, vàng đủ (3 màu có vai trò như nhau) => Đổi thành thiếu 2 xanh, đỏ đủ, thừa 2 vàng => đổi 2 vàng thành 2 xanh = done => mất 2 lần đổi.
if (tongThieu == 1){
        count +=2;
}
//TH2: tổng thiếu = 2 là trường hợp: thiếu 1 xanh, thiếu 1 đỏ, dư 2 vàng =>thiếu 2 xanh, thiếu 2 đỏ, dư 4 vàng => thiếu 2 xanh, đủ đỏ, dư 2 vàng => đổi 2 vàng thành 2 xanh = done. => mất 3 lần đổi.
if (tongThieu == 2){
        count +=3;
}
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?