3948번 - 홍준이의 친위대 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 128 MB | 573 | 383 | 310 | 66.955% |
문제
홍준 왕국의 국왕 홍준이는 자신을 호위하는 N명의 친위대 병사가 있다. 병사들의 키는 모두 다르다. 홍준이는 그들을 일렬로 세울 때, 키 순서대로 세우는 것보다 맨 끝 두 병사를 제외한 나머지 병사들의 양 옆 두 병사의 키가 자신 보다 크거나 모두 자신보다 작을 때 보기 좋다고 생각한다. 예를 들어, 홍준이에게 7명의 친위대 병사가 있고, 그 들의 키가 160, 162, 164, 166, 168, 170, 그리고 172cm 라고 하자. 아래와 같이 병사가 일렬로 서있으면 홍준이는 보기 좋다고 생각한다.
만약 홍준이가 매일 같은 병사 배치를 본다면 매우 지루해할 것이다. 때문에 매일 병사들의 배치를 새롭게 하고 싶다. 즉, 병사 N명이 있을 때 서로 다른 배치가 몇 가지 있는지 알고 싶어한다.
예를 들어, 병사가 4명이 있고 편의상 그들의 키를 1, 2, 3, 4라고 나타내자. 그러면 아래와 같이 10가지 배치가 가능하다.
1324, 2143, 3142, 2314, 3412, 4231, 4132, 2413, 3241, 1423
병사의 수 N이 주어졌을 때, 가능한 배치의 수를 구하는 프로그램을 작성하자.
입력
첫 줄에 테스트케이스 수 T가 주어진다. (1 ≤ T ≤ 1,000)
각 테스트케이스마다 병사의 수를 나타내는 자연수 N이 주어진다. (1 ≤ N ≤ 20)
출력
각 테스트케이스 마다 가능한 배치의 수를 줄로 구분하여 출력한다.
예제 입력 1
4 1 3 4 20
예제 출력 1
1 4 10 740742376475050
출처
ICPC > Regionals > North America > Greater New York Region > 2012 Greater New York Programming Contest F번
- 문제를 번역한 사람: myungwoo
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호