2015-2016 Petrozavodsk Winter Training Camp, Saratov SU Contest

Problem A

Solved by ultmaster. 02:54 (+)

题意：类似双塔问题。不过这是 三塔问题。

题解：跟双塔问题一样做，不过要记两维状态：第二座比第一座高多少，第三座比第二座高多少。不过状态可能高达 1E4 * 1E4，还要乘 400，难以接受。

zerol 提出可能中间状态也不会转移到太高的地方去，900 或者 1000 就够了。但是内存不够，没法回溯。

ultmaster 遂改成了 200，反复迭代 random_shuffle 跑到 4 秒退出。跑了很久 AC 了。

Problem F

Solved by kblack. 03:36 (+1)

Problem G

Solved by zerol. 00:34 (+3)

签到失败，背锅。我能把 product 看成 sum 也是很厉害的。

Problem H

Solved by ultmaster. 01:38 (+)

题意：给一个点集 $\{(x_i, y_i)\}$，每次询问 $(a,b)$，让你在点集中挑一个点使得 $ax+by$ 最小。

题解：令 $ax+by=c$ 则 $y=\frac{c}{b}-\frac{a}{b}x$。即求截距最小。数形结合一下可知，一定在点集的下凸壳上取到。把下凸壳求出来，然后在凸壳上二分斜率即可。注意会有斜率分母为 0 的情况，所以比较的时候不要用除法。

Problem I

Solved by kblack. 02:10 (+)

Problem J

Solved by kblack. 01:27 (+1)