Consider the sequence of numbers x[0]
, x[1]
, ..., x[n-1]
, generated with the next formula:
x[0]
= p,
x[i]
= (a * x[i-1]
* x[i-1]
+ b * x[i-1]
+ c) mod m, where 0 < i < n
Create a Linked List from these numbers: List = x[0]
→ x[1]
→ ... → x[n-1]
.
Let k = x[n]
mod n. If x[n]
< m / 2, let tail → next
of your list points to the k-th element. Otherwise tail → next
= NULL. Setup the value of tail → next
according to this condition.
Consider the example: p = 1, a = 1, b = 1, c = 1, m = 100, n = 5. Here List = 1 → 3 → 13 → 83 → 73, x[n]
= 3, so k = 3 < 100 / 2 = m / 2 and tail → next
points to the third element that equals to 83 (elements' positions in a List starts from 0).
Write a method hasCycle
that determines if a List has a cycle in it.
Write the code according to the next interface:
class Node
{
public:
int data;
Node *next;
Node() : next(NULL) {};
Node(int data, Node *next = NULL) : data(data), next(next) {};
};
class List
{
public:
Node *head, *tail;
List() : head(NULL), tail(NULL) {};
void addToTail(int val); // Add number val to the end of the Linked List
int hasCycle(void) // Returns 1 if a List has a cycle, and 0 otherwise
};
You can create (use) additional methods if needed.
One line contains six numbers: p, a, b, c, m, n. All numbers are integers in the range from 0 to 1000, m and n are greater than 0.
Print 1 if the Linked List has a cycle and 0 otherwise.