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

#41

bài này em làm trên web á nên ko có đáp án :3 để em nghiền ngẫm thêm, có đáp án em post lên :grin::grin:

#42

nó có chia ra bài khó hay dễ ko, đây chắc là bài hard hả? Chứ easy hay medium gì ghê vậy =]

2 Likes
#43

đây là bài khó…bài cuối cùng của sasuke 29 trên codelearn đó a ơi :V

#44

hèn gì bó tay .com =]]

cái đề đơn giản mà khó thật =]

2 Likes
#45

thế mà nhiều thánh AC lắm :3 ko biết có thuyết âm mưu gì ko

2 Likes
#46

nhiều thánh nhân kinh dị lắm, chắc họ thi lâu năm nên biết nhiều trick là 1, 2 là iq cao vút =]]

anh nghĩ là tách nó ra thành số cơ số 3 rồi chuyển đổi gì đó trong mảng 2 chiều nx3 tìm min ma trận, chuyển đổi thì xài DFS là được nhưng code khó là 1, 2 là ko biết chạy có nhanh ko =]

ví dụ :V

16 = 1 2 1     2 0 1 (đôn 2*3 lên thành 1*9)
 6 = 0 2 0 --> 0 2 0
 4 = 0 1 1     0 1 1
       4         3

36 = 4 0 0
13 = 1 1 1
 4 = 0 1 1
       5 (ko thể chuyển tốt hơn được nữa)

50 = 5 1 2     5 2 0     6 0 0  (đôn 2*1 thành 1*3, rồi đôn tiếp 2*3 thành 1*9)
 3 = 0 1 0 --> 0 1 0 --> 0 1 0
 0 = 0 0 0     0 0 0     0 0 0
       8         7         6

 9 = 1 0 0     0 3 0  (hạ 1*9 xuống 3*3)
18 = 2 0 0 --> 2 0 0
 9 = 1 0 0     1 0 0
       4         3

15 = 1 2 0     1 1 3  (hạ 1*3 xuống 3*1)
25 = 2 2 1 --> 2 2 1
25 = 2 2 1     2 2 1
       6         5

 9 = 1 0 0     0 3 0     0 2 3  (hạ 1*9 xuống 3*3 rồi hạ tiếp 1*3 xuống 3*1)
25 = 2 2 1 --> 2 2 1 --> 2 2 1
31 = 3 1 1     3 1 1     3 1 1
       6         6         5

2 = 0 0 2     0 1 0     0 1 0  (đôn 2*1 thành 1*3)
6 = 0 2 0 --> 0 2 0 --> 1 0 0  (đôn 2*3 thành 1*9)
4 = 0 1 1     0 1 1     0 1 1
      3         4         2

8 = 0 2 2     1 0 0
8 = 0 2 2     1 0 0
8 = 0 2 2     1 0 0
8 = 0 2 2     1 0 0
8 = 0 2 2 --> 1 0 0
8 = 0 2 2     1 0 0
8 = 0 2 2     0 2 2
8 = 0 2 2     0 2 2
8 = 0 2 2     0 2 2
     18         6

60 = 6 2 0     7 0 0
 0 = 0 0 0 --> 0 0 0
 0 = 0 0 0     0 0 0
       8         7
4 Likes
#47

thôi hóng cao nhân nào vào cmt trong phần trao đổi của codelearn luôn
bài này khó quá :3 thế mà cũng qua được 7 test làm e mừng hụt :grin::grin:

2 Likes
#48

nộp đại được điểm partial cũng ngon rồi =]

3 Likes
#49

e ko biết web này nó chấm điểm kiều gì :v e nộp được 12/15 mà 0 điểm
phải 13 trở lên mới có ít ít :v thốn

2 Likes
#50

Thế nên mảng có 1, 2 phần tử nên tính riêng ra mà :v

60 59 58 => 8 7 6 (-13 * 4) => -1 4 5 => -2 1 -4 => -5 -8 -5 (14 lần)

Hay là

ceil(sum(a) / 13) + (sum(a) % 13 < 12)

nhể :cold_face: cộng thêm magic number vào :cold_face:

4 Likes
#51 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;

#define EL printf("\n")
#define sz(A) (int)A.size()
#define FOR(i, l, r) for (int i = l; i <= r; i++)
#define FOD(i, r, l) for (int i = r; i >= l; i--)
#define faster ios_base::sync_with_stdio(false) && cin.tie(NULL)

// #define debug 1

int n, a[10], x[10], y[10], z[10], T;

bool dfs(int i) {
    if (x[0] < 0 || y[0] < 0 || z[0] < 0) { // invalid case
        return false;
    }
    if (i > 1) { // check if last index is valid
        if (x[i - 1] + y[i - 1] + z[i - 1] > T)
            return false;
    }
    if (i == n + 1) { // final state
        return true;
    }
    if (x[0] * 9 + y[0] * 3 + z[0] < a[0]) { // can't find the solution
        return false;
    }
    int sum = a[i];
    int nx = (sum + 8) / 9; // assign to x[i]
    nx = min(nx, x[0]);
    for (; nx >= 0; nx--) {
        x[i] = nx;
        x[0] -= x[i];
        sum -= x[i] * 9;
        int ny = (sum + 2) / 3; // assign to y[i]
        if (sum <= 0)
            ny = 0;
        ny = min(ny, y[0]);
        for (; ny >= 0; ny--) {
            y[i] = ny;
            y[0] -= y[i];
            sum -= y[i] * 3;
            z[i] = max(0, sum);
            z[0] -= z[i];
            a[0] -= a[i];
            int ok = dfs(i + 1);
            if (ok)
                return true;
            a[0] += a[i];
            z[0] += z[i];
            y[0] += y[i];
            sum += y[i] * 3;
        }
        sum += x[i] * 9;
        x[0] += x[i];
    }
    return false;
}

int mutaliskAttack(std::vector<int> scvs) {
    n = sz(scvs);
    sort(scvs.begin(), scvs.end(), greater<int>());
    FOR(i, 0, n - 1) a[i + 1] = scvs[i];

    a[0] = 0;
    FOR(i, 1, n) a[0] += a[i];
    int minS = a[0] / 13;

    int l = minS, r = 41, res = 42;
    while (l <= r) {
        int m = (l + r) >> 1;
        T = x[0] = y[0] = z[0] = m;
        int ok = dfs(1);
        if (ok) {
            res = m;
            r = m - 1;
        } else {
            l = m + 1;
        }
    }
    return res;
}

bây giờ em mới có lời giải của bài này, nhưng ko hiểu gì hết :3 mọi người tham khảo ạ

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