UVa 11971 Polygon

发表于 更新于 分类于

题目

题目大意

有一根长度为\(n\)的木条, 随机选\(k\)个位置把它们切成\(k + 1\)段小木条。求这些小木条能组成一个多边形的概率。

题解

答案显然与\(n\)无关, 若要不能组成多边形, 则其中一段小木条必定有至少一半的长度, 则要使这些木条组不成多边形的概率为\(\frac{k + 1}{2^k}\), 能组成多边形的概率为\(1 - \frac{k + 1}{2^k}\)。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <cstdio>
template<class IntegerType>
inline IntegerType GreatestCommonDivisor(const IntegerType &a, const IntegerType &b) {
  return b ? GreatestCommonDivisor(b, a % b) : a;
}
long long k;
long long a, b, gcd;
int T, cases;
int main(int argc, char **argv) {
  scanf("%d", &T);
  while (T--) {
    scanf("%lld %lld", &k, &k);
    a = k + 1,
    b = (long long)(1ll << k);
    gcd = GreatestCommonDivisor(a, b);
    a /= gcd,
    b /= gcd;
    printf("Case #%d: %lld/%lld\n", ++cases, b - a, b);
  }
  return 0;
}