Задача на с++ 8 класс

Question

Задача на с++ 8 класс

г 2009 Ученик (88), на голосовании 6 дней назад

Имеется лента известной длины, на которой записаны цифры от 0 до 9. Требуется разрезать эту ленту на кусочки- числа так, чтобы эти числа образовывали
несколько (одну или больше) убывающих числовых последовательностей, причем
перестановка чисел не допускается. Разрезание происходит по следующему нехитрому алгоритму:
1) Отрезается первое число a1 в последовательности. Оно выбирается максимально близким к заданному числу M, но строго меньше его.
2) Каждое следующее число ai в последовательности выбирается максимально
возможным, но не превосходящим число ai−1.
3) Числа ai отрезаются до тех пор, пока это возможно. Каждое число может
иметь несколько ведущих нулей. Если очередное число отрезать невозможно,
то последовательность заканчивается. Начинается новая убывающая последовательность, и вс`е повторяется заново.
Ваша задача — промоделировать данный процесс и вывести получившиеся после
разрезания последовательности.
Формат входных данных
В первой строке записано число M (10 ≤ M ≤ 105
). В следующей строке записано
число N (1 ≤ N ≤ 105
) — количество символов на числовой ленте. В последней
строке записаны N цифр с числовой ленты.
Формат выходных данных
Для каждой числовой последовательности выведите по одной строке — числа
последовательности, разделенные запятыми.

Answer 1

Формат входных данных:

В первой строке записано число M (10 ≤ M ≤ 105).
В следующей строке записано число N (1 ≤ N ≤ 105) — количество символов на числовой ленте.
В последней строке записаны N цифр с числовой ленты.
Формат выходных данных:

Для каждой числовой последовательности вывести по одной строке — числа последовательности, разделённые запятыми.

Пример входных данных: 15, 11, 12109554302. 1 Пример выходных данных: 12, 10, 9, 5, 5, 4, 3, 02.

Answer 2

Код программы, которая решает задачу:

 #include <iostream> 
#include <vector> 
#include <string> 
#include <sstream> 
#include <algorithm> 
 
using namespace std; 
 
int main() { 
    int M; 
    cin >> M; 
 
    int N; 
    cin >> N; 
 
    string tape; 
    cin >> tape; 
 
    vector<string> sequences; 
    size_t i = 0; 
 
    while (i < N) { 
        vector<string> current_sequence; 
        string number = ""; 
 
        // Выбор первого числа, близкого к M 
        while (i < N && (number.empty() || stoll(number) < M)) { 
            number += tape[i++]; 
            if (stoll(number) < M) { 
                current_sequence.push_back(number); 
            } 
        } 
 
        // Выбор следующих чисел в убывающей последовательности 
        while (i < N && !current_sequence.empty()) { 
            number = ""; 
            while (i < N && (number.empty() || stoll(number) <= stoll(current_sequence.back()))) { 
                number += tape[i++]; 
            } 
 
            if (!number.empty()) { 
                current_sequence.push_back(number); 
            } 
        } 
 
        // Запись текущей последовательности в результат 
        if (!current_sequence.empty()) { 
            stringstream ss; 
            for (size_t j = 0; j < current_sequence.size(); j++) { 
                ss << current_sequence[j]; 
                if (j < current_sequence.size() - 1) { 
                    ss << ","; 
                } 
            } 
            sequences.push_back(ss.str()); 
        } 
    } 
 
    // Вывод всех последовательностей 
    for (const string& seq : sequences) { 
        cout << seq << endl; 
    } 
 
    return 0; 
}