Transforming Pairs
골드 I의견: 0
Bessie the brilliant bovine has discovered a new fascination—mathematical
magic! One day, while trotting through the fields of Farmer John’s ranch, she
stumbles upon two enchanted piles of hay. The first pile contains \(a\) bales, and
the second pile contains \(b\) bales (\(1\le a,b\le 10^{18}\)).
Next to the hay, half-buried in the dirt, she discovers an ancient scroll. As
she unfurls it, glowing letters reveal a prophecy:
*To fulfill the decree of the Great Grasslands, the chosen one must transform
these two humble hay piles into exactly \(c\) and \(d\) bales—no more, no less.
*
Bessie realizes she can only perform the following two spells:
- She can magically conjure new bales to increase the first pile’s size by the amount currently in the second pile.
- She can magically conjure new bales to increase the second pile’s size by the amount currently in the first pile.
She must perform these operations sequentially, but she can perform them any
number of times and in any order. She must reach exactly \(c\) bales in the first
pile and \(d\) bales in the second pile
(\(1\le c,d\le 10^{18}\)).
For each of \(T\) (\(1\le T\le 10^4\)) independent test cases, output the minimum
number of operations needed to fulfill the prophecy, or if it is impossible to
do so, output -1.
Problem credits: Benjamin Qi
SCORING
- Inputs 3-4: \(\max(c, d) \le 20 \cdot\min(a, b)\)
- Inputs 5-7: \(T \le 10\) and \(a,b,c,d\le 10^6\)
- Inputs 8-12: No additional constraints
Problem credits: Benjamin Qi
The first line contains \(T\).
The next \(T\) lines each contain four integers \(a,b,c,d\).
Output \(T\) lines, the answer to each test case.
4
5 3 5 2
5 3 8 19
5 3 19 8
5 3 5 3-1
3
-1
0In the first test case, it is impossible since \(b>d\) initially, but operations
can only increase \(b\).
In the second test case, initially the two piles have \((5, 3)\) bales. Bessie
can first increase the first pile by the amount in the second pile, resulting in
\((8, 3)\) bales. Bessie can then increase the second pile by the new amount in
the first pile, and do this operation twice, resulting in \((8, 11)\) and finally
\((8, 19)\) bales. This matches \(c\) and \(d\) and is the minimum number of
operations to get there.
Note that the third test case has a different answer than the second because \(c\)
and \(d\) are swapped (the order of the piles matters).
In the fourth test case, no operations are necessary.
1
1 1 1 1000000000000000000999999999999999999riseoj 작성
출처 올림피아드 > USACO > 2024-2025 > February > Silver
평가 및 의견
Transforming Pairs
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Transforming Pairs