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

minhcanhtu · September 9, 2018, 1:16am

Chào mọi người. Mình có đang làm 1 problem sau: http://ntucoder.net/Problem/Details/5621
Hướng giải của mình sẽ là dùng quay lui để giải như sau:

Đầu tiên, ta sinh 1 dãy nhị phân có độ dài bằng số chữ số của x + số chữ số của y (tối đa là 18 chữ số theo giới hạn của đề) bằng quay lui.
Ta sẽ quy ước trong dãy nhị phân, ký tự 0 nghĩa là lấy chữ số đầu tiên của x từ trái sang bỏ vào mảng kết quả result[], ký tự 1 nghĩa là lấy chữ số đầu tiên của y tù trái sang bỏ vào mảng kết quả result[]. (như thế chúng sẽ vẫn giữ nguyên thứ tự ghi ghép số)
Vì quy ước trên, những dãy nhị phân có tổng số ký tự 0 khác số chữ số của x hoặc tổng số ký tự 1 khác số chữ số của y thì sẽ sai, ta không xét đến.
Sau cùng, ta sẽ tìm min và max của mảng kết quả result[], đó chính là kết quả trả về của chương trình.

VD: x = 13, y = 26
Ta sẽ sinh dãy nhị phân có độ dài = 4 mà số ký tự 0 là 2 và số ký tự 1 là 2:

Với 0011 ta sẽ có giá trị: 1326
Với 0101 ta sẽ có giá trị: 1236
Với 0110 ta sẽ có giá trị: 1263
Với 1001 ta sẽ có giá trị: 2136
Với 1010 ta sẽ có giá trị: 2163
Với 1100 ta sẽ có giá trị: 2613
Dễ thấy, trong 6 giá trị tìm được, GTNN là 1236 và GTLN là 2613, đây chính là output của thuật toán.

Dựa vào ý tưởng trên, mình code như sau: https://ideone.com/LQA9cw

#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
int 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[]*/

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 = static_cast<int>(::a/pow(10, _na--)) % 10;
            result[_index] += digit * pow(10, temp--);
        }
        else {
            int digit = static_cast<int>((::b)/pow(10, _nb--)) % 10;
            result[_index] += digit * pow(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, 262144);
    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ì code khá dài nên mình chú thích từng đoạn cho mọi người đọc dễ hiểu.
Khi submit lên trang NTUcoder thì code bị sai ở test số 9 (tức là có bug).
Mình tìm hoài không thấy nên post lên đây nhờ các cao nhân giúp đỡ ạ!
Xin cảm ơn.

Gio · September 9, 2018, 2:52am

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)).

minhcanhtu · September 9, 2018, 5:10am

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

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

rogp10 · November 13, 2018, 5:50am

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).

minhcanhtu · September 9, 2018, 6:18am

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!

Bạn có thể hướng dẫn mình cách fix không?

minhcanhtu · September 9, 2018, 7:33am

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!

SITUVN.gcd · September 9, 2018, 9:55am

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.

Xét 1x và 2y => lấy 1x. Giữ lại 2y. Được 1
Xét 3x và 2y => lấy 2y. Giữ lại 3x. Được 12
Xét 3x và 6y => lấy 3x. Giữ lại 6y. Được 123
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.

1x và 2y: lấy 2y, giữ 1x. Được 2.
1x và 6y: lấy 6y, giữ 1x. Được 26.
y đã xét xong, lấy 1x. Được 261.
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

tntxtnt · September 9, 2018, 12:26pm

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à

SITUVN.gcd · September 9, 2018, 12:37pm

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

tntxtnt · September 9, 2018, 1:26pm

đâ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 =)

rogp10 · September 9, 2018, 1:27pm

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

tntxtnt · September 9, 2018, 1:52pm

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";
}

rogp10 · September 9, 2018, 2:20pm

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ỉ.

tntxtnt · September 9, 2018, 2:21pm

ổ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