레이팅 미적용베시는 여가 시간에 실험 물리학을 즐긴다. 최근에 베시는 무트리노(mootrino)와 반무트리노(antimootrino)라는 새로운 아원자 입자 쌍을 발견했다. 표준적인 물질-반물질 쌍처럼 무트리노와 반무트리노는 서로 만나면 쌍소멸하여 사라진다. 그런데 이 입자들이 특별한 점은, 베시가 그들을 관측할 때마다 (같은 속력을 유지한 채) 운동 방향을 반대로 바꾼다는 것이다.
최근 실험에서 베시는 이 입자들을 짝수 개인 \(N\) (\(2 \leq N \leq 2 \cdot 10^5\))개만큼 일직선 위에 놓았다. 줄은 왼쪽의 무트리노로 시작해 두 종류의 입자가 번갈아 나타나며, \(i\)번째 입자는 위치 \(p_i\)에 있다 (\(0 \leq p_1 < \cdots < p_N \leq 10^{18}\)). 무트리노는 처음에 오른쪽으로, 반무트리노는 처음에 왼쪽으로 움직이며, \(i\)번째 입자는 초당 \(s_i\)단위의 일정한 속력으로 움직인다 (\(1 \leq s_i \leq 10^9\)).
베시는 다음 시각들에 관측을 한다.
- 먼저 실험 시작 \(1\)초 후.
- 그다음 첫 번째 관측에서 \(2\)초 후.
- 그다음 두 번째 관측에서 \(3\)초 후.
- ...
- 그다음 \(n\)번째 관측에서 \(n + 1\)초 후.
각 관측 때 베시는 어떤 입자들이 사라졌는지 기록한다.
이 실험은 끝나기까지 엄청나게 오래 걸릴 수 있으므로, 베시는 먼저 결과를 시뮬레이션하고 싶다. 실험 설정이 주어질 때, 각 입자가 사라진 것이 언제(즉, 몇 번째 관측에서) 관측되는지 베시가 알아내도록 도와주자! 모든 입자가 결국 사라짐을 보일 수 있다.
출제: Aryansh Shrivastava, Benjamin Qi
배점
- 입력 3: \(N = 2\).
- 입력 4: \(N \leq 2000\)이고 모든 입자에 대해 \(p_i \leq 10^4\).
- 입력 5-7: \(N \leq 2000\).
- 입력 8-12: 추가 제약 없음.
출제: Aryansh Shrivastava, Benjamin Qi
각 입력은 \(T\) (\(1\le T\le 10\))개의 독립적인 테스트 케이스를 포함한다.
각 테스트 케이스는 세 줄로 이루어진다. 첫째 줄에 \(N\), 둘째 줄에 \(p_1,\dots,p_N\), 셋째 줄에 \(s_1\dots,s_N\)이 주어진다.
모든 \(N\)의 합이 \(2\cdot 10^5\)를 넘지 않음이 보장된다.
각 테스트 케이스마다, 각 입자가 사라지는 관측 번호를 공백으로 구분하여 출력한다.
4
2
1 11
1 1
2
1 12
1 1
2
1 11
4 6
2
1 11
4 59 9
11 11
1 1
3 3For the first test, Bessie observes the following during the first \(8\)
observations:
- The mootrino (initially moving right) appears at positions \(2 \rightarrow 0 \rightarrow 3 \rightarrow -1 \rightarrow 4 \rightarrow -2 \rightarrow 5 \rightarrow -3\).
- The antimootrino (initially moving left) appears at positions \(10 \rightarrow 12 \rightarrow 9 \rightarrow 13 \rightarrow 8 \rightarrow 14 \rightarrow 7 \rightarrow 15\).
Then right at observation \(9\), the two particles meet at position \(6\) and
annihilate each other.
For the second test, the antimootrino starts \(1\) additional unit to the right,
so the two particles meet at position \(6.5\) half a second before observation
\(11\).
Note that we only care about observation numbers, not times or positions.
2
4
1 3 5 8
1 1 1 1
4
1 4 5 8
1 1 1 11 1 3 3
7 2 2 7For the first test:
- The two leftmost particles meet at position \(2\) right at observation \(1\).
- The two rightmost particles meet at position \(6.5\) half a second before observation \(3\).
riseoj 작성
출처 올림피아드 > USACO > 2023-2024 > February > Gold