2883번 - 남극의 과학자 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 128 MB | 4 | 1 | 1 | 33.333% |
문제
얼마전 남극 연구 탐사진들은 새로운 종을 발견하였다. 연구진은 테스트를 하기 위해 샘플을 하나 추출해 연구실로 보냈다.
이번에 발견된 새로운 종은 짧은 주기를 갖고 번식한다. 번식할 때 부모는 하나만 있으면 된다. 한 부모는 두 번 번식할 수 있으며, 그 이후에는 더 이상 번식할 수 없다.
따라서, 연구실에 있는 표본의 수는 급속도로 늘어났고, 가계도가 필요한 시점이 되었다.
연구진은 간단한 텍스트 에디터를 이용해 가계도를 그리려고 한다. 가계도는 다음과 같은 규칙을 지켜야 한다.
표번의 이름은 '-', '|', 'o'로 이루어진 박스로 둘러쌓여져 있어야 한다. 윗 변과 아랫 변의 중앙에는 '+' 마크가 있어야 한다. 변의 길이가 짝수인 경우에는 두 중앙 중 왼쪽 중앙에 '+'를 표시한다.
o--+--o |anton| o--+--o |
o----+----o |anamarija| o----+----o |
o-+--o |pero| o-+--o |
박스를 링크를 이용해 연결해야 한다. 한 링크는 두 개 또는 그 이상의 박스를 연결할 수 있으며, '+'와 연결되어 있어야 한다. 부모 박스가 위에, 자식 박스가 아래에 있어야 한다. 박스와 링크는 겹칠 수 없다.
+ | o | + |
+
|
o---o---o
| |
+ +
|
+
|
o-----o-----o
| |
+ +
|
자식의 수가 1개인 경우에는 가장 왼쪽 그림에 나와있는 링크를 사용한다. 둘 이상의 자식을 가지는 경우에는 중간에 갈라진 링크를 사용해야 하며, 왼쪽에는 나이가 많은 자식, 오른쪽에는 적은 자식이 있어야 한다.
링크는 수평방향으로 늘어날 수 있으며, 좌우의 '-'의 개수는 같아야 한다. 링크는 수직방향으로 늘어날 수는 없다.
각 표본의 정보가 주어졌을 때, 가계도를 그리는데 필요한 문자의 개수를 구하는 프로그램을 작성하시오. 단, 공백의 개수는 세지 않으며, '-', '|', '+', 'o', 이름만 센다.
입력
첫째 줄에 실험실에 있는 표본의 수 N (1 ≤ N ≤ 300,000)이 주어진다. 각 표본은 1번부터 N번까지 태어난 순서대로 번호가 매겨져 있다. 즉, 가장 나이가 많은 표본은 1, 어린 표본은 N이다.
다음 N개 줄에는 각 표본의 이름과 부모의 번호가 주어진다. (첫 번째 표본의 부모는 알 수 없다) 이름은 알파벳 소문자로만 이루어진 문자열로 길이는 20을 넘지 않는다.
출력
첫째 줄에 가계도를 그리는데 필요한 글자의 수를 출력한다.
예제 입력 1
3 adam kain 1 abel 1
예제 출력 1
64
o-+--o |adam| o-+--o | o--o--o | | o-+--oo-+--o |kain||abel| o-+--oo-+--o
예제 입력 2
12 anton ana 1 luka 1 mia 2 tea 3 jakov 3 semiramida 5 dominik 5 anamarija 4 eustahije 4 lovro 2 lovro 11
예제 출력 2
371
o--+--o
|anton|
o--+--o
|
o------------o------------o
| |
o-+-o o-+--o
|ana| |luka|
o-+-o o-+--o
| |
o-------o-------o o--o--o
| | | |
o-+-o o--+--o o-+-oo--+--o
|mia| |lovro| |tea||jakov|
o-+-o o--+--o o-+-oo--+--o
| | |
o-----o-----o o o-----o-----o
| | | | |
o----+----o o----+----o o--+--oo----+-----o o---+---o
|anamarija| |eustahije| |lovro||semiramida| |dominik|
o----+----o o----+----o o--+--oo----+-----o o---+---o
출처
Olympiad > Croatian Highschool Competitions in Informatics > 2010 > Croatian Olympiad in Informatics 2010 3번
- 문제를 번역한 사람: baekjoon
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호