글 읽기 - 1344번 축구 질문입니다.

goodksj 7년 전 1

dp를 짜보았는데요

제 알고리즘 정의는

match(score_a, score_b, time) = time시간까지 A가 score_a이고 B가 score_b을 넣었을 때 경기가 끝나고 둘 중 하나의 점수가 소수일 확률 입니당

0.526656

답은 요렇게 나오는데 오차에서 틀린거 같은데 어떻게 하면 될까요?

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

double a,b;
bool isPrime(int n);
double match(int score_a, int score_b, int time);
double cache[20][20][20];
int main(){
	freopen("input.txt","r",stdin);
	cin>>a>>b;
	a/=100; b/=100;
	memset(cache, -1, sizeof(cache));
	cout<<match(0, 0, 0)<<endl;
	return 0;
}

double match(int score_a, int score_b, int time){
	
	if(time == 18)	return (isPrime(score_a) || isPrime(score_b));

	double& ret = cache[score_a][score_b][time];

	if(ret > -0.5) return ret;
	
	
	ret = 0;

	ret += a*(1-b)*match(score_a + 1, score_b, time + 1);
	ret += (1-b)*b*match(score_a, score_b + 1, time + 1);
	ret += a*b*match(score_a + 1, score_b + 1, time + 1);
	ret += (1-a)*(1-b)*match(score_a, score_b, time + 1);
	return ret;
}

bool isPrime(int n){
	int prime[10] = {1,2,3,5,7,11,13,17,19,23};

	for(int i = 0 ; i < 10; i++){
		if(n == prime[i]){
			return true;
		}
	}
	return false;
}

ntopia 7년 전 1

1은 소수가 아닙니다

goodksj 7년 전 0

후 감사합니다 소수판정을 바꿔서

다음과 같이 바꿔봤는데도 틀린 이유가 뭘까요 ..ㅠㅠㅠ

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

double a,b;
bool isPrime(int n);
double match(int score_a, int score_b, int time);
double cache[20][20][20];
int main(){
	freopen("input.txt","r",stdin);
	cin>>a>>b;
	a/=100; b/=100;
	memset(cache, -1, sizeof(cache));
	printf("%.12f\n",match(0,0,0) );
	return 0;
}

double match(int score_a, int score_b, int time){
	
	if(time == 18)	return (isPrime(score_a) || isPrime(score_b));

	double& ret = cache[score_a][score_b][time];

	if(ret > -0.5) return ret;
	
	
	ret = 0;

	ret += a*(1-b)*match(score_a + 1, score_b, time + 1);
	ret += (1-b)*b*match(score_a, score_b + 1, time + 1);
	ret += a*b*match(score_a + 1, score_b + 1, time + 1);
	ret += (1-a)*(1-b)*match(score_a, score_b, time + 1);
	return ret;
}

bool isPrime(int n){
	int prime[9] = {2,3,5,7,11,13,17,19,23};

	for(int i = 0 ; i < 9; i++){
		if(n == prime[i]){
			return true;
		}
	}
	return false;
}

ntopia 7년 전 1

일단... freopen 주석처리 잘 하신거 맞죠?

ntopia 7년 전 2

double 형 배열에 대해서는 memset이 제대로 작동하지 않습니다.

memset은 입력받은 값을 unsigned char로 캐스팅한 뒤, 그 값을 바이트마다 모조리 쓰는 함수 입니다.

double 형은 부동소수점 표준 IEEE754 로 표현되어지므로 memset으로 -1을 채우면 이상한 값이 되어버립니다.

(디버거 돌려서 확인해볼 수 있습니다.)

아마 이것 때문에 채점머신에 따라 다른 결과를 뱉을 수 있다고 생각됩니다.

ntopia 7년 전 1

그리고 결정적으로 32번째 줄이 틀렸네요

goodksj 7년 전 0

감사합니다!!

32번째 줄의 오류였네요 ㅠㅠ

아 코드를 자세히 읽어주셔서 감사합니다.

우선 말씀해주신 freopen은 주석처리 되게끔 입력을 했었습니다.

그리고 double을 memset으로 -1로 초기화해서 출력을 하니까 - nan으로 ntopia 님 말씀대로

이상한 값이 들어가있습니다.

그래도 일단 답이 나와서 맞추긴 했습니다.

그래도 좀 찜찜해서 몇가지 테스를 해보았는데

memset(cache) 이후

cout<<(cache[0][0][0] < -0.5)<<endl; cout<<(cache[0][0][0] > -0.5)<<endl; cout<<(cache[0][0][0] == -0.5)<<endl;

을 모두 해보았는데도 모두 0이 나왔습니다.

음수가 문제인가 싶어서 -0.5대신 1을 넣어봤는데 1도 역시 모두 0이 나왔습니다.

말씀해주신대로 모두 이상한 값이 들어간 것같습니다.

그러면 double 형 인 경우에 cache의 초기화를 어떻게 하면 될까요?

for문으로 일일히 초기화를 하는 수 밖에 없는 것인가요??

ntopia 7년 전 0

네

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

1344번 축구 질문입니다.

goodksj 7년 전 1

ntopia 7년 전 1

goodksj 7년 전 0

ntopia 7년 전 1

ntopia 7년 전 2

ntopia 7년 전 1

goodksj 7년 전 0

ntopia 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말