sqrt log sin#1207

sqrt log sin (Editorial)

The value of $x_{i}$ x_i will be computed using the function $f (i)$ . To do this, we need to implement the recurrence relation:

f (i) = f (⌊ i - i ⌋) + f (⌊ l n (i)⌋) + f (⌊ i \cdot s i n^{2} (i)⌋)

f(i) = f(\lfloor i - \sqrt{i} \rfloor) + f(\lfloor ln(i) \rfloor) + f(\lfloor i \cdot sin^2(i) \rfloor)

f (0) = 1

f(0) = 1

while storing the values of $f (i)$ in a linear array $d p$ of size $1 0^{6}$ 10^6.

Algorithm implementation

Store the values of $x_{i}$ x_i in the array $d p$ .

#define MAX 1000001
int dp[MAX];

The function $f (n)$ computes the value of $x_{n}$ x_n.

int f(int n)
{

Terminate the recursion when $n = 0$ n = 0.

  if (n == 0) return 1;

If the value of $x_{n}$ x_n is already computed $(d p [n] \neq = - 1)$ (dp[n] \ne -1), return it.

  if (dp[n] != -1) return dp[n];

Recursively compute the first, second, and third terms.

  int a = f((int)(n - sqrt(n)));
  int b = f((int)(log(n)));
  int c = f((int)(n * sin(n) * sin(n)));

Compute, store, and return the value of $x_{n}$ x_n.

  return dp[n] = (a + b + c) % 1000000;
}

The main part of the program. Let $d p [i] = - 1$ dp[i] = -1 if the value of $x_{i}$ x_i is not computed yet.

memset(dp,-1,sizeof(dp));

Process multiple test cases. For each value of $n$ , print the result.

while(scanf("%d",&n), n != -1)
  printf("%d\n",f(n));

Algorithm implementation — nonrecursive

Store the values of $x_{i}$ x_i in the array $x$ .

int x[1000001];

Fill the elements of the array $x$ according to the given recurrence relation.

x[0] = 1;
for (i = 1; i <= 1000000; i++)
  x[i] = (x[(int)(i - sqrt(i))] + x[(int)(log(i))] +
          x[(int)(i * sin(i) * sin(i))]) % 1000000;

Process multiple test cases. For each value of $n$ , print the result.

while (scanf("%d", &n), n != -1)
  printf("%d\n", x[n]);

Java implementation

import java.util.*;

public class Main
{
  static int dp[] = new int[1000001];

  static int f(int n)
  {
    if (n == 0) return 1;
    if (dp[n] != -1) return dp[n];
    
    int a = f((int)(n - Math.sqrt(n)));
    int b = f((int)(Math.log(n)));
    int c = f((int)(n * Math.sin(n) * Math.sin(n)));
    return dp[n] = (a + b + c) % 1000000;
  }
  
  public static void main(String[] args)
  {
    Scanner con = new Scanner(System.in);
    Arrays.fill(dp, -1);
    while(true)
    {
      int n = con.nextInt();
      if (n == -1) break;
      System.out.println(f(n));
    }
    con.close();
  }
}

Java

Python implementation

import math

Initialize the array $x$ .

x = [0] * 1000001
x[0] = 1

Fill the elements of the array $x$ according to the given recurrence relation.

for i in range(1, 1000001):
  x[i] = (x[int(i - math.sqrt(i))] +
          x[int(math.log(i))] +
          x[int(i * math.sin(i)**2)]) % 1000000

Process multiple test cases. For each value of $n$ , print the result.

while True:
  n = int(input())
  if n == -1:
    break
  print(x[n])