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

[TDM (Đạt Phạm)]

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

[SITUVN.gcd]

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

[TDM (Đạt Phạm)]

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

[SITUVN.gcd]

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.

[TDM (Đạt Phạm)]

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

[hungaya (Hung)]

#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);
}

[SITUVN.gcd]

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

[phamvandung]

ghé cái

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