wizardrabbit   3년 전

* 본 지문은 12539번 문제를 번역 및 재구성하여 작성했습니다. 또한, 이 문제는 12540번 문제와 제한조건을 제외하고 동일한 문제입니다. 하단의 제한조건을 확인하세요.

문제


별조각으로 코인을 구매하고, 다시 되팔아서 별조각을 많이 벌어보자! 당신은 현재 별조각을 $M$ 개 가지고 있다.

코인은 총 $12$ 일에 걸쳐 판매하고 있으며, 매일 시세가 변동된다. 어느 두 날의 코인 시세가 같은 경우는 없다.

당신은 별조각을 벌기 위해, 아래의 두 작업을 각각 한 번만 수행할 수 있다.

  • 가진 별조각을 사용해 코인을 원하는 만큼 구매한다.
  • 가진 코인을 원하는 만큼 판매해 별조각으로 교환한다.

언제 코인을 구매하고, 언제 코인을 팔아야 별조각을 최대한 많이 벌 수 있을까?

입력


입력은 여러 개의 테스트 케이스로 이루어져 있다. 첫 번째 줄에는 테스트 케이스의 개수 $N$ 가 주어진다. 이후 $N$ 개의 테스트 케이스가 주어진다.

각 테스트 케이스의 첫 번째 줄에는 별조각의 수 $M$ 이 주어진다.

두 번째 줄에는 $P_1, P_2, P_3, ..., P_{12}$ 가 공백으로 구분되어 주어진다. $P_i$ 는 $i$ 번째 날에 코인 당 가격이 $P_i$ 별조각이라는 의미이다.

출력


각 테스트 케이스마다, 언제 코인을 구매하고, 언제 코인을 팔아야 별조각을 최대한 많이 벌 수 있는지를 아래의 형식대로 출력한다.

Case #n: a b c
  • $n$ 은 테스트 케이스의 번호 $(1, 2, 3, ..., N)$
  • $a$ 는 몇 번째 날에 코인을 구매해야 하는지
  • $b$ 는 몇 번째 날에 코인을 판매해야 하는지
  • $c$ 는 얼마나 별조각을 이득 볼 수 있는지

를 의미한다.

만약 어떻게 코인을 구매하고 판매하더라도 별조각을 이득볼 수 없다면, 아래의 형식대로 답을 대신 출력하도록 한다.

Case #n: IMPOSSIBLE

별조각을 가장 많이 벌 수 있는 방법이 여러 가지인 경우, 코인 하나의 가격이 가장 쌀 때 구매하는 경우를 정답으로 채택한다.

제한


  • $1 \le N \le 10$
  • $100 \le M \le 500$
  • $1 \le P \le 250$
  • $N, M, P$ 는 정수

댓글을 작성하려면 로그인해야 합니다.