Farmer John Actually Farms
브론즈 II의견: 0
Farmer John is growing \(N\) (\(1 \leq N \leq 2\cdot 10^5\)) plants of asparagus on
his farm! However some of his plants have genetic differences, so some plants
will grow faster than others. The initial height of the \(i\)th plant is \(h_i\)
inches, and after each day, the \(i\)th plant grows by \(a_i\) inches.
FJ likes some of his plants more than others, and he wants some specific plants
to be taller than others. He gives you an array of distinct values
\(t_1,\dots,t_N\) containing all integers from \(0\) to \(N-1\) and he wants the \(i\)th
plant to have exactly \(t_i\) other plants that are taller than it. Find the
minimum number of days so that FJ's request is satisfied, or determine that it
is impossible.
Problem credits: Chongtian Ma
SCORING
- Input 3: \(N \le 2\)
- Inputs 4-5: \(N \le 50\) and \(a_i, h_i \le 10^3\)
- Inputs 6-8: \(N \le 10^3\)
- Inputs 9-13: No additional constraints.
Problem credits: Chongtian Ma
The first will consist of an integer \(T\), denoting the number of independent
test cases \((1 \leq T \leq 10)\).
The first line of each test case consists of an integer \(N\).
The second line consists of \(N\) integers \(h_i\) \((1 \leq h_i \leq 10^9)\) denoting
the initial height of the \(i\)th plant in inches.
The third line consists of \(N\) integers \(a_i\) \((1 \leq a_i \leq 10^9)\) denoting
the number of inches the \(i\)th plant grows each day.
The fourth line consists of \(N\) distinct integers \(t_i\) denoting the array that
FJ gives you.
It is guaranteed that the sum of \(N\) over all test cases does not exceed
\(2\cdot 10^5\).
Output \(T\) lines, the answer to each test case on a different line. If it is not
possible, output \(-1\).
Note that the large size of integers involved in this problem may require the
use of 64-bit integer data types (e.g., a "long long" in C/C++).
6
1
10
1
0
2
7 3
8 10
1 0
2
3 6
10 8
0 1
2
7 3
8 9
1 0
2
7 7
8 8
0 1
2
7 3
8 8
1 00
3
2
5
-1
-1In the first sample input, there are 6 test cases.
In the first test case, there is only one plant, so the condition is satisfied
on day 0.
In the second test case, we need the first plant to be shorter than the second
plant. After day 1, the heights are 15 and 13. After day 2, the heights are
both 23. After day 3, the heights are 31 and 33, and that's the first day in
which the condition is satisfied.
The third and fourth test cases are similar to the second.
In the fifth test case, both plants start with an initial height of 7 and a
growth rate of 8. So they will always have identical heights, and therefore the
condition is never satisfied.
In the sixth test case, the condition is not satisfied initially and the growth
rates are the same. So the condition can never be satisfied.
2
5
7 4 1 10 12
3 4 5 2 1
2 1 0 3 4
5
4 10 12 7 1
3 1 1 4 5
2 4 3 1 04
7In the second sample input, there are 2 test cases.
In the first test case, the final heights after day 4 are 19, 20, 21, 18, 16.
In the second test case, the final heights after day 7 are 25, 17, 19, 35, 36.
riseoj 작성
출처 올림피아드 > USACO > 2023-2024 > December > Bronze
평가 및 의견
Farmer John Actually Farms
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Farmer John Actually Farms