LED (DHBB CT)

Xem PDF
Tác giả:
Small
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:

  1. Có bao nhiêu vạch LED được kích hoạt để hiển thị số \(N\).
  2. 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 
17

Test 2

Input 
2 
823
Output 
5
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


  • 0
    SPyofgame    11:04 p.m. 12 Tháng 6, 2020 ← chỉnh sửa 4

    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:

    Duyệt i từ trái sang phải

    Gọi ctw = count_total_ways là số cách chọn chữ số tại vị trí i

    Gọi clw = count_less_ways là số cách chọn chữ số bé hơn tại vị trí i

    Gọi res là tổng số cách chọn trước đó

    Dựa vào đó ta tính tổng số cách chọn bây giờ

    Hint 4

    • Query 2:

    Ta có thể tiền xử lí xem với mỗi chữ số d = 0..9 thì số cách chọn ctw[d] và clw[d] là gì

    Có ctw[d] là số lượng số x thỏa x chứa các vạch led d bật

    Có clw[d] là số lượng số x < d thỏa x chứa các vạch led d bật

    Từ đó suy ra công thức toán học

    Hint 5

    • Query 2: Multiplicative Formula: res = res * ctw[d] - clw[d]

    Reference AC code | \(O(log_{10} n)\) + \(O(log_{10} n)\) time | \(O(1)\) auxiliary space | Brute-forces + DP_digit | Online Solving Implementation

    C++
                 ///   0  1  2  3  4  5  6  7  8  9
vector<int> csl = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6}; /// Đếm số vạch led bật
vector<int> ctw = {2, 7, 2, 3, 3, 4, 2, 5, 1, 2}; /// Số cách chọn chữ số tại vị trí i
vector<int> clw = {0, 1, 0, 0, 0, 0, 0, 2, 0, 1}; /// Số cách chọn chữ số bé hơn tại vị trí i
inline bool isDig(char c) { return '0' <= c && c <= '9'; } /// isDigit(char) ?
void solve1() /// O(log10 n)
{
    int res = 0;
    char c;
    while (c = getchar(), !isDig(c));
    do res += csl[c - '0']; while (isDig(c = getchar()));
    cout << res;
}

void solve2() /// O(log10 n)
{
    ll res = 1;
    char c;
    while (c = getchar(), !isDig(c));
    do res = res * ctw[c - '0'] - clw[c - '0']; while (isDig(c = getchar()));
    cout << res - 1; /// Bỏ qua trường hợp bằng nhau
}
      • 4 bình luận nữa