ACM/ICPC 2011 成都现场赛 Break the Chocolate 题解
这道题还是比较水的。如果用手掰的话，不管怎么掰，每次掰块数都会增加 1. 比如说，一开始是一整坨巧克力，然后掰一下，变成 2 坨，再掰，成 3 坨。一直掰到 N · M · K 坨，需要掰 N · M · K – 1 下。然后用刀切，对于一个面来说，切一次，少一条缝；切两次，少 3 条缝……总之，大概就是切个 [latex] \lceil \log_{2}{N} \rceil + \lceil \log_{2}{M} \rceil + \lceil \log_{2}{K} \rceil [/latex] 下。
注意这题的数据范围，每个数最大 2000, 三个数一乘，可以到 80 亿。所以用个 64 位整型才行。还有就是算对数的时候，可以用位运算，比 math 库里那些快多了。
代码如下（是不是太短了……）：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 | #include <cstdio> using namespace std; typedef unsigned long long ull; inline ull f(ull a) { ull r = 0; for (--a ; a; a >>= 1) ++r; return r; } int main() { int n; scanf("%d", &n); for (int i = 1; i <= n; ++i) { ull x, y, z; scanf("%llu %llu %llu", &x, &y, &z); ull hand = x * y * z - 1; ull knife = f(x) + f(y) + f(z); printf("Case #%d: %llu %llu\n", i, hand, knife); } return 0; } |
