Simultaneous Floor

AtCoder
IDagc063_f
Time4000ms
Memory256MB
Difficulty
You are given pairs of non-negative integers $a = (a_1,a_2)$ and $b = (b_1,b_2)$. You can perform the following operation on the pair $a$ any number of times, possibly zero. * Operation: Choose a **positive real number** $x$. Replace $a = (a_1,a_2)$ with $(\lfloor a_1x\rfloor, \lfloor a_2x\rfloor)$. Your objective is to make the pair $a$ equal the pair $b$. Determine whether it is achievable. If it is, find the minimum number of times you must perform the operation to achieve it. You have $T$ test cases to solve. ## Constraints * $1\leq T\leq 10^5$ * $0\leq a_1, a_2, b_1, b_2 \leq 10^9$ ## Input The input is given from Standard Input in the following format: $T$ $\text{case}_1$ $\vdots$ $\text{case}_T$ Each test case is given in the following format: $a_1$ $a_2$ $b_1$ $b_2$ [samples]
Samples
Input #1
7
2 3 1 1
1 1 2 3
3 2 9 8
12 34 56 78
56 78 12 34
87 65 43 21
43 21 87 65
Output #1
1
-1
3
-1
4
2
-1

For the first test case, here is one optimal solution.

*   Initially, $a = (2,3)$.
*   Perform the operation with $x = 0.6$, replacing $a$ with $(\lfloor 1.2 \rfloor, \lfloor 1.8\rfloor) = (1,1)$.

For the third test case, here is one optimal solution.

*   Initially, $a = (3,2)$.
*   Perform the operation with $x = 1.5$, replacing $a$ with $(4,3)$.
*   Perform the operation with $x = 1.7$, replacing $a$ with $(6,5)$.
*   Perform the operation with $x = 1.6$, replacing $a$ with $(9,8)$.
Input #2
9
5 5 5 5
5 5 3 3
3 9 0 2
3 9 0 3
0 3 3 9
3 0 2 0
5 2 0 0
0 0 5 2
0 0 0 0
Output #2
0
1
1
2
-1
1
1
-1
0
API Response (JSON)
{
  "problem": {
    "name": "Simultaneous Floor",
    "description": {
      "content": "You are given pairs of non-negative integers $a = (a_1,a_2)$ and $b = (b_1,b_2)$. You can perform the following operation on the pair $a$ any number of times, possibly zero. *   Operation: Choose a *",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 4000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "agc063_f"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You are given pairs of non-negative integers $a = (a_1,a_2)$ and $b = (b_1,b_2)$. You can perform the following operation on the pair $a$ any number of times, possibly zero.\n\n*   Operation: Choose a *...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments