http://codeforces.com/gym/100379

首先说一个一般的方法,可以解决k阶线性齐次递推关系的通解的相邻两项之比的极限。
首先循环10遍后判断是否存在二者中至少有一个为0的情况,有就输出NO。
(10遍就够了,毕竟题目所给的都是整数)
若没有,记为递推式各项前面的系数
则由于

所以先把算出来,然后迭代1000次,结束后判断是否有即可。

但是二阶的递推是可以直接解出通解的,利用通解判断就行(见下方代码),复杂度O(1)。

int main()
{
    int a, b, g0, g1, delta;
    double x1, x2;
    SII(a, b), SII(g0, g1);
    if (g0 == 0 && g1 == 0) puts("NO");
    else
    {
        if (a == 0 || b == 0)
        {
            if (a == 0 && b == 0) puts("NO");
            else if (a == 0) /// b!=0
         {
                if (g0 == 0 || b * g0 * g0 != g1 * g1) puts("NO");
                else printf("YES\n%.8f\n", (double)g1 / g0);
            }
            else /// a!=0 && b==0
         {
                if (g1 == 0) puts("NO");
                else puts("YES"), PI(a);
            }
        }
        else
        {
            delta = a * a + 4 * b;
            if (delta < 0) puts("NO"); /// 通项与三角级数有关,无极限值
         else
            {
                puts("YES");
                if (delta == 0) printf("%.8f\n", a / 2.0);
                else
                {
                    x1 = ((double)a + sqrt((double)delta)) / 2.0;
                    x2 = ((double)a - sqrt((double)delta)) / 2.0;
                    /// 特判两线性无关解前面的常数为0的情况
                 if (fabs(g0 * x2 - g1) < eps) printf("%.8f\n", x2);/// c1==0
                 else if (fabs(g0 * x1 - g1) < eps) printf("%.8f\n", x1);/// c2==0
                 else printf("%.8f\n", fabs(x1) > fabs(x2) + eps ? x1 : x2);
                }
            }
        }
    }
    return 0;
}

Comments

comments powered by Disqus