Codefest

Problem 5: Evaluate the function

Time limit: 2 secs

A function f(n) is defined recursively as:

f(n) = f(n-1) mod 10000; if f(n-1)>=10000
       2*f[n-1]+5; if f(n-1)<10000 and f(n-1) mod 2 = 0
       f[n-1]+3; if f(n-1)<10000 and f(n-1) mod 2 is not 0

Given n and value of f(0), you need to determine f(n).

Input:

First line of input contains t, number of test cases.
On the next each of t lines are two integer n and f(0) separated by space.

Output:

For each n, output f(n) on a separate line

Constraints:

0<t<20
0<=n<=1000000
0<=f(0)<=1000000000

Sample Input:

2
10 1
10 19999

Sample Output:

373
149

Score:

USE OF FUNCTIONS IN "math.h" IS NOT ALLOWED
C : Number of parentheses '(' or ')'
L : Number of for, while, do, goto
I : Number of if, else, ternary(?), switch

T = 30000/(300 + C + 2000*L + 1000*I)

Solution:

The lame approach for solving this problem is using:

• Using Loops
  We can calculate the value of f(n) starting from i=1 to i=n, which gives the result for f(n).
  Although, this approach gets accepted, but since loops and conditional statements have been constrained, this approach is not scoring.
• Using Recursion
  Recursion can be used to solve this recursive function, for small values on n. For values of n, that are big, program will result in stack overflow causing Runtime Error.

Runtime error in Recursive solution, is due to the fact that call stack overflows. This can be avoided if we use multiple recursions. We use them in such a way that it does not cause very high call stack.
For the current problem, it can be solved using two separate recursions. Using the first recursive function we call other recursive functions, which calculates in blocks of 10000. This does not cause call stack to overflow.

References: stack overflow, 4.10 Recursion, Dennis Ritchie

Code:

n,a[1000001];
c(i)
{
  ((i-1)%10000)&&c(i-1);
  (((a[i-1]>10000)&&(a[i]=a[i-1]%10000))||((a[i-1]<10000 && a[i-1]%2==0)&&(a[i]=2*a[i-1]+5))||((a[i-1]<10000 && a[i-1]%2!=0)&&(a[i]=a[i-1]+3)));
  return 1;
}
F(i)
{
  (i<n)&&c(i+10000)&&F(i+10000);
  return 1;
}
main(i)
{
  i&&scanf("%*d");
  ~scanf("%d%d",&n,&a[0])&&F(0)&&printf("%d\n",a[n])&&main(0);
}

Check the Best Solutions