4208번 - 열쇠 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 128 MB | 19 | 3 | 3 | 27.273% |
문제
숭이는 자신이 가신 열쇠더미의 절반을 혜빈이에게 주려고 한다. 열쇠는 나선형을 따라 밀어서 열쇠 고리에 걸거나 분리할 수 있다. 같은 방식으로 열쇠 고리도 서로 연결하거나 분리 할 수 있다. 열쇠 고리에 열쇠를 연결하는 작업은 성가신 작업이기 때문에(숭이는 혜빈이가 손톱에 네일아트를 해주기 때문에 손톱을 다쳐선 안 된다) 이 과정을 최소로 하여 연결하려고 한다.
열쇠를 연결하거나 분리하거나, 열쇠 고리를 연결하거나 분리하는 것은 하나의 작업으로 간주된다. 열쇠를 밀어서 연결하거나 분리하는것은 고리를 연결하거나 분리하는 것에 비해 비해 매우 힘들기 때문에 숭이는 열쇠를 연결하거나 분리하는 과정을 최소로 하려고 한다. 만약 열쇠를 연결하거나 분리하는 횟수가 서로 같다면 열쇠 고리를 연결하거나 분리하는 과정을 최소로 해야 한다.
모든 작업이 완료되면, 숭이는 혜빈이에게 열쇠 더미를 건네준다(정확히 숭이꺼, 혜빈이꺼 두덩이로 분리되어야 한다). 예외가 되는 경우는 숭이가 갖는 열쇠 더미가 없거나 혜빈이에게 줄 수 있는 열쇠 더미가 없는 경우이다. 각각의 열쇠는 반드시 하나의 고리에 연결되어 있어야 한다. 열쇠 고리는 남은것이 생길 수 있다. 이때에는 두 그룹에서 분리시킨다
아래의 왼쪽 그림은 네개의 열쇠와 세개의 고리로 연결되어 있는 초기 상태를 나타낸다. 숭이는 혜빈이에게 2개의 열쇠인 N,R을 주려고 한다. 이때에 두 번의 열쇠 동작과 한번의 고리 동작으로 줄 수 있다. 이러한 결과가 아래의 오른쪽 그림이다.
입력
각각의 테스트 케이스는 하나 또는 여러개의 줄로 이루어져 있다. 각각의 테스트 케이스는 2개 문자로 이루어져 있다. 영어 소문자는 열쇠 고리를 나타내며 대문자는 열쇠를 나타낸다. 입력된 2개의 문자는 열쇠와 고리가 연결된 상태를 나타내거나, 고리와 고리가 연결된 상태를 나타낸다. 테스트 케이스 마지막 줄에는 0이 주어진다.
A부터 M까지의 열쇠는 숭이가 갖고, N부터 Z까지의 열쇠는 혜빈이에게 준다.
두 개의 문자가 모두 대문자인 경우는 없다. 테스트 케이스 내에서 같은 쌍으로 이루어진 문자열은 주어지지 않는다. 각각의 열쇠는 반드시 하나의 고리에 연결되어야 한다. 초기에 주어지는 열쇠 상태에서 고리에는 반드시 열쇠가 연결되어 있다(분리하면서 고리만 존재하는 경우는 발생할 수 있다). 존재하는 모든 열쇠와 고리는 반드시 한번 이상 주어진다.
출력
각각의 테스트 케이스에 대해서 열쇠를 연결하거나 분리하는 최소 횟수와 고리를 연결하거나 분리하는 최소 횟수를 출력한다.
만일 그러한 경우가 없다면 "impossible"을 출력한다.
예제 입력 1
ab bc aA aN Rb cB 0 aA bB Cc 0 aA aZ 0 aA bB cC xX yY ax xb by yc 0
예제 출력 1
Case 1: 2 1 Case 2: 0 2 Case 3: impossible Case 4: 0 7
출처
ICPC > World Finals > ACM-ICPC World Finals 2012 F번
- 문제를 번역한 사람: lll4592
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호