Cowntact Tracing 2
브론즈 II의견: 0
Farmer John has \(N\) cows in a line (\(1 \leq N \leq 3\cdot 10^5\)). Unfortunately,
there is a sickness spreading throughout.
Initially, some cows start off infected. Every night, an infected cow spreads
the sickness to the cows on their left and right (if they exist). Once a cow is
infected, she stays infected.
After some amount of nights, Farmer John realizes that the issue has gotten out
of control, so he tests his cows to determine who has the sickness. Find the
minimum number of cows that could have started with the sickness.
Problem credits: Suhas Nagar
SCORING
- Inputs 3-7: \(N \le 1000\)
- Inputs 8-12: No additional constraints.
Problem credits: Suhas Nagar
The first line contains \(N\), the number of cows that Farmer John has.
The next line contains an \(N\) character bitstring of only \(1\)s and \(0\)s where a
\(1\) represents an infected cow and a \(0\) represents an uninfected cow after some
number of nights.
Output a single integer: the minimum number of cows that could have started
with the sickness.
5
111111Suppose the middle cow was the only cow to start off infected. Then the cows
would be infected in the following order:
0 nights: 00100 (the third cow is initially infected)
1 night: -> 01110 (the second and fourth cows are now infected)
2 nights: -> 11111 (the first and fifth cows are now infected)
3 nights: -> 11111 (all cows already were infected, so no additional cows are infected)
-> ...
After two or more nights, the final state of the cows would look like the input.
There are many other initial states and number of nights that could have
produced the input state, such as:
0 nights: 10001
1 night: -> 11011
2 nights: -> 11111
or:
0 nights: 01001
1 night: -> 11111
or:
0 nights: 01000
1 night: -> 11100
2 nights: -> 11110
3 nights: -> 11111
All of these initial states contain at least one infected cow.
6
0111014The only initial state and number of nights that could have led to this final
state is if no nights have passed and each of the four infected cows in the
input started off with the sickness.
riseoj 작성
출처 올림피아드 > USACO > 2023-2024 > December > Bronze
평가 및 의견
Cowntact Tracing 2
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Cowntact Tracing 2