Информатика C++ помогите с задачей

Question

Информатика C++ помогите с задачей

Матвей Кузнецов Знаток (449), открыт 1 день назад

Помогите разобраться и решить эту задачу через C++

253) Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в обеих командах v и w обозначают цепочки символов.
заменить (v, w)
нашлось (v)
Первая команда заменяет в строке первое слева вхождение цепочки у на цепочку w. Если цепочки v в строке нет, эта команда не изменяет строку. Вторая команда проверяет, встречается ли
цепочка v в строке исполнителя Редактор.
Дана программа для Редактора:
ПОКА нашлось (111)
заменить (111, 2)
заменить (2222, 333)
заменить (33, 1)
КОНЕЦ ПОКА
Известно, что исходная строка содержала более 100 единиц и не содержала других цифр. Укажите минимально возможную длину исходной строки, при которой в результате работы этой программы получится строка, содержащая минимально возможное количество единиц.

Answer 1

 #include <iostream> 
#include <string> 
 
using namespace std; 
 
// Функция замены первого вхождения v на w 
void replace(string& s, const string& v, const string& w) { 
    size_t pos = s.find(v); 
    if (pos != string::npos) { 
        s.replace(pos, v.length(), w); 
    } 
} 
 
// Функция проверки наличия подстроки v 
bool found(const string& s, const string& v) { 
    return s.find(v) != string::npos; 
} 
 
// Подсчет единиц в строке 
int count_ones(const string& s) { 
    int count = 0; 
    for (char c : s) { 
        if (c == '1') count++; 
    } 
    return count; 
} 
 
int main() { 
    int min_N = 101; // Минимальная длина > 100 
    int min_ones = 101; // Больше, чем возможно 
    int best_N = 0; 
 
    // Перебираем длины строк > 100 
    for (int N = 101; N <= 120; N++) { 
        string s(N, '1'); // Строка из N единиц 
        string original = s; 
 
        // Выполняем программу 
        while (found(s, "111")) { 
            replace(s, "111", "2"); 
            replace(s, "2222", "333"); 
            replace(s, "33", "1"); 
        } 
 
        int ones = count_ones(s); 
        if (ones < min_ones) { 
            min_ones = ones; 
            best_N = N; 
            cout << "N = " << N << ", result = " << s << ", ones = " << ones << endl; 
        } 
    } 
 
    cout << "Минимальная длина: " << best_N << ", единиц: " << min_ones << endl; 
    return 0; 
}