2019牛客网多校赛（第一场）题解

约定不等于承诺〃 2021-12-04 00:45 364阅读 0赞

### 官方题解：[https://ac.nowcoder.com/discuss/208642?type=101&order=0&pos=9&page=1][https_ac.nowcoder.com_discuss_208642_type_101_order_0_pos_9_page_1] ###

## A ： Equivalent Prefixes ##

### 题目链接 ： [https://ac.nowcoder.com/acm/contest/881/A][https_ac.nowcoder.com_acm_contest_881_A] ###

![20190719123116960.png][]

题解：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dpdGh1Yl8zOTUzMzQxNA_size_16_color_FFFFFF_t_70][]

#include <iostream>
    #include <cstring>
    #include <cstdlib>
    #include <stdio.h>
    #include <algorithm>
    #include <vector>
    #include <queue>
    #include <set>
    #include <stdlib.h>
    #include <math.h>
    #include <map>
    #include <string>
    #include <math.h>
    #include <stdlib.h>
    #include <iomanip>
    #include <list>
    #include <deque>
    #include <stack>
    #define ull unsigned long long
    #define ll long long
    #define INF 0x3f3f3f3f
    #define maxn 100005
    #define MAXN 1000010
    #define N 100050
    using namespace std;
    const ull inf = 1LL << 61;
    const long long mod=1e9+7;//注意两数相减加一个mod
    const double PI=acos(-1);
    const double eps=1e-5;
    double gcd(double a,double b)
    {
      return (!b)?a:gcd(b,(long long)a%(long long)b);
    }
    double lcm(double a,double b)
    {
      return a/gcd(a,b)*b;
    }
    int dp1[maxn][20];
    int dp2[maxn][20];
    int arr1[maxn];
    int arr2[maxn];
    bool check(int l,int r)
    {
      if(l>r) return 1;
      int k=log2(r-l+1);
      int r1=arr1[dp1[l][k]]<arr1[dp1[r-(1<<k)+1][k]]?dp1[l][k]:dp1[r-(1<<k)+1][k];
      int r2=arr2[dp2[l][k]]<arr2[dp2[r-(1<<k)+1][k]]?dp2[l][k]:dp2[r-(1<<k)+1][k];
      if(r1!=r2) return 0;
      return check(l,r1-1)&&check(r1+1,r);
    }
    int main()
    {
        //freopen("d:in.txt","r",stdin);
        //freopen("d:out.txt","w",stdout);
        priority_queue <int,vector<int>,less<int> > p1,p2;
        priority_queue <int,vector<int>,greater<int> > q;
     
        int n;
        while(~scanf("%d",&n))
        {
          for(int i=1;i<=n;i++) scanf("%d",&arr1[i]);
          for(int i=1;i<=n;i++) scanf("%d",&arr2[i]);
          for(int i=1;i<=n;i++) {dp1[i][0]=i;dp2[i][0]=i;}
          for(int j=1;(1<<j)<=n;j++)
            for(int i=1;i+(1<<j)-1<=n;i++)
              {
                int u,v;
                u=dp1[i][j-1];v=dp1[i+(1<<(j-1))][j-1];
                dp1[i][j]=arr1[u]<arr1[v]?u:v;
                u=dp2[i][j-1];v=dp2[i+(1<<(j-1))][j-1];
                dp2[i][j]=arr2[u]<arr2[v]?u:v;
              }
          int l=1,r=n+1;
          while(l<r-1)
          {
            int mid=(l+r)/2;
            if(check(1,mid)) l=mid;
            else r=mid;
          }
          cout<<l<<endl;
        }
        return 0;
     
    }

## B Integration  ##

题目链接：[https://ac.nowcoder.com/acm/contest/881/B][https_ac.nowcoder.com_acm_contest_881_B]

题目描述：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dpdGh1Yl8zOTUzMzQxNA_size_16_color_FFFFFF_t_70 1][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dpdGh1Yl8zOTUzMzQxNA_size_16_color_FFFFFF_t_70 2][]

### 题解：  ###

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dpdGh1Yl8zOTUzMzQxNA_size_16_color_FFFFFF_t_70 3][]

### 思路： [https://blog.csdn.net/qq\_41730082/article/details/96443875][https_blog.csdn.net_qq_41730082_article_details_96443875] ###

### c++代码： ###

#include<stdio.h>
    #include<string.h>
    #include<algorithm>
    #include<iostream>
    #include<queue>
    #include<math.h>
    #include<time.h>
    #include<vector>
    #include<set>
    #include<map>
    #include <assert.h>
    #include<stack>
    #define LL long long
    #define mem(a,b) memset(a,b,sizeof(a))
    using  namespace std;
    LL mod=1e9+7;
    const double PI=acos(-1.0);
    const double eps=1e-10;
    void quickread(){std::ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);}
    int lowbit(int x){return x&(-x);}
    LL a[1004];
    LL c[1004];
    LL quick(LL x,LL n)
    {
        LL ans=1;
        while(n)
        {
            if(n%2) ans=ans*x%mod;
            n/=2;
            x=x*x%mod;
        }
        return ans;
    }
    int main()
    {
       int n;
       while(~scanf("%d",&n))
       {
            for(int i=1;i<=n;i++ )scanf("%lld",&a[i]);
            for(int i=1;i<=n;i++)
            {
                LL sum=1;
                for(int j=1;j<=n;j++)
                {
                    if(i==j ) continue;
                    else{
                        sum=sum*((a[j]*a[j]%mod-a[i]*a[i]%mod)+mod)%mod;
                    }
                }
                sum=quick(sum,mod-2);
                c[i]=sum;
            }
            LL ans=0;
            for(int i=1;i<=n;i++)
            {
                ans=(ans+c[i]*quick(2*a[i],mod-2)%mod)%mod;
            }
            printf("%lld\n",(ans+mod)%mod);
       }
       return 0;
    }

## C :   Euclidean Distance ##

### 题目描述 ： ###

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dpdGh1Yl8zOTUzMzQxNA_size_16_color_FFFFFF_t_70 4][]

### 题解：  ###

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dpdGh1Yl8zOTUzMzQxNA_size_16_color_FFFFFF_t_70 5][]

### C++ 代码： ###

#include <bits/stdc++.h>
    using namespace std;
    #define debug(a) cout << #a": " << a << endl;
    #define mst(a, b) memset(a, b, sizeof(a))
    #define ALL(x) x.begin(), x.end()
    #define lc rt << 1
    #define rc rt << 1 | 1
    #define X first
    #define Y second
    inline int lowbit(int x) { return x & -x; }
    typedef long long LL;
    typedef unsigned long long ULL;
    typedef double db;
    typedef pair<int, int> pii;
    const int N = 1e4 + 10;
    const int M = 1e5 + 10;
    const int inf = 0x3f3f3f3f;
    const LL INF = 0x3f3f3f3f3f3f3f3fLL;
    const int mod = 1e9 + 7;
     
    LL a[N];
    LL pre[N];
     
    int main() {
    #ifdef purple_bro
        freopen("in.txt", "r", stdin);
    #endif
        ios::sync_with_stdio(false);
        cin.tie(0);
     
        int n, m;
     
        for (;cin >> n >> m;) {
            for (int i = 1; i <= n; i++)
                cin >> a[i];
     
            sort(a + 1, a + 1 + n, [](int a, int b) -> bool {
                    return a > b;
                 });
     
            pre[0] = -m;
     
            for (int i = 1; i <= n; i++)
                pre[i] = pre[i - 1] + a[i];
     
            int now = n;
     
            for (int i = 1; i < n; i++) if (pre[i] > a[i + 1] * i) {
                now = i;
                break;
            }
     
            LL t = pre[now] * pre[now];
            LL d = now;
            for (int i = now + 1; i <= n; i++)
                t += a[i] * a[i] * d;
            d *= m * m;
            LL gcd = __gcd(t, d);
            t /= gcd; d /= gcd;
            if (d == 1 || !t)
                cout << t << "\n";
            else
                cout << t << "/" << d << "\n";
        }
     
        return 0;
    }

## D:  Parity of Tuples ##

![2019071912382147.png][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dpdGh1Yl8zOTUzMzQxNA_size_16_color_FFFFFF_t_70 6][]

#include<cstdio>
    #include<algorithm>
    using namespace std;
    typedef long long ll;
    const ll mod=1e9+7;
    ll i,j,u,vv,n,m,k,a[11],kp,dp[1048576],inv2,v[1024],l[1024],pk,pt,cnt[1048576],pm;
    ll lowbit(ll p){return p&-p;}
    ll M(ll p)
    {
        if(p<0)return p+mod;
        if(p>=mod)return p-mod;
        return p;
    }
    ll pow(ll a,ll b)
    {
        ll ans=1;
        while(b)
        {
            if(b&1)ans=ans*a%mod;
            a=a*a%mod;
            b>>=1;
        }
        return ans;
    }
    int main()
    {
        inv2=pow(2LL,mod-2LL);
        cnt[0]=1;
        for(i=1;i<(1<<20);i++)cnt[i]=-cnt[i-lowbit(i)];
        while(scanf("%lld%lld%lld",&n,&m,&k)!=EOF)
        {
            //init();
            for(i=0;i<(1<<k);i++)dp[i]=0;
            pk=0;
            for(i=1;i<=n;i++)
            {
                v[0]=0;
                for(j=1;j<=m;j++)scanf("%lld",&a[j]),v[1<<(j-1)]=a[j];
                dp[0]+=1;l[0]=1;
                for(j=1;j<(1<<m);j++)
                {
                    kp=lowbit(j);
                    v[j]=v[j-kp]^v[kp];
                    l[j]=-l[j-kp];
                    dp[v[j]]+=l[j];
                    //printf("%lld %lld %lld\n",j,v[j],l[j]);
                }
            }
            for(i=0;i<(1<<k);i++)dp[i]=M(dp[i]*cnt[i]);
            for(i=0;i<k;i++)
            {
                for(j=0;j<(1<<k);j++)
                {
                    if(j&(1<<i))
                    {
                        u=dp[j];vv=dp[j-(1<<i)];
                        dp[j]=M(u+vv);
                        dp[j-(1<<i)]=M(vv-u);
                    }
                }
            }
            //for(i=0;i<(1<<k);i++)printf("%lld %lld\n",i,dp[i]);
            pm=pow(inv2,m);
            for(i=0,pt=1;i<(1<<k);i++,pt=pt*3%mod)pk^=dp[i]*pm%mod*pt%mod;
            printf("%lld\n",pk);
        }
        return 0;
    }

# #

## E : ABBA ##

![20190719123913620.png][]

样例：

20 36
    40 69
    100 1000
    1000 200
    200 99
    99 1
     
     
    1 2
    0 1dp1
    0 2dp1
    1 0dp1
    1 1dp2
    1 2dp3
    1 3dp4
    2 1dp3
    2 2dp6
    2 3dp10
    3 1dp4
    3 2dp10
    3 3dp20
     
     
    20 36
    677063087
    40 69
    357970915
    100 1000
    651709122
    1000 200
    946791934
    200 99
    568337085
    99 1
    554042848

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dpdGh1Yl8zOTUzMzQxNA_size_16_color_FFFFFF_t_70 7][]

#include <iostream>
    #include <cstring>
    using namespace std;
    #define MOD 1000000007
    int dp[3000][3000];
     
    int main()
    {
        int n, m;
        while(cin >> n >> m)
        {
            for(int i = 0; i <= n + m; ++i)
            {
                for(int j = 0; j <= n + m; ++j)
                {
                    dp[i][j] = 0;
                }
            }
            dp[0][0] = 1;
            for(int i = 1; i <= m; ++i)
            {
                dp[0][i] = 1;
            }
            for(int i = 1; i <= n; ++i)
            {
                dp[i][0] = 1;
            }
     
            for(int i = 1; i <= n + m; ++i)
            {
                for(int j = 1; j <= n + m; ++j)
                {
                    if(i <= n + j&&j <= m + i)
                        dp[i][j] = (dp[i - 1][j] + dp[i][j - 1])%MOD;
                }
            }
            cout << dp[n + m][n + m]<<endl;
        }
        return 0;
    }
    /*
    
    20 36
    40 69
    100 1000
    1000 200
    200 99
    99 1
     
     
    1 2
    0 1dp1
    0 2dp1
    1 0dp1
    1 1dp2
    1 2dp3
    1 3dp4
    2 1dp3
    2 2dp6
    2 3dp10
    3 1dp4
    3 2dp10
    3 3dp20
     
     
    20 36
    677063087
    40 69
    357970915
    100 1000
    651709122
    1000 200
    946791934
    200 99
    568337085
    99 1
    554042848
    */

## F  : Random Point in Trangle ##

![20190719124146102.png][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dpdGh1Yl8zOTUzMzQxNA_size_16_color_FFFFFF_t_70 8][]

#include <bits/stdc++.h>
      
    using namespace std;
      
    typedef long long ll;
      
    #ifdef iq
      mt19937 rnd(228);
    #else
      mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
    #endif
      
    int main() {
    #ifdef iq
      freopen("a.in", "r", stdin);
    #endif
      ios::sync_with_stdio(0);
      cin.tie(0);
      int x1, y1, x2, y2, x3, y3;
      while (cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3) {
        ll a = x2 - x1, b = y2 - y1;
        ll c = x3 - x1, d = y3 - y1;
        ll ans = abs(a * d - b * c);
        cout << ans * 11 << '\n';
      }
    }

## G : Substrings 2 ##

# #

## ![2019071912430495.png][] ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dpdGh1Yl8zOTUzMzQxNA_size_16_color_FFFFFF_t_70 9][] ##

#include<bits/stdc++.h>
    #define rep(i,x,y) for(auto i=(x);i<=(y);++i)
    #define dep(i,x,y) for(auto i=(x);i>=(y);--i)
    #define see(x) (cerr<<(#x)<<'='<<(x)<<endl)
    #define pb push_back
    #define fr first
    #define sc second
    using namespace std;
    typedef long long ll;
    typedef pair<int,int>pii;
    const int N=5e4+10;
    const int M=300;
    const ll mo=998244353;
    const ll D=18113219;
    const ll DL=181321;
    ll pw[M],s[N][M],nw[N][M];int n,m,b[N],l[N],r[N];
    inline bool cmp(int x,int y){
        rep(i,0,m)if(s[x][i]!=s[y][i]){
            rep(j,0,m){int p=m*i+j;
                if(x+p>n)return 1;
                if(y+p>n)return 0;
                int X=l[x+p]<x?0:l[x+p]-x+1;
                int Y=l[y+p]<y?0:l[y+p]-y+1;
                if(X<Y)return 1;
                if(X>Y)return 0;
            }
        }return 0;
    }
    void sol(){
        if(scanf("%d",&n)==EOF)exit(0);
        map<int,int>mp;m=sqrt(n)+1;
        rep(i,1,n){int x;
            scanf("%d",&x);
            if(mp[x])r[mp[x]]=i;
            l[i]=mp[x];r[i]=0;mp[x]=i;
        }
        rep(i,0,m)nw[n][i]=s[n][i]=0;
        s[n][0]=DL;
        dep(i,n-1,1){ll ls=DL;bool lf=0;
            rep(j,0,(n-i)/m){
                int p=i+(j+1)*m,c;
                nw[i][j]=(nw[i+1][j]*D+lf)%mo;lf=0;
                if(r[i]&&(r[i]-i)/m==j)(nw[i][j]+=pw[r[i]-(i+j*m)])%=mo;
                if(p<=n&&l[p]>i){
                    lf=1;(nw[i][j]+=mo-pw[m])%=mo;
                }
                if(p<=n){
                    if(l[p]<=i)c=DL;else c=DL+l[p]-i;
                }else c=0;
                s[i][j]=(s[i+1][j]*D+mo-c*pw[m]%mo+ls+nw[i][j])%mo;ls=c;
            }
        }
        rep(i,1,n)b[i]=i;
        sort(b+1,b+n+1,cmp);
        ll ans=n-b[1]+1;
        rep(i,2,n){int lcp=0;
            rep(j,0,m)if(s[b[i-1]][j]!=s[b[i]][j]){
                rep(k,0,m){int p=m*j+k;
                    if(max(b[i-1],b[i])+p>n||
                    (l[b[i-1]+p]<b[i-1]?0:l[b[i-1]+p]-b[i-1]+1)
                    !=(l[b[i]+p]<b[i]?0:l[b[i]+p]-b[i]+1))break;
                    ++lcp;
                }break;
            }else lcp+=m;
            ans+=n-b[i]-lcp+1;
        }
        printf("%lld\n",ans);
    }
    int main(){pw[0]=1;
        rep(i,1,M-1)pw[i]=pw[i-1]*D%mo;
        for(;;)sol();
    }

## H:  XOR  ##

### 具体题面：[https://blog.csdn.net/u013534123/article/details/96482572][https_blog.csdn.net_u013534123_article_details_96482572] ###

![20190719124400414.png][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dpdGh1Yl8zOTUzMzQxNA_size_16_color_FFFFFF_t_70 10][]

#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
     
    const int MN=63;
    const int mod=1000000007;
     
    ll num[100005];
     
     
    struct LinearBase {
        ll base[MN];
     
        bool flag;//该线性基能否表示0
        int cnt;
     
        void Copy(LinearBase b) {
            cnt=b.cnt;
            flag=b.flag;
            memcpy(base,b.base,sizeof(base));
        }
     
        void Clear() {
            cnt=0;
            flag=false;
            memset(base,0,sizeof( base));
        }
     
        //尝试向线性基中插入一个值
        void Insert(ll x) {
            for(int i=MN; ~i; i--)
                if(x&(1ll<<i))
                    if(!base[i]) {
                        base[i]=x;
                        cnt++;
                        return;
                    } else
                        x^=base[i];
            flag=true;
        }
     
        //判断该线性基能否表示x
        bool Check(ll x) {
            for(int i=MN; ~i; i--)
                if(x&(1ll<<i)) {
                    if(!base[i])
                        return false;
                    else
                        x^=base[i];
     
                }
            return true;
        }
    } B1,B2,B3;
     
    ll qpow(ll x,int n) {
        ll res=1;
        while(n) {
            if(n&1)
                res=res*x%mod;
            x=x*x%mod;
            n>>=1;
        }
        return res;
    }
     
    ll ans,p2;
     
    vector<int>B1ID;
     
    int main() {
    #ifdef Yinku
        freopen("Yinku.in", "r", stdin);
        //freopen("Yinku.out", "w", stdout);
    #endif // Yinku
        int n;
        while(~scanf("%d", &n)) {
     
            //cout<<"0.\n";
            for(int i=1; i<=n; i++) {
                scanf("%lld",&num[i]);
            }
     
            B1.Clear();
            B2.Clear();
            B1ID.clear();
     
            for(int i=1; i<=n; i++) {
                if(B1.Check(num[i])) {
                    B2.Insert(num[i]);
                } else {
                    B1.Insert(num[i]);
                    B1ID.push_back(i);
                }
            }
     
            ans=0;
            if(n!=B1.cnt) {
                p2=qpow(2,n-B1.cnt-1);
                ans+=p2*(n-B1.cnt)%mod;
            }
     
            for(ll i:B1ID) {
                B3.Copy(B2);
                for(ll j:B1ID) {
                    if(i!=j) {
                        B3.Insert(num[j]);
                    }
                }
                if(B3.Check(num[i])) {
                    //num[i]能被其他数表示
                    ans=(ans+p2)%mod;
                }
            }
     
            printf("%lld\n", ans);
        }
    }

## I题 ##

## Points  Division ##

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dpdGh1Yl8zOTUzMzQxNA_size_16_color_FFFFFF_t_70 11][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dpdGh1Yl8zOTUzMzQxNA_size_16_color_FFFFFF_t_70 12][]

#include<bits/stdc++.h>
    using namespace std;
    #define ll long long
    const int N=100010;
    const ll inf=1000000000000007ll;
     
    #define ls (x<<1)
    #define rs (x<<1|1)
    #define mid (l+r>>1)
    ll mx[N<<2],ad[N<<2];
    void pushup(int x){
        mx[x]=max(mx[ls],mx[rs]);
    }
    void pushdown(int x){
        ad[ls]+=ad[x];ad[rs]+=ad[x];
        mx[ls]+=ad[x];mx[rs]+=ad[x];
        ad[x]=0;
    }
    void build(int x,int l,int r){
        mx[x]=0;ad[x]=0;
        if(l==r)return ;
        build(ls,l,mid);build(rs,mid+1,r);
    }
    void add(int x,int l,int r,int L,int R,ll p){
        if(L>r||l>R)return ;
        if(L<=l&&r<=R){
            mx[x]+=p;ad[x]+=p;
            return ;
        }
        pushdown(x);
        add(ls,l,mid,L,R,p);
        add(rs,mid+1,r,L,R,p);
        pushup(x);
    }
    void change(int x,int l,int r,int pos,ll v){
        if(pos<l||pos>r)return ;
        if(l==r){
            mx[x]=max(mx[x],v);
            return ;
        }
        pushdown(x);
        change(ls,l,mid,pos,v);
        change(rs,mid+1,r,pos,v);
        pushup(x);
    }
    ll query(int x,int l,int r,int L,int R){
        if(L>r||l>R)return -inf;
        if(L<=l&&r<=R){
            return mx[x];
        }
        pushdown(x);
        return max(query(ls,l,mid,L,R),query(rs,mid+1,r,L,R));
    }
    int n;
    struct E{
        int x,y,a,b;
    }a[N];
    bool comp(E A,E B){
        if(A.x==B.x)return A.y>B.y;
        return A.x<B.x;
    }
    int len,b[N];
    int main(){
        while(~scanf("%d",&n)){
            len=0;
            for(int i=1;i<=n;i++){
                scanf("%d%d%d%d",&a[i].x,&a[i].y,&a[i].a,&a[i].b);
                b[++len]=a[i].y;
            }
            sort(b+1,b+len+1);
            len=unique(b+1,b+n+1)-b-1;
            for(int i=1;i<=n;i++)a[i].y=lower_bound(b+1,b+len+1,a[i].y)-b,a[i].y++;
            len++;
            build(1,1,len);
            sort(a+1,a+n+1,comp);
            for(int i=1;i<=n;i++){
                ll tmp=query(1,1,len,1,a[i].y);
                change(1,1,len,a[i].y,tmp+a[i].b);
                add(1,1,len,a[i].y+1,len,a[i].b);
                add(1,1,len,1,a[i].y-1,a[i].a);
            }
            printf("%lld\n",mx[1]);
        }
        return 0;
    }

## J题 ##

## Fraction Comparision ##

![20190719124654620.png][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dpdGh1Yl8zOTUzMzQxNA_size_16_color_FFFFFF_t_70 13][]

#include <bits/stdc++.h>
    #define For(i,x,y) for(int i=x; i<y; ++i)
    #define mem(x,y) memset(x,y,sizeof(x))
    #define PII pair<int,int>
    #define INF 0x3f3f3f3f
    #define ll long long
    #define se second
    #define fi first
    #define maxn 100005
    #define endl '\n'
    using namespace std;
    ll gcd(ll a ,ll b){
        if(b) return gcd(b,a%b);
        return a;
    }
    int main(){
        ll x,y,a,b;
        while(cin>>x>>a>>y>>b){
            if(x*b==y*a) cout<<'='<<endl;
            else {
                if(x/a>y/b) { cout<<'>'<<endl; continue; }
                if(x/a<y/b) { cout<<'<'<<endl; continue; }
                x%=a;
                y%=b;
                if(x*b>y*a) cout<<'>'<<endl;
                else cout<<'<'<<endl;
            }
        }
        return 0;
    }

[https_ac.nowcoder.com_discuss_208642_type_101_order_0_pos_9_page_1]: https://ac.nowcoder.com/discuss/208642?type=101&order=0&pos=9&page=1
[https_ac.nowcoder.com_acm_contest_881_A]: https://ac.nowcoder.com/acm/contest/881/A
[20190719123116960.png]: /images/20211203/3dddedcbbfcc4b0f8eb3cc03e81df997.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dpdGh1Yl8zOTUzMzQxNA_size_16_color_FFFFFF_t_70]: /images/20211203/df713d85926a490a8131e315756ce280.png
[https_ac.nowcoder.com_acm_contest_881_B]: https://ac.nowcoder.com/acm/contest/881/B
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dpdGh1Yl8zOTUzMzQxNA_size_16_color_FFFFFF_t_70 1]: /images/20211203/a1ccc899bab44b0d9189ede399c23c63.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dpdGh1Yl8zOTUzMzQxNA_size_16_color_FFFFFF_t_70 2]: /images/20211203/dd6b147ebdd340fa8a652f2602bf5549.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dpdGh1Yl8zOTUzMzQxNA_size_16_color_FFFFFF_t_70 3]: /images/20211203/defc7520c7ce4af39c1481b2200de12d.png
[https_blog.csdn.net_qq_41730082_article_details_96443875]: https://blog.csdn.net/qq_41730082/article/details/96443875
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dpdGh1Yl8zOTUzMzQxNA_size_16_color_FFFFFF_t_70 4]: /images/20211203/2721d16abc6848939263f17af8c80068.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dpdGh1Yl8zOTUzMzQxNA_size_16_color_FFFFFF_t_70 5]: /images/20211203/c507007e38f64deb907d635192f54e0c.png
[2019071912382147.png]: /images/20211203/bc95fece51c74e29adba79492a69eb04.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dpdGh1Yl8zOTUzMzQxNA_size_16_color_FFFFFF_t_70 6]: /images/20211203/d7a49184cdf4438d9de4269961ede093.png
[20190719123913620.png]: /images/20211203/10faa729b10741b1a18d9a2015cc4d5a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dpdGh1Yl8zOTUzMzQxNA_size_16_color_FFFFFF_t_70 7]: /images/20211203/9a2556b65adf4d3f9c4bedb24d06ccef.png
[20190719124146102.png]: /images/20211203/31a90c4458d54bc3935a4c48912864e5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dpdGh1Yl8zOTUzMzQxNA_size_16_color_FFFFFF_t_70 8]: /images/20211203/f4525c719b064d5bb194fb009089633d.png
[2019071912430495.png]: https://img-blog.csdnimg.cn/2019071912430495.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dpdGh1Yl8zOTUzMzQxNA_size_16_color_FFFFFF_t_70 9]: /images/20211203/e5eccc13a384423f83b1854e0ed28392.png
[https_blog.csdn.net_u013534123_article_details_96482572]: https://blog.csdn.net/u013534123/article/details/96482572
[20190719124400414.png]: /images/20211203/dd470d7bd604441bae5f9fd33f576514.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dpdGh1Yl8zOTUzMzQxNA_size_16_color_FFFFFF_t_70 10]: /images/20211203/99dbe3d1571744a8938af2b8944fbd33.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dpdGh1Yl8zOTUzMzQxNA_size_16_color_FFFFFF_t_70 11]: /images/20211203/515e2bca41db4077989dea41339fb6b5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dpdGh1Yl8zOTUzMzQxNA_size_16_color_FFFFFF_t_70 12]: /images/20211203/7673fc8cdc104a53a62060bab5871bbc.png
[20190719124654620.png]: /images/20211203/2808ec1f48b14e568bd181ae679a153a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dpdGh1Yl8zOTUzMzQxNA_size_16_color_FFFFFF_t_70 13]: /images/20211203/f58a9bfe6ad445b2b640c364f6472178.png