The Halfwitters
시간 제한5초메모리 제한512 MB
각 시작 순열에서 인접 교환(비용 a), 전체 뒤집기(비용 b), 무작위 재배치(비용 c)를 써서 항등 순열에 도달하는 최소 기대 시간을 계산한다.
문제
최근 상관에게 멋진 장난을 쳤다. 장난은 아주 잘 먹혀서, 곧 강등당하고 직위를 잃은 뒤, 정예 소대를 지휘하게 되었다. 정예 소대는 신중하게 선발된 병사들로 이루어진 유명한 Halfwitters다. Halfwitters는 적에게 매수된 적도, 전투에서 명예를 잃은 적도 없다고 한다. 이들은 후퇴나 배신이라는 개념 자체를 이해하지 못한다. 그리고 외부 기온이 자기 IQ보다 낮은 곳에서 복무한 Halfwitter도 없다.
n명의 병사로 구성된 소대가 앞에 한 줄로 서 있다. 병사들이 가장 키 큰 병사(1번)부터 가장 작은 병사(n번) 순서로 서게 하고 싶다. 하지만 아직 소대에게 이 사실을 설명하지 않았다. 지금 병사들은 디저트를 가장 먼저 먹은 사람이 앞에 서는, 좋아하는 순서대로 서 있다. 다음과 같은 세 가지 행동을 할 수 있다.
- 이웃한 두 병사에게 자리를 바꾸라고 명령한다. 설명하는 데 정확히 a분이 걸린다.
- 소대 전체에게 줄의 순서를 뒤집으라고 명령한다. 어려운 동작이지만 이미 훈련되어 있어, 상기시키는 데 b분이 걸린다.
- 화를 내며 c분 동안 소리친다. 큰 혼란과 당황이 일어나고, 소리치기를 멈추면 병사들은 완전히 무작위 순서로 다시 배열된다.
최선의 전략을 사용한다고 가정할 때, 원하는 순서 (1, 2, ..., n)를 만드는 데 걸리는 기대 시간은 얼마인가? 여러 디저트가 있어서 매일 다른 순서로 시작하며, d일 동안 훈련한다. 각 날짜에 대해 답을 계산하라.
입력
첫 줄에는 테스트 케이스의 수 z가 주어진다. 그다음에 테스트 케이스의 설명이 이어진다.
각 테스트 케이스는 다섯 정수 n, a, b, c, d (2 ≤ n ≤ 16, 1 ≤ a, b, c ≤ 1000, 1 ≤ d ≤ 10 000)로 시작한다. n은 병사의 수, a, b, c는 각 행동의 비용, d는 날짜 수다. 다음 d개 줄에는 각각 수열 (1, 2, ..., n)의 순열이 주어진다. 이는 연속된 날짜에 병사들이 서 있는 초기 순서다. 모든 테스트 케이스의 날짜 수 합은 100 000을 넘지 않는다.
출력
각 테스트 케이스마다 d개 줄을 출력한다. 모든 날짜에 대해, 병사들을 원하는 순서로 배열하는 데 필요한 기대 시간을 출력한다. 이 값은 유리수이므로 p/q 형태의 기약분수로 나타낸다.