Муниципальный этап ВсОШ по информатике в Самаре 2024-2025 (9-11 классы)
Statement is not available in English language
A. Чтение в дороге
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Юный программист Кеша сегодня участвует в соревнованиях по программированию. До места соревнований он добирается на трамвае, и ехать ему предстоит достаточно долго. В дороге Кеша обычно читает разные интересные статьи.

У Кеши на смартфоне открыты $$$n$$$ статей, которые он хотел бы прочитать. Будем считать их занумерованными от $$$1$$$ до $$$n$$$. Для чтения Кеша всегда выбирает самую короткую статью из ещё не прочитанных. Если есть несколько статей, требующих одинакового времени на чтение, Кеша всегда выбирает статью с меньшим номером.

По дороге Кеша прочитал все $$$n$$$ статей. Известен порядок номеров статей $$$a_1, a_2, \ldots, a_n$$$, в котором Кеша их читал.

Кеша обратил внимание, что на чтение статьи с номером $$$a_1$$$ он потратил время $$$t_{a_1} = 1$$$. Кроме того, он заметил, что для каждой пары статей с номерами $$$a_j$$$ и $$$a_{j+1}$$$ верно одно из двух: либо $$$t_{a_{j+1}} = t_{a_j}$$$, либо $$$t_{a_{j+1}} = t_{a_j} + 1$$$.

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

Входные данные

В первой строке содержится целое число $$$n$$$ $$$(1 \le n \le 10^5)$$$ — количество статей, прочитанных Кешей.

В каждой из следующих $$$n$$$ строк содержится по одному целому числу $$$a_j$$$ $$$(1 \le a_j \le n, j = 1, 2, \ldots, n)$$$ — номеру очередной статьи, которую читал Кеша.

Гарантируется, что для любых $$$i$$$ и $$$j$$$ верно, что если $$$i \not= j$$$, то и $$$a_i \not= a_j$$$.

Выходные данные

Выведите два целых числа —минимально возможное время, которое Кеша мог потратить на чтение всех статей, и максимально возможное время, которое Кеша мог потратить на чтение всех статей. Разделяйте числа пробелом или переводом строки.

Обратите внимание, что ответ может превышать возможное значение $$$32$$$-битной целочисленной переменной, поэтому необходимо использовать $$$64$$$-битные целочисленные типы данных (тип $$$int64$$$ в языке $$$Pascal$$$, тип $$$long \, long$$$ в $$$C++$$$, тип $$$long$$$ в $$$Java$$$ и $$$C\#$$$).

Система оценки

В во всех трех подзадачах применяется потестовая система оценки. В графе «Баллы» указано количество баллов за тест и в скобках максимальное количество баллов, которое можно набрать за подзадачу. Участнику сообщаются номера тестов подзадачи, которые не были пройдены.

Для второй подзадачи требуется, чтобы программа верно решала первую подзадачу, для третьей подзадачи требуется, чтобы программа верно решала первую и вторую подзадачи. Более подробно разбиение на подзадачи показано в таблице ниже.

Тесты из условия не оцениваются.

ПодзадачаБаллы за тестОграниченияНеобходимыеИнформация
(баллыподзадачио проверке
за подзадачу)
11 (до 10)$$$n \le 10$$$нетполная
25 (до 50)$$$n \le 1000$$$1полная
35 (до 40)$$$n \le 10^5$$$1, 2полная

Пример
Входные данные
4
2
3
1
4
Выходные данные
6
10
Примечание

Поясним приведённый пример.

  • Самой первой Кеша прочёл статью $$$a_1 = 2$$$. Это означает, что
    • $$$t_2 = 1$$$;
    • $$$t_1 \gt t_2$$$ (иначе бы он первой прочитал статью $$$1$$$, а не $$$2$$$);
    • $$$t_3 \ge t_2$$$ (при равенстве Кеша всё равно сначала прочитает статью $$$2$$$);
    • $$$t_4 \ge t_2$$$.
  • Далее Кеша прочёл статью $$$a_2 = 3$$$:
    • $$$t_3 = t_2$$$ либо $$$t_3 = t_2 + 1$$$;
    • $$$t_1 \gt t_3$$$ (иначе бы он выбрал статью $$$1$$$ до $$$3$$$);
    • $$$t_4 \ge t_3$$$ (при равенстве Кеша всё равно выберет $$$3$$$).
  • После этого Кеша прочёл статью $$$a_3 = 1$$$:
    • $$$t_1 = t_3 + 1$$$ ($$$t_1 \gt t_3$$$ исходя из предыдущего пункта);
    • $$$t_4 \ge t_1$$$ (при равенстве Кеша всё равно выберет $$$1$$$).
  • Последней Кеша прочёл статью $$$a_4 = 4$$$:
    • $$$t_4 = t_1$$$ либо $$$t_4 = t_1 + 1$$$;

Минимальное время прочтения всех статей достигается при $$$t_2 = t_3 = 1$$$ и $$$t_1 = t_4 = 2$$$ — суммарно $$$2 + 1 + 1 + 2 = 6$$$.

Максимальное время прочтения всех статей достигается при $$$t_2 = 1$$$, $$$t_3 = 2$$$, $$$t_1 = 3$$$ и $$$t_4 = 4$$$— суммарно $$$3 + 1 + 2 + 4 = 10$$$.

Statement is not available in English language
B. Штрафные очки
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Кеша участвует в соревнованиях по программированию. По правилам соревнований участники упорядочиваются по количеству решённых задач, а при равенстве — по количеству штрафных баллов.

Один штрафной балл начисляется за одну неудачную попытку по задаче, которая в итоге была решена участником. Например, если участник сделал три неудачных попытки решить задачу, а в четвёртый раз решил задачу правильно, за эту задачу будет начислено три штрафных балла.

Если участник не смог решить задачу, штрафные баллы за неё не начисляются.

Кеша мог делать попытки решения задач в любом порядке. Он мог сделать неудачную попытку по некоторой задаче, затем сделать попытки по другим задачам (возможно, успешные) и вновь вернуться к той, которую не решил.

К моменту окончания соревнования Кеша решил $$$k$$$ задач. Известно, что:

  • если Кеша решил некоторую задачу, он больше не делал по ней ни одной попытки;
  • если Кеша решил задачу с номером $$$X$$$, то он решил все задачи с номерами, меньшими $$$X$$$, по которым он сделал хотя бы одну попытку.

Вам дан список номеров задач в той последовательности, в которой Кеша делал попытки их решить.

Ваша задача — посчитать количество штрафных баллов, которые будут начислены Кеше.

Входные данные

В первой строке содержится целое число $$$k$$$ $$$(1 \le k \le 10^5)$$$ — количество задач, решённых Кешей.

Во второй строке содержится целое число $$$m$$$ $$$(k \le m \le 3 \cdot 10^5)$$$ — количество попыток, сделанных Кешей.

В каждой из следующих $$$m$$$ строк содержится по одному целому числу $$$p_i$$$ $$$(1 \le p_i \le 10^6, \, i = 1, 2, \ldots, m)$$$, номера задач в той последовательности, в которой Кеша делал по ним попытки.

Выходные данные

Выведите единственное целое число — количество штрафных баллов, которые будут начислены Кеше.

Система оценки

В первой, второй и третьей подзадачах применяется потестовая система оценки. В графе «Баллы» указано количество баллов за тест и в скобках максимальное количество баллов, которое можно набрать за подзадачу. Участнику сообщаются номера тестов подзадачи, которые не были пройдены.

Для решения второй подзадачи требуется, чтобы программа верно решала первую позадачу.

В четвёртой подзадаче баллы начисляются только в случае прохождения всех тестов этой подзадачи. Участнику сообщается либо номер первого непройденного теста и результат проверки на этом тесте, либо что все тесты подзадачи пройдены.

Также для четвёртой подзадачи требуется, чтобы программа верно решала предшествующие подзадачи.

Более подробно разбиение на подзадачи показано в таблице ниже.

ПодзадачаБаллы за тестОграниченияНеобходимыеИнформация
(баллыподзадачио проверке
за подзадачу)
12 (до 10)$$$m, \, p \le 10$$$нетполная
22 (до 30)$$$m, \, p \le 1000$$$1полная
32 (до 10)$$$k = 1$$$нетполная
40 (50)любые допустимые значения1, 2, 3первая ошибка

Пример
Входные данные
3
10
5
2
2
8
5
2
7
5
8
2
Выходные данные
5
Примечание

В приведенном примере Кеша сделал $$$10$$$ попыток и решил $$$3$$$ задачи.

Он пытался решать задачи с номерами $$$5$$$, $$$2$$$, $$$8$$$ и $$$7$$$ и справился со всеми, кроме задачи $$$8$$$.

Если предположить, что Кеша решил задачу $$$8$$$, то он должен был решить и задачу $$$5$$$, и задачу $$$2$$$, и задачу $$$7$$$, поскольку они имеют меньшие номера. Но в этом случае он решил бы $$$4$$$ задачи, что неверно.

Посчитаем штрафные баллы. Изначально их у Кеши $$$s = 0$$$.

Первая попытка по задаче $$$5$$$ была неудачной. Однако эту задачу Кеша в итоге решил, поэтому за нее начисляется штрафной балл, $$$s = 1$$$.

Первая попытка по задаче $$$2$$$ также была неудачной, но и эту задачу Кеша решил, поэтому за нее также будет начислен штрафной балл, $$$s = 2$$$.

Вторая попытка по задаче $$$2$$$ не привела к успеху, $$$s = 3$$$.

Первая попытка по задаче $$$8$$$ была неудачной, но, поскольку Кеша так и не решил эту задачу, количество штрафных баллов останется без изменений: $$$s = 3$$$.

Далее следует вторая неудачная попытка по задаче $$$5$$$, и $$$s = 4$$$.

Ещё одна (третья) неудачная попытка по задаче $$$2$$$ приведёт к начислению ещё одного штрафного балла, $$$s = 5$$$.

Затем Кеша с первой попытки решает задачу $$$7$$$, штрафные баллы за неё не начисляются.

После этого Кеша, наконец, справляется с задачей $$$5$$$ — и за удачную попытку штрафные баллы не начисляются.

Вторая попытка по задаче $$$8$$$ не приводит к успеху, однако и не увеличивает количество штрафных баллов.

Наконец, Кеша предпринимает четвёртую попытку сдать задачу $$$2$$$, и ему сопутствует успех. Количество штрафных баллов остается прежним.

Таким образом, Кеше будет начислено $$$5$$$ штрафных баллов.

Statement is not available in English language
C. Музыкальный выбор
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Юный программист Кеша принял участие в соревнованиях по программированию и вместе со своими друзьями — Лизой, Мишей и Настей — ожидает объявления итогов.

Организаторы приготовили разные шуточные призы для лучших участников и решили выложить их на столе и позволить каждому из участников выбрать приз самостоятельно. Первым будет выбирать приз тот, кто занял первое место, вторым — тот, кто занял второе место и так далее.

Кеша и его друзья увидели среди призов четыре музыкальных инструмента: барабан, бубен, вувузелу и губную гармошку. Оказалось, что у каждого из ребят есть предпочитаемый музыкальный инструмент, который они хотели бы получить в качестве приза. Впрочем, если к моменту, когда подойдет их очередь выбирать приз, именно этого инструмента уже не будет, у каждого из них есть второй предпочитаемый музыкальный инструмент. Если же и второй предпочитаемый инструмент будет отсутствовать, они выберут какой-то другой приз.

Вам известны первый и второй предпочитаемые инструменты для каждого из ребят. Ваша задача — определить, в какой последовательности они должны занять места, чтобы каждый смог взять себе какой-либо из желаемых музыкальных инструментов. Можете считать, что все остальные участники не выберут себе в качестве приза музыкальные инструменты.

Входные данные

Ради упрощения обозначим музыкальные инструменты заглавными латинскими буквами:

  • $$$A$$$ — барабан,
  • $$$B$$$ — бубен,
  • $$$C$$$ — вувузела,
  • $$$D$$$ — губная гармошка.

В первой строке содержится целое число $$$t$$$ $$$(1 \le t \le 5000)$$$ — количество тестов.

Далее следует $$$t$$$ групп по 4 строки.

В первой строке группы содержатся два символа без пробела, обозначающие первый и второй предпочитаемые инструменты Кеши.

Во второй строке группы содержатся два символа без пробела, обозначающие первый и второй предпочитаемые инструменты Лизы.

В третьей строке группы содержатся два символа без пробела, обозначающие первый и второй предпочитаемые инструменты Миши.

В четвертой строке группы содержатся два символа без пробела, обозначающие первый и второй предпочитаемые инструменты Насти.

Гарантируется, что для каждого из ребят первый и второй предпочитаемые инструменты не совпадают.

Выходные данные

Выведите $$$t$$$ строк из четырех символов $$$K$$$ (Кеша), $$$L$$$ (Лиза), $$$M$$$ (Миша), $$$N$$$ (Настя) без пробелов, показывающую последовательность, в которой ребята должны занять места, чтобы каждый имел возможность выбрать один из предпочитаемых музыкальных инструментов.

Если такой последовательности не существует, выведите строку $$$UUUU$$$.

Если для какого-либо теста существует более одного правильного ответа, выводите любой из них.

Система оценки

В первой и второй подзадачах применяется потестовая система оценки. В графе «Баллы» указано количество баллов за тест и в скобках максимальное количество баллов, которое можно набрать за подзадачу. Участнику сообщаются номера тестов подзадачи, которые не были пройдены.

В третьей подзадаче баллы начисляются только в случае прохождения всех тестов этой подзадачи. Участнику сообщается либо номер первого непройденного теста и результат проверки на этом тесте, либо что все тесты подзадачи пройдены.

Для второй и третьей подзадач требуется, чтобы программа верно решала предшествующие подзадачи. Более подробно разбиение на подзадачи показано в таблице ниже.

ПодзадачаБаллы за тестОграниченияНеобходимыеИнформация
(баллыподзадачио проверке
за подзадачу)
12 (до 10)$$$t = 1$$$нетполная
23 (до 30)$$$2 \le t \le 10$$$1полная
30 (60)любые допустимые значения t1,2первая ошибка

Пример
Входные данные
4
BC
BA
CD
AB
AB
BA
AB
CD
AB
BA
AD
AD
CD
AC
BA
AB
Выходные данные
NLKM
UUUU
UUUU
NMLK
Примечание

Поясним приведённый пример.

В нём содержится $$$4$$$ теста.

Первый тест

Ребята хотят получить следующие инструменты:

  • Кеша хочет получить $$$B$$$, в случае отсутствия $$$B$$$ хочет получить $$$C$$$;
  • Лиза хочет получить $$$B$$$, в случае отсутствия $$$B$$$ хочет получить $$$A$$$;
  • Миша хочет получить $$$C$$$, в случае отсутствия $$$C$$$ хочет получить $$$D$$$;
  • Настя хочет получить $$$A$$$, в случае отсутствия $$$A$$$ хочет получить $$$B$$$.

Если ребята займут места в порядке NLKM, то

  • Настя выберет $$$A$$$;
  • Лиза выберет $$$B$$$;
  • Кеша не сможет выбрать $$$B$$$, поэтому выберет $$$C$$$;
  • Миша не сможет выбрать $$$C$$$, поэтому выберет $$$D$$$.

Обратите внимание, что ответы LNKM, LKNM и LKMN также являются корректными.

Второй тест

Ребята хотят получить следующие инструменты:

  • Кеша хочет получить $$$A$$$, в случае отсутствия $$$A$$$ хочет получить $$$B$$$;
  • Лиза хочет получить $$$B$$$, в случае отсутствия $$$B$$$ хочет получить $$$A$$$;
  • Миша хочет получить $$$A$$$, в случае отсутствия $$$A$$$ хочет получить $$$B$$$;
  • Настя хочет получить $$$C$$$, в случае отсутствия $$$C$$$ хочет получить $$$D$$$.

Как можно видеть, Кеша, Лиза и Миша хотят получить только инструменты $$$A$$$ или $$$B$$$. Очевидно, что при любом раскладе один из них не получит желаемый инструмент.

Третий тест

Ребята хотят получить следующие инструменты:

  • Кеша хочет получить $$$A$$$, в случае отсутствия $$$A$$$ хочет получить $$$B$$$;
  • Лиза хочет получить $$$B$$$, в случае отсутствия $$$B$$$ хочет получить $$$A$$$;
  • Миша хочет получить $$$A$$$, в случае отсутствия $$$A$$$ хочет получить $$$D$$$;
  • Настя хочет получить $$$A$$$, в случае отсутствия $$$A$$$ хочет получить $$$D$$$.

Как можно видеть, на четверых участников приходится $$$3$$$ желаемых инструмента (никто не хочет $$$C$$$). Очевидно, что при любом раскладе один из них не получит желаемый инструмент.

Четвёртый тест

Ребята хотят получить следующие инструменты:

  • Кеша хочет получить $$$C$$$, в случае отсутствия $$$C$$$ хочет получить $$$D$$$;
  • Лиза хочет получить $$$A$$$, в случае отсутствия $$$A$$$ хочет получить$$$C$$$;
  • Миша хочет получить $$$B$$$, в случае отсутствия $$$B$$$ хочет получить $$$A$$$;
  • Настя хочет получить $$$A$$$, в случае отсутствия $$$A$$$ хочет получить $$$B$$$.

Если ребята займут места в порядке NMLK, то

  • Настя выберет $$$A$$$;
  • Миша выберет $$$B$$$;
  • Лиза не сможет выбрать $$$A$$$, поэтому выберет $$$C$$$;
  • Кеша не сможет выбрать $$$C$$$, поэтому выберет $$$D$$$.

Обратите внимание, что ответы MNLK, NLMK и NLKM также являются корректными.

Statement is not available in English language
D. Диапазоны
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Кеша участвует в соревнованиях по программированию. Его друг Прохор не особенно интересуется алгоритмическим программированием, поэтому просто наблюдает за соревнованиями со стороны: просматривает приходящие уведомления и таблицу результатов.

По правилам соревнований участники упорядочиваются по количеству решенных задач; участник, решивший наибольшее количество задач, занимает первое место и т.д. При равном количестве решенных задач используются дополнительные критерии, но Прохор не хочет в них разбираться. Ему достаточно знать диапазон мест, занятых участниками с таким же количеством задач, которое в данный момент решил Кеша.

Каждый раз, когда какой-либо участник решает какую-либо задачу, приходит уведомление об этом. Для упрощения будем считать, что уведомление содержит только номер участника. Кеша получил номер участника $$$1$$$.

В некоторые моменты Прохор интересуется, в каком диапазоне мест находится сейчас Кеша. Это значит, что он хочет узнать два числа:

  • наиболее высокое место (минимальное значение), которое занимает участник, решивший столько же задач, сколько и Кеша;
  • наименее высокое место (максимальное значение), которое занимает участник, решивший столько же задач, сколько и Кеша.

Ваша задача — получить ответы на вопросы Прохора.

Входные данные

В первой строке содержится целое число $$$n$$$ $$$(2 \le n \le 3 \cdot 10^5)$$$ — суммарное количество уведомлений и запросов Прохора.

Во второй строке содержится $$$n$$$ целых чисел $$$q_j$$$ $$$(0 \le q_j \le 10^6, \, j = 1, 2, \ldots, n)$$$ через пробел:

  • Если $$$q_j \gt 0$$$ — это номер участника, сдавшего очередную задачу. Напомним, что у Кеши номер $$$1$$$.
  • Если же $$$q_j = 0$$$, то это запрос Прохора: нужно вывести наиболее высокое и наименее высокое места участников, решивших столько же задач, сколько и Кеша.

Гарантируется, что:

  • во входных данных имеется по крайней мере одно уведомление и по крайней мере один запрос.
  • Прохор впервые заинтересуется диапазоном не ранее, чем Кеша решит хотя бы одну задачу.
Выходные данные

Для каждого $$$q_j = 0$$$ выведите два целых числа — наиболее высокое и наименее высокое места участников, решивших в этот момент столько же задач, сколько и Кеша.

Разделяйте числа пробелом или переводом строки.

Система оценки

В первой и второй подзадачах применяется потестовая система оценки. В графе «Баллы» указано количество баллов за тест и в скобках максимальное количество баллов, которое можно набрать за подзадачу. Участнику сообщаются номера тестов подзадачи, которые не были пройдены.

Для решения второй подзадачи требуется, чтобы программа верно решала первую подзадачу.

В третьей подзадаче баллы начисляются только в случае прохождения всех тестов этой подзадачи. Участнику сообщается либо номер первого непройденного теста и результат проверки на этом тесте, либо что все тесты подзадачи пройдены.

Также для третьей подзадачи требуется, чтобы программа верно решала предшествующие подзадачи.

Более подробно разбиение на подзадачи показано в таблице ниже.

ПодзадачаБаллы за тестОграниченияНеобходимыеИнформация
(баллыподзадачио проверке
за подзадачу)
12 (до 10)$$$\max\limits_{j=1}^{n}{q_j} \le 10, \, n \le 100$$$нетполная
22 (до 30)$$$\max\limits_{j=1}^{n}{q_j}, \, n \le 1000$$$1полная
30 (60)любые допустимые значения1, 2первая ошибка

Пример
Входные данные
25
2 7 1 2 0 3 7 1 0 2 2 0 5 7 0 5 0 3 1
0 1 0 2 7 0
Выходные данные
2 3
1 3
2 3
3 3
3 4
2 3
1 2
2 3
Примечание

Поясним приведённый пример.

  • К первому запросу Прохора:
    • участник $$$2$$$ занимает место $$$1$$$ с двумя решенными задачами;
    • участники $$$7$$$ и $$$1$$$ (Кеша) занимают места со $$$2$$$ по $$$3$$$ с одной решенной задачей.
  • Ко второму запросу Прохора:
    • участники $$$2$$$, $$$7$$$ и $$$1$$$ (Кеша) занимают места с $$$1$$$ по $$$3$$$ с двумя решенными задачами;
    • участник $$$3$$$ — место $$$4$$$ с одной задачей.
  • К третьему запросу Прохора:
    • участник $$$2$$$ занимает место $$$1$$$ с четырьмя решенными задачами;
    • участники $$$7$$$ и $$$1$$$ (Кеша) занимают места со $$$2$$$ по $$$3$$$ с двумя решенными задачами;
    • участник $$$3$$$ — место $$$4$$$ с одной задачей.
  • К четвертому запросу Прохора:
    • участник $$$2$$$ занимает место $$$1$$$ с четырьмя решенными задачами;
    • участник $$$7$$$ занимает место $$$2$$$ с тремя решенными задачами;
    • участник $$$1$$$ (Кеша) занимает место $$$3$$$ с двумя решенными задачами;
    • участники $$$3$$$ и $$$5$$$ — места с $$$4$$$ по $$$5$$$ с одной задачей.
  • К пятому запросу Прохора:
    • участник $$$2$$$ занимает место $$$1$$$ с четырьмя решенными задачами;
    • участник $$$7$$$ занимает место $$$2$$$ с тремя решенными задачами;
    • участники $$$1$$$ (Кеша) и $$$5$$$ занимают места с $$$3$$$ по $$$4$$$ с двумя решенными задачами;
    • участник $$$3$$$ — место $$$5$$$ с одной задачей.
  • К шестому запросу Прохора:
    • участник $$$2$$$ занимает место $$$1$$$ с четырьмя решенными задачами;
    • участники $$$7$$$ и $$$1$$$ (Кеша) занимают места со $$$2$$$ по $$$3$$$ с тремя решенными задачами;
    • участники $$$5$$$ и $$$3$$$ занимают места с $$$4$$$ по $$$5$$$ с двумя решенными задачами.
  • К седьмому запросу Прохора:
    • участники $$$2$$$ и $$$1$$$ (Кеша) занимают места с $$$1$$$ по $$$2$$$ с четырьмя решенными задачами;
    • участник $$$7$$$ занимает место $$$3$$$ с тремя решенными задачами;
    • участники $$$5$$$ и $$$3$$$ занимают места с $$$4$$$ по $$$5$$$ с двумя решенными задачами.
  • К восьмому запросу Прохора:
    • участник $$$2$$$ занимает место $$$1$$$ с пятью решенными задачами;
    • участники $$$7$$$ и $$$1$$$ (Кеша) занимают места со $$$2$$$ по $$$3$$$ с четырьмя решенными задачами;
    • участники $$$5$$$ и $$$3$$$ занимают места с $$$4$$$ по $$$5$$$ с двумя решенными задачами.

Statement is not available in English language
E. B + C
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Очень часто на пробном туре соревнований участникам предлагается задача $$$A + B$$$. Организаторы соревнований, в которых участвует Кеша, так и поступили. А на основном туре предложили другую задачу, $$$B + C$$$.

Кеше нравятся короткие условия, поэтому он сразу же взялся решать эту задачу.

На доске записали равенство $$$A = B + C$$$, где $$$A$$$, $$$B$$$ и $$$C$$$ — целые положительные числа без ведущих нулей.

Затем некоторые цифры в равенстве стёрли.

Ваша задача (и Кеши, конечно, тоже) — определить, сколькими способами можно восстановить стёртые цифры, чтобы равенство осталось верным.

Входные данные

В первой строке записано число $$$A$$$ $$$(1 \le |A| \le 100)$$$ — последовательность десятичных цифр и символов # без пробелов.

Во второй строке записано число $$$B$$$ $$$(1 \le |B| \le 100)$$$ — последовательность десятичных цифр и символов # без пробелов.

В третьей строке записано число $$$C$$$ $$$(1 \le |C| \le 100)$$$ — последовательность десятичных цифр и символов # без пробелов.

Символы # заменяют стёртые цифры.

Гарантируется, что $$$A$$$, $$$B$$$, $$$C$$$:

  • содержат только символы 0-9 и #;
  • не начинаются с (ведущего) нуля.
Выходные данные

Обозначим через $$$m$$$ количество способов заменить знаки # на десятичные цифры 0-9 согласно условию задачи. Поскольку число $$$m$$$ может быть очень большим, выведите остаток от деления $$$m$$$ на $$$10^9 + 7$$$.

Способ считается верным, если при замене цифр:

  • выполняется равенство $$$A = B + C$$$;
  • числа $$$A$$$, $$$B$$$, $$$C$$$ —положительные;
  • числа $$$A$$$, $$$B$$$, $$$C$$$ не начинаются с ведущего нуля.
Система оценки

Во всех подзадачах баллы начисляются только в случае прохождения всех тестов этой подзадачи и необходимых подзадач.

Более подробно разбиение на подзадачи показано в таблице ниже.

ПодзадачаБаллы за тестОграниченияНеобходимыеИнформация
(баллыподзадачио проверке
за подзадачу)
10 (10)$$$|A|, |B|, |C| \le 3$$$нетпервая ошибка
20 (10)$$$|A|, |B|, |C| \le 5$$$, $$$A$$$ не содержит #нетпервая ошибка
30 (10)$$$|A|, |B| \le 5$$$, $$$|C| \le 2$$$нетпервая ошибка
40 (10)$$$|A|, |B|, |C| \le 5$$$1, 2, 3первая ошибка
50 (15)$$$A$$$ не содержит #, $$$|C| \le 2$$$нетпервая ошибка
60 (15)$$$A$$$ не содержит #2, 5первая ошибка
70 (15)$$$|C| \le 2$$$3, 5первая ошибка
80 (15)любые допустимые значения4, 6, 7первая ошибка

Примеры
Входные данные
12#
#4
57
Выходные данные
1
Входные данные
968
#0#
8#
Выходные данные
0
Входные данные
9
#
#
Выходные данные
8
Примечание

Поясним приведённые примеры.

Первый пример Единственный возможный способ восстановить значения:

  • $$$A = 121$$$;
  • $$$B = 64$$$;
  • $$$C = 57$$$.

Второй пример

Невозможно восстановить ни одним способом.

Как легко заметить, в числе $$$B$$$ десятков $$$0$$$, в $$$C$$$ десятков $$$8$$$, а в числе $$$A$$$ десятков $$$6$$$.

Третий пример

Подойдут следующие способы:

  • $$$1 + 8$$$;
  • $$$2 + 7$$$;
  • ...
  • $$$8 + 1$$$.