아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

시장에서 투자하기

면접 대비

시간 제한5초메모리 제한512 MB

요약
12개월 가격에서 매수 월과 이후 매도 월을 정해 정수 단위로 살 수 있는 수량의 매매 차익을 가장 크게 합니다.
난이도

쉬움10점 중 2점

유형
완전 탐색, 배열
정답자
아직 제출이 없습니다

문제

투자할 돈 MM이 있고, 다가오는 1년 동안 매달 초의 상품 가격을 예측한 자료 P1,P2,…,P12P_1, P_2, \dots, P_{12}가 있다. 언제 사서 언제 팔아야 이익이 가장 커지는지 구한다.

상품은 쪼개서 살 수 없고 정수 개수로만 산다. 매수는 한 번만 한다. BB번째 달에 사서 SS번째 달에 판다고 하면(B<SB < S), 가진 돈으로 살 수 있는 만큼 최대한 사서 그 전부를 판다. 즉 k=⌊M/PB⌋k = \lfloor M / P_B \rfloor개를 사고, 이익은 k×(PS−PB)k \times (P_S - P_B)이다.

한 테스트 케이스 안의 가격 12개는 모두 다르다. 이익이 같은 계획이 둘 이상이면 단위 가격이 더 낮은 쪽, 즉 PBP_B가 더 작은 쪽을 고른다. 어떻게 사고팔아도 이익을 낼 수 없으면 IMPOSSIBLE을 출력한다.

입력

첫 줄에 테스트 케이스의 개수 NN이 주어진다. 각 테스트 케이스는 두 줄이다.

  • 첫 줄에 투자할 금액 MM이 주어진다.
  • 둘째 줄에 각 달 초의 가격 P1P_1부터 P12P_{12}까지 정수 12개가 공백으로 구분되어 주어진다.

제한

  • 1≤N≤101 \le N \le 10
  • 100≤M≤500100 \le M \le 500
  • 1≤Pi≤2501 \le P_i \le 250
  • 한 테스트 케이스 안의 가격 12개는 서로 다르다.

출력

각 테스트 케이스마다 한 줄을 출력한다. 줄은 Case #x:로 시작하고 공백 하나를 둔다. xx는 1부터 세는 테스트 케이스 번호다. 그 뒤에 이익을 낼 수 없으면 IMPOSSIBLE을 출력하고, 그렇지 않으면 정수 세 개를 공백으로 구분해 출력한다.

  • 상품을 사는 달의 번호 BB. 1 이상 11 이하의 정수다.
  • 상품을 파는 달의 번호 SS. B+1B + 1 이상 12 이하의 정수다.
  • 그 계획으로 얻는 이익.

예제1

  1. 예제 1

    입력
    3
100
1 2 3 4 5 6 7 8 9 10 11 12
100
52 50 25 100 61 63 70 51 71 55 10 5
100
200 150 250 132 125 110 210 220 180 176 108 113
    예상 출력
    Case #1: 1 12 1100
Case #2: 3 4 300
Case #3: IMPOSSIBLE