레이팅 미적용농부 존의 소들은 각자 자신의 소울메이트, 즉 자신과 비슷한 특성을 가져 궁합이 최고인 다른 소를 찾고 싶어 한다. 각 소의 성격은 정수 \(p_i\)(\(1 \leq p_i \leq 10^{18}\))로 표현된다. 성격이 같은 두 소는 소울메이트이다. 소는 "변경 연산"을 통해 성격을 \(2\)배로 만들거나, (\(p_i\)가 짝수이면) \(2\)로 나누거나, \(1\)을 더해서 성격을 바꿀 수 있다.
농부 존은 처음에 소들을 임의의 방식으로 짝지어 놓는다. 그는 각 소 쌍을 소울메이트로 만들기 위해 몇 번의 변경 연산이 필요한지 궁금하다. 각 쌍에 대해, 쌍의 첫 번째 소가 두 번째 소와 소울메이트가 되기 위해 수행해야 하는 변경 연산의 최소 횟수를 구하라.
출제자: Quanquan Liu
배점
- 테스트 케이스 1-4는 \(p_i \le 10^5\)를 만족한다.
- 테스트 케이스 5-12는 추가 제약이 없다.
출제자: Quanquan Liu
첫째 줄에 소 쌍의 수 \(N\)(\(1\le N\le 10\))이 주어진다. 나머지 \(N\)개의 줄에 각 소 쌍의 성격을 나타내는 두 정수가 주어진다. 첫 번째 수는 두 번째 수와 같아지도록 바뀌어야 하는 소의 성격을 나타낸다.
\(N\)개의 줄을 출력한다. 각 쌍에 대해, 첫 번째 소의 성격을 두 번째 소의 성격과 같게 만들기 위해 필요한 연산의 최소 횟수를 출력한다.
6
31 13
12 8
25 6
10 24
1 1
997 1208
3
8
3
0
20For the first test case, an optimal sequence of changes is
\(31 \implies 32 \implies 16 \implies 8 \implies 9 \implies 10 \implies 11 \implies 12 \implies 13\).
For the second test case, an optimal sequence of changes is
\(12 \implies 6 \implies 7 \implies 8\).
riseoj 작성
출처 올림피아드 > USACO > 2021-2022 > January > Silver