列表

详情


NC257433. 游游的正整数

描述

游游拿到了一个正整数a,她每次操作可以选择将a加上x,但必须满足l\leq x \leq r。游游希望操作结束后a恰好等于b。游游想知道,最少需要多少次操作,最多需要多少次操作?

输入描述

共有t组询问。
每组询问输入四个正整数a,b,l,r
1\leq t \leq 10^4
1\leq l \leq r \leq 10^9
1\leq a \leq b \leq 10^9

输出描述

对于每组询问,输出一行答案。
如果无论如何都不能让a等于b,则输出-1。
否则输出两个整数,分别代表最少操作次数和最多操作次数。

示例1

输入:

3
1 6 2 5
1 4 2 2
2 10 2 6

输出:

1 2
-1
2 4

说明:

第一组询问,操作一次的方案:直接使a加5。操作2次的方案:先加2再加3。
第二组询问,由于只能加2,显然无法使得1变成4。
第三组询问,操作2次的方案:先加3再加5(方案不唯一)。操作4次的方案:加4次2。

原站题解

上次编辑到这里,代码来自缓存 点击恢复默认模板

C++(g++ 7.5.0) 解法, 执行用时: 47ms, 内存消耗: 508K, 提交时间: 2023-08-13 21:16:45

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll a,b,l,r,t,q;
int main(){
    cin>>t;
    while(t--){
        cin>>a>>b>>l>>r;
        q=(b-a)/l;
        if(r*q<(b-a)) cout<<-1<<'\n';
        else cout<<(b-a-1+r)/r<<" "<<(b-a)/l<<"\n";
    }
    return 0;
}

Python3 解法, 执行用时: 219ms, 内存消耗: 4696K, 提交时间: 2023-08-13 23:02:13

import math

T = int(input())

for _ in range(T):
    a, b, l, r = map(int,input().split())
    num = b-a
    min_num = math.ceil(num/r)
    max_num = math.floor(num/l)
    if min_num > max_num:
        print(-1)
    else:
        print(min_num,max_num)

C++(clang++ 11.0.1) 解法, 执行用时: 47ms, 内存消耗: 568K, 提交时间: 2023-08-14 09:49:50

#include<bits/stdc++.h>
using namespace std;
int main()
{
    long long t,a,b,l,r,c;
    cin>>t;
    while(t--)
    {
        cin>>a>>b>>l>>r;
        c=b-a;
        if(c/l*(r-l)<c%l)cout<<-1<<endl;
        else cout<<(c+r-1)/r<<' '<<c/l<<endl;
    }
}

pypy3 解法, 执行用时: 163ms, 内存消耗: 26984K, 提交时间: 2023-08-13 20:33:52

import sys
input = sys.stdin.readline

for _ in range(int(input())):
    a, b, l, r = map(int, input().split())
    diff = b - a
    mn, mx = (diff + r - 1) // r, diff // l
    if mx < mn:
        print(-1)
    else:
        print(mn, mx)

上一题