데이터 마이닝

Tuple 박사는 어느 상용 상품 회사를 위해 새로운 데이터 마이닝 응용 프로그램을 개발하고 있다. 그중 한 서브루틴은 각각 $N$개의 레코드를 담은 두 배열 $P$와 $Q$를 다룬다(레코드 번호는 $0$부터 $N-1$까지이다). 배열 $P$는 키로 이루어진 해시 형태의 구조를 담고 있어 레코드를 찾는 데 쓰이며, 해당 레코드의 실제 데이터는 배열 $Q$에서 읽어 온다.

배열 $P$의 모든 레코드 크기는 $S_P$바이트, 배열 $Q$의 모든 레코드 크기는 $S_Q$바이트이다. 이 서브루틴은 프로그램 전체에서 가장 자주 실행되는 부분이므로 최대한 빠르게 동작해야 한다. 그런데 $S_P$와 $S_Q$는 실행 시점에야 알 수 있어서 여러 컴파일 타임 최적화를 적용할 수 없다.

$i$번째 레코드의 바이트 오프셋은 보통 다음과 같이 계산한다.

$Pofs(i) = S_P \cdot i, \qquad Qofs(i) = S_Q \cdot i.$

최신 프로세서에서 곱셈은 덧셈보다 훨씬 느리다. 그래서 Tuple 박사는 배열 $P$를 훑을 때 인덱스 $i$ 대신 바이트 오프셋 $Pofs(i)$를 저장하고, 이웃한 레코드로 이동할 때는 $Pofs(i+1) = Pofs(i) + S_P$ 또는 $Pofs(i-1) = Pofs(i) - S_P$를 사용한다.

$P$에서 레코드를 찾을 때마다 대응하는 $Q$의 레코드를 읽어야 하며, 이를 위해 오프셋 $Qofs(i)$가 필요하다. 위 두 식으로부터 다음을 얻는다.

$Qofs(i) = Pofs(i) / S_P \cdot S_Q.$

이 식에는 곱셈뿐 아니라 (느린) 정수 나눗셈이 들어 있다. 이를 피하기 위해 Tuple 박사는 다음의 빠른 식을 사용한다.

$Qofs'(i) = \big(Pofs(i) + (Pofs(i) \ll A)\big) \gg B,$

여기서 $A$와 $B$는 음이 아닌 정수이고, $x \ll A$는 $A$비트 왼쪽 시프트(즉 $x \cdot 2^A$), $x \gg B$는 $B$비트 오른쪽 시프트(즉 $\lfloor x / 2^B \rfloor$)를 뜻한다. 레지스터는 충분히 넓어서 오버플로는 절대 일어나지 않는다고 가정한다. $Pofs(i) = S_P \cdot i$이므로 이 식은 다음과 같다.

$Qofs'(i) = \left\lfloor \frac{S_P \cdot (1 + 2^A) \cdot i}{2^B} \right\rfloor.$

대부분의 $A$, $B$ 선택에서는 이 값이 $Qofs(i)$와 같지 않지만, 메모리를 조금 더 쓰면 여전히 사용할 수 있다. $Q$를 일반적인 방식으로 배치하면 $N \cdot S_Q$바이트가 필요하다. Tuple 박사는 항상 적절한 $K$($K \ge N \cdot S_Q$)를 고를 수 있는데, $Q$에 $K$바이트를 할당하고 $A$, $B$를 잘 선택하면 빠른 식이 $N$개의 레코드를 서로 겹치지 않게 저장한다. 즉 레코드 $i$는 바이트 구간 $[Qofs'(i),\ Qofs'(i) + S_Q)$를 차지하고, $N$개의 구간은 서로 겹치지 않으며, 모두 $[0, K)$ 안에 들어간다.

최소의 $K$와 그에 해당하는 $A$, $B$를 찾는 프로그램을 작성하라. 같은 최소 $K$를 주는 $(A, B)$ 쌍이 여러 개라면 $A$가 가장 작은 것을, 그래도 여러 개라면 $B$가 가장 작은 것을 출력한다.

공백으로 구분된 세 정수 $N$, $S_P$, $S_Q$가 주어진다 ($1 \le N \le 2^{20}$, $1 \le S_P \le 2^{10}$, $1 \le S_Q \le 2^{10}$).

공백으로 구분된 세 정수 $K$, $A$, $B$를 한 줄에 출력한다.