游游的正整数

[编程题]游游的正整数

热度指数：202 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

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

输入描述:

共有组询问。
每组询问输入四个正整数。

输出描述:

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

示例1

输入

输出

1 2
-1
2 4

说明

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

算法知识视频讲解

Python

yq19

n = int(input())
for _ in range(n):
    a, b, l, r = map(int, input().split())
    m = b - a

    result = [-1, -1]

    maxcnt = m // l
    
    mincnt = m // r
    if m % r != 0:
        mincnt += 1
    
    if m >= mincnt * l and m <= mincnt * r and m >= maxcnt * l and m <=maxcnt * r:
        print(mincnt, maxcnt)
    else:
        print(-1)

编辑于 2023-10-08 19:49:25 回复(0)