比赛 |
2025.9.13 |
评测结果 |
AAAAAAAAAAAA |
题目名称 |
Transforming Pairs |
最终得分 |
100 |
用户昵称 |
xxz |
运行时间 |
0.150 s |
代码语言 |
C++ |
内存使用 |
3.79 MiB |
提交时间 |
2025-09-13 10:56:42 |
显示代码纯文本
#include<bits/stdc++.h>
#define int long long
using namespace std;
int t,a,b,c,d,op1,op2,flag,k,ans;
int tp(int a,int b,int c,int d){
if(a>c||b>d){
return -1;
}
if(a>c&&b==d||b>d&&a==c){
return -1;
}
if(a==c&&b==d)return 0;
return -2;
}
void dfs(int x,int y,int step){
if(x==c&&y==d){
cout<<step<<endl;
flag=1;
return;
}
if(tp(x+y,y,c,d)!=-1){
dfs(x+y,y,step+1);
}
if(tp(x,x+y,c,d)!=-1){
dfs(x,x+y,step+1);
}
return;
}
struct node{
int x,y,step;
}p;
int bfs(int x,int y){
flag=0;
int ans=0;
queue<node>q;
q.push({x,y,0});
while(!q.empty()){
p=q.front();q.pop();
if(tp(p.x,p.y,c,d)==0){
ans=p.step;
flag=1;
break;
}
if(tp(p.x+p.y,p.y,c,d)!=-1){
q.push({p.x+p.y,p.y,p.step+1});
}
if(tp(p.x,p.x+p.y,c,d)!=-1){
q.push({p.x,p.x+p.y,p.step+1});
}
}
return ans;
}
void solve(){
while(a!=c||b!=d){
if(c<a||d<b){
ans=-1;break;
}
if(c<d){
swap(c,d);
swap(a,b);
}
k=(c-a)/d;
ans+=k;
c-=max(k,1ll)*d;
}
return;
}
signed main(){
freopen("Transforming.in","r",stdin);freopen("Transforming.out","w",stdout);
cin>>t;
while(t--){
ans=0;
flag=0;
scanf("%lld%lld%lld%lld",&a,&b,&c,&d);
// if(!tp(a,b,c,d)){
// cout<<0<<endl;
// continue;
// }else if(tp(a,b,c,d)==-1){
// cout<<-1<<endl;
// continue;
// }
// int y=bfs(a,b);
// if(!flag)cout<<-1<<endl;
// else cout<<y<<endl;
solve();
cout<<ans<<endl;
}
return 0;
}