eolymp
bolt
Try our new interface for solving problems
Məsələlər

Цифровая строка

Цифровая строка

Однажды мальчик Вова, который совсем недавно научился считать и писать, решил объединить эти два умения и выписать на листке бумаги подряд все натуральные числа начиная с единицы. Петя, старший брат Вовы, обратил внимание на получившуюся бесконечную строку символов из цифр \textbf{S}: \includegraphics{https://static.e-olymp.com/content/8e/8e583556a54499e334be786465a6a6ef69074ff8.jpg} \textit{Рисунок №1. Цифровая строка}. Так как Петя увлекается программированием, он решил исследовать свойства этой строки. Подстрокой строки\textbf{S} для заданной пары целых чисел (\textbf{i}, \textbf{j}), \textbf{i} ≤ \textbf{j}, будем называть строку из цифр '\textbf{S_iS_i_\{+1\}…S_j}'. Например, паре (\textbf{1}, \textbf{3}) соответствует подстрока '\textbf{123}', а паре (\textbf{9}, \textbf{12}) подстрока '\textbf{9101}'. \includegraphics{https://static.e-olymp.com/content/4d/4d3f60423316c6c51d220fc241523b3cea1d9729.jpg} \textit{Рисунок №2. Примеры подстрок.} Шаблоном будем называть строку \textbf{T}, состоящую из цифр от \textbf{0} до \textbf{9}, символов '\textbf{?}' и '\textbf{*}'. Будем говорить, что строка \textbf{Q} удовлетворяет шаблону \textbf{T}, если строку \textbf{Q} можно получить из \textbf{T} заменой каждого символа '\textbf{?}' на одну цифру, а символы '\textbf{*}' на последовательность цифр, возможно пустую. Пете необходимо для заданного шаблона \textbf{T} найти подстроку строки \textbf{S,} удовлетворяющую заданному шаблону. Например, шаблону '\textbf{?1*1}' удовлетворяют подстроки, соответствующие парам чисел (\textbf{9}, \textbf{12}), (\textbf{9}, \textbf{13}), (\textbf{9}, \textbf{14}), (\textbf{9},\textbf{16}), (\textbf{11}, \textbf{13}), (\textbf{11}, \textbf{14}), (\textbf{11}, \textbf{16}) и т.д. Помогите Пете в решении этой непростой задачи! \includegraphics{https://static.e-olymp.com/content/cc/cc70b729036a1f96e715b7b1deac4f9c4253e969.jpg} \textit{Рисунок №3. Описание второго примера.} \InputFile Первая строка входного файла содержит одно натуральное число \textbf{N }(1 ≤ \textbf{N} ≤ \textbf{20}) -- длину строки \textbf{T}. Вторая строка входного файла содержит одну строковую величину \textbf{T}, содержащую \textbf{N} символов '\textbf{0}'-'\textbf{9}', '\textbf{?}' и '\textbf{*}'. \OutputFile Первая и единственная строка выходного файла должна содержать два целых числа \textbf{i} и \textbf{j}, разделенных одиночным пробелом, где (\textbf{i}, \textbf{j}) -- пара целых чисел, таких, что соответствующая им подстрока строки \textbf{S} удовлетворяет заданному шаблону \textbf{T}. Если существует несколько пар целых чисел (\textbf{i}, \textbf{j}), таких, что соответствующие им подстроки удовлетворяют шаблону \textbf{T}, то необходимо вывести наименьшую пару. Будем считать, что пара (\textbf{i_1}, \textbf{j_1}) меньше пары (\textbf{i_2}, \textbf{j_2}), если \textbf{i_1}<\textbf{i_\{2 \}}либо \textbf{i_1}= \textbf{i_2 }и \textbf{j_1}< \textbf{j_\{2.\}} Если не существует подстроки строки \textbf{S}, удовлетворяющей заданному шаблону \textbf{T}, то выведите '\textbf{0 0}'.
Zaman məhdudiyyəti 3 saniyə
Yaddaşı istafadə məhdudiyyəti 256 MiB
Giriş verilənləri #1
3
101
Çıxış verilənləri #1
10 12