Algorithm Class - Asymptotic Notation 3

Interview

Time limit1sMemory limit512 MB

Summary

Given f(n) = a1*n + a0 and constants c1, c2, n0, decide whether c1*n <= f(n) <= c2*n holds for every n >= n0.

Level: Easy3 of 10
Topics: Math, Implementation
Solved: No attempts yet

Problem

Seojun is working as a teaching assistant for the asymptotic notation class again today. Let us check through a problem whether the students understood what his father taught in class.

The Θ-notation (big-theta) that describes the running time of an algorithm is defined as follows.

Θ(g(n)) = {f(n) | there exist positive constants c1, c2, n0 such that c1 × g(n) ≤ f(n) ≤ c2 × g(n) for all n ≥ n0}

This definition may differ from the actual Θ-notation (https://en.wikipedia.org/wiki/Big_O_notation).

Given the function f(n) = a1n + a0 and positive integers c1, c2, n0, determine whether they satisfy the definition of Θ(n).

Input

The first line gives the integers a1, a0 representing the function f(n). (0 ≤ |ai| ≤ 100)

The next line gives the positive integers c1, c2. (1 ≤ c1 ≤ c2 ≤ 100)

The next line gives the positive integer n0. (1 ≤ n0 ≤ 100)

Output

Print 1 if f(n), c1, c2, n0 satisfy the definition of Θ(n), and 0 otherwise.

Examples2

Example 1
Input
```
7 -7
6 8
1
```
Expected output
```
0
```
Example 2
Input
```
7 -7
6 8
10
```
Expected output
```
1
```