12516번 - 챔피언소트 (Large) 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 5 초 | 512 MB | 182 | 104 | 91 | 59.477% |
문제
여기, 특이한 방법으로 정렬을 하려고 하는 사람이 있다.
그리고 그의 이름은 존 시나!!!!
알고리즘 전문이 아닌 존 시나는 자신만의 방법으로 수를 정렬하려고 한다. 존 시나가 정렬할 배열에는 1부터 N까지의 자연수가 하나씩 들어있다. 우선 존 시나는 배열 안에서 몇 개의 원소를 골라 "You can't see me"라고 발언한다. 그 후 선택한 원소에 동시에 파이브 너클 셔플을 날린다. 그러면 선택한 원소들이 큰 대미지를 입으며 순서가 무작위로 섞이게 된다.
존 시나는 섞을 원소를 선택할 때 최적의 전략을 사용하고자 한다. 즉, 정렬하는 데 필요한 파이브 너클 셔플 횟수의 기댓값을 최소화하려고 한다. (동시에 사용하는 파이브 너클 셔플은 하나로 친다.) 그 기댓값은 얼마일까?
입력
첫 줄에 테스트케이스의 개수 T가 주어진다. 각 테스트케이스는 두 줄로 이루어져 있다. 첫 줄에는 배열의 길이 N이 주어진다. 두 번째 줄에는 배열의 원소가 차례대로 주어진다.
1 ≤ T ≤ 100이고, 1 ≤ N ≤ 1000이다. 배열에는 1부터 N까지의 자연수가 하나씩 있다.
출력
각 줄에 테스트케이스 번호 x와 최소 기댓값 y를 Case #x: y의 형태로 출력한다. y는 반올림하여 소수점 아래 6자리까지 출력한다.
예제 입력 1
3 2 2 1 3 1 3 2 4 2 1 4 3
예제 출력 1
Case #1: 2.000000 Case #2: 2.000000 Case #3: 4.000000
힌트
케이스 #1: 존 시나는 두 원소를 모두 선택하여 파이브 너클 셔플을 날린다. 1/2의 확률로 배열이 정렬되고, 1/2의 확률로 그대로 있으므로 기댓값은 2가 된다.
케이스 #2: 존 시나는 3과 2를 선택하여 파이브 너클 셔플을 날린다. #1과 마찬가지로 기댓값은 2가 된다.
케이스 #3: 존 시나는 2와 1을 선택하여 파이브 너클 셔플을 날린다. #1과 마찬가지로 이때까지의 기댓값은 2가 된다. 그 후 4와 3을 선택하여 파이브 너클 셔플을 날리면 총 기댓값은 4가 된다.
출처
Contest > Google > Code Jam > Google Code Jam 2011 > Qualification Round D2번
- 문제를 번역한 사람: jh05013
채점 및 기타 정보
- 예제는 채점하지 않는다.
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호