# Problems

## A. Height Ordering

### Solution

统计逆序对或者模拟插入排序。

## B. Islands in the Data Stream

### Solution

枚举区间O(n^2)。

## C. Floating-Point Format Conversion

### Solution

细节比较麻烦，可以先列出IEEE标准各阶段的上下限，然后将输入值转换为1.x*2^k的形式与上下限比较。建议对float取地址强制类型转换为int*，当成int用位运算处理。

## D. Happy Happy Prime Prime

### Solution

记忆化搜索，注意处理成环的情况。

## E. Mancala

### Solution

题目中写明了每个n有且仅有一解，可以搜索出所有可行解，因为大部分点都是确定的，复杂度其实为O(BN)。

递推构造方法是找到最小的为零的位置i，将[1,i-1]的盒子向后移一位，在新的i号盒子里放入一个。盒子1置零。

## F. A Rational Sequence

### Solution

向上到达第一个不是右儿子的节点i，进入i的父亲结点的右儿子，一直向左直到和原结点同层即可。注意用除法，减法会超时。

## G. Growing Rectangular Spiral

### Solution

简单推导可得y<=x&&&y<=3的点是不可到达的。两段线段可到达y=x以上的全部点，六段线段可到达剩余位置。

## H. Farey Sums

### Solution

Farey Sequence中连续的三个数a/b,p/q,c/d满足p=a+c,q=b+d（该性质可由Stern-Brocot树证明）。递推时加入数n，Farey Sum中必定是某项a/(n-a)变为a/n+n/(n-a)，与对称位置的(n-a)/a变为(n-a)/n+n/a一起考虑可以得出这一对n的加入使和增加3。而n的出现次数即为n的欧拉函数。因此结果即为欧拉函数前缀和*3/2+常数。

## I. The Queen's Super-circular Patio

### Solution

第一层圆的半径计算较为简单，第n层和第n-1层的半径之比可以通过元相切构造直角三角形，得出二次方程解得。最外层圆弧刚好拼成一个圆，设半径为r，则答案为2r(n+PI)。