레이팅 미적용농부 존은 농장에서 \(N\) (\(1 \leq N \leq 2\cdot 10^5\))그루의 아스파라거스를 기르고 있다! 그런데 일부 식물들은 유전적 차이가 있어서, 어떤 식물은 다른 식물보다 빨리 자란다. \(i\)번째 식물의 초기 높이는 \(h_i\)인치이고, 하루가 지날 때마다 \(i\)번째 식물은 \(a_i\)인치씩 자란다.
농부 존은 어떤 식물을 다른 식물보다 더 좋아해서, 특정 식물이 다른 식물보다 더 크기를 원한다. 그는 \(0\)부터 \(N-1\)까지의 모든 정수를 포함하는 서로 다른 값들의 배열 \(t_1,\dots,t_N\)을 주고, \(i\)번째 식물보다 큰 식물이 정확히 \(t_i\)그루이기를 원한다. 농부 존의 요구가 만족되기까지 걸리는 최소 일수를 구하거나, 불가능함을 판별하라.
문제 제공: Chongtian Ma
채점 방식
- 입력 3: \(N \le 2\)
- 입력 4-5: \(N \le 50\)이고 \(a_i, h_i \le 10^3\)
- 입력 6-8: \(N \le 10^3\)
- 입력 9-13: 추가 제약 조건 없음.
문제 제공: Chongtian Ma
첫째 줄에 독립적인 테스트 케이스의 수를 나타내는 정수 \(T\)가 주어진다 \((1 \leq T \leq 10)\).
각 테스트 케이스의 첫째 줄에 정수 \(N\)이 주어진다.
둘째 줄에 \(i\)번째 식물의 초기 높이(인치)를 나타내는 \(N\)개의 정수 \(h_i\) \((1 \leq h_i \leq 10^9)\)가 주어진다.
셋째 줄에 \(i\)번째 식물이 하루에 자라는 길이(인치)를 나타내는 \(N\)개의 정수 \(a_i\) \((1 \leq a_i \leq 10^9)\)가 주어진다.
넷째 줄에 농부 존이 주는 배열을 나타내는 서로 다른 \(N\)개의 정수 \(t_i\)가 주어진다.
모든 테스트 케이스에 대한 \(N\)의 합은 \(2\cdot 10^5\)를 넘지 않음이 보장된다.
\(T\)개의 줄에 걸쳐 각 테스트 케이스의 답을 서로 다른 줄에 출력한다. 불가능하다면 \(-1\)을 출력한다.
이 문제에서 다루는 정수가 매우 클 수 있으므로 64비트 정수 자료형(예: C/C++의 "long long")이 필요할 수 있음에 유의하라.
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