P13117 [GCJ 2019 #2] New Elements: Part 2

Rigel · 2026-01-31 12:03:07 · 题解

题意

给定 \mathbf{N} 组 (\mathbf{C_i},\mathbf{J_i})，你需要找到一组 (x,y)，满足：

思路

首先将式子化简：

令 p \gets \mathbf{C_i} - \mathbf{C_{i+1}}，q \gets \mathbf{J_{i+1}} - \mathbf{J_i}，则有：

设 \dfrac{x}{y} \in (l,r)。

初始时 l \gets 0, r \gets +\infin，即 \dfrac{x}{y} \in (0,+\infin)。

考虑 p 与 q 的正负性。

• - $q<0$。此时 $\dfrac{q}{p} > 0$，$\dfrac{x}{y} > \dfrac{q}{p}$ 为有效的限制条件。若 $l < \dfrac{q}{p}$，则令 $l \gets \dfrac{q}{p}$。 - $q \ge 0$。此时 $\dfrac{q}{p} \le 0$，$\dfrac{x}{y} > \dfrac{q}{p}$ 显然成立。
• - $q<0$。无解。 - $q>0$。符合条件。
• - $q \le 0$。此时 $\dfrac{q}{p} \le 0$，$\dfrac{x}{y} < \dfrac{q}{p}$ 不可能成立，无解。 - $q>0$。此时 $\dfrac{q}{p} > 0$，$\dfrac{x}{y} < \dfrac{q}{p}$ 为有效的限制条件。若 $r > \dfrac{q}{p}$，则令 $r \gets \dfrac{q}{p}$。

若最后 l \ge r，则无解。

此时我们得到了 \dfrac{x}{y} \in (l,r) 的限制。

设 l = \dfrac{A}{B}，r = \dfrac{C}{D}。

则 \dfrac{A}{B} < \dfrac{x}{y} < \dfrac{C}{D}。

然后就可以用 P5179 的方法做了。

具体地说，考虑在 Stern-Brocot 树上二分。

初始时左边界为 \dfrac{0}{1}，右边界为 \dfrac{1}{0}，分别代表 0 与 +\infin。

设当前 \dfrac{a}{b} \le \dfrac{A}{B} < \dfrac{C}{D} \le \dfrac{c}{d}。

向右子结点连续移动 k 次后，左边界收缩至 \dfrac{a+kc}{b+kd}。

而 \dfrac{a+kc}{b+kd} \le \dfrac{A}{B}，解得 k \le \dfrac{bA-aB}{cB-dA}。

向左子结点连续移动 k 次后，右边界收缩至 \dfrac{ka+c}{kb+d}。

而 \dfrac{C}{D} \le \dfrac{ka+c}{kb+d}，解得 k \le \dfrac{cD-dC}{bC-aD}。

当 \dfrac{A}{B} < \dfrac{a+c}{b+d} < \dfrac{C}{D} 时终止二分，此时 \dfrac{a+c}{b+d} 即为所求的 \dfrac{x}{y}。

根据 Stern-Brocot 树的性质可知这个 \dfrac{x}{y} 为符合条件的最小既约分数。

Code

#include<bits/stdc++.h>
#define int long long

const int N=15;

using namespace std;

int T,n;

int _c[N],_j[N];

int tim;

struct _frac{
    int x,y;
    _frac(int _x,int _y){x=_x,y=_y;}
    bool operator<(const _frac &b)const{return x*b.y<y*b.x;}
    bool operator==(const _frac &b)const{return x*b.y==y*b.x;}
};

inline int read(){
    int ret=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9')ret=ret*10+(ch&15),ch=getchar();
    return ret*f;
}

void _solve(){
    tim++;
    n=read();
    for(int i=1;i<=n;i++)_c[i]=read(),_j[i]=read();
    printf("Case #%lld: ",tim);
    _frac l=_frac(0,1),r=_frac(1,0);
    for(int i=1;i^n;i++){
        int p=_c[i]-_c[i+1],q=_j[i+1]-_j[i];
        if(p<0){
            if(q<0){
                p=-p,q=-q;
                int g=__gcd(p,q);
                p=p/g,q=q/g;
                if(l<_frac(q,p))l=_frac(q,p);
            }
            if(q>=0)continue;
        }
        if(p==0){
            if(q<0){printf("IMPOSSIBLE\n");return;}
            if(q>0)continue;
        }
        if(p>0){
            if(q<=0){printf("IMPOSSIBLE\n");return;}
            if(q>0){
                int g=__gcd(p,q);
                p=p/g,q=q/g;
                if(_frac(q,p)<r)r=_frac(q,p);
            }
        }
    }
    if(r<l||l==r){printf("IMPOSSIBLE\n");return;}
    int a=0,b=1,c=1,d=0;
    int A=l.x,B=l.y,C=r.x,D=r.y;
    bool f=1;
    while(!(_frac(A,B)<_frac(a+c,b+d)&&_frac(a+c,b+d)<_frac(C,D))){
        if(f){
            int k=(b*A-a*B)/(c*B-d*A);
            if(!k){f^=1;continue;}
            a+=k*c;
            b+=k*d;
        }else{
            int k=(c*D-d*C)/(b*C-a*D);
            c+=k*a;
            d+=k*b;
        }
        f^=1;
    }
    printf("%lld %lld\n",a+c,b+d);
}

signed main(){
    T=read();
    while(T--)_solve();
    return 0;
}