timus 1175. Strange Sequence 解题报告

时间：2021-10-26 16:00:59

1.题目描述：

1175. Strange Sequence

Time limit: 1.0 second
Memory limit: 2 MB
You have been asked to discover some important properties of one strange sequences set. Each sequence of the parameterized set is given by a recurrent formula:
Xn+1 = F(Xn-1, Xn),
where n > 1, and the value of F(X,Y) is evaluated by the following algorithm:
  1. find H = (A1*X*Y + A2*X + A3*Y + A4);
  2. if H > B1 then H is decreased by C until H ≤ B2;
  3. the resulting value of H is the value of function F.
The sequence is completely defined by nonnegative constants A1, A2, A3, A4, B1, B2 and C.
One may easily verify that such sequence possess a property that Xp+n = Xp+q+n for appropriate large enough positive integers p and q and for all n ≥ 0. You task is to find the minimal p and q for the property above to hold. Pay attention that numbers p and q are well defined and do not depend on way minimization is done.

Input

The first line contains seven integers: A1, A2, A3, A4, B1, B2 and C. The first two members of sequence (X1 and X2) are placed at the second line. You may assume that all intermediate values of H and all values of F fit in range [0..100000].

Output

An output should consist of two integers (p and q) separated by a space.

Sample

input output 
0 0 2 3 20 5 7

0 1
 
2 3

2.解题思路

题目要求确定p和q，我们先确定q再确定p，有了q只需要从x1，x2开始逐个尝试就能得出p。如何确定q呢？既然题目说了这个序列以q为循环节，我们可以假定序列在迭代足够多次之后就进入了循环，设这个次数为max。这样迭代max后再从1开始寻找q就可以啦~

3.代码：

#include <iostream>

#define max 300000

using namespace std;

int a1,a2,a3,a4,b1,b2,c,x1,x2;

int p,q;

int cal(int x, int y) {

    int h = a1*x*y+a2*x+a3*y+a4;

    if (h > b1) {

        while (h > b2) {

            h -= c;

        }

    }

    return h;

}

void iter(int& x, int& y) {

    int tmp = cal(x, y);

    x = y;

    y = tmp;

}

//假定迭代max次后处于稳定状态

//思路:迭代max次；继续迭代找到q；x1，x2迭代q次得到x3，x4；同时迭代直到x1==x3 && x2 == x4，找到p

int main() {

    cin >> a1 >> a2 >> a3 >> a4 >> b1 >> b2 >> c >> x1 >> x2;

    int i, tmp1, tmp2, tmp3, tmp4;

    tmp3 = x1;

    tmp4 = x2;

    for (i = ; i < max; i++) {

        iter(x1, x2);

    }

    tmp1 = x1;

    tmp2 = x2;

    q = ;

    iter(x1, x2);

    while (x1 != tmp1 || x2 != tmp2) {

        q++;

        iter(x1, x2);

    }

    tmp1 = tmp3;

    tmp2 = tmp4;

    iter(tmp1,tmp2);

    i = ;

    while (i != q) {

        i++;

        iter(tmp1, tmp2);

    }

    p = ;

    while (tmp1 != tmp3 || tmp2 != tmp4) {

        p++;

        iter(tmp1, tmp2);

        iter(tmp3, tmp4);

    }

    cout << p << " " << q << endl;

}

4.复杂度：

空间:O(1)

时间:O(p+q+max)

5.心得：

把这道题写出来，是因为我第一次尝试时思路是错的：把<x0,x1>作为一个pair，pos是迭代次数，用一个map<pair,pos> result存储，一直迭代<x0,x1>，递增pos，并把结果存入result，当重复插入时(x.pair == y.pair,x.pos < y.pos)，就求出了p，q: p = x.pos， q = y.pos - x.pos。

。。。

没错我当时就是这么写的，然后华丽丽的爆了内存。

这种做法的复杂度：

时间：O(p+q)

空间：O(p+q)

然而根据题目要求，空间限制2M，是很严格的。。以后一定要好好看题目。。

相关文章