Решение задачи Dreamoon и WiFi с Codeforces

Без пояснения   Просмотров: 310

Dreamoon стоит на отметке 0 на числовой прямой. Drazil отправляет ему на смартфон список команд через Wi-Fi, а Dreamoon следует им.

Каждая команда относится к одному из двух типов:

Пройти на 1 единицу в положительном направлении, обозначается как «+»
Пройти на 1 единицу в отрицательном направлении, обозначается как «-»
Но так как уровень сигнала Wi-Fi очень слабый, смартфон Dreamoon'а сообщает, что некоторые команды не поддаются распознаванию. Более того, Dreamoon знает, что даже некоторые из рапознанных команд могут быть неверными. Dreamoon решил выполнять каждую распознанную команду, а для нераспознанных команд бросать монетку (это значит, что он пойдёт на 1 единицу в положительном или отрицательном направлении с одинаковой вероятностью 0.5).

Вам дан изначальный список команд, которые выслал Drazil, и список, который получил Dreamoon. Какова вероятность того, что Dreamoon окажется в том положении, к которому привели бы команды Drazil'а?

Код 

#include <bits/stdc++.h>
using namespace std;
 
int f(int n,int h) {
	if(n)
		return f(n - 1, h + 1) + f(n - 1,h - 1);
	else if(h == 0) 
        return 1;
	else 
        return 0;
}
int main() {
	string a,b;
	cin >> a >> b;
	int i,c,d,e;
	c = d = e = 0;
	for(i = 0; i < a.length(); i++) {
		if(a[i] == '+') c++;
		if(a[i] == '-') c--;
		if(b[i] == '+') d++;
		if(b[i] == '-') d--;
		if(b[i] == '?') e++;
	}
	printf("%0.9f\n",(double)f(e,c-d)/pow(2,e));
}

         

Администратор Photo Автор: Администратор




Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться


© 2020 HSECODES [email protected] Карта сайта