Eventually periodic sequence

Eventually periodic sequence

时间: 1ms        内存:128M

描述:

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

提示:

参考答案(内存最优[760]):

#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;
         }
      }
   }
}

参考答案(时间最优[8]):

/*
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
    radius of that planet. Each radius is positive.
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>

static double CenterX[3], CenterY[3], Radius[3];



/* 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 */
    double ra;     /* radius */
    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;

    il->isLine = Radius[idx1] == Radius[idx2];
    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 */
	rd = Radius[idx1] * dist;
	t1 = rd / (Radius[idx1] - Radius[idx2]);
	t2 = rd / (Radius[idx1] + Radius[idx2]);
	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",
	&CenterX[0], &CenterY[0], &Radius[0],
	&CenterX[1], &CenterY[1], &Radius[1],
	&CenterX[2], &CenterY[2], &Radius[2]) == 9)
    {
	if (Radius[0] == 0.0) break; /* input delimiter */
	doit();
    }

    return 0;
}

/**************************************************************
	Problem: 1293
	User: zhblue
	Language: C++
	Result: Wrong Answer
****************************************************************/

题目和答案均来自于互联网,仅供参考,如有问题请联系管理员修改或删除。

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注