2007-2008 Summer Petrozavodsk Camp, Andrew Stankevich Contest 26 (ASC 26) Codeforces Gym 100153_26u

2007-2008 Summer Petrozavodsk Camp, Andrew Stankevich Contest 26 (ASC 26)

A. War Academy

枚举团体训练的时间。注意只看相对误差，所以需要注意精度。

B. Discount

与A题相似，按(100-b)*a/b排序后，可以分成打折和减价两段。

C. Dowry

折半排序。

D. Minimal Cut Matrix

求任意两点最小割时，任何一张图都可以等价为一最小割树。所以如果不是NO，那么就可以构造最小割树，可以证明最大生成树即满足条件。

E. Shortest Path

跨越两个平面一定在中间的圆环上，分段三分即可。

F. Infinite Recursion

小编译器。注意变量名可能与函数重名。没有定义常量，所以1可以作为一个函数名或者变量名。

G.Yet Another Rooks Problem

rooks不超过100个，dp[i][j][k]表示前i行有j列有0个rook有k列有1个rook。

H. School of Magic

随机游走与决策结合，暴力迭代即可。

I. Shepherd’s Problem

每个点有两个圆，没两个点可以画一条线。求出所有交点，暴力判断。
模拟退火也能过。