Problem E
Recursion + Rand = !Fun

Consider the simple recursive function defined below. For a particular parameter value, i, this function might return several different values, depending on the results of its calls to myRNG(). That function returns random integer values in the range $[0, 2^{31}-1]$, and you should assume that it could return any sequence when called. Your job is to tell the difference between values the function f(int i) could produce and those it could not.

int f(int i) {
    if (i <= 0)
        return 1;
    return a + myRNG() % b + f(i - 1 - (myRNG() % c));


Input contains up to $300$ test cases. Each test case is described by five integer values, $a, b, c, i$, and $k$. The first four of these give the values for the variables with the same names in the definition of f(), while $k$ is the value you wish to know if f(i) can return. Their limits are $0 \le a \le 10$, $1 \le b, c \le 10$, $0 \le i \le 100$, and $1 \le k \le 10\, 000$. Input ends at the end of file.


For every test case, output the word “possible” if it’s possible for f(i) to return the value $k$, or “impossible” if it’s not possible.

Sample Input 1 Sample Output 1
1 1 1 1 1
1 1 1 1 2
2 2 2 1 4
2 2 2 1 5
2 2 2 2 5
CPU Time limit 1 second
Memory limit 1024 MB
Statistics Show
David Sturgill
Source Baylor Competitive Learning course
License Creative Commons License (cc by-sa)

Please log in to submit a solution to this problem

Log in