# Eventually periodic sequence

Eventually periodic sequence

Given is a function

f: 0..N --> 0..N

for a non-negative

N

and a non-negative integer

n

N

. One can construct an infinite sequence

F = f 1(n), f 2(n), ... f k(n) ...

, where

f k(n)

is defined recursively as follows:

f 1(n) = f(n)

and

f k+1(n)

=

f(f k(n))

.

It is easy to see that each such sequence F is eventually periodic, that is periodic from some point onwards, e.g 1, 2, 7, 5, 4, 6, 5, 4, 6, 5, 4, 6 ... . Given non-negative integer N ≤ 11000000 , n ≤ N and f, you are to compute the period of sequence F.

Each line of input contains N, n and the a description of f in postfix notation, also known as Reverse Polish Notation (RPN). The operands are either unsigned integer constants or N or the variable x. Only binary operands are allowed: + (addition), * (multiplication) and % (modulo, i.e. remainder of integer division). Operands and operators are separated by whitespace. The operand % occurs exactly once in a function and it is the last (rightmost, or topmost if you wish) operator and its second operand is always N whose value is read from input. The following function:

```
2 x * 7 + N %
```

is the RPN rendition of the more familiar infix

(2*x+7)%N

. All input lines are shorter than 100 characters. The last line of input has

N

equal 0 and should not be processed.

For each line of input, output one line with one integer number, the period of F corresponding to the data given in the input line.

``````10 1 x N %
11 1 x x 1 + * N %
1728 1 x x 1 + * x 2 + * N %
1728 1 x x 1 + x 2 + * * N %
100003 1 x x 123 + * x 12345 + * N %
0 0 0 N %
``````

``````1
3
6
6
369
``````

``````#include <stdio.h>
#include <string.h>
#include <assert.h>

char op[101][101];
int i,j,k,n,N,no;

int eval(int x){
int i,j;
int stack[101], n=0;
for (i=0;i<no;i++){
if (!strcmp(op[i],"x")) {
stack[n++] = x;
} else if (!strcmp(op[i],"+")) {
stack[n-2] = (stack[n-2]+stack[n-1])%N;
n--;
} else if (!strcmp(op[i],"*")) {
stack[n-2] = ((long long)stack[n-2]*stack[n-1])%N;
n--;
} else {
stack[n++] = atoi(op[i]);
}
}
assert (n == 1);
return stack[0];
}

main(){
int x,xx;
while (2 == scanf("%d%d",&N,&n)&&N) {
for (i=0;1 == scanf("%s",op[i]) && strcmp(op[i],"%");i++);
no = i-1;
x = xx = n;
for (j=1;;j++) {
x = eval(x);
xx = eval(xx);
xx = eval(xx);
if (x == xx) {
for (k=1;x != (xx=eval(xx));k++);
printf("%d\n",k);
break;
}
}
}
}
``````

``````/*
Problem : Point of view in Flatland

In Flatland, there are three circular planets: their centers and radii
are given. Find a point in Flatland, from which all three planets appear
to have the same size (same angular diameter). Let's call such a point
an _isoobservation_ point.

The input has several lines.
Each line has nine numbers, three for each planet.
Each triple has X and Y coordinates of a planet center, and the
The input ends with a line with nine zeros; do not process this line.

For each input line, print the X and Y coordinates of an isoobservation
point in the format shown in the sample; but if there is no such point,
print "No solution".

To simplify the problem you may assume that:
- The planets' centers are not all collinear.
- The planets are totally disjoint.
- The planets are transparent and non-refractive. That is, a planet
is visible and has the same apparent shape and size, whether or
not there's another planet in front of it.
- The input data are such that the existence or non-existence of
such a point is computable, even with slight rounding error. But
use double-precision, eh?
*/

/* If there are two isoobservation points, this program prints both. */

#include <math.h>
#include <stdio.h>
#include <stdbool.h>

/* The locus of isoobservation points of two planets is either a line
or a circle.
If it's a line, keep a point on the line and a vector along the line;
if it's a circle, keep the center and radius. */
typedef struct {
double px, py; /* point on line or center of circle */
double vx, vy; /* vector along line */
bool isLine;   /* %%% put last, to workaround GDB bug */
} isolocus;

static void computeIsolocus(int idx1, int idx2, isolocus *il) {
double ux, uy, dist, rd, t1, t2;

if (il->isLine) {
/* midpoint is on line */
il->px = (CenterX[idx1] + CenterX[idx2]) / 2.0;
il->py = (CenterY[idx1] + CenterY[idx2]) / 2.0;

/* vx,vy is difference, rotated 90 degrees
(or -90 degrees; don't care which) */
il->vx = CenterY[idx1] - CenterY[idx2];
il->vy = CenterX[idx2] - CenterX[idx1];
} else {
/* compute distance and unit delta */
ux = CenterX[idx2] - CenterX[idx1];
uy = CenterY[idx2] - CenterY[idx1];
dist = hypot(ux, uy);
ux /= dist;
uy /= dist;

/* compute circle radius and center */
il->ra = fabs(t1 - t2) / 2.0;
t1 = (t1 + t2) / 2.0;
il->px = CenterX[idx1] + t1 * ux;
il->py = CenterY[idx1] + t1 * uy;
}
}

static void intersectLines(const isolocus *il1, const isolocus *il2) {
double det, dx, dy, tt, xx, yy;

det = il1->vx * il2->vy - il1->vy * il2->vx;
/* If det==0, the planets are collinear. */
dx = il1->px - il2->px;
dy = il1->py - il2->py;
#if 1
/* These two computations should come out the same. */
tt = (dx * il2->vy - dy * il2->vx) / det;
xx = il1->px - tt * il1->vx;
yy = il1->py - tt * il1->vy;
#else
tt = (dy * il1->vx - dx * il1->vy) / det;
xx = il2->px + tt * il2->vx;
yy = il2->py + tt * il2->vy;
#endif
printf("%.2f %.2f\n", xx, yy);
}

static void intersectCircs(const isolocus *il1, const isolocus *il2) {
double dx, dy, dist, aa, bb, xx, yy;

dx = il2->px - il1->px;
dy = il2->py - il1->py;
dist = hypot(dx, dy);
aa = (dist * dist + il1->ra * il1->ra - il2->ra * il2->ra) / (2.0 * dist);
bb = il1->ra * il1->ra - aa * aa;
if (bb < 0.0) {
printf("No solution\n");
return;
}
bb = sqrt(bb) / dist;
aa /= dist;

xx = il1->px + aa * dx;
yy = il1->py + aa * dy;
if (xx - bb * dy<0)
printf("%.2f %.2f\n",
xx + bb * dy, yy - bb * dx);
else
printf("%.2f %.2f\n",
xx - bb * dy, yy + bb * dx);
/* Here dx,dy is rotated. */
}

static void doit(void) {
isolocus il1, il2;

computeIsolocus(0, 1, &il1);
computeIsolocus(0, 2, &il2);

if (il1.isLine) {
if (il2.isLine) {
intersectLines(&il1, &il2);
} else {
/* avoid writing intersectLineCirc */
computeIsolocus(1, 2, &il1);
intersectCircs(&il1, &il2);
}
} else {
if (il2.isLine) {
/* avoid writing intersectLineCirc */
computeIsolocus(1, 2, &il2);
}
intersectCircs(&il1, &il2);
}
}

int main(void) {
while (scanf("%lf %lf %lf %lf %lf %lf %lf %lf %lf",
{
if (Radius[0] == 0.0) break; /* input delimiter */
doit();
}

return 0;
}

/**************************************************************
Problem: 1293
User: zhblue
Language: C++