목성의 위성 이오(Io)에서 열린 개발자 컨퍼런스에 참석자들을 맞이하기 위해, 주최 측은 거대한 비치볼을 많이 불어 놓았다. 각 공은 대략 1 또는 0 모양인데, 이는 글자 I와 O처럼 보이기 때문이다. 컨퍼런스가 막 끝났고, 이제 비치볼을 치워야 한다. 다행히 비치볼 청소 로봇 BALL-E가 이 일을 맡고 있다!

컨퍼런스는 무한한 수평선 위에서 열렸고, 가운데에 정거장(station) 0이 있으며, 오른쪽에는 1, 2, \dots, 왼쪽에는 -1, -2, \dots 정거장들이 있다. 정거장 0에는 컨퍼런스의 유일한 비치볼 보관 창고(warehouse)가 있다. 그 외의 각 정거장에는 비치볼이 최대 하나까지 있을 수 있다.

Illustration of Sample Cases 1, 2, and 3.

BALL-E에는 저장 칸(storage compartment)이 두 개 있고, 각 칸에는 비치볼 하나만 담을 수 있다. 한 칸은 1 모양 공만 담을 수 있고, 다른 칸은 0 모양 공만 담을 수 있다. (1 모양 공은 0 모양 공보다 더 길쭉해서, 서로의 칸에 들어가지 않는다.)

BALL-E는 처음에 0 칸과 1 칸이 모두 비어 있는 상태로 정거장 0에서 시작한다. 로봇은 다음 행동들을 할 수 있다:

왼쪽으로 한 정거장 또는 오른쪽으로 한 정거장 이동한다. 이는 전력 1을 소모한다.
현재 정거장에 공이 있고, BALL-E가 그 모양의 공을 아직 보관하고 있지 않다면, 그 공을 해당 칸에 넣을 수 있다. 이는 전력을 0 소모한다.
현재 정거장에 공이 있다면, 그 공을 압축하여 반대 모양으로 바꿀 수 있다. 즉 1 모양 공은 0 모양 공이 되고, 그 반대도 가능하다. 이를 수행하는 데 전력 \mathbf{C}를 소모한다. 단, BALL-E가 이미 자신의 칸에 넣어 둔 공의 모양은 바꿀 수 없다.
BALL-E가 정거장 0에 있고 하나 이상의 공을 보관 중이라면, 보관 중인 모든 공을 창고에 한 번에 내려놓을 수 있다. 이는 전력을 0 소모하며 두 칸을 모두 비운다.

BALL-E가 어떤 정거장으로 이동했을 때 공이 그곳에 있더라도, 해당 모양의 빈 칸이 있다고 해서 즉시 집어야 하는 것은 아니다. 또한 BALL-E가 창고가 있는 정거장에 도착하더라도, 보관 중인 공을 반드시 내려놓아야 하는 것은 아니다.

위에서 설명한 행동들만 사용하여 모든 공을 창고로 옮기기 위해 필요한 전력 소모량의 최솟값을 구하라.

#10438 upload 1 done 1 how_to_reg 1

I, O 봇 timer 40s memory 1024MB

#10438

I, O 봇 40s 1024MB