b******s
发帖数: 2919 | 1 You are given an object with the following state and method:
{
private constant int x0 = ?
private constant int v0 = ?
private int i = 0
public boolean test(int x)
{
++i
return x == x0 + i * v0
}
}
Find out the value of x0 and v0,
by invoking test(x) only, for a finite number of times. | m********i
发帖数: 5 | | t**8
发帖数: 4527 | 3 关键要找到 test return true
用 overflow 和 underflow 试试
【在 b******s 的大作中提到】
: You are given an object with the following state and method:
: {
: private constant int x0 = ?
: private constant int v0 = ?
:
: private int i = 0
: public boolean test(int x)
: {
: ++i
: return x == x0 + i * v0
| C**o
发帖数: 10373 | 4 把这些题做熟了，以后可以随便玩千老的夫人
盹盹盹
：You are given an object with the following state and method:
：{
： private constant int x0 = ?
： private constant int v0 = ?
：
： private int i = 0
： public boolean test(int x)
： {
： ++i
： return x == x0 + i * v0
：..........
【在 b******s 的大作中提到】
: You are given an object with the following state and method:
: {
: private constant int x0 = ?
: private constant int v0 = ?
:
: private int i = 0
: public boolean test(int x)
: {
: ++i
: return x == x0 + i * v0
| s*****l
发帖数: 7106 | 5 提供个思路
没细想 也许不成
假设int的upper limit是n
search space是n square
随便猜一个数大概能排除n个possibility
roughly猜n次是可以猜出来的 | h*********4
发帖数: 1 | 6 为了方便用3位整数[-4, 3]
step 0:test(0)
step 1:test(1)
...
step 7:test(7)
step 8:test(0) aka test(8)
step 9:test(1) aka test(9)
...
step 63: test(7) aka test(63)
如果这一循环没有true，那么x++移位重新test
step 64:test(1)
step 65:test(2)
...
step 127: test(0)
因为左边是移位，右边没变,所以最多第8个循环的时候一定会有一个test为true
记为
x + k1 == x0 + k1*v0 (1)
这不再移位，用同一个x继续test，一定会在某个k2得到
x + k2 == x0 + k2*v0 (2)
可知
(k1 - k2) = (k1 - k2)* v0 mod 8
和
(k1-k2)*x = (k1 - k2)*x0 mod 8
这里k1, k2, x都是已知，可以算出v0和x0，但是k1-k2跟8不互质的时候解不唯一,解的
周期是8/gcd(k1-k2, 8) | i******0
发帖数: 609 | 7 这个本质上是如何enumerate整数对的问题。
定义tuple p = (x, k), x为任意整数，k为正整数。
对于任意p, 运行test(x) up to k times直到得到true,
- 如果得到true，记下x和实际循环次数k' (<= k)，成功次数++。如果成功次数达到2，
退出循环，否则取下一个tuple，重复这个操作
- 如果执行k次之后还是false, 取下一个tuple，重复这个操作
只要得到两组返回true的(x1, k1')和(x2, k2'), 即可解方程组求出x0, v0。
问题的关键是产生sequence穷举这样的(x, k) tuples，方法跟穷举有理数类似，这里
就不再赘述了。
【在 b******s 的大作中提到】
: You are given an object with the following state and method:
: {
: private constant int x0 = ?
: private constant int v0 = ?
:
: private int i = 0
: public boolean test(int x)
: {
: ++i
: return x == x0 + i * v0
|
|
