시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 128 MB | 93 | 36 | 32 | 48.485% |
과학자들은 화성에서 특이한 박테리아를 발견했고, 열심히 조사하고 있다. 그들은 박테리아의 개수가 2의 제곱수인 것을 알아챘다. 그것은 이들이 1개의 박테리아에서 시작되고, 각 박테리아는 매 세대 2개의 박테리아로 분열하기 때문이다(원래의 박테리아는 없어지는 꼴이다).
즉, 1세대는 하나의 박테리아, 2세대는 첫 세대의 박테리아가 둘로 나누어진 두 박테리아, 3세대는 또 그것이 나누어진 네 개의 박테리아, 4세대는 여덟 개, 이런 식으로 K+1세대에는 2k개의 박테리아가 있는 것을 알게 되었다.
과학자들은 그들이 찾아낸 박테리아를 1부터 2K까지 다음과 같이 번호 붙였다.
중괄호는 이들이 한 박테리아의 후손들이라는 뜻이다. 즉 어떤 조상 박테리아의 후손도 연속된 번호를 가지고 있도록 번호붙여졌다.
이때 박테리아의 순서를 바꾸더라도 여전히 위의 규칙을 만족하게 할 수 있는데, 과학자들은 그런 순서들 중 '순열의 길이'를 최소화하는 규칙을 찾으려 한다. '순열의 길이'는 이웃한 박테리아 사이의 거리를 모두 합한 것으로 정의된다.
정확히는, 모든 두 박테리아 사이에는 반발력이 존재하는데, 이 반발력은 수치로 나타내어진다. 두 박테리아 사이의 반발력은 두 박테리아가 서로 이웃해 있을 때 떨어져야 하는 최소 길이이다(두 박테리아가 이웃하지 않는다면 반발력은 아무 효과도 미치지 않는다). 모든 박테리아 쌍들의 반발력이 주어질 때, 이들을 앞서 말한 규칙을 지키면서 나열할 수 있는 최소의 길이를 구하시오.
입력의 첫 줄에는 문제에서 언급한 양수 K가 주어진다(1 ≤ K ≤ 9).
그 후의 2K개의 줄에는 [0, 106] 범위에 있는 2K개의 자연수가 주어진다. 2K × 2K개의 숫자는 박테리아 쌍들 사이의 반발력을 뜻한다: 여기서 (m, n)에 있는 숫자는 박테리아 m과 n 사이의 반발력을 뜻한다. (m, n)과 (n, m)에는 같은 숫자가 들어가고, m = n일 때는 0이다.
조건을 만족하면서 박테리아를 나열하는 최소의 길이만을 출력하라.
2 0 7 2 1 7 0 4 3 2 4 0 5 1 3 5 0
13
3 0 2 6 3 4 7 1 3 2 0 7 10 9 1 3 6 6 7 0 3 5 6 5 5 3 10 3 0 9 8 9 7 4 9 5 9 0 9 8 4 7 1 6 8 9 0 8 7 1 3 5 9 8 8 0 10 3 6 5 7 4 7 10 0
32
Contest > Croatian Open Competition in Informatics > COCI 2012/2013 > Contest #1 6번