Đề bài hơi dài nên em tóm tắt như sau:
Xin ý tưởng về giải thuật cho bài toán trừ các số trong mảng cho đến khi chỉ còn lại các số không dương
xài A* thôi em :V Đầu tiên viết BFS trước xem nó chạy chậm quá thì chuyển sang A* :V
9 phần tử x 60 mỗi phần tử là 540, mỗi lần chỉ trừ 9+3+1=13, vậy trừ cỡ 42 lần cũng ko nhiều lắm :V Chỉ có điều từ mỗi mảng số bước tiếp theo có thể là 9P3 = 504 bước :V 504^42 chắc chết :V
3 Likes
ok anh để em tìm hiểu về A*…e mới nghe lần đầu
Bài này là toán mà nhỉ.
Nhận xét thấy B là {3^2, 3^1, 3^0} vậy phân tích toàn bộ các số thành dạng tổng và tích của 3^2, 3^1, 3^0. Ví dụ 19 thành 2 * 3^2 + 1 * 3^0, lưu thành (2, 0, 1), rồi cộng tổng toàn bộ bộ 3 số của các số.
Ví dụ:
19 = (2, 0, 1)
4 = (0, 1, 1)
3 = (0, 1, 0)
Cộng tổng lại (2, 2, 2)
Gọi bộ ba số này là (a, b, c).
Rồi chuyển a thành b, b thành c, có là 1a = 3b, 1b = 3c.
Chuyển sao cho (a, b, c) cân bằng nhất max(a-b, b-c) là min.
Rồi kết quả là max(a, b, c).
4 Likes
a ơi cho em hỏi vì sao 1a = 3b, 1b = 3c thế a
Ví dụ như này:
Ví dụ (a, b, c) là (4, 1, 0), thì sẽ chuyển (4, 1, 0) thành (3, 3, 3) (đã chuyển 1b thành 3c, và 1a = 3b) và (3, 3, 3) là cân bằng nhất.
Vì tổng = a * 3^2 + b * 3^1 + c * 3^0= (a - 1) * 3^2 + (b + 3) * 3^1 + c * 3 ^ 0.
Nên chuyển (a, b, c) thành (a - 1, b + 3, c) được
Tương tự với b và c.
1 Like
em hiểu rồi, nhưng mà như vậy thì em có thể chuyển (a-2, b+6, c) , (a-3, b+9, c) … thì khi nào mới dừng được đây ạ
có thể chuyển (a, b - 1, c + 3),… nữa.
Dừng khi nó cân bằng nhất max(a, b, c) nhỏ nhất tương đương với max(a, b, c) - min(a, b, c) nhỏ nhất.
2 Likes
à ok a…em hiểu rồi, cám ơn a
a ơi em có 1 test case như thế này
6 12 14
e phân tích: 6 = 2 * 3^1
12=1 * 3^2 + 1 * 3^1
14=1 * 3^2 + 1 * 3^1 + 2 * 3^0
tổng lai là 2 4 2
thì 2 4 2 là cân bằng nhất luôn… nên cần 4 bước
nhưng e giải tay theo đề bài thì chỉ cần 3 bước là được rồi ạ -.-
2 4 2 chuyển thành 3 1 2 được nè :V
3 Likes
như vậy có khác lấy tổng các số rồi chia 13 rồi lấy ceil ko nhỉ? :V Thấy có gì đó kì kì :V
ví dụ 3 7 3 chuyển thành 0 4 1, rồi chuyển thành 1 1 1 là chỉ cần 1 lần trừ, nhưng thực tế cần 2 lần :V Cộng lại rồi cân bằng a b c giống như cộng 3 số rồi chia 13 lấy ceil thôi :V
tổng = 13 nhưng cần 2 lần trừ: tất cả bộ ba khác permutation của 9 3 1 :V
3 Likes
thế thì (19,4,3) tổng là 26 / 13 = 2 thì ceil cũng là 2 mà a :v
1 Like
thì vậy cách này chắc ko ổn, duyệt trâu A* thì chắc ko nổi :V
tách thành tổng có lẽ là bước đi đúng rồi, nhưng đừng cộng lại @_@
4 Likes
vâng a…giờ em đọc lại cái 19 4 3 kia nếu tách ra rồi + lại thì được 2 2 2 là cân bằng nhất rồi
nên đáp án là 2 nhưng thực tế phải là 3
chắc là em phải chuyển làm sao cho tổng cột và tổng hàng bé nhất nữa :V
ví dụ 6 12 14
6 = 0 2 0 1 0 0 1 0 0
12 = 1 1 0 --> 1 1 0 --> 1 1 0
14 = 1 1 2 1 1 2 1 2 0
6 có thể trừ cho 9 cũng ko sao (thay vì trừ 2 lần số 3), bước chuyển này giúp cột thứ 2 từ 4 còn 2, tuy cột 1 tăng từ 2 lên 3, nhưng vẫn đỡ hơn. min cột = 3
14 có thể trừ 1 lần số 9, 2 lần số 3. Chuyển 14 thành 1 2 0 thì cột thứ 3 từ 4 còn 3, min hàng là 3. Bước chuyển này min cột vẫn là 3 :V
vậy min cả ma trận là 3, cần 3 bước :V
3 = 0 1 0 0 1 0
7 = 0 2 1 --> 1 0 1 --> min cột = 2, min hàng = 2, min ma trận = 2
3 = 0 1 0 0 1 0
19 = 2 0 1
4 = 0 1 1 --> ko chuyển được nữa :V min cột = 2, min hàng = 3, min ma trận = 3
3 = 0 1 0
xem ra chuyển ma trận cũng khó nhằn :V :V n lên 9 thì ma trận 9x3 (ko phải 9x9 :V) mò làm sao :V
à em có thể xài BFS/DFS?? cho ma trận này, mỗi ma trận chỉ có thể chuyển sang 2n ma trận khác, chắc dễ thở hơn =]]
3 Likes
giải tay còn rối thế này giờ em mang vào code chắc e bí luôn quá a ơi :3
anh cũng bó tay, chờ cao nhân khác vào chém =]]
4 Likes
Mình nhẩm thì thấy thế này, mọi số a, b, c luôn có cách trừ tối ưu dù bắt đầu như thế nào (cần chứng minh :3)
như
- (32 10 23) -> (31 1 20) -> (30 -8 17) -> (29 -8 5) -> (25 -8 -4) -> (12 -8 -4) -> (-1 -8 -4) = 6 lần
- (32 10 23) -> (23 9 20) -> (14 8 17) -> (5 7 14) -> (-4 6 11) -> (-4 -5 7) -> (-4 -5 -2) = 6 lần
- (32 10 23) -> (19 10 23) -> (6 10 23) -> (-3 6 23) -> (-3 -3 19) -> (-3 -3 6) -> (-3 -3 -3) = 6 lần
Nếu chứng minh được điều trên là đúng. Thì ta sẽ không quan tâm thứ tự trừ ở đây nữa.
Khi đó, bài toán sẽ là, gom các cặp 3 số lại với nhau (a, b, c), tính min từng cặp rồi tổng lại.
Cách tính min do ko quan trọng thứ tự trừ cũng đơn giản hơn. Lấy số thứ a - 9, b - 3, c - 1 khi nào tới âm thì dừng. Khi đó, lấy số kế tiếp > 0 cộng số trừ đằng trước.
Như nếu a <= 0, thì lấy b - (3 + 9). Nếu c = 0 thì a sẽ thành a - (9 + 1)
Hoặc, lấy số a trừ lần lượt 9, 3, 1 ở mỗi vòng. (Tất nhiên ráng chọn số trừ cho khéo, như a = 4 thì chọn 3, 1 chẳng hạn hay vì 9) Trừ khi nào âm thì dừng chuyển sang số b. (Như ví dụ 3)
Khi đó phức tạp cỡ O((n/3)*[floor((a + b + c) / 13) + 1])
Lấy 60 60 60 thì mất cỡ (60 * 3) / 13 + 1 = 14 bước
Cũng ko quá tệ
~~ Ô :)) Lúc nghĩ ra công thức complexity tính ra cũng đúng phết
floor((a + b + c) / 13) + 1
Bạn thử làm theo công thức này <(") Biết đâu ăn được test -> O(n/3)
5 Likes
Em có test 12 10 4
Theo công thức sẽ là 3 nhưng thật ra chỉ có 2 thôi a :3
2 Likes
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?