2956번 - 대칭 행렬 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 128 MB | 38 | 17 | 15 | 45.455% |
문제
행렬은 글자로 채워져 있는 직사각형 표이다. 정사각형 행렬은 열의 수와 행의 수가 같을 때이다. 정사각형 행렬 M이 대칭이라면, 모든 i,j쌍에 대해서 Mij = Mji를 만족할 때이다.
아래 두 행렬은 대칭인 경우이다.
AAB AAA ACC ABA BCC AAA
아래 두 행렬은 대칭이 아닌 경우이다.
ABCD AAB ABCD ACA ABCD DAA ABCD
사용할 수 있는 문자가 주어졌을 때, 이 문자를 모두 사용해서 만들 수 있는 대칭행렬 중에서, 사전순으로 앞서는 행렬의 열의 부분집합을 출력하는 프로그램을 작성하시오.
어떤 행렬의 열의 부분집합이란 특정 열을 제외하고는 모두 지워버린 행렬이다. 아래와 같은 행렬을 살펴보자.
AAB ACC BCC
위 행렬의 1,3열의 부분집합은 다음과 같다. (2열에 등장하는 문자를 모두 지워버리면 된다.)
AB AC BC
두 행렬 A와 B를 사전순으로 비교하려면, 각 행렬을 행을 순서대로 모두 이어붙여 긴 문자열로 만든 뒤 문자열 비교를 한다고 생각하면 된다.
입력
첫째 줄에 두 정수 N과 K가 주어진다. N은 행렬의 크기이고, K는 사용할 수 있는 서로 다른 문자의 개수이다. (1 ≤ N ≤ 30000, 1 ≤ K ≤ 26)
다음 K개 줄에는 사용할 수 있는 문자와 그 개수가 공백으로 구분되어 주어진다. 문자는 모두 알파벳 대문자이다. 예를 들어, "A 3"은 A를 3번 사용할 수 있다는 뜻이다.
사용할 수 있는 문자의 개수는 정확히 N2개이다.
다음 줄에는 열의 부분집합의 크기 P가 주어진다. (1 ≤ P ≤ 50)
마지막 줄에는, P개의 숫자가 주어지고, 열의 부분집합의 내용이다. 각 숫자는 1보다 크거나 같고, N보다 작거나 같으며, 오름차순으로 정렬되어 있고, 중복되지 않는다.
출력
주어진 문자로 대칭행렬을 만드는 것이 가능하다면, 행렬의 열의 부분집합을 출력한다. 만약, 불가능하다면 "IMPOSSIBLE"을 출력한다. (따옴표는 출력하지 않는다)
예제 입력 1
3 3 A 3 B 2 C 4 3 1 2 3
예제 출력 1
AAB ACC BCC
예제 입력 2
4 4 A 4 B 4 C 4 D 4 4 1 2 3 4
예제 출력 2
AABB AACC BCDD BCDD
예제 입력 3
4 5 E 4 A 3 B 3 C 3 D 3 2 2 4
예제 출력 3
AC BE DE ED
예제 입력 4
4 6 F 1 E 3 A 3 B 3 C 3 D 3 4 1 2 3 4
예제 출력 4
IMPOSSIBLE
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호