Quantum Moochanics
플래티넘 III의견: 0
In her free time, Bessie likes to dabble in experimental physics. She has
recently discovered a pair of new subatomic particles, named mootrinos
and antimootrinos. Like standard
matter-antimatter pairs,
mootrinos and antimootrinos annihilate each other and disappear when they meet.
But what makes these particles unique is that they switch their direction of
motion (while maintaining the same speed) whenever Bessie looks at them.
For her latest experiment, Bessie has placed an even number \(N\)
(\(2 \leq N \leq 2 \cdot 10^5\))
of these particles in a line. The line starts with a mootrino on the left and
then alternates between the two types of particles, with the \(i\)-th particle
located at position \(p_i\) (\(0 \leq p_1 < \cdots < p_N \leq 10^{18}\)). Mootrinos
initially move right while antimootrinos initially move left, and
the \(i\)-th particle moves with a constant speed of \(s_i\) units per second
(\(1 \leq s_i \leq 10^9\)).
Bessie makes observations at the following times:
- First, \(1\) second after the start of the experiment.
- Then \(2\) seconds after the first observation.
- Then \(3\) seconds after the second observation.
- ...
- Then \(n + 1\) seconds after the \(n\)-th observation.
During each observation, Bessie notes down which particles have disappeared.
This experiment may take an extremely long time to complete, so Bessie would
like to first simulate its results. Given the experiment setup, help Bessie
determine when (i.e., the observation number) she will observe each
particle disappear! It may be shown that all particles will eventually
disappear.
Problem credits: Aryansh Shrivastava, Benjamin Qi
SCORING
- Input 3 satisfies \(N = 2\).
- Input 4 satisfies \(N \leq 2000\) and \(p_i \leq 10^4\) for all cows.
- Inputs 5-7 satisfy \(N \leq 2000\).
- Inputs 8-12 satisfy no additional constraints.
Problem credits: Aryansh Shrivastava, Benjamin Qi
Each input contains \(T\) (\(1\le T\le 10\)) independent test cases.
Each test case consists of three lines. The first line contains \(N\), the second
line contains \(p_1,\dots,p_N\), and the third line contains \(s_1\dots,s_N\).
It is guaranteed that the sum of all \(N\) does not exceed \(2\cdot 10^5\).
For each test case, output the observation number for each particle's
disappearance, separated by spaces.
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
평가 및 의견
Quantum Moochanics
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Quantum Moochanics