3698번 - 애매함 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 128 MB | 47 | 13 | 12 | 40.000% |
문제
단어의 첫 글자와 마지막 글자를 제외한 나머지 글자의 순서를 섞어도 그 단어는 쉽게 읽을 수 있다. 예를 들어, 문장 "tihs snetncee mkaes prfecet sesne"는 많은 사람들이 쉽게 읽을 수 있다.
문장의 공백을 모두 제거해도 그 문장은 쉽게 읽을 수 있다. 예를 들면 "thissentencemakesperfectsense" 이다.
하지만, 글자의 순서를 섞고, 공백을 제거하면 문장은 쉽게 읽을 수 없다. "tihssnetnceemkaesprfecetsesne"와 같은 문장은 쉽게 읽을 수 없다.
글자의 순서를 섞고, 단어 사이의 공백을 제거한 문장이 주어진다. 또, 올바른 단어의 목록이 주어진다. 이때, 원래 문장을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스의 개수는 최대 100개이다.
각 테스트 케이스의 첫째 줄에는 글자의 순서를 뒤섞고, 공백을 제거한 문장이 주어진다. 이 문장은 알파벳 소문자로만 이루어져 있으며, 길이는 최대 1000글자이다.
둘째 줄에는 올바른 단어의 개수 n (1 ≤ n ≤ 10,000)이 주어진다. 다음 n개 줄에는 올바른 단어가 주어진다. 모든 단어는 중복되지 않으며, 알파벳 소문자로만 이루어져 있다. 또, 길이는 최대 100글자이다.
출력
각 테스트 케이스마다, 원래 문장을 유일하게 만들 수 있으면 그 문장을 출력한다. 문장을 만들 수 있는 방법이 여러 가지인 경우에는 "ambiguous"를, 불가능한 경우에는 "impossible"을 출력한다.
예제 입력 1
3 tihssnetnceemkaesprfecetsesne 5 makes perfect sense sentence this hitehre 2 there hello hitehre 3 hi there three
예제 출력 1
this sentence makes perfect sense impossible ambiguous
출처
ICPC > Regionals > Europe > Northwestern European Regional Contest > NWERC 2007 H번
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호