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

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

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:

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

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

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.