1.There is a prize hidden in a box; the value of the prize is a positive integer between 1 and N, and you are
given N. To win the prize, you have to guess its value. Your goal is to do it in as few guesses as possible. You
start with a number of chips (specified below). Each chip allows you one guess that’s too high. If you guess
too high, and you have no chips, you lose. So, for example, if you start with no chips, then you can win in N
guesses by simply guessing the sequence 1, 2, 3, ... .
Suppose you start with 1 chip. Describe a strategy that makes O(pN) guesses.
2. Use the Carter-Wegman trick to determine the value of 1463528785364712 mod 99999999 without using any
calculating devices or long division. You have a limit of ten lines for your answer.
3. Suppose you have N rational numbers r1, r2, r3, ...rN, whose numerators and denominators are all between
1 and N; you may assume all the rational numbers have value at least 1. Show how to sort these numbers
in linear time, assuming that any operations on the numerators or denominators (adds, subtracts, multiplies,
integer divides, and integer mod operations) take constant time. Hint: Linear-time sorts are generally done by
radix sort. Suppose ri − rj > 0. What is the minimum value of ri − rj?
求大神指点，看不大懂，还有这几题的解题思路是怎样的。

1.    在盒子里有个奖品，奖品的数字是一个1到N之间的正整数。为了赢得奖品，你不得不猜它的值。你的目标就是竟可能晓得猜中它。你开始有一堆卡片。每个卡片允许你猜的高一次。如果你猜高了而且你没卡片了，那就输了。 所以，例如，你刚开始没有卡片，你可以简单赢得奖品从1,2,3。。。这个序列猜N次。         现在假设你刚开始有1张卡片，描述一下一个猜O(N^(1/2))次的方法。
2.    用Carter-Wegman trick证明1463528785364712 MOD 99999999的值。不能用计算器和长除法。
3.    假设你有N个有理数t1,t2,t3,…..tn,  它的分子分母全部在1到N之间， 你可以假设所有有理数的值最小是1.展现如何将这些书排序成线性时间。 假设任何在分子分母上的操作（加减乘除取余）是常数时间。  提示：线性时间排序一般由基数排序完成。假设Ri-Rj>0. Ri-Rj最小值是多少？

找人翻译了下，好了。

描述一下一个猜O(N^(1/2))次的方法。
没看懂 这句话的意思

就是说让你用一个算法可以再O（根号下N）次猜出来奖品的方法。还有那个Carter-Wegman trick不大清楚是什么。望大神指点。

[ 本帖最后由 leonlong 于 2012-10-2 13:28 编辑 ]