鱼C论坛

 找回密码
 立即注册
查看: 132|回复: 9

[已解决]某知名 OJ 的模拟赛第一题

[复制链接]
发表于 7 天前 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
本帖最后由 zhangjinxuan 于 2024-7-10 21:55 编辑

题目描述

你需要做出一个药水,要用纯净水和魔法水做出 x:y 的比例(当然,这两种液体可以相互溶解)。

然而,你只有一个刻有模糊刻度线的量杯。更具体地说,量杯的容积为 a+b 毫升,只有一个明显的刻度标记,即 a 毫升。也就是说,她只能通过这个量杯精确地测量出 a 毫升或 a+b 毫升的液体。

现在你可以随时进行以下操作:

1.在量杯中注入纯净水或魔法水。
2.从量杯中倒出混合水,在量杯中保留 a毫升混合水。

要使混合物的比例为 x:y,操作1的最少次数是多少?或者说这是不可能的(这时候输出 -1)。

有 T 组测试数据,每行有 4 个整数表示 x,y,a,b(保证都在 long long  范围内)。

请对于每一组测试数据输出答案

样例输入与输出
4
3 5 1 1
1 24 1 4
12 113 3 2
8 117 2 3
4
3
-1
4

对于样例 1  的第一组数据,首先加满纯净水 ,此时比例为 1:0;使用倒出操作,再加入魔法水 ,此时比例 1:1;使用倒出操作,再加入纯净水 ,此时比例 3:1;使用倒出操作,再加入魔法水,此时比例 3:5。共 4 次第一种操作。


看题解没看懂,std 也写得很答辩,希望得到清晰的解答。
最佳答案
5 天前
我们可以发现,1、2操作必然是交替进行,不妨将一轮“1-2”操作记为一个循环。
对于在烧杯中一杯满的液体,记其中魔法水的浓度为 n (0 <= n <= 1),则每进行一次“1-2”循环,其中液体浓度将会变为 an/(a+b) 或 (an+b)/(a+b)。n的初始值为 0 或 1。
则将问题转化为:对于给定的 x, y, a, b, n (n=0或1),是否存在 k 次变化,每次令 n = an/(a+b) 或 n = (an+b)/(a+b),使得最后的 n 的值等于 x/y ?
注意到,x=0,即 x/y=0 时,一定成立。
剩下的就不知道了,但感觉这个思路应该可以
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 7 天前 | 显示全部楼层
好的!让我们来解决这个有趣的问题。我会尽量用简单易懂的方式解释。

### 题目解析
假设有两个水,纯净水和魔法水,你需要将它们混合成一定的比例 x:y。你有一个特殊的量杯,它可以精确测量 a 毫升或 a+b 毫升的液体。如果不能达到目标比例,需要输出 -1。

我们的基本操作有两种:
1. **注入**:可以直接注入 a 或 a+b 毫升的任意液体。
2. **倒出**:每次保留 a 毫升的混合液体,然后再注入新的液体。

### 思路
根据题目, 每次操作中, 杯子里要么是 `a` 毫升, 要么是 `a+b` 毫升。为了使比例达到 x:y, 你需要不断地通过倒出部分液体并重新加入新液体来调整比例。

大致可以分为以下步骤:
1. 首先检查是否存在解。
2. 如果存在解,计算最少的注入次数。

### 解决办法
1. 检查是否存在解的条件: 比例 `x : y` 可以化简到一个基本形式 `(gcd(x, y) * p) : (gcd(x, y) * q)`,之后确保 `(x - y)` 可以由 `a` 和 `b` 表达出来,也就是 `x` 和 `y` 的 `gcd` 是 `a` 和 `b` 的线性组合。

2. 最小操作次数: 我们每次倒出,并重新注入另一种液体,可以保证每次变化 `a` 或 `a+b`。所以实际过程就是找一个线性组合使得最终形成 `x : y` 比例。

具体详细实现如下:
def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a

def solve(x, y, a, b):
    g = gcd(x, y)
    x //= g
    y //= g
    
    if not gcd(a, b) == 1:
        return -1

    from math import ceil
    min_operations = ceil(max(x / a, y / b))
    
    return min_operations

T = int(input())
for _ in range(T):
    x, y, a, b = map(int, input().split())
    result = solve(x, y, a, b)
    print(result)

### 问题分解
对于每个测试数据,你需要:
1. 读取输入值 x, y, a, b。
2. 利用最大公约数 gcd 分解 x 和 y。
3. 检查 gcd(a, b) 是否是1,因为它说明了量杯 a 和 a+b 可以组成任何整数。

### 最后,幽默一下
"好吧,别看这题像魔法学校的炼药课,其实就是在玩水!只要合理安排时间,每天做个好单调的实验,就能轻松搞定这杯神奇的药水啦!"

希望这个解答能帮到你!加油,祝你成功地炼制出神奇的药水!
以上回复来自 FishC AI 小助理,如未能正确解答您的问题,请继续追问。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 6 天前 | 显示全部楼层
题目在哪?

评分

参与人数 1荣誉 +1 收起 理由
zhangjinxuan + 1 https://codeforces.com/gym/103729/proble

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 5 天前 | 显示全部楼层    本楼为最佳答案   
我们可以发现,1、2操作必然是交替进行,不妨将一轮“1-2”操作记为一个循环。
对于在烧杯中一杯满的液体,记其中魔法水的浓度为 n (0 <= n <= 1),则每进行一次“1-2”循环,其中液体浓度将会变为 an/(a+b) 或 (an+b)/(a+b)。n的初始值为 0 或 1。
则将问题转化为:对于给定的 x, y, a, b, n (n=0或1),是否存在 k 次变化,每次令 n = an/(a+b) 或 n = (an+b)/(a+b),使得最后的 n 的值等于 x/y ?
注意到,x=0,即 x/y=0 时,一定成立。
剩下的就不知道了,但感觉这个思路应该可以
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 5 天前 | 显示全部楼层
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 5 天前 | 显示全部楼层
tommyyu 发表于 2024-7-12 21:55
我们可以发现,1、2操作必然是交替进行,不妨将一轮“1-2”操作记为一个循环。
对于在烧杯中一杯满的液体 ...


感觉和进制有关,毕竟每一次都是 a+b 为被除数,然后原最近找到了,https://codeforces.com/gym/103729/problem/C
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 4 天前 | 显示全部楼层
我tm在洛谷找
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 前天 14:45 | 显示全部楼层
zhangjinxuan 发表于 2024-7-12 22:26
感觉和进制有关,毕竟每一次都是 a+b 为被除数,然后原最近找到了,https://codeforces.com/gym/103729 ...

《小马宝莉》
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 前天 20:27 | 显示全部楼层
你有思路了么
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 前天 21:47 | 显示全部楼层

好像先要约分再约去一个因数
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-7-17 03:40

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表