Camins aleatoris P33549


Statement
 

pdf   zip

thehtml

Un camí aleatori consisteix en una seqüència de posicions, cadascuna de les quals s’obté a partir de l’anterior fent un pas aleatori. En aquest exercici considerem camins aleatoris en el pla, amb inici a (0, 0). Sigui k un natural esctrictament positiu. Cada pas serà un increment entre −k i k, aleatori i independent, de les dues coordenades.

Ens cal doncs una font d’atzar. La manera habitual de simular-lo consisteix a generar nombres pseudoaleatoris. Aquests nombres s’obtenen amb un algorisme, i per tant no són realment aleatoris, però ho semblen prou. Els generadors lineals congruencials es defineixen amb quatre naturals m (mòdul), a (multiplicador), b (sumador) i s (llavor inicial). La seqüència generada és

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

Per exemple, si m = 9, a = 2, b = 7, s = 3, llavors obtenim

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

Aquests nombres es troben tots entre 0 i m − 1, però en aquest exercici ens cal passar-los a nombres entre −k i k. La manera més simple és la del codi següent; useu-lo tal qual:

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

Seguint amb l’exemple, per a k = 2 la seqüència d’increments és

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

i, si incrementem la primera coordenada abans que la segona, els passos són

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

Feu un programa que calculi els n primers passos d’una sèrie de camins aleatoris definits amb k, m, a, b i s.

Entrada

L’entrada són tot nombres naturals, i consisteix en una sèrie de casos, cadascun en dues línies. La primera línia conté n i k. La segona línia conté m, a, b i s. Tant n com k com m són estrictament positius, i tant a com b com s són més petits que m.

Sortida

Per a cada cas de l’entrada, escriviu primer el seu número començant en 1, seguit del camí de n passos definit amb k, m, a, b i s. Si alguna posició es repeteix, cal indicar-ho i aturar el camí tal i com es pot veure a l’exemple. Escriviu una línia en blanc al final de cada cas.

Public test cases
  • Input

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

    Output

    Cami #1
    (0, 0)
    (2, -1)
    (1, -3)
    (1, -2)
    (3, -3)
    
    Cami #2
    (0, 0)
    (-1, -1)
    (0, -2)
    (-1, -1) repetit!
    
    Cami #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
    Catalan
    Other languages
    English
    Official solutions
    C++
    User solutions
    C++