LED (DHBB CT)

Tác giả:

Dạng bài

Điểm: 400 (p) Thời gian: 1.0s Bộ nhớ: 1023M Input: bàn phím Output: màn hình

Minh nhận được một chiếc máy tính bấm tay màn hình LCD. Màn hình được chia thành các ô biểu diễn chữ số, mỗi ô gồm \(7\) vạch LED và mỗi chữ số sẽ tương ứng với một số vạch LED được kích hoạt nổi màu đen trên ô đó. Cách hiển thị các số như sau:

Minh bấm số nguyên dương \(N\) hiển thị trên màn hình và thắc mắc 2 câu hỏi:

Có bao nhiêu vạch LED được kích hoạt để hiển thị số \(N\).
Tính số lượng các số lớn hơn \(N\), có thể được hiển thị bởi kích hoạt thêm ít nhất một vạch LED ngoài các vạch đang được kích hoạt để hiển thị số \(N\) (không tắt bất kỳ vạch LED nào đang hiển thị và không kích hoạt vạch LED trên ô chưa có vạch kích hoạt).

Yêu cầu: Hãy lập trình giúp Minh trả lời \(2\) câu hỏi trên.

Input

Dòng đầu tiên ghi mã câu hỏi \(V\) là \(1\) hoặc \(2\).
Dòng thứ 2 ghi số nguyên dương \(N\) (không bắt đầu bởi chữ số \(0\)).

Output

Nếu \(V=1\) thì in ra số vạch LED được kích hoạt để hiển thị số \(N\).
Nếu \(V=2\) thì in ra số lượng số lớn hơn \(N\), có thể được hình thành bằng cách kích hoạt thêm ít nhất một vạch LED, bên cạnh các vạch đã kích hoạt được sử dụng để hiển thị số \(N\).

Constraints

\(N \leq 10 ^ {18}\)

Scoring

Subtask \(1\) (\(45\%\) số điểm): \(V = 1, N \leq 10 ^ {18}\).
Subtask \(2\) (\(20\%\) số điểm): \(V = 2, N < 20\)
Subtask \(3\) (\(35\%\) số điểm): \(V = 2, 20 \leq N \leq 10 ^ {18}\)

Example

Test 1

Input

1 
823

Output

Test 2

Input

2 
823

Output

Note

Ví dụ \(1\): số 8 dùng 7 vạch, số 2 dùng 5 vạch, số 3 dùng 5 vạch, do đó cần 17 vạch.
Ví dụ \(2\): có 5 số lớn hơn 823 là 828, 829, 883, 888, 889.

Bình luận

`Spoiler Alert`

Hint 1

Query 1: Tính tổng vạch led bật mỗi chữ số từ số n
Query 2: Với mỗi số x > n có cùng độ dài với n. Tăng biến đếm nếu x có chứa các vạch led n

Hint 2

Query 1: Ta có thể tiền xử lí 10 chữ số 0..9 xem nó có bao nhiêu vạch led bật để tiện
Query 2: Ta có thể thử xây từng chữ số cho x, từ đó đưa ta đến thuật quy hoạch động chữ số

Hint 3

Query 1: vector<int> csl = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6}; /// Count set-led
Query 2: Thử xây từng chữ số với hàm đệ quy magic(int index, bool isGreater)

Với index là vị trí các chữ số của n từ trái sang phải

Với isGreater là biến kiểm tra xem số hiện tại lớn hơn n chưa

Ta thử xây chữ số tiếp theo là chữ số có chứa các vạch led bật sẵn

Hint 4

Query 2:

Ta có thể tiền xử lí xem với mỗi chữ số d = 0..9 thì có những số nextd nào có vạch led d bật, tức những cách thỏa mãn

Nếu số hiện tại đã lớn hơn n, thì mình có thể chọn mọi số nextd <=> lower_limit = 0

Nếu số hiện tại chưa lớn hơn n, thì mình chỉ có thể chọn mọi số nextd ≥ d <=> lower_limit = d

Nếu số hiện tại đã lớn hơn n hoặc nextd > d thì isGreater = true (khởi tạo là False nhé)

Sau đó ta đệ quy chữ số tiếp theo

Hint 5

Query 2: Recursive Formula: res = res + magic(index + 1, isGreater || (nextd > lower_limit))

Reference AC code | \(O(log_{10} n)\) + \(O(log_{10} n * 2 * 7)\) time | \(O(1)\) auxiliary space | Brute-forces + DP_digit | Adjacency List Implementation

C++

/// Tiền xử lí các vạch led bật
vector<int> cntled = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6};
void solve1()
{
    /// Biểu diễn số dưới dạng xâu
    string s;
    cin >> s;

    /// Kết quả là tổng số lượng vạch led bật
    int res = 0;
    for (char c : s)
        res += cntled[c - '0'];

    cout << res;
}

/// Tiền xử lí
/// vector thứ n biểu diễn tất cả các đèn led mà các vạch led có trong n được bật
vector<vector<int> > G = {
    {0, 8},                 /// [0]
    {0, 1, 3, 4, 7, 8, 9},  /// [1]
    {2, 8},                 /// [2]
    {3, 8, 9},              /// [3]
    {4, 8, 9},              /// [4]
    {5, 6, 8, 9},           /// [5]
    {6, 8},                 /// [6]
    {0, 3, 7, 8, 9},        /// [7]
    {8},                    /// [8]
    {8, 9},                 /// [9]
};

int n;                  /// Độ dài của số nhận vào
vector<int> v;          /// vector chứa các chữ số
vector<vector<ll> > f;  /// vector 2 chiều quy hoạch động
/// hàm magic(i, ign)
/// tại vị trí (i) của số biểu diễn bởi vector (v)
/// đếm số cách mà xây dựng được số có (ign) = true
ll magic(int i = 0, bool ign = false) /// O(n * 2 * 7)
{
    /// Nếu đã duyệt hết vector
    if (i >= n) return ign;

    /// Dùng con trỏ để tiện tính toán
    ll &res = f[i][ign];
    if (res != -1) return res; /// Nếu đã được tính trước đó
    else res = 0;              /// Ngược lại thì reset giá trị

    /// Chúng ta chỉ đếm các số lớn hơn
    int lim = ign ? 0 : v[i];
    for (int d : G[v[i]])
        if (d >= lim)
            res += magic(i + 1, ign || (d > lim));

    /// Đừng quên trả về kết quả :D
    return res;
}

void solve2()
{
    /// Biểu diễn số dưới dạng xâu
    string s;
    cin >> s;

    /// Dùng vector (v) độ dài (n) để lưu trữ các chữ số
    n = s.size();
    for (char c : s) v.pb(c - '0');

    /// Khởi tạo -1 tức là chưa được tính trước đó
    f.assign(n + 1, vector<ll>(2, -1));
    cout << magic();
}

Reference AC code | \(O(log_{10} n)\) + \(O(log_{10} n * 2 * 7)\) time | \(O(1)\) auxiliary space | Brute-forces + DP_digit

C++

/// Tiền xử lí các vạch led bật
vector<int> cntled = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6};
void solve1()
{
    ll n = readLong();
    int res = 0;       /// Kết quả là tổng số lượng vạch led bật
    do res += cntled[n % 10]; while (n /= 10);
    cout << res;
}


/// Tiền xử lí
/// bit thứ (i) của vector thứ (n) biểu diễn có thể chuyển đổi từ (led-i) sang (led-n) hay không
vector<vector<bool> > G = {
    {1, 0, 0, 0, 0, 0, 0, 0, 1, 0}, /// [0] - 0, 8
    {1, 1, 0, 1, 1, 0, 0, 1, 1, 1}, /// [1] - 0, 1, 3, 4, 7, 8, 9
    {0, 0, 1, 0, 0, 0, 0, 0, 1, 0}, /// [2] - 2, 8
    {0, 0, 0, 1, 0, 0, 0, 0, 1, 1}, /// [3] - 3, 8, 9
    {0, 0, 0, 0, 1, 0, 0, 0, 1, 1}, /// [4] - 4, 8, 9
    {0, 0, 0, 0, 0, 1, 1, 0, 1, 1}, /// [5] - 5, 6, 8, 9
    {0, 0, 0, 0, 0, 0, 1, 0, 1, 0}, /// [6] - 6, 8
    {1, 0, 0, 1, 0, 0, 0, 1, 1, 1}, /// [7] - 0, 3, 7, 8, 9
    {0, 0, 0, 0, 0, 0, 0, 0, 1, 0}, /// [8] - 8
    {0, 0, 0, 0, 0, 0, 0, 0, 1, 1}, /// [9] - 8, 9
};

int n;                  /// Độ dài của số nhận vào
vector<int> v;          /// vector chứa các chữ số
vector<vector<ll> > f;  /// vector 2 chiều quy hoạch động
/// hàm magic(i, ign)
/// tại vị trí (i) của số biểu diễn bởi vector (v)
/// đếm số cách mà xây dựng được số có (ign) = true
ll magic(int i = 0, int ign = false) /// O(n * 2 * 9)
{
    /// Nếu đã duyệt hết vector
    if (i >= n) return ign;

    /// Dùng con trỏ để tiện tính toán
    ll &res = f[i][ign];
    if (res != -1) return res; /// Nếu đã được tính trước đó
    else res = 0;              /// Ngược lại thì reset giá trị

    /// Chúng ta chỉ chọn những chữ số có thể chuyển đổi được
    int lim = ign ? 0 : v[i];
    for (int d = 9; d >= lim; --d)
        if (G[v[i]][d] == true)
            res += magic(i + 1, ign || (d > lim));

    /// Đừng quên trả về kết quả :D
    return res;
}

void solve2()
{
    /// Biểu diễn số dưới dạng xâu
    string s;
    cin >> s;

    /// Dùng vector (v) độ dài (n) để lưu trữ các chữ số
    n = s.size();
    for (char c : s) v.pb(c - '0');

    /// Khởi tạo -1 tức là chưa được tính trước đó
    f.assign(n + 1, vector<ll>(2, -1));
    cout << magic();
}

5 bình luận nữa