По пятницам мы часто играем в популярную ролевую игру "Релиз до выходных" с коллегами. Правила этой игры довольно сложны и предполагают хорошую стратегию и планирование. Чтобы иметь представление о последствиях тех или иных ходов, часто хочется понимать, насколько вероятен тот или иной исход ситуации, с учетом разных вариантов выпадения игральных костей.

Необходимо написать программу, которая сможет, приняв на вход последовательность операндов и операций, вывести все возможные варианты результата и их вероятности.

Выражение на входе может содержать скобки, и следующие операторы в порядке уменьшения их приоритета:

• * – умножение
• + и - – сложение и вычитание
• > - левый операнд больше, чем правый. Результат равен 1, если истинно, и 0 - если ложно

Операторы равного приоритета выполняются слева направо.


В качестве операндов могут выступать:

• n - целые положительные числа, либо 0 (0≤n≤100 000)
• dn - результат броска игральной кости, где n целое положительное число, количество граней (1≤n≤100). Результатом будет равномерное распределение вероятностей между всеми гранями (от 1 до n). Каждый такой операнд в выражении – это результат отдельного броска (например, d4+d4 – это сумма результатов двух разных бросков четырехгранной кости).

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


Выходные данные (ожидаются в стандартном потоке вывода) Одна или несколько строк, в каждой из которых есть два числа, разделенных пробелом:

• 1. целое – один из вариантов результата
• 2. вещественное - процент вероятности такого варианта с математическим округлением до 2 знаков и разделителем .

Строки на выходе должны быть отсортированы от меньшего результата к большему.

Примечание к округлению - в связи с округлением вероятностей - суммарная вероятность всех исходов может быть не равна 100%, это нормально, компенсировать это в решении не нужно.


Пример 1 Ввод:

2+2 Вывод:

4 100.00
Пример 2 Ввод:

d4+2 Вывод:

3 25.00
4 25.00
5 25.00
6 25.00

Пример 3 Ввод:

d4+(d6>2) Вывод:

1 8.33
2 25.00
3 25.00
4 25.00
5 16.67

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

При отправке решений на Java необходимо назвать исполняемый класс Main. В решении не нужно указывать пакет.


Примеры работы со стандартными потоками ввода и вывода Для JS можно использовать readline и console.log:

const readline = require('readline').createInterface(process.stdin, process.stdout);
readline.on('line', (line) => {
// Введенная строка в переменной line, тут можно написать решение и вывести его с помощью console.log
...
console.log(String(result));
readline.close();
}).on('close', () => process.exit(0));

в Python можно использовать встроенные функции input() и print():

line = input()
...
print(result)

в Java можно использовать java.util.Scanner и System.out.println:

Scanner in = new Scanner(System.in);
String line = in.nextLine();
...
System.out.println(result);

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