jtw7913   11달 전

문제

당신은 ACM-ICPC 대회 참가자로서, 제한된 시간 안에 가능한 많은 문제를 풀고, 동시에 전체 소요 시간을 최소화하는 것이 목표입니다.

각 문제를 해결하는 데 걸릴 시간을 사전에 추정할 수 있다고 가정합시다. 당신의 과제는 풀 수 있는 문제 수를 최대화하면서 총 시간(total time)을 최소화하도록 문제들을 풀 계획을 세우는 것입니다.
총 시간(total time)은 각 문제를 풀어 제출한 시점의 시간(대회 시작 후 경과한 분 단위)을 모두 더한 값입니다.

계획을 세울 때 다음을 가정할 수 있습니다.

  • 각 문제는 추정한 시간만큼 정확히 걸리며, 첫 제출에서 바로 맞았다고 가정해도 됩니다. 즉, 패널티 시간은 고려하지 않아도 됩니다.

  • 동시에 여러 문제를 풀 수 없으며, 한 번에 하나의 문제만 해결할 수 있습니다.

입력

첫 줄에는 테스트 케이스의 수 T (1 ≤ T ≤ 20) 가 주어집니다.

각 테스트 케이스는 두 줄로 구성됩니다.

  1. 첫 번째 줄:

    • N (1 ≤ N ≤ 20): 문제의 개수

    • L (1 ≤ L ≤ 1500): 대회 시간(분)

  2. 두 번째 줄:

    • N개의 정수: 각 문제를 해결하는 데 필요한 추정 시간(분)

출력

각 테스트 케이스마다 다음 형식으로 출력합니다.

Case X: S M T
  • S: 해결한 문제의 수

  • M: 마지막으로 푼 문제가 제출된 시각(분)

  • T: 총 시간(total time)

한 문제도 풀 수 없을 경우 M과 T는 0으로 출력하십시오. (*게시글 에 따라 추가함)

형식은 예제 출력을 참고하십시오.

힌트

예제 입력의 첫 번째 테스트 케이스에서, 대회는 100분 동안 6개의 문제(A~F)를 포함합니다. 두 번째 줄에 각 문제의 해결 시간이 주어집니다. 예를 들어 A는 15분, B는 23분, C는 41분 등입니다.

이 경우 최적의 전략은 최대 5개 문제를 푸는 것입니다. 마지막 문제는 85분에 제출되며, 총 시간은 228이 됩니다. 문제 C는 시간 부족으로 풀 수 없습니다.

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