Ghép hai số cho trước thỏa mãn đạt cực đại và cực tiểu bằng thuật toán quay lui

Mình nhận thấy các vấn đề sau:

• các ghép 2 số có 8 chữ số sẽ được số có 16 chữ số(10^16) vậy int ~ 2*10^9 không đủ chứa mà phải chuyển sang long.
• memset là set theo byte của mảng, nên phải là memset(result,0,sizeof(result)).

các ghép 2 số có 8 chữ số sẽ được số có 16 chữ số(10^16) vậy int ~ 2*10^9 không đủ chứa mà phải chuyển sang long .

Hmm mình quên mất chỗ này. Thế là mình chỉnh lại mảng toàn cục unsigned long long result[262144];
và chỉnh nốt chỗ memset(result, 0, sizeof(result)); thì code chạy được đến test 70 bị wrong answer tiếp.
Mình nghi có thể test đó cho giá trị “khủng”. Bạn có thấy chỗ nào trong code khả nghi nữa không?

P/S: Khi code xong mình thấy có chỗ hơi kỳ là nếu nhập input hai số 287 và 45 thì Codeblocks lại ccho kết quả 24586 và 45286 sai! Trong khi đem bỏ lên rextester thì cả gcc, clang và vc++ đều cho kết quả đúng 24587 và 45287 : http://rextester.com/LTGJ3679

image.png1366x768 64.2 KB

Không biết chỗ này có ảnh hưởng gì đến code không nhỉ ?

TDM-GCC (compiler mặc định của CB) bị lỗi hàm pow rồi. Dù ko xài CB thì nên đổi hết chỉ dùng phép tính số nguyên (thay log với pow gì đấy).

bài này làm như merge mảng ấy

Mình chưa hiểu lắm !

Theo mình thấy thì có vẻ code mình sai ở mấy chỗ pow() do truyền tham số nguyên. Mình có sửa lại thành tham số thực và đổi datatype của result[] thành long double thì submit lại sai ở test 4!

Ideone.com

Ideone.com

Ideone is something more than a pastebin; it's an online compiler and debugging tool which allows to compile and run code online in more than 40 programming languages.

Mình đã tự viết 1 hàm power() tính lũy thừa riêng thì cuối cùng cũng AC.

#include <iostream>
#include <cmath> // pow() and log10()
#include <cstring> // memset()
#include <algorithm> // std::min_element() and std::max_element()

using namespace std;

// Problem: http://ntucoder.net/Problem/Details/5621

int arr[18]; // Store the binary sequence
unsigned long long result[262144]; // (=2^18) Store the possible results of number z
int a, b, na, nb, _index = 0, n = 0;
/* a and b is the 2 numbers of input. na is the number of digit of a, nb is the number of
digit of b, _index is the index of array result[], n is the number of elements of result[]*/

unsigned long long power(int base, int exponent)
{
    unsigned long long res = 1;
    for (int i = 1; i <= exponent; ++i)
        res *= base;
    return res;
}

void Analyze(int a[])
{
    /* "_na" is used with pow() of base 10 and mod 10 to take the first digit of "a" from
    the left to the right. So is "_nb".
    For instance: a = 584 => na = 3 => _na = 2 => (584 / 10^2) % 10 = 5 is the first digit
    of a from the left to the right.
    */
    int _na = na - 1, _nb = nb - 1, temp = na + nb - 1;
    for (int i = 0; i < (na + nb); ++i) {
        if (a[i] == 0) {
            int digit = (::a/power(10, _na--)) % 10;
            result[_index] += digit * power(10, temp--);
        }
        else {
            int digit = (::b/power(10, _nb--)) % 10;
            result[_index] += digit * power(10, temp--);
        }
    }
    ++_index; // update the index of result[] for the next assignments.
}

// Backtracking
void ListBinary(int i)
{
    // na + nb is the length of the binary sequence.
    if (i == (na + nb)) {
        /* Count if the number of value 0 in the binary sequence is equal to the length of
        a and the number of value 1 in the binary sequence is equal to the length of b. */
        int zero = 0, one = 0;
        for (int i = 0; i < (na + nb); ++i) {
            if (arr[i] == 0)
                ++zero;
            else ++one;
        }
        /* If the binary sequence is appropriate, then we will use it to create a number
        and put into the result[] */
        if (zero == na && one == nb) {
            ++n;
            Analyze(arr);
        }
    }
    else {
        arr[i] = 0;
        ListBinary(i + 1);
        arr[i] = 1; // backtrack
        ListBinary(i + 1);
    }
}

int main()
{
    memset(result, 0, sizeof(result));
    cin >> a >> b;
    na = (int)log10(a) + 1;
    nb = (int)log10(b) + 1;
    ListBinary(0);
    cout << *min_element(result, result + n) << endl << *max_element(result, result + n);
    return 0;
}

Vậy là tối qua giờ sai ở chỗ là sai số !
Cảm ơn mọi người đã pay attention to!

Cách giải của mình:
Xét từng chữ số của cả x và y từ trái qua phải và so sánh:

• Để số là số lớn nhất thì lấy chữ số lớn hơn, cứ thế xét từng chữ số của cả x và y rồi so sánh và cộng vào kết quả.
• Nhỏ hơn thì tương tự và ngược lại.

• Chữ số nào chưa được lấy thì số đó sẽ vẫn tiếp tục được so sánh.

Vd:

x=13
y=26

Sẽ được từng chữ số:

ax=[1,3]
ay=[2,6]

Lặp tổng độ dài của x và y (4):

• Để lấy số nhỏ nhất. Lấy chữ số nhỏ hơn.

0. Xét 1x và 2y => lấy 1x. Giữ lại 2y. Được 1
1. Xét 3x và 2y => lấy 2y. Giữ lại 3x. Được 12
2. Xét 3x và 6y => lấy 3x. Giữ lại 6y. Được 123
3. x đã được xét xong cứ thế mà gán các chữ số còn lại của y vào. Lấy 6y. Kết thúc.
   => 1236

• Số lớn nhất: lấy chữ số lớn hơn.

0. 1x và 2y: lấy 2y, giữ 1x. Được 2.
1. 1x và 6y: lấy 6y, giữ 1x. Được 26.
2. y đã xét xong, lấy 1x. Được 261.
3. y đã xét xong, lấy 3x. Được 2613.
   => 2613

Quá trình lặp đã tự đảm bảo thứ tự của các chữ số của x và y

Mã:
https://ideone.com/Z3yc6E

cách merge phải xét xem trường hợp 2 chữ số bằng nhau nữa, ví dụ 94 93 thì phải lấy số 9 thứ 2 chứ ko phải 9 thứ nhất, rồi tới 3, rồi 9 rồi 4, có khi còn khó hơn duyệt trâu =)

đọc vào int làm gì, đọc vào 2 chuỗi rồi tha hồ mà quẩy, duyệt trâu tối đa 2¹⁶ trường hợp nên cũng lẹ mà

Bằng nhau thì lấy số nào cũng vậy thôi mà.
Ý tưởng ban đầu là chuyển sang chuỗi, nhưng làm thế cho nguyên bản

đâu có, khác chứ, ví dụ 92 93 và 94 93 là thấy. Nếu nó chọn số 9 thứ nhất thì số nhỏ nhất sẽ in ra sai ở trường hợp 94 93 (in ra 9493, đúng phải là 9394), nếu nó chọn số 9 thứ hai thì số nhỏ nhất sẽ sai ở trường hợp 92 93 (in ra 9392, đúng phải là 9293)

92
93
chọn 9 thứ 2 -> 9---

92
3
3 nhỏ hơn, chọn 3 -> 93-- (sai)

trường hợp 92 93 phải chọn số 9 thứ nhất, trường hợp 94 93 thì phải chọn số 9 thứ 2, nên thành ra nếu xét 2 chữ số bằng nhau thì phải nhìn tiếp mấy số phía sau nữa, nếu 2 chuỗi dài bằng nhau thì đỡ khác nhau lại phải xét if else cái nào hết chữ cái để đọc v.v… rắc rối vô cùng =) nếu chỉ merge kiểu kia được thì ghi 2 dòng là xong rồi

std::string a, b, c, d; std::cin >> a >> b;
std::merge(begin(a), end(a), begin(b), end(b), std::back_inserter(c),
           std::less<char>{});
std::merge(begin(a), end(a), begin(b), end(b), std::back_inserter(d),
           std::greater<char>{});
std::cout << c << "\n" << d << "\n";

đằng này phải xét x == y nữa, phải nhìn trước ngó sau tùm lum tá lả thôi duyệt trâu dễ hơn =)

duyệt trâu dễ hơn

Duyệt trâu O(2^(m+n)) còn merge thì O(mn) chứ mấy khác nhau hẳn luôn.

m+n tối đa có 16 nên 2^16 khác gì O(1) đâu =) với lại chỉ tính 1 cặp a b chứ đâu phải 100 ngàn cặp đâu mà lo, cái này chạy trâu cũng khác gì O(1) luôn đâu

tại người ra đề chắc giải với a b là số nguyên nên hạn chế như vậy, chứ cho a b là chuỗi thì m+n 1000 cũng được, khi đó phải tính theo kiểu merge, chịu khó ngồi debug =)

edit: trâu cày 22 dòng =)

#include <iostream>
#include <string>

int main()
{
    std::string a, b; std::cin >> a >> b;
    std::string smin = a + b, smax = smin;
    for (unsigned slen = a.size() + b.size(), i = 1u << slen; i--; )
    {
        std::string s;
        decltype(begin(a)) p[][2] { {begin(a), end(a)}, {begin(b), end(b)} };
        for (unsigned j = i, k = slen; k--; j >>= 1)
        {
            auto& q = p[j % 2];
            if (q[0] == q[1]) break;
            s += *q[0]++;
        }
        if (s.size() == slen)
            if (s < smin) smin = s; else if (s > smax) smax = s;
    }
    std::cout << smin << "\n" << smax << "\n";
}

Cái này gọi là phương pháp sinh

Nếu là “487…” vs. “482…” thì bỏ qua phần 48 trùng rồi lấy 482 ổn không nhỉ.

ổn vì phải theo thứ tự mà, mấy số sau làm sao trèo lên mấy số trước được