Bài toán khôi phục dãy số - Sử dụng nhánh cận

Cho một xâu số nguyên S. Hãy đặt thêm các dấu “, ” vào giữa các chữ số của xâu S đó để được một dãy tăng.
Yêu cầu: Hãy đếm xem có bao nhiêu cách thêm dấu “,” vào giữa các chữ số để được một dãy tăng.
Dữ liệu: Xâu S gồm các chữ số.
Kết quả: Một số nguyên là số lượng cách thêm dấu ", ".

Ví dụ:
RECOVER.INP

111

RECOVER.OUT

2

RECOVER.INP

21023

RECOVER.OUT

3

Giải thích ví dụ 1: {1, 11}; {111}
Giải thích ví dụ 2: {2, 10, 23}; {2, 1023}; {21023}

Note: Độ dài xâu S yêu cầu là: 20 < |S| ≤ 100

Làm được gì chưa bạn?

4 Likes

Chưa bạn ơi. Mình có suy nghĩ đến dùng dãy nhị phân để từ đó tách nhưng như thế rất khó để loại bỏ những thành phần mà mình biết chắc là bị loại :grinning:

Rẽ nhánh và xét từng nhánh cho đến hết chuỗi xem kết quả nào đúng.
Các trường hợp xem xét:

  • Giá trị có số 0 đầu tiên là không hợp lệ. Vì 21023 không có kết quả: {21, 023}.
  • Chỉ tách không quá 1 nửa độ dài của chuỗi số, vì số thứ nhất mà dài hơn thì số còn lại chắc chắn nhỏ hơn.
  • Chính số ban đầu cũng là một kết quả hợp lệ. Nếu không bắt đầu là 0.

:thinking:

5 Likes

Bạn có thể code theo mã giả được không. Cơ bản là nó thế nhưng mà mình vẫn chưa giải quyết đc

:face_with_monocle: :face_with_monocle: :face_with_monocle:

#include <iostream>
#include <string>
#include <vector>
#include <list>

struct state {
    std::vector<int> numbers;
    int size = 1;
    
    state(std::vector<int> nums, int s): numbers{nums}, size{s} {}
    state(const state &old_state, int n, int len) {
        numbers = old_state.numbers;
        numbers.push_back(n);
        size = old_state.size + len;
    }
};

std::list<state> first_states(const std::string &str) {
    std::list<state> states;
    if (str.size() == 1 && str[0] == '0') return states;
    if (str.size() > 1 && str[0] == '0' && str[1] == '0') return states;
    
    int n = 0;
    for (int i = 0; i < str.size(); i++) {
        n = 10 * n + (str[i] - '0');
        states.push_back({ {n}, i + 1 });
    }
    
    return states;
}

std::list<state> next_states(const std::string &str, const state &curr) {
    std::list<state> next_states;
    if (str[curr.size] == '0') return next_states;
    
    int n = 0;
    int x = *(curr.numbers.end() - 1);
    
    for (auto i = curr.size; i < str.size(); i++) {
        n = 10 * n + (str[i] - '0');
        if (n > x) next_states.emplace_back(curr, n, i - curr.size + 1);
    }
    
    return next_states;
}

int increment_seq_count(const std::string &str) {
    int count = 0;
    std::list<state> states = first_states(str);
    
    while (!states.empty()) {
        auto curr = states.front();
        states.pop_front();
        count += curr.size == str.size();
        states.splice(states.end(), next_states(str, curr));
    }
    
    return count;
}

int main() {
    std::string input;
    std::getline(std::cin, input);
    std::cout << increment_seq_count(input);
}

:yum:

7 Likes

Javascript thôi. :smiling_imp:
https://codepen.io/SITUVN_gcd/pen/voGPoK

7 Likes

ghé cái :grin:

Rust theo functional programming

play it: https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=8714870eda1397ce85e6a14250f9a646


// bug: input bắt đầu là "0" thì kết quả ra 1. Phải kiểm tra chuỗi input!
fn main() {
    assert!(find("111") == 2);
    assert!(find("22023") == 3);
}
fn check_valid(num: &[u8]) -> bool {
    match num[0] {
        48 => false,
        _ => true,
    }
}

fn less_than(left: &[u8], right: &[u8]) -> bool {
    if left.len() == right.len() {
        less_than_helper(left, right)  
    } else {
        left.len() < right.len()
    }
}

fn less_than_helper(left: &[u8], right: &[u8]) -> bool {
    if left.len() == 0 {
        false
    } else {
        if left[0] == right[0] {
            less_than_helper(&left[1..], &right[1..])
        } else {
            left[0] < right[0]
        }
    }
}

fn find_inner(prev_num: &[u8], curr_num: &[u8]) -> usize {
    (prev_num.len()..curr_num.len() / 2 + 1)
        .map(|n| (&curr_num[..n], &curr_num[n..]))
        .filter(|(left, right)| {
            println!("{:?}, {:?}", left, right);
            match less_than(prev_num, left) && less_than(left, right) && check_valid(right) {
                true => {
                    println!("ok");
                    true
                }
                _ => {
                    println!("nope");
                    false
                }
            }
        })
        .map(|(left, right)| 1 + find_inner(left, right))
        .sum()
}

fn find(num: &str) -> usize {
    println!("\n{}:", num);
    let num = num.as_bytes();
    1 + find_inner(&num[0..0], &num[0..])
}
8 Likes
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?