Найти наибольшую арифметически корректную подстроку равную нулю

Question

Найти наибольшую арифметически корректную подстроку равную нулю

Рейтинг: 2Ответов: 5Опубликовано: 16.02.2025

Не могу правильно решить задачу из ЕГЭ по информатике. Объясните, пожалуйста, в чём я ошибся.

Задача с KompEGE:

№ 17685 Пересдача 04.07.24 (Уровень: Гроб)

Текстовый файл состоит из десятичных цифр, знаков «+» и «*» (сложения и умножения). Определите максимальное количество символов в непрерывной последовательности, являющейся корректным арифметическим выражением с целыми неотрицательными числами (без знака), значение которого равно нулю. В этом выражении никакие два знака арифметических операций не стоят рядом, порядок действий определяется по правилам математики. В записи чисел отсутствуют незначащие (ведущие) нули. В ответе укажите количество символов.

Ответ: 169

Файл к задаче

Мой код:

s = open("24_17641.txt").read()
while "**" in s or "++" in s or "*+" in s or "+*" in s:
    if "**" in s:
        s = s.replace("**", "* *")
    if "++" in s:
        s = s.replace("++", "+ +")
    if "*+" in s:
        s = s.replace("*+", "* +")
    if "+*" in s:
        s = s.replace("+*", "+ *")
s = s.split()
print(s)
a = [i[1:-1] for i in s if i != "+" and i != "*"]
a = a[1:-1]
mx = 0
for i in a:
    if eval(i) == 0:
        mx = max(mx, len(i))
print(mx)

python алгоритм

Источник: Stack Overflow на русском

Answer 1

▲ 7Принят

Я вызвал ваше решение с выражением 0*0+1*1, получил ответ 0. А правильный ответ 3 для выражения 0*0. Ошибка в алгоритме.

NB Это вторая попытка. Первая строилась на анализе выражений "сверху вниз" и ломалась на 10+1 и 10*1. Если обработку 10+1 можно было починить, глядя на предыдущее слагаемое, то 10*1 куда хуже. Оно не чинится, если мы разбили выражение на слагаемые и коэффициенты. Я бросил этот подход и сделал по другому.

Класс Expr принимает последовательные символы (e.update(с)) и содержит следующие поля:

e.length – длина текста, пока он синтаксически правильный;
e.valid_prefix – истина, если текст может быть продолжен до правильной формулы с нулевым значением;
e.valid_zero – истина, если текст прямо сейчас представляет правильную формулу с нулевым значением;
e.last_term_is_zero – истина, если последнее слагаемое в формуле содержит нулевой множитель.

На каждой итерации хранятся максимум три выражения-корректных префикса:

самая длинная формула, у которой последний множитель не ноль (но которая имеет шанс стать нулевой в будущем);
самая длинная формула, у которой последний множитель ноль (она обновляет текущий максимум);
формула из одного последнего символа.

Алгоритм работает за линейное время и избегает, как мне кажется, описания большого количества тонких мест.

Я переделал программу, чтобы её можно было тестировать с разными текстами. Для исходного текста её надо запускать так: cat 24_17641.txt | python zero-expr.py.

class Expr:
    def __init__(self):
        self.length = 0
        self.valid_prefix = True
        self.valid_zero = False
        self.last_term_is_zero = False
        self._last_factor = ''              # '' for empty last factor
                                            # '0' for zero last factor
                                            # '1' for nonzero last factor

    def update(self, char):
        if self.valid_prefix and self._update(char):
            self.length += 1
            self.valid_zero = self.last_term_is_zero and self._last_factor != ''
        else:
            self.valid_prefix = False
            self.valid_zero = False

    def _update(self, char):
        if char == '+':
            if self._last_factor == '':
                return False                # no digit before `+` sign
            if not self.last_term_is_zero:
                return False                # whole expression is above zero
            self.last_term_is_zero = False
            self._last_factor = ''          # start new factor
            return True

        if char == '*':
            if self._last_factor == '':
                return False                # no digit before `*` sign
            self._last_factor = ''          # start new factor
            return True

        if char == '0':
            if self._last_factor == '':
                self._last_factor = '0'
                self.last_term_is_zero = True
                return True
            return self._last_factor != '0' # leading zero before digit

        if '1' <= char <= '9':
            if self._last_factor == '':
                self._last_factor = '1'     # nonzero last factor
                return True
            return self._last_factor != '0' # leading zero before digit

        return False                        # unknown character


def main():
    with open(0) as f:
        text = f.read()

    max_length = 0
    exprs = []
    for c in text:
        exprs.append(Expr())
        for e in exprs:
            e.update(c)
            if e.valid_prefix and e.valid_zero:
                max_length = max(max_length, e.length)

        new_exprs = []
        for e in exprs:
            if e.valid_prefix:
                new_exprs.append(e)
                break
        for e in exprs:
            if e.valid_prefix and e.last_term_is_zero and e not in new_exprs:
                new_exprs.append(e)
                break
        exprs = new_exprs

    print(max_length)


main()

Answer 2

▲ 3

Вещи держать в уме:

Нулевая последовательность может быть под-последовательностью ненулевой последовательности.
Можно "украсть" конечный ноль у ненулевого число. Например, в последовательности 12340+567*0 макс нулевая последовательность это 0+567*0.
Если нет ненулевых выражений, но есть цифра "0" в тексте, то это и есть макс последовательность.

Спасибо @Vitalizzare за находку ошибок в моем коде.

Итак, исправленный код будет:

import re

def find_longest_zero_expr(text):
    longest = "0" if "0" in text else ""
    
    for expr in re.split("[*+]{2,}", text.strip("*+")):
        if len(expr) < len(longest): continue
    
        zeros = []
        for prod in expr.split('+'):
            if "*0*" not in '*' + prod + '*':
                parsed = "+".join(zeros)
                if len(parsed) > len(longest): longest = parsed

                pos = prod.find("0*")
                if pos > 0:
                    # take "0*..." sub-sequence from non-zero product
                    zeros = [prod[pos:]]
                elif prod.endswith('0'):
                    # take trailing '0' from non-zero product
                    zeros = ["0"]
                else: zeros = []
    
            else: zeros += [prod]
    
        parsed = "+".join(zeros)
        if len(parsed) > len(longest): longest = parsed
        
    return longest

text = open("9rWpROaef.txt").read()
print(len(find_longest_zero_expr(text)))

Answer 3

▲ 1

как насчет того чтобы вжухнуть задачку одной регуляркой? :)

RegEx:

/(?:
  (?:             (?# первый "нулевой мультик" - группа множителей с как минимум 1м нулём )
    (?:[0-9]+\*)*
    (?<![0-9])   (?# без хвоста)
    0+
    (?![0-9])    (?# и без ведущего)
    (?:\*[0-9]+)*
  )

  (?:             (?# все остальные мульты )
    \+
    (?:[0-9]+\*)*
    0+
    (?![0-9])     (?# и без прочих ведущих )
    (?:\*[0-9]+)*
  )*
)/gx   (?# флаги - Global, eXtended )

JavaScript:

let s = `999***0*123*0*2*4*8*0****630+32373*0*60611+0*0*29472+0+49966*47103*0*0*0+0+0+0+0*54026*0+22544*0*0*0+0+0+0*0*0*0*0*0+0+0+0*0*29624+0+0+60153*0+0+0*52823*0*0*0*0*0*0*0+0+0*0+0+0+0*17505+0+0*0*0*0+0
['*100000*1+0*', '0*1+0'],
['1000001', '0'],
['10+00002', '0+0'],    # can be skipped, no leading zero expected
 '1*0+00002'
['0', '0'],
['0*', '0'],
['*0', '0'],
['*0*', '0'],
['0+1', '0'],
['0+0', '0+0'],
['0*0', '0*0'],
['10', '0'],
['101', '0'],
['10+0', '0+0'],
['10*1+0', '0*1+0'],`;
let p = /(?:(?:(?:[0-9]+\*)*(?<![0-9])0+(?![0-9])(?:\*[0-9]+)*)(?:\+(?:[0-9]+\*)*0+(?![0-9])(?:\*[0-9]+)*)*)/g;

for(e of s.match(p))
{
  console.log(e.length + ' < ' + e)
}

и наконец Python:

import re

s = '999***0*123*0*2*4*8*0****630+32373*0*60611+0*0*29472+0+49966*47103*0*0*0+0+0+0+0*54026*0+22544*0*0*0+0+0+0*0*0*0*0*0+0+0+0*0*29624+0+0+60153*0+0+0*52823*0*0*0*0*0*0*0+0+0*0+0+0+0*17505+0+0*0*0*0+0';
p = "(?:(?:(?:[0-9]+\*)*(?<![0-9])0+(?![0-9])(?:\*[0-9]+)*)(?:\+(?:[0-9]+\*)*0+(?![0-9])(?:\*[0-9]+)*)*)";

for e in re.findall(p, s):
    print(len(e), ' < ', e)

Answer 4

▲ 0

Это c++ версия, которая работает на той же основе как моя питон версия.

zero.cpp

#include <algorithm>
#include <fstream>
#include <iostream>
#include <regex>
#include <sstream>
#include <string>

auto find_longest_zero_expr(std::string text)
{
    text.erase(0, text.find_first_not_of("*+"));
    text.erase(text.find_last_not_of("*+") + 1);

    int max_len = text.contains("0");

    std::regex re{ "[*+]{2,}" };
    std::sregex_token_iterator it{ text.begin(), text.end(), re, -1 }, end;
    for (; it != end; ++it)
    {
        if (auto expr = it->str(); expr.size() > max_len)
        {
            int new_len = 0;

            std::stringstream ss{ expr };
            for (std::string prod; std::getline(ss, prod, '+');)
            {
                if (('*'+prod+'*').find("*0*") == prod.npos)
                {
                    max_len = std::max(max_len, new_len);

                    if (auto pos = prod.find("0*"); pos != prod.npos)
                        new_len = prod.size() - pos; // take "0*..." sub-seq from non-zero product
                    else new_len = prod.ends_with('0'); // take trailing '0' from non-zero product
                }
                else new_len += prod.size() + !!new_len; // !!new_len for the '+' sign
            }
        
            max_len = std::max(max_len, new_len);
        }
    }
        
    return max_len;
}

int main()
{
    std::string text;
    std::getline(std::ifstream{"./9rWpROaef.txt"}, text, '\0');
    std::cout << find_longest_zero_expr(text) << std::endl;
    return 0;
}

Компилируется с:

g++ -O3 -std=c++23 zero.cpp -o zero

Answer 5

▲ -1

tio.run

import re

print(
  max((len(m.group()) for m in re.finditer(
    r'0[+0]*(?<!\+)',
    re.sub(
      r'[*\d]+',
      lambda m:
        '0' * len(m.group()) if re.search(r'\*0|\b0\*|^0$', m.group())
        else 'X' + m.group()[-1],
      re.sub(
        r'[+*]{2,}(?:0*(?=\d)|$)|(?<=\b0)(?:0+(?=\d)|$)',
        ' ', 
        re.sub(r'\b00*(?=\d)', '0 ', input())
      )
    )
  )), default=0)
)

На приведённом входном файле получается 169.

Найти наибольшую арифметически корректную подстроку равную нулю

Ответы

и наконец Python: