mà em thấy như vậy là sai đề á a, vì mỗi vòng thì mỗi phần tử chỉ được trừ cho 1 trong 3 số 9 3 1 thôi…chứ ko thể trừ 1 số cho nhiều số như thế được
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
Thế mảng chỉ có 1 phần tử thì sao? O_O
Đề bắt vậy hóa ra đề sai à?
Với mình ko thấy chỗ nào đề bắt vậy cả 
Còn nếu bắt vậy thật thì mình cũng chịu lun. Hết cách tối ưu 
4 Likes
mảng chỉ có 1 phần tử thì cứ mỗi lần trừ đi 9 thôi :3
ý là mỗi lần chọn ra 3 phần tử để mang trừ cho 3 số 9 3 1 thì trừ tương ứng
vd : a b c
a mà - 9 rồi thì b c phải trừ cho 3 hoặc 1 chứ ko thể lấy a - 9 - 3 - 1 luôn được
1 Like
thế thì mình thấy không có cách nào phải search rồi
Vì việc ko cho gom như vậy thì cách đầu của mình cũng ko khả dụng khi khi còn 2 phần tử sẽ trừ liên tiếp -> sai đề.
* lót dép chờ cao thủ chung với tnt *
4 Likes
Tham lam thì sai, hay là phải tham lam có chọn lọc 
Test 12 10 4:
(12 10 4) -> (3 7 3) = (7 3 3) -> (-2 0 2) (L)
(12 10 4) -> (3 9 1) = (9 3 1) -> (0 0 0) (2 lần)
12 10 4 chính là trường hợp đặc biệt, 12 = 9 + 3, 10 = 9 + 1, 4 = 3 + 1.
3 Likes
ban đầu em tiếp cận tham lam thì ăn đc 6 test nhưng mà submit thì bị cái test này :3
nên chắc tham lam ko đúng
1 Like
n = 1 -> ans = ceil(a[0] / 9)
n = 2 -> ans = ceil((a[0] + a[1]) / 12)
n >= 3:
Thử ceil((a + b + c) / 13) xem sao.
3 Likes
:v TNT thử ở trên và tạch rồi
5 Likes
Mình đang nghĩ đến mô hình 12 - 10 - 4. Tức là thay vì trừ 9 - 3 - 1 thông thường thì mình làm trừ 12 - 10 - 4 trước.
Ví dụ:
10 32 23 => (2+4+4) (8+12+12) (3+10+10) => 2 8 3 (+4 lần) => 1 -1 0 => -8 -2 -3 (6 lần)
19 4 3 => (5+12) (-6+10) (-1+4) => 5 -6 -1 (+2 lần) => -4 -7 -4 (3 lần)
Sắp xếp giảm dãy rồi chia dãy thành 1 số nhóm rồi trừ đi, còn lại mình đang suy nghĩ tiếp :v
5 Likes
if(a.size() % 3 == 1){
a.push_back(0);
a.push_back(0);
}
else if(a.size() % 3 == 2){
a.push_back(0);
}
sort(a.begin(), a.end());
int j = 0, cnt = 0;
while(j < a.size()){
priority_queue<int> q;
for(int i = j; i < j + 3; i++){
q.push(a[i]);
}
while(q.top() > 0){
int x = q.top(); q.pop();
int y = q.top(); q.pop();
int z = q.top(); q.pop();
x -= 9;
if(y % 3 == 0 || (z-1)%3 ==0){
y -= 3;
z -= 1;
}else if((y-1)%3==0 || z % 3 == 0){
y -= 1;
z -= 3;
}
else{
y -= 3;
z -= 1;
}
q.push(x);
q.push(y);
q.push(z);
cnt++;
}
j += 3;
}
em code như thế này thì ăn được 6 test
ko biết có ai chỉ ra lỗi sai ở đâu để fix ko ta…e thấy cách này khá đúng
số lớn nhất e luôn trừ đi 9
2 số kia làm như sau: nếu có số nào là ước của 3 thì trừ đi số đó cho 3, số còn lại trừ 1
nếu ko thì trừ thử 1 xem có là ước của 3 ko
nếu cả 2 đều ko được thì trừ số lớn cho 3 số nhỏ cho 1
ko biết có cần thêm điều kiện nào nữa ko…chứ có test này bị sai
55, 60, 53 (đáp án 14, theo code ra 13)
3 Likes
Test nhỏ cho dễ thấy: 12 9 4
Theo code của bạn x sẽ luôn trừ 9 dù khi đã được trừ
Lần 1; 3 6 3
Lần 2: -6 3 2
Lần 3: …
Trong khi nếu trừ -3, -9 -1 thì chỉ cần 2 lần
12 9 4 -> 3 0 3 -> -6 0 0
Mấu chốt ở chỗ, bạn ko tái sử dụng lại con số 9 được nên bị sai. Với việc cứ trừ 9 như vậy cũng không đúng được. Mục tiêu của đề bài là trừ sao cho dãy số cuối gần 9 3 1 nhất. vì khi đó sẽ chỉ tốn 1 bước để dọn.
Để ý cũng thấy 2 ví dụ đều ráng gom về 9 3 1. Ở vd 1 thì là 10 2 1, Ở ví dụ 2 đúng là 9 3 1
5 Likes
60 55 53 -> 48 45 49 -> 38 41 37 -> 28 29 33 -> 24 19 21 -> 12 15 11 -> 2 3 7 -> 1 0 -2 -> -8 -3 -3
Như mình làm là 14. Nếu bạn ra 13 thì thử trace output xem có đúng không.
2 Likes
mình nghĩ bài này chỉ có if else thôi :3 ko biết có thêm điều kiện gì ko
vì làm if else mình qua đc tận 7 test
1 Like
ừm mình cũng muốn gom về 9 3 1 đấy nên mới đặt if else kiểu (x - 1) % 9 == 0 … mà vẫn sai :3
2 Likes
:v Thế mới đau đầu đó, biết mục tiêu nhưng làm sao tối ưu thì chịu. Vì gặp những case như 60 59 58 không biết trừ ai trước ai sau luôn
4 Likes
đáp án là 14 thì đề sai rồi @_@ 13 mới đúng chứ :V
trừ 52 52 52 còn 3 8 1 trừ thêm 1 lần nữa là còn 0, trừ 52 52 52 tốn 12 lần tổng cộng: 9 3 1 + 3 1 9 + 1 9 3 = 13 13 13, tốn 3 lần trừ, trừ 4 lần như vậy là 3x4 = 12 lần. Tổng cộng là 13 lần :V
tử hình thầy nào ra đề 
vọc mãi thì thấy đáp án luôn là ceil(sum(a) / 13) hoặc ceil(sum(a) / 13) + 1 :V Tuy nhiên ko biết lúc nào mới +1 vào :V
3 Likes
á hic lỗi em anh ơi :3 đáp án 13 theo code 14
em bấm nhầm…laggggggg
công thức đó ko đúng đâu a ơi … ví dụ mảng a chỉ có 1 phần tử 60 thì cần 7 lần lận :v
ờm, vậy chắc thêm +2 nữa :V :V chắc ko thể có +3 được :V
1 Like
bài này giới hạn cỡ này backtrack được ko a
e backtrack mà ko biết sai ở đâu :3
e if else 6 trường hợp luôn…số nhỏ này chắc chạy nổi
int cnt = 0, MIN = INT_MAX;
bool check(int a, int b, int c){
return a <= 0 && b <= 0 && c <= 0;
}
void Try(int i, vector<int> a){
for(int j = 0; j < 6; j++){
if(j == 0){
a[i] -= 9;
a[i+1] -= 3;
a[i+2] -= 1;
}
else if(j == 1){
a[i] -= 9;
a[i+1] -= 1;
a[i+2] -= 3;
}
else if(j == 2){
a[i] -= 3;
a[i+1] -= 9;
a[i+2] -= 1;
}
else if(j == 3){
a[i] -= 3;
a[i+1] -= 1;
a[i+2] -= 9;
}
else if(j == 4){
a[i] -= 1;
a[i+1] -= 9;
a[i+2] -= 3;
}
else if(j == 5){
a[i] -= 1;
a[i+1] -= 3;
a[i+2] -= 9;
}
cnt++;
if(i == a.size() - 1 && cnt < MIN && check(a[i], a[i+1], a[i+2])) MIN = cnt;
if(i < a.size() - 1 && !check(a[i], a[i+1], a[i+2])) Try(i+1, a);
if(j == 0){
a[i] += 9;
a[i+1] += 3;
a[i+2] += 1;
}
else if(j == 1){
a[i] += 9;
a[i+1] += 1;
a[i+2] += 3;
}
else if(j == 2){
a[i] += 3;
a[i+1] += 9;
a[i+2] += 1;
}
else if(j == 3){
a[i] += 3;
a[i+1] += 1;
a[i+2] += 9;
}
else if(j == 4){
a[i] += 1;
a[i+1] += 9;
a[i+2] += 3;
}
else if(j == 5){
a[i] += 1;
a[i+1] += 3;
a[i+2] += 9;
}
cnt--;
}
}
int mutaliskAttack(vector<int> a)
{
if(a.size() % 3 == 1){
a.push_back(0);
a.push_back(0);
}
else if(a.size() % 3 == 2){
a.push_back(0);
}
int res = 0;
for(int i = 0; i < a.size(); i+=3){
vector<int> tmp(a.begin() + i, a.begin() + i + 3);
Try(0, tmp);
res += cnt;
cnt = 0;
MIN = INT_MAX;
}
return res;
}
khó là cái đề cho mảng A có thể có tới 9 phần tử, backtrack chạy gì nổi :V
số nhỏ vậy chắc ko có công thức :V mà ko biết quy hoạch động kiểu gì :V thôi em hỏi thầy rồi post đáp án lên đi =]]]]]]]
5 Likes
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?