Sirion
|
|
� : Октябрь 23, 2015, 14:21:47 � |
|
Я знаю, как решать эту задачу, но не знаю, как решать её быстро. Все алгоритмы, до которых я могу додуматься, имеют сложность по времени не ниже экспоненты.
Группа ковбоев решила устроить перестрелку в стиле "останется только один". У каждого ковбоя есть параметр точности - вероятность того, что сделанный им выстрел окажется результативным. Все ковбои стреляют по очереди, если очередь заканчивается, а в живых остались больше одного ковбоя - начинают дальше по кругу. Каждый ковбой стреляет в того из оставшихся в живых соперников, у кого больше точность. Если таких несколько - в того, чья очередь стрельбы раньше.
Входные данные: массив, содержащий точности стрельбы ковбоев. Очередь стрельбы задаётся порядком индексов массива. Что хотелось бы иметь на выходе: массив той же длины, содержащий вероятности победы для каждого ковбоя.
Примеры.
Вход: [1, 1]. Выход: [1, 0]. Вход: [1, 1, 1]. Выход: [0, 0, 1]. Вход: [1, 0.5, 0.5]. Выход: [0.5, 0, 0.5].
З.Ы. Вероятностные алгоритмы не канают.
|