Algorithm Class - Asymptotic Notation 1

Interview

Time limit1sMemory limit512 MB

Summary

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

Level: Easy2 of 10
Topics: Math, Implementation, Brute force, Array
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.

Define the O-notation (big-O) that describes the running time of an algorithm as follows.

O(g(n)) = {f(n) | there exist a positive constant c and an n0 such that f(n) ≤ c × g(n) for all n ≥ n0}

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

Given the function f(n) = a1n + a0, a positive integer c, and n0, determine whether they satisfy the definition of O(n).

Input

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

The next line gives a positive integer c. (1 ≤ c ≤ 100)

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

Output

If f(n), c, and n0 satisfy the definition of O(n), print 1; otherwise print 0.

Examples2

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