CF 177E1 - Space Voyage
The voyage is defined by a fixed sequence of planets. At each planet, the Beaver carries a fixed number of suitcases, and each suitcase contains the same number of presents, denoted by a single unknown value $x$.
Rating: 1700
Tags: binary search
Solve time: 25s
Verified: no
Solution
Problem Understanding
The voyage is defined by a fixed sequence of planets. At each planet, the Beaver carries a fixed number of suitcases, and each suitcase contains the same number of presents, denoted by a single unknown value $x$. So the total number of presents loaded at planet $i$ is $a_i \cdot x$, and the total number carried across the whole trip is $(\sum a_i)\cdot x$.
Once he arrives at a planet, the behavior is deterministic. The first day is always spent acclimating, so it contributes exactly one day regardless of anything else. Starting from the second day, each day he distributes $b_i$ presents to citizens. This continues as long as he can still fully satisfy the next day’s requirement. If at the start of a day he has fewer than $b_i$ presents left, he stops distributing and leaves immediately. The remaining presents are discarded.
So for each planet, the number of days spent there depends only on how many full batches of $b_i$ presents can be repeatedly given after the initial arrival day. The total travel time is the sum of these per-planet durations, and flights take zero time.
The task is to count how many positive integers $x$ make the total number of days across all planets exactly equal to a given value $c$. If there are infinitely many such $x$, the answer is $-1$.
The constraints make brute enumeration over $x$ impossible. Since $x$ can be up to $10^9$ implicitly (and even larger ranges are possible), any solution depending on iterating over all candidates is ruled out. Similarly, computing the total number of days must be done in logarithmic or constant time per planet for each evaluation, otherwise a nested dependence on $n$ and $x$ would be too slow.
A subtle edge case appears when some planet has $a_i = 0$. In that case, no presents are ever delivered there, so the Beaver always leaves immediately after the first day. For example, if a single planet has $a_1 = 0, b_1 = 5$, then regardless of $x$, the trip takes exactly 1 day. This introduces the possibility that the answer is infinite when all planets behave independently of $x$, or when the total duration becomes constant.
Another edge case arises from planets where $a_i \cdot x < b_i$, meaning the Beaver cannot even