Random paths P33549


Statement
 

pdf   zip

thehtml

A random walk consists of a sequence of positions, each one obtained from the previous one by making a random step. In this exercise we consider random walks in the plane, starting at (0, 0). Let k be a strictly positive natural number. Each step will be an increment between −k and k, random and independent, of the two coordinates.

Hence, we need a source of randomness. The usual way to simulate it consists in generating pseudorandom numbers. These numbers are the result of an algorithm, so they are not really random, but they look random enough. The linear congruential generators are defined with four natural numbers m (module), a (multiplier), b (adder) and s (initial seed). The generated sequence is

x1 = (a*s + b)  mod  m,   x2 = (a*x1 + b)  mod  m,   x3 = (a*x2 + b)  mod  m,   …

For instance, if m = 9, a = 2, b = 7, s = 3, then we get

x1 = (2*3 + 7)  mod  9 = 4,   x2 = (2*4 + 7)  mod  9 = 6, ⁠ ⁠ 1, ⁠ ⁠ 0, ⁠ ⁠ 7, ⁠ ⁠ 3, ⁠ ⁠ 4, ⁠ ⁠ 6, ⁠ ⁠ …

These numbers are between 0 and m − 1, but in this exercise we need numbers between −k and k. The easiest way to achieve this is with the following code; use it just like that:

int random(int k, int m, int a, int b, int& s) { s = (a*s + b)%m; return s%(2*k + 1) - k; }

Following with the example, for k = 2 the sequence of increments is

4  mod  5   −   2 = 2, ⁠ ⁠ 6  mod  5   −   2 = −1, ⁠ ⁠ 1  mod  5   −   2 = −1, ⁠ ⁠ −2, ⁠ ⁠ 0, ⁠ ⁠ 1, ⁠ ⁠ 2, ⁠ ⁠ −1, ⁠ ⁠ …

and, if we increase the first coordinate before the second one, the steps are

(0, 0), ⁠ ⁠ (2, −1), ⁠ ⁠ (1, −3), ⁠ ⁠ (3, −3), ⁠ ⁠ …

Write a program to compute the first n steps of a sequence of random walks defined by k, m, a, b and s.

Input

Input is all natural numbers, and consists of several cases, each one in two lines. The first line contains n and k. The second line contains m, a, b and s. All n, k and m are strictly positive, and a, b and s are less than m.

Output

For each case of the input, first print its number starting at 1, followed by the walk of n steps defined by k, m, a, b and s. If some position gets repeated, indicate it and stop the walk as it is shown in the example. Print an empty line at the end of each case.

Public test cases
  • Input

    5 2
    9 2 7 3
    8 1
    7 2 0 5
    12 100
    1007 74 985 333
    

    Output

    Path #1
    (0, 0)
    (2, -1)
    (1, -3)
    (1, -2)
    (3, -3)
    
    Path #2
    (0, 0)
    (-1, -1)
    (0, -2)
    (-1, -1) repeated!
    
    Path #3
    (0, 0)
    (-50, 95)
    (-41, 156)
    (-19, 202)
    (73, 102)
    (94, 14)
    (-4, -18)
    (-16, -102)
    (11, -7)
    (-10, 79)
    (51, 73)
    (122, 1)
    
    
  • Information
    Author
    Salvador Roura
    Language
    English
    Translator
    Carlos Molina
    Original language
    Catalan
    Other languages
    Catalan
    Official solutions
    C++
    User solutions
    C++