uva 10288 - Coupons(확률)
제목 대의: n을 정하여 n중 교환권이 있기 위해 현재 상자를 한 번 열 때마다 그 중의 교환권을 확률적으로 얻을 수 있습니다.평균 몇 개의 상자를 열어야 n종의 교환권을 모을 수 있느냐고 물었다.
문제 풀이 방향: dp[i]는 i종이 아직 획득하지 못했다는 것을 나타낸다. dp[i]=n - in dp[i]+in dp[i - 1]+1===dp[i]+ni
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long type;
struct Fraction {
type member; // ;
type denominator; // ;
Fraction (type member = 0, type denominator = 1);
void operator = (type x) { this->set(x, 1); }
Fraction operator * (const Fraction& u);
Fraction operator / (const Fraction& u);
Fraction operator + (const Fraction& u);
Fraction operator - (const Fraction& u);
void set(type member, type denominator);
};
inline type gcd (type a, type b) {
return b == 0 ? a : gcd(b, a % b);
}
/*Code*/
/////////////////////////////////////////////////////
const int maxn = 33;
typedef long long ll;
Fraction dp[maxn+5][maxn+5];
void init () {
for (int i = 1; i <= maxn; i++) {
dp[i][0] = 0;
for (int j = 1; j <= i; j++)
//dp[i][j] = (dp[i][j-1] * Fraction(j, i) + Fraction(1, 1)) / Fraction(j, i);
dp[i][j] = dp[i][j-1] + Fraction(i, j);
}
}
inline int countbit (ll u) {
int ret = 0;
while (u) {
ret++;
u /= 10;
}
return ret;
}
void put_ans (Fraction u) {
type d = u.member / u.denominator;
type member = u.member % u.denominator;
int cn = countbit(d);
int cd = countbit(u.denominator);
int n = cn + (cn == 0 ? 0 : 1);
if (member) {
for (int i = 0; i < n; i++) printf(" ");
printf("%lld
", member);
}
printf("%lld", d);
if (member) {
if (d)
printf(" ");
for (int i = 0; i < cd; i++) printf("-");
printf("
");
for (int i = 0; i < n; i++) printf(" ");
printf("%lld", u.denominator);
}
printf("
");
}
int main () {
int n;
init();
while (scanf("%d", &n) == 1) {
put_ans(dp[n][n]);
}
return 0;
}
/////////////////////////////////////////////////////
Fraction::Fraction (type member, type denominator) {
this->set(member, denominator);
}
Fraction Fraction::operator * (const Fraction& u) {
return Fraction(member * u.member, denominator * u.denominator);
}
Fraction Fraction::operator / (const Fraction& u) {
return Fraction(member * u.denominator, denominator * u.member);
}
Fraction Fraction::operator + (const Fraction& u) {
return Fraction(member * u.denominator + denominator * u.member, denominator * u.denominator);
}
Fraction Fraction::operator - (const Fraction& u) {
return Fraction(member * u.denominator - denominator * u.member, denominator * u.denominator);
}
void Fraction::set (type member, type denominator) {
type tmp_d = gcd(member, denominator);
this->member = member / tmp_d;
this->denominator = denominator / tmp_d;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.