레이팅 미적용*참고: 이 문제의 시간 제한과 메모리 제한은 3초와 512MB로, 각각 기본의 1.5배와 2배이다.*
농부 존의 \(N\)(\(1 \leq N \leq 10^5\))마리 소들은 각자 비트 문자열('0'과 '1'로 이루어진 문자열) 형태의 농장 ID 번호를 가지고 있다. 가장 나이가 많은 소인 베시는 모든 소의 농장 ID 번호를 외우고 있으며, 돌아다니면서 소들에게 ID 번호를 묻는 것을 좋아한다.
소는 자신의 농장 ID 번호를 질문받으면 올바른 비트 문자열을 말하기 시작하지만, 헷갈려서 끝까지 말하지 못하고 도중에 멈출 수 있다. 베시가 들은 비트 문자열이 농장의 어떤 소의 농장 ID 번호도 아니라면, 베시는 어깨를 으쓱하고 자리를 뜬다. 하지만 그것이 질문한 소가 아닌 다른 소의 ID 번호라면, 베시는 신원 도용이 일어났다고 판단하고 농장을 봉쇄한다. 이는 소가 자신의 농장 ID 번호를 끝까지 말한 경우에도 일어날 수 있음에 유의하자.
농부 존은 이런 일이 일어나지 않도록 소들의 농장 ID 번호에 비트를 추가하여 번호를 바꾸려 한다. 그는 1초에 어떤 소든 그 소의 농장 ID 번호 끝에 비트 하나를 추가할 수 있다. 봉쇄가 절대 일어나지 않도록 하는 데 필요한 최소 시간을 구하여라.
문제 제공: Benjamin Qi
배점
- 입력 6-7: 모든 농장 ID 번호의 길이가 정확히 \(1\)이다.
- 입력 8-15: \(N\le 10^2\)이고 농장 ID 번호의 길이의 합이 \(10^3\)을 넘지 않는다.
- 입력 16-25: 추가 제약 없음.
문제 제공: Benjamin Qi
첫째 줄에 농부 존의 농장에 있는 소의 수 \(N\)이 주어진다.
다음 \(N\)개의 줄이 이어진다. \(k\)번째 줄에는 농장의 \(k\)번째 소의 농장 ID 번호에 해당하는 비트 문자열이 주어진다.
어떤 소의 농장 ID 번호도 비어 있지 않으며, 모든 농장 ID 번호의 길이의 합은 최대 \(10^6\)이다.
봉쇄가 절대 일어나지 않도록 하기 위해 농부 존이 써야 하는 최소 시간(초)을 출력한다.
3
1
1
15This sample satisfies the constraints for the first subtask.
We can make a lockdown impossible in 5 seconds by adding '0' to the first Farm
ID number, '10' to the second Farm ID number, and '11' to the third Farm ID
number, making the Farm ID numbers '10', '110', and '111'.
You can prove that this cannot be done in 4 or fewer seconds. For example, if
you leave the Farm ID numbers as they are, then all 3 cows have the same Farm ID
number '1', so when Bessie hears it it will always be the Farm ID number of
another cow.
As another example, if you spend just 2 seconds to add '0' to the second Farm ID
number and '1' to the third Farm ID number, then the Farm ID numbers are '1',
'10', and '11', and so the second and third cows, when saying their Farm ID
numbers, might stop in the middle and just say '1', which would be the Farm ID
number of the first cow.
3
1
11
1112We can make a lockdown impossible in 2 seconds by adding '0' to the first two
Farm ID numbers, making the Farm ID numbers '10', '110', and '111' like before.
You can prove that this cannot be done in 1 second.
3
1
1
114We can make a lockdown impossible in 4 seconds by adding '00' to the first Farm
ID number and '01' to the second Farm ID number. You can prove that this cannot
be done in 3 or fewer seconds.
5
0
01
0011
010
01614
0
1
1
0
1
0
1
1
1
1
1
0
0
141This sample satisfies the constraints for the first subtask.
riseoj 작성
출처 올림피아드 > USACO > 2023-2024 > US Open > Platinum