예제 10 - 17 사탕 UVa 1639
2. 문제 풀이 방향: 문제 의 뜻 에 따라 마지막 에 첫 번 째 상 자 를 열 어도 무방 하 다. 이때 두 번 째 상 자 는 i 개의 사탕 이 있 기 때문에 그 전에 모두 n + (n - i) 의 상 자 를 열 었 다. 그 중에서 n 번 은 상자 1, n - i 번 은 상자 2 를 찾 았 고 취 법 은 모두 C (2 * n - i, n) 종이 있 기 때문에 상자 2 에 i 개의 사탕 이 남 았 을 확률 은 C (2 * n - i, n) * p ^ (n + 1) * (1 - p) ^ (n - i) 이다.마지막 으로 상 자 를 열 확률 도 계산 해 야 합 니 다.확률 이 있 으 면 기대 하 는 정의 에 따라 답 을 구하 기 어렵 지 않다.그러나 주의해 야 할 것 은 n 이 매우 클 수 있 기 때문에 대수 로 계산 하여 과도 한 정밀도 손실 을 방지 해 야 한 다 는 것 이다.프로그램의 효율 을 높이 기 위해 서 는 n 을 미리 계산 할 수 있 습 니 다!자연 대수 의 값 을 취하 면 후속 계산 에 편리 하 다.또한 p 의 경 계 는 0 또는 1 일 수 있 으 므 로 단독으로 처리 해 야 합 니 다.
3. 코드:
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<algorithm>
#include<string>
#include<sstream>
#include<set>
#include<vector>
#include<stack>
#include<map>
#include<queue>
#include<deque>
#include<cstdlib>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<ctime>
#include<functional>
using namespace std;
#define N 200000
long double v1, v2;
long double Log[2*N+100];
void init()// , n!
{
for (int i = 1; i <= N * 2; i++)
Log[i] = Log[i - 1] + log(i);
}
int main()
{
//freopen("test.txt", "r", stdin);
int rnd = 0;
int n;
double p;
init();
while (cin >> n >> p)
{
double ans = 0.0;
printf("Case %d: ", ++rnd);
if (p == 0 || p == 1)ans = n;//
else
{
long double p1 = log(p);
long double q1 = log(1 - p);
for (int i = 1; i <= n; i++)
{
long double c = Log[2 * n - i] - Log[n] - Log[n - i];
v1 = c + (n + 1)*p1 + (n - i)*q1;
v2 = c + (n + 1)*q1 + (n - i)*p1;
ans += (double)i*(exp(v1) + exp(v2));
}
}
printf("%.6lf
", ans);
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
UVA - 10986 Sending email(Dijkstra 인접 테이블 + 우선 순위 대기열 최적화)제목 대의: s점에서 t점까지의 최소 거리를 구하는 그림을 주세요. 확인: 적나라한 최단길이지만 n이 너무 크면 인접 행렬을 사용할 수 없기 때문에 Dijkstra에 대한 인접표 + 우선 대기열 최적화가 필요합니다....
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.