5175번 - 문제없는 문제 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 128 MB | 45 | 19 | 18 | 45.000% |
문제
ACM 코더들은 보편적으로 사용하는 많은 알고리즘들에 대한 이해도가 폭넓게 높아야 한다. 그래서 일반적으로 ACM 대회를 개최할 땐 되도록이면 많은 알고리즘을 두루두루 사용하게끔 문제를 낸다.
하지만 어떤 대회에서, 문제 전체에서 단 한 번도 사용되지 않는 알고리즘이 하나라도 존재한다면 그건 문제 있는 문제 세트이다. 예를 들면 DP가 없거나, 그래프 이론과 관련된 알고리즘이 없는 문제 세트는 문제가 있다는 것이다.
이번 문제에서는 이번 대회를 위해 만든 문제 세트에 대하여, 문제들의 부분집합으로 이루어진 문제 세트들 중 문제 없는 문제 세트를 만들어볼 것이다. 세트 내에서 어떤 알고리즘이 너무 많이 사용되는 것은 상관없으나, 모든 알고리즘들을 반드시 한 번 이상 사용해야만 한다.
하지만 문제를 만드는 것은 매우 어려운 일이기 때문에 되도록이면 적은 문제로 이루어진 세트를 찾아야 한다. 그렇게 해야 남는 문제를 다음 대회에 사용할 수가 있다.
입력
첫 줄에 테스트 케이스의 수 K가 주어진다.
각 테스트 케이스의 첫 줄엔 두 정수 M과 N이 주어진다. (1 ≤ M, N ≤ 20)
M은 대회에서 사용할 알고리즘의 개수이며, N은 문제의 총 개수이다.
대회에서 사용해야 할 알고리즘은 1부터 M까지의 모든 자연수이며, 문제는 첫 번째 문제가 A, 두 번째 문제가 B, 세 번째 문제가 C.. 의 방식으로 이름을 붙인다.
이어서 N줄에 걸쳐 첫 번째 문제부터 N번째 문제까지 어떤 알고리즘들을 사용하는지가 공백으로 구분되어 주어진다.
출력
각 테스트 케이스마다 Data Set K: 를 출력한 뒤, 1부터 M까지의 모든 알고리즘을 포함할 수 있는 최소 크기의 문제 세트에 속한 문제들을 사전순으로 출력한다.
만일 답이 여러 가지라면 그 중 사전순으로 가장 앞선 것을 출력한다.
모든 테스트 케이스에서 답이 존재하지 않는 경우는 없다.
각 테스트 케이스의 사이엔 빈 줄을 하나 출력한다.
예제 입력 1
2 2 3 1 2 1 2 4 5 1 2 3 1 2 2 4 1 3 4 2 3 4
예제 출력 1
Data Set 1: C Data Set 2: A C
출처
University > The USC Programming Contest > Fall 2007 A번
- 문제를 번역한 사람: portableangel
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호