27470번 - 멋진 부분집합 서브태스크스페셜 저지다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 542 | 80 | 57 | 14.767% |
문제
KSA 학생들은 멋진 집합을 좋아한다. 멋진 집합이란 모든 원소들의 최대공약수가 $1$보다 큰 정수들의 중복집합이다. 크기가 $N$인 중복집합이 주어졌을 때, 주어진 중복집합의 부분집합 중 크기가 $\left\lceil\cfrac{N}{2}\right\rceil$인 멋진 집합을 찾아보자!
입력
첫 번째 줄에 정수 $N$이 주어진다.
두 번째 줄에 중복집합의 원소들인 $N$개의 정수가 주어진다.
출력
첫 번째 줄에 멋진 집합이 존재한다면 YES, 아니라면 NO를 출력한다.
만약 멋진 집합이 존재한다면, 두 번째 줄에 멋진 집합에 속한 $\left\lceil\cfrac{N}{2}\right\rceil$개의 정수를 출력한다.
정답이 여러 개 존재한다면 아무거나 출력해도 상관없으며, 각 원소를 출력하는 순서는 상관없다.
제한
- $3 \leq N \leq 5 \times 10^{5}$
- 주어지는 중복집합의 원소들은 $2$ 이상 $10^{9}$ 이하의 정수
서브태스크
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 5 | $N \leq 10$ |
| 2 | 15 | $N \leq 1000$ |
| 3 | 80 | 추가 제약 조건 없음 |
예제 입력 1
4 2 3 4 5
예제 출력 1
YES 2 4
예제 입력 2
5 3 5 7 9 11
예제 출력 2
NO
출처
High School > 한국과학영재학교 > 2023 KSA Automata Winter Contest F번
- 문제를 검수한 사람: eric00513, heeda0528, hjroh0315, jk410, kiwiyou, ssamt, tony9402, whqkrkt04, wizardrabbit
- 문제를 만든 사람: flakepowders
채점 및 기타 정보
- 예제는 채점하지 않는다.
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호