Camins aleatoris P33549

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 $$x_1 = (a*s + b) \mbox{ mod } m, \quad x_2 = (a*x_1 + b) \mbox{ mod } m, \quad x_3 = (a*x_2 + b) \mbox{ mod } m, \quad \dots$$

Per exemple, si $m = 9, a = 2, b = 7, s = 3$, llavors obtenim $$x_1 = (2*3 + 7) \mbox{ mod } 9 = 4, \quad x_2 = (2*4 + 7) \mbox{ mod } 9 = 6, \enspace 1, \enspace 0, \enspace 7, \enspace 3, \enspace 4, \enspace 6, \enspace \dots$$

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 \mbox{ mod } 5 \, - \, 2 = 2, \enspace 6 \mbox{ mod } 5 \, - \, 2 = -1, \enspace 1 \mbox{ mod } 5 \, - \, 2 = -1, \enspace -2, \enspace 0, \enspace 1, \enspace 2, \enspace -1, \enspace \dots$$ i, si incrementem la primera coordenada abans que la segona, els passos són $$(0, 0), \enspace (2, -1), \enspace (1, -3), \enspace (3, -3), \enspace \dots$$

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.