Bài toán tìm số, nằm trong khoảng 2 số nguyên dương cho trước, là tổ hợp lặp của 6 và 9

#1

Đạt mới nhận được một câu hỏi như sau, có bạn nào muốn thử sức không?

Cho hai số nguyên dương A và B. Độ dài của A và B không quá 12 số. Tìm tổng số nguyên bao gồm cả A và B, sao cho các số ngày chỉ chứa 6 và 9. Ví dụ: 6, 9, 66, 69, 96, 99, 666, 999, 696, 699, 969, 966, 996, …

Ví dụ:

Nếu A=5 và B=70, ta có 4 số
Nếu A=3 và B=100, ta có 6 số

  1. Cài đặt hàm sau

    int GetTotalNumber(long long A, long long B)
    {

    }

  2. Độ phức tạp của cách bạn cài đặt?

1 Like
#2

nghe đến 69 là khoái rồi :sunglasses:
e dùng thêm 1 hàm phụ nữa ko biết có đc ko nhỉ :v

EDIT: e quên mất, A,B là kiểu dữ liệu siêu to :3, bài này sai rồi :">

bool is69(int num) {
    if(num%3!=0) {
        return false;
    } else {
        do {
            int rearNum = num%10;
            num/=10;
            if(rearNum!=6&&rearNum!=9) {
                return false;
            }
        } while(num!=0);
    }
    return true;
}

int GetTotalNumber(long long A, long long B) {
    int totalNum=0;
    for(int i=A; i<=B; i++) {
        if(is69(i))totalNum++;
    }
    return totalNum;
}

Mà quái lạ, VS2015 không tạo được project C++ nhỉ, toàn là visual C++ thôi @@

1 Like
#3

Chương trình này nhập vào số 1 và số 999999999999 xem thử mất bao lâu?

#4

a,b kiểu int sao nhập nổi số đó a :v 12 số 9 là kiểu dữ liệu gì a:v sr e ko để ý nó kiểu long long :v
Mà máy e cũng ko tạo đc project c++ để test dc nữa :v

#5

vì chỉ có 2 số 6 và 9, mà A và B có tối đa 12 chữ số, vậy chỉ có tổng cộng 2 + 4 + 8 + 16 + … + 4096 = 8190 số chỉ có số 6 và 9 thôi. Viết 1 hàm tạo mảng X chứa 8190 số này theo thứ tự, coi như là constant time. Sau đó binary search A trong mảng X ra vị trí i sao cho X[i] nhỏ nhất và >= A, binary search B ra vị trí j sao cho X[j] lớn nhất và <= B. Kết quả là j - i + 1. Tuy tìm nhị phân thì có độ phức tạp là log(n) nhưng n ở đây là constant (8190) nên cũng coi như constant time O(1).

#include <iostream>
#include <vector>
#include <algorithm>

long long to69(unsigned i, int digit)
{
    long long n = 0;
    for (unsigned mask = 1 << (digit-1); digit--; mask >>= 1)
        n = 10*n + (mask&i ? 9 : 6);
    return n;
}

std::vector<long long> getAll69Numbers(int maxDigit)
{
    std::vector<long long> result;
    unsigned max = 2;
    for (int digit = 1; digit <= maxDigit; ++digit, max <<= 1)
        for (unsigned i = 0; i < max; ++i)
            result.push_back(to69(i, digit));
    return result;
}

int GetTotalNumber(long long a, long long b)
{
    static const std::vector<long long> N69 = getAll69Numbers(12); //
    int i = std::lower_bound(N69.begin(), N69.end(), a) - N69.begin();
    int j = std::upper_bound(N69.begin(), N69.end(), b) - N69.begin();
    return j - i;
}

int main()
{
    std::cout << "[5, 70]: " << GetTotalNumber(5, 70) << "\n";
    std::cout << "[3, 100]: " << GetTotalNumber(3, 100) << "\n";
    std::cout << "[65, 68]: " << GetTotalNumber(65, 68) << "\n";
    std::cout << "[0, 999999999999]: " << GetTotalNumber(0, 999999999999) << "\n";
}

up thêm cái code, nếu xài C++11 thì có cái auto thì xài std::distance để tính khoảng cách giữa iterator i và j, khỏi mất công trừ N69.begin() để lấy index:

auto i = std::lower_bound(N69.begin(), N69.end(), a);
auto j = std::upper_bound(N69.begin(), N69.end(), b);
return std::distance(i, j);
5 Likes
#6

A, B kiểu long long em :smile:

1 Like
#7 
#include <iostream>

using namespace std;

unsigned long long a, b;
int c = 0;

void Try(int i, int x)
{
    if (i <= 12)
    {
        for (int j = 6; j <= 9; j += 3)
        {
            if (x * 10 + j >= a && x * 10 + j <= b)
                ++c;
            Try(i + 1, x * 10 + j);
        }
    }
}

int main()
{
    cin >> a >> b;
    Try(1, 0);
    cout << c;
    return 0;
}

code của e đây ạ :smiley: độ phức tạp của nó là O(2^12) ạ :smiley:

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