Töskuröðun

commons.wikimedia.org에서 가져온 이미지

여느 때처럼 Atli는 또 다른 대회에 참가하기 위해 수하물을 가지고 여행한다. 짐을 가볍게 꾸리는 대신, 해외에서 저렴하게 쇼핑할 수 있도록 거의 빈 여행 가방을 가져간다. 이 때문에 목적지에 도착하면 수하물 수취대에서 자신의 수하물을 기다려야 하는 경우가 많으며, 때로는 기내 수하물만 가지고 그와 함께 여행하는 사람들도 그를 기다려야 한다. 이를 방지하기 위해 Atli는 다음번에는 최적의 시점에 수하물을 위탁하려고 한다. 수하물이 가능한 한 빨리 나오게 하려면 언제 위탁해야 할까?

가방들은 먼저 체크인 장소에서 비행기로 옮겨질 때까지 보관되는 큰 더미로 이동한다. 먼저 도착한 가방들은 맨 아래에 놓이므로, 가장 먼저 도착한 가방이 마지막에 나가고 가장 마지막에 도착한 가방이 먼저 나간다. 가방을 더미에 쌓을 때마다 가방의 순서는 이와 같이 재배열된다.

다음으로 가방들을 카트에 싣는다. 처음 $K_a$개의 가방은 첫 번째 카트에 더미로 쌓고, 다음 $K_a$개는 두 번째 카트에 더미로 쌓는 식이다. 가방 수가 $K_a$의 배수가 아니면 마지막 카트에는 단순히 더 적은 수의 가방이 실린다. 가방을 카트에 실을 때마다 가방의 순서는 이와 같이 재배열되며, 이후 가방들을 운반할 때는 첫 번째 카트에서 위부터 아래까지 꺼낸 다음 두 번째 카트에서 같은 방식으로 꺼내는 식으로 진행한다.

다음으로 가방들을 비행기 안에 더미로 쌓는다. 연결 항공편이 있다면 $i$번째 환승에서 가방들을 각각 $K_i$개씩 카트에 실은 다음 새 비행기 안에 더미로 쌓는다. 마지막으로 목적지에서는 가방들을 각각 $K_b$개씩 카트에 실은 뒤, 승객들이 찾아갈 수 있도록 현재 순서대로 수하물 수취대에 내놓는다.

Atli는 모든 공항을 미리 조사했으므로, 전체 가방 수 $n$뿐만 아니라 모든 항공편에 대한 $K_a, K_i, K_b$의 값도 알고 있다. 체크인 순서를 $1$부터 $n$까지 번호로 매긴다면, 자신의 가방이 목적지에서 가장 먼저 나오도록 하려면 몇 번째 순서여야 하는가?

채점

그룹 | 점수 | 제한

1 | 25 | $m = 0$, $1 \leq n \leq 10$, $K_a = K_b = n$.

2 | 25 | $m = 0$, $1 \leq n \leq 1\,000$.

3 | 25 | $0 \leq m \leq 1\,000$, $1 \leq n \leq 1\,000$.

4 | 25 | $0 \leq m \leq 100\,000$, $1 \leq n \leq 10^{18}$.

첫째 줄에 두 정수 $n$와 $m$가 주어진다. 여기서 $n$는 가방의 수이고 $m$는 연결 항공편의 수이다. $n$는 항상 양수이다. 둘째 줄에 출발 공항과 목적지 공항에서 사용하는 카트의 크기인 두 정수 $K_a$와 $K_b$가 $1 \leq K_a, K_b \leq 10^{18}$와 함께 주어진다. 마지막으로, $m \neq 0$이면 연결 항공편이 있는 각 공항에서 사용하는 카트의 크기인 $m$개의 정수 $K_i$가 $1 \leq K_i \leq 10^{18}$와 함께 이동 순서대로 한 줄에 추가로 주어진다.

Atli의 가방이 목적지에서 가장 먼저 나오도록 체크인 순서에서 Atli가 있어야 하는 위치에 해당하는 번호를 출력한다.