Вывести все возможные варианты результата и их вероятности

@duck_nukem · Регистрация: 23.08.2021

Студворк — интернет-сервис помощи студентам

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

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

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

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

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

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

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

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

1. целое – один из вариантов результата
2. вещественное - процент вероятности такого варианта с математическим округлением до 2 знаков и разделителем .
Строки на выходе должны быть отсортированы от меньшего результата к большему.

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

@FedorPup · 02.09.2021, 14:24

Сообщение от eaa

FedorPup, введите: 'd4+d4'

2 6.25
3 12.50
4 18.75
5 25.00
6 18.75
7 12.50
8 6.25

Ответ программы. Пересчитал вручную на листике - вроде все ок

@eaa · 02.09.2021, 14:26

FedorPup, серьезно? как 3, 5 и 7 получить?

@FedorPup · 02.09.2021, 14:31

Сообщение от eaa

FedorPup, серьезно? как 3, 5 и 7 получить?

Я думаю что у нас разные кубики d4. На одном выпадает 1 на другом 2 - в сумме ответ 3. Если авторы задачи подразумевали что только один бросок - определяет сразу все вероятности этого кубика - ну тогда я просто потратил пару дней зря

@eaa · 02.09.2021, 14:37

Сообщение от duck_nukem

dn - результат броска игральной кости

одной игральной кости.

@FedorPup · 02.09.2021, 14:39

eaa, Спасибо за наводку! Вы очень помогли! Перепишу программу как вы указали.

@eaa · 02.09.2021, 14:42

FedorPup, посмотрите мое решение выше, оно правильное, только переборное и ответ в конце нужно отсортировать.

@Goover · 02.09.2021, 15:50

Каждый операнд – результат отдельного броска, так что d4+d4 должен вернуть 7 вариантов, как правильно и заметил FedorPup.

Добавили эту информацию в условие.

@FedorPup · 02.09.2021, 15:53

Сообщение от Goover

Добавили эту информацию в условие.

Вот это скорость реагирования. Я даже помог дополнить условие задачи. Ну надо же.

@eaa · 02.09.2021, 16:14

полное условие задачи напишите

@FedorPup · 02.09.2021, 16:23

Сообщение от eaa

полное условие задачи напишите

Автор темы полностью написал.

@Einsamkeit · 02.09.2021, 16:45

Такая же беда, пишет неправильный ответ.

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
def search_d(string):
    """возвращает кол-во граней кубика"""
    edge_count = ""
    for char in string[string.index("d") + 1:]:
        if char.isdigit():
            edge_count += char
        else:
            return edge_count
    return edge_count
 
 
def execute(string):
    """заменяет кубики всеми вероятностями броска и
    заполняет словарь вычислениями результата"""
    if "d" in string:
        edge_count = search_d(string)
        for number in range(1, int(edge_count) + 1):
            execute(string.replace(f"d{edge_count}", str(number), 1))
    else:
        temp = int(eval(string))
        dct[temp] = dct.get(temp, 0) + 1
 
 
dct = {}
execute(input())
summ = sum(dct.values())
for i in sorted(dct):
    print(f"{i} {round(dct[i] / summ * 100, 2):.2f}")

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

@FedorPup · 02.09.2021, 16:51

Einsamkeit,

Попробуйте дождаться решения 'd4+(d6>2)+d4+(d6>2)+d4+(d6>2)+d4+(d6>2) +d4+(d6>2)+d4+(d6>2)+d4+(d6>2)+d4+(d6>2) +d4+(d6>2)+d4+(d6>2)' - и это строка меньше 110 символов. Скорее всего (но не точно!) - дело в этом. В условии задачи - время выполнения менее 1 сек.

@Einsamkeit · 02.09.2021, 17:05

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

@FedorPup · 02.09.2021, 17:13

Сообщение от FedorPup

Einsamkeit,

Мне авторы в поддержке прямо ответили что в случае превышения лимита времени - может выдавать статус "Неправильный ответ" А требования ослабили - вроде вначале была строка 200 символов, затем стало 110. Я считаю что нужно решение не пропорциональное произведению всех вероятностей. А использовать что то вроде "Сортировочной станции". Хотя опять же я не программист и не берусь утверждать что я точно прав. Но подумайте сами: функция eval() работает точно правильно, вероятности округлены правильно, вывод отсортирован правильно. Вы проверили на десятках вариантах. В чем же может быть дело?

@Einsamkeit · 02.09.2021, 17:34

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

@FedorPup · 02.09.2021, 17:43

Einsamkeit, Как вариант дополнить кубиками и '>' вот это https://habr.com/ru/post/273253/ - тоже должно выполниться за линейное время

@eaa · 02.09.2021, 17:45

странная задача:
d4-d6+d6 тут должно быть 4 варианта.
а по условию я так понял будет 13?

@FedorPup · 02.09.2021, 17:48

Сообщение от eaa

странная задача:
d4-d6+d6 тут должно быть 4 варианта.
а по условию я так понял будет 13?

14 если быть точным

-4 0.69
-3 2.08
-2 4.17
-1 6.94
0 9.72
1 12.50
2 13.89
3 13.89
4 12.50
5 9.72
6 6.94
7 4.17
8 2.08
9 0.69

@Einsamkeit · 02.09.2021, 17:49

eaa, у меня 14 вариантов выдает:
-4 0.69
-3 2.08
-2 4.17
-1 6.94
0 9.72
1 12.50
2 13.89
3 13.89
4 12.50
5 9.72
6 6.94
7 4.17
8 2.08
9 0.69

@eaa · 02.09.2021, 17:56

ну 14, я в ручную считал. ошибся)

Новые блоги и статьи Все статьи Все блоги /
Из невошедшего на форум (диалог с ИИ-гугла) zorxor 29.07.2026 А вот, что интересно, сказал мне ИИ-гугла: Этот текст — эмоциональный пост пользователя под ником zorxor на интернет-форуме (вероятно, посвященном мистике, непознанному или альтернативной науке). . . .	Был праздник вчера, а я и не знал. kumehtar 28.07.2026 27. 07. 2026г. Intel Core 2 Duo исполнилось 20 лет Новости компьютерного мира и их обсуждение (4) Салют, шампанское, овации! :drink:	Нейтральные знания, чистый код - бла-бла-бла-бла, на самом деле кликбейт и самореклама, плагиат, и вот почему Hrethgir 27.07.2026 То-есть отклонение такой публикации говорит само за себя, и пусть только возьмут на вооружение после отклонения публикации - это будет чистейшим актом плагиата. Отклонял Хабр. Дословно, отклонённая. . .	тв 16 бой ии anaschu 27.07.2026 Великий Перелом ИИ: Как уравнения ОДУ Radau дожали цензурные фильтры Алисы Фиксируем в мемофонде Теории Всего беспрецедентный факт в истории ИИ-зондирования. В затяжном многораундовом. . .
мв 15. непроверенное, возможно, глюк anaschu 27.07.2026 НАУЧНО-АНАЛИТИЧЕСКИЙ ОТЧЕТ. РАЗДЕЛ 1. 1: «НАУКА» (РАСШИРЕННАЯ СТЕХИОМЕТРИЧЕСКАЯ И ГЕНЕТИЧЕСКАЯ ВЕРСИЯ)Тема: Теоретическое обоснование инвариантности 19-мерного тензорного ядра непрерывных ОДУ и. . .	Очистка реквизитов и табличных частей документа при копировании (вариант 2) Maks 26.07.2026 Алгоритм из решения ниже разработан на примере нетипового документа "ЗаявкаНаРаботу", разработанного в КА2. Задача: Заменить алгоритм запрета копирования документов для сотрудников с ролью "Стажер",. . .	Доктрина интенционального знания - Доктрина для портала "Срез". Hrethgir 25.07.2026 Может найдётся кто захочет оценить доктрину. . . Написания правил участия для меня роскошь, требующая лимита времени, поэтому все сообщения не прошедшие модерацию будут видны только участникам портала,. . .	сукцессия 44. Решил подать на припринт в межународные сервисы препринтов. Но нужно одобрение от ученых anaschu 25.07.2026 Английский вариант. Пока кто то не одобрит мою личность, мне не получиться это опубликовать на препринте. Но заявку на публикацию статьи я сегодня подам.

@duck_nukem 3 / 3 / 0 Регистрация: 23.08.2021 Сообщений: 71

	Вывести все возможные варианты результата и их вероятности 23.08.2021, 18:46. Показов 29219. Ответов 65 Метки нет (Все метки) По пятницам мы часто играем в популярную ролевую игру "Релиз до выходных" с коллегами. Правила этой игры довольно сложны и предполагают хорошую стратегию и планирование. Чтобы иметь представление о последствиях тех или иных ходов, часто хочется понимать, насколько вероятен тот или иной исход ситуации, с учетом разных вариантов выпадения игральных костей. Необходимо написать программу, которая сможет, приняв на вход последовательность операндов и операций, вывести все возможные варианты результата и их вероятности. Выражение на входе может содержать скобки, и следующие операторы в порядке уменьшения их приоритета: * – умножение + и - – сложение и вычитание > - левый операнд больше, чем правый. Результат равен 1, если истинно, и 0 - если ложно В качестве операндов могут выступать: n - целые положительные числа, либо 0 (0≤n≤100 000) dn - результат броска игральной кости, где n целое положительное число, количество граней (1≤n≤100 000). Результатом будет равномерное распределение вероятностей между всеми гранями (от 1 до n). Входные данные (поступают в стандартный поток ввода) Одна строка без пробелов, содержащая выражение для вычисления. Выражение гарантировано вычисляемое и не содержит синтаксических ошибок. Максимальная длина строки 200 символов. Выходные данные (ожидаются в стандартном потоке вывода) Одна или несколько строк, в каждой из которых есть два числа, разделенных пробелом: 1. целое – один из вариантов результата 2. вещественное - процент вероятности такого варианта с математическим округлением до 2 знаков и разделителем . Строки на выходе должны быть отсортированы от меньшего результата к большему. Примечание к округлению - в связи с округлением вероятностей - суммарная вероятность всех исходов может быть не равна 100%, это нормально, компенсировать это в решении не нужно. 1

@eaa Status 418 4584 / 2350 / 601 Регистрация: 26.11.2017 Сообщений: 5,262 Записей в блоге: 3
	02.09.2021, 14:26
	FedorPup, серьезно? как 3, 5 и 7 получить? 0

@FedorPup 1 / 1 / 0 Регистрация: 02.09.2021 Сообщений: 14
	02.09.2021, 14:39
	eaa, Спасибо за наводку! Вы очень помогли! Перепишу программу как вы указали. 0

@eaa Status 418 4584 / 2350 / 601 Регистрация: 26.11.2017 Сообщений: 5,262 Записей в блоге: 3
	02.09.2021, 14:42
	FedorPup, посмотрите мое решение выше, оно правильное, только переборное и ответ в конце нужно отсортировать. 0

@Goover 0 / 0 / 0 Регистрация: 02.09.2021 Сообщений: 1
	02.09.2021, 15:50
	Каждый операнд – результат отдельного броска, так что d4+d4 должен вернуть 7 вариантов, как правильно и заметил FedorPup. Добавили эту информацию в условие. 0

@eaa Status 418 4584 / 2350 / 601 Регистрация: 26.11.2017 Сообщений: 5,262 Записей в блоге: 3
	02.09.2021, 16:14
	полное условие задачи напишите 0

@FedorPup 1 / 1 / 0 Регистрация: 02.09.2021 Сообщений: 14
	02.09.2021, 16:51
	Einsamkeit, Попробуйте дождаться решения 'd4+(d6>2)+d4+(d6>2)+d4+(d6>2)+d4+(d6>2) +d4+(d6>2)+d4+(d6>2)+d4+(d6>2)+d4+(d6>2) +d4+(d6>2)+d4+(d6>2)' - и это строка меньше 110 символов. Скорее всего (но не точно!) - дело в этом. В условии задачи - время выполнения менее 1 сек. 1

@Einsamkeit 3 / 3 / 0 Регистрация: 02.09.2021 Сообщений: 7
	02.09.2021, 17:05
	FedorPup, поначалу первые решения не проходили по лимиту времени, но затем авторы немного ослабили требования, и вместо превышения лимита времени стало писать, что ответ неверный, так что дело скорей всего не в этом. 0

@Einsamkeit 3 / 3 / 0 Регистрация: 02.09.2021 Сообщений: 7
	02.09.2021, 17:34
	FedorPup, если дело все-таки во времени, то тогда надо разбирать вариант eaa и на его основе писать решение. В его варианте предложенный вами пример вычисляется за тысячную долю секунды, пусть и не совсем правильно. 0

@FedorPup 1 / 1 / 0 Регистрация: 02.09.2021 Сообщений: 14
	02.09.2021, 17:43
	Einsamkeit, Как вариант дополнить кубиками и '>' вот это https://habr.com/ru/post/273253/ - тоже должно выполниться за линейное время 0

@eaa Status 418 4584 / 2350 / 601 Регистрация: 26.11.2017 Сообщений: 5,262 Записей в блоге: 3
	02.09.2021, 17:45
	странная задача: d4-d6+d6 тут должно быть 4 варианта. а по условию я так понял будет 13? 0

@Einsamkeit 3 / 3 / 0 Регистрация: 02.09.2021 Сообщений: 7
	02.09.2021, 17:49
	eaa, у меня 14 вариантов выдает: -4 0.69 -3 2.08 -2 4.17 -1 6.94 0 9.72 1 12.50 2 13.89 3 13.89 4 12.50 5 9.72 6 6.94 7 4.17 8 2.08 9 0.69 0

@eaa Status 418 4584 / 2350 / 601 Регистрация: 26.11.2017 Сообщений: 5,262 Записей в блоге: 3
	02.09.2021, 17:56
	ну 14, я в ручную считал. ошибся) 0