**UVA Problem 10696 – f91 Solution:**

Click here to go to this problem in uva Online Judge.

**Solving Technique:**

This is a simple DP problem (OR, so it looks **but there’s a better way**). It can be solved both **iteratively and recursively with or without memoization.** Still it will get accepted. But still the runtime is slow due huge input. So using a faster io may help it get accepted with a better rank.

For the matter of practice i will show all four methods i know of to solve this problem. Codes are given in this order,

- dynamic programming solution.
- Recursive solution without Memoization.
- Recursive solution with Memoization.
- Shortcut Trickery.
**Maybe extend the shortcut Trickery with memoization or other technique by yourself ? try it !!**

###### Before starting to look below take look at this codes ( Fibonacci DP, Memoization ) with explanation.

#### Solution explanation:

Here the formula is given, we just need rearrange it and get the **recurrence relation**,

If N ≤ 100, then f91(N) = f91(f91(N+11));

If N ≥ 101, then f91(N) = N-10.

So from the given statement generating recurrence relation will be,

f(n) = { f(f(n+11)), if n <= 100 { n - 10, if n >= 101

Here **base case** is for any **n greater than or equal to 101 is return n – 10**. **No more recursive call on that**.

This can be simplified but i won’t go into that. The codes below will give a better idea.

**Now, just create a function named f and use if else or ternary to implement the given relation** and it’ll work.

#### Memoization:

Since we’ve found out the recurrence relation it won’t be hard to memoize the code. We can use a **memo array to store the already calculated results.** We need not change much from the previous recursive solution to memoize it.

**Add an if condition in the beginning if the value is already calculated and stored in memo array just return**. **Other wise when returning just store the return values in memo.**

That’s it.

#### Dynamic Programming ( bottom up method ):

Our recurrence relation will never change. Since there is no other function needed we just calculate and store values in memo array. I started from 1,000,000 because the problem statement said an integer may be at most 1,000,000. Just** loop through that many times and store results in memo array.**

##### Last Solution Trick:

It come to me when i was testing my own inputs. **Anything less or equal 100 result in 91**. **Any greater value results in that value minus 10. **Take a look at the code below to get the idea.

** Important: **Be sure to add or print a new line after each output unless otherwise specified. The outputs should match exactly because sometimes even a space character causes the answer to be marked as wrong answer. Please compile with c++ compiler as some of my codes are in c and some in c++.

**Input:**

500 91 1 5 190 100 101 0

**Output:**

490 91 91 91 180 91 91

### Code Bottom Up (Iterative) Dynamic Programming:

/** * @author Quickgrid ( Asif Ahmed ) * @link https://quickgrid.wordpress.com * Problem: UVA 10696 - f91 * Type: Bottom Up (Iterative) Dynamic Programming */ #include<cstdio> #include<sstream> using namespace std; #define N 1000000 static int F[N]; int main(){ int n, i; for(i = N; i >= 0; --i){ if(i >= 101) F[i] = i - 10; else F[i] = F[F[i + 11]]; } while(scanf("%d", &n) && n) printf("f91(%d) = %d\n", n, F[n]); return 0; }

### Code Top Down (Recursive) Without Memoization:

/** * @author Quickgrid ( Asif Ahmed ) * @link https://quickgrid.wordpress.com * Problem: UVA 10696 - f91 * Type: Top Down (Recursive) without Memoization */ #include<stdio.h> int f(int n){ return (n >= 101) ? n - 10 : f(f(n + 11)); } int main(){ int n; while(scanf("%d",&n) && n) printf("f91(%d) = %d\n", n, f(n)); return 0; }

### Code Top Down (Recursive) with Memoization:

/** * @author Quickgrid ( Asif Ahmed ) * @link https://quickgrid.wordpress.com * Problem: UVA 10696 - f91 * Type: Top Down (Recursive) with Memoization */ #include<stdio.h> static unsigned F[1000000]; unsigned f(unsigned n){ if(F[n]) return F[n]; if(n >= 101) return F[n] = n - 10; else return F[n] = f(f(n+11)); } int main(){ unsigned n; while(scanf("%u",&n) && n) printf("f91(%u) = %u\n", n, f(n)); return 0; }

### Shortcut Technique:

/** * @author Quickgrid ( Asif Ahmed ) * @link https://quickgrid.wordpress.com * Problem: UVA 10696 - f91 * Type: shortcut technique */ #include<stdio.h> int main(){ unsigned n; while(scanf("%u", &n) && n){ if(n <= 100) printf("f91(%d) = 91\n", n); else printf("f91(%d) = %d\n", n, n - 10); } return 0; }