Typical DP Contest

Submission #6341879

Source codeソースコード

#include <stdio.h>
#include <string.h>
#include <vector>
#include <string>
#pragma warning(disable : 4996)

#define MAX_N 100

template <typename T> bool chmin(T &a, const T &b) {
	if (a > b) {
		a = b;
		return true;
	}
	return false;
}
template <typename T> bool chmax(T &a, const T &b) {
	if (a < b) {
		a = b;
		return true;
	}
	return false;
}
int Abs(int a) {
	if (a < 0) return a *= -1;
	return a;
}

int min(int a, int b) {
	if (a < b) return a;
	return b;
}
long long max(long long a, long long b) {
	if (a > b) return a;
	return b;
}

int N;
long long D;
double DP[MAX_N+1][MAX_N * 2+1][MAX_N+1][MAX_N+1];
int main(void) {
	scanf("%d", &N);
	scanf("%lld", &D);
	// factorization D
	int exp[3] = { 0, 0, 0 };
	int pf[3] = { 2, 3, 5 };
	for(int i = 0; i < 3; ++i) {
		if (D == 0) break;
		while (D%pf[i] == 0) {
			D /= pf[i];
			++exp[i];
		}
	}
	if (D != 1) {
		printf("0");
		return 0;
	}
	int dpf[6][3] = {
		{ 0, 0, 0 }, //1
		{ 1, 0, 0 }, //2
		{ 0, 1, 0 }, //3
		{ 2, 0, 0 }, //4
		{ 0, 0, 1 }, //5
		{ 1, 1, 0 }, //6
	};
	DP[0][0][0][0] = 1.0;
	for (int i = 1; i <= N; ++i) {
		for (int d = 0; d < 6; ++d) {
			for (int a = 0; a <= N * 2; ++a) {
				for (int b = 0; b <= N; ++b) {
					for (int c = 0; c <= N; ++c) {
						if (DP[i - 1][a][b][c] != 0) {
							DP[i][a + dpf[d][0]][b + dpf[d][1]][c + dpf[d][2]] += DP[i - 1][a][b][c] / 6.0;
						}
					}
				}
			}
		}
	}
	double e = 0;
	for (int a = exp[0]; a <= N * 2; ++a) {
		for (int b = exp[1]; b <= N; ++b) {
			for (int c = exp[2]; c <= N; ++c) {
				e += DP[N][a][b][c];
			}
		}
	}
	printf("%lf", e);
	return 0;
}

Submission

Task問題 D - サイコロ
User nameユーザ名 ided345
Created time投稿日時
Language言語 C++14 (GCC 5.4.1)
Status状態 MLE
Score得点 0
Source lengthソースコード長 1681 Byte
File nameファイル名
Exec time実行時間 ms
Memory usageメモリ使用量 -

Compiler messageコンパイルメッセージ

./Main.cpp: In function ‘int main()’:
./Main.cpp:41:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &N);
^
./Main.cpp:42:19: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld", &D);
^

Test case

Set

Set name Score得点 / Max score Cases
All 0 / 4 00,01,02,03,04,05,06,07,08,09,10,90,91

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
00 AC 53 ms 145536 KB
01 MLE
02 MLE
03 AC 71 ms 176256 KB
04 AC 66 ms 168064 KB
05 MLE
06 MLE
07 MLE
08 AC 16 ms 57472 KB
09 MLE
10 AC 1 ms 128 KB
90 AC 1 ms 4224 KB
91 AC 2 ms 6272 KB