문제
Farmer John's
When a cow is asked their Farm ID number, they will start to say the correct bitstring, but may get confused and stop before finishing it. When Bessie hears the bitstring, if it is not the Farm ID number of any cow on the farm, then she will shrug and walk off. However, if it is the ID number of a different cow than the one she asked, then she will assume that identity theft has occurred and place the farm into lockdown. Note that this can happen even when the cow says their full Farm ID number.
Farmer John would like to prevent this from happening, and is willing to change the cows' Farm ID numbers by adding some more bits to them. In one second, he can add one bit to the end of the Farm ID number of any cow. Figure out the minimum amount of time it will take for him to prevent a lockdown from ever occurring.
입력
The first line contains
Then
No cow's Farm ID number is empty, and the total length of all Farm ID numbers is at most
출력
Output the minimum number of seconds Farmer John needs to spend to ensure that a lockdown will never occur.
부분문제
| 번호 | 점수 | 조건 |
|---|---|---|
| #1 | 20점 | All Farm ID numbers have length exactly 1 |
| #2 | 30점 | |
| #3 | 50점 | 추가 제약 조건 없음 |
예제 #1
3
1
1
1
5
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.
예제 #2
3
1
11
111
2
We 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
3
1
1
11
4
We 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.
예제 #4
5
0
01
0011
010
01
6
예제 #5
14
0
1
1
0
1
0
1
1
1
1
1
0
0
1
41
로그인해야 코드를 작성할 수 있어요.