R02014
분할 셔플
골드 V레이팅
의견: 0
설명
분할 셔플이란, 연속된 수(\(a_i = a_{i-1}+1\))의 길이가 \(n\)이고 패턴의 개수가 \(k\)인 수열에서 수열을 반으로 나눠서 두번째 수열(\(nk/2+1 \sim nk\))을 첫번째 수열(\(1 \sim nk/2\)) 사이에 끼워넣는 연산이다. (수열을 반으로 나누어 뒤쪽 절반의 원소들을 앞쪽 절반의 원소들 사이에 끼워 넣는다.)
이 분할 셔플을 몇 번 해야 원본 수열로 순환하는지를 구하는 프로그램을 작성해야 한다.
예시로, \(n=4\), \(k=2\)라면 12341234이고, 이걸 원본 수열로 순환할 때까지 분할 셔플 해보면 다음과 같다:
12341234
11223344
13132424
12341234
정답: \(3\).
제약
- \(n\), \(k\)는 \(2\)의 제곱수
- \(2 \le n \le 2^{30}\)
- \(1 \le k \le 2^{30}\)
입력 형식
첫번째 줄에 \(n\), \(k\)가 공백으로 구분되어 주어진다.
출력 형식
첫번째 줄에 정답을 출력한다.
서브태스크
| 서브태스크 | 점수 | 설명 |
|---|---|---|
1 | 10점 | \(k = 1\) |
2 | 30점 | \(n \le 8,\ k \le 8\) |
3 | 60점 | 추가 제약 조건 없음 |
예제 1
입력
4 2출력
3설명
본문과 같다.
예제 2
입력
4 4출력
4설명
1234123412341234 -> 1122334411223344 -> 1111222233334444 -> 1313131324242424 -> 1234123412341234
문제 정보
gras 작성
출처 Original
태그
평가 및 의견
분할 셔플
개별 의견
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
분할 셔플
게스트로 둘러보고 있습니다. 로그인하면 풀이를 제출하고 진행 상황을 확인할 수 있습니다.
로그인하고 제출하기