유로의 효율성

2002년 1월 1일, 네덜란드를 비롯한 여러 유럽 국가가 자국 통화를 버리고 유로화를 도입했다. 이로 인해 국내외를 막론하고 돈을 내는 방식이 달라졌다.

예전에 68길더짜리 책을 사는 학생은 50길더 지폐 한 장과 10길더 지폐 두 장을 내고 2길더를 거슬러 받을 수 있었다: 50 + 10 + 10 - 1 - 1 = 68. 다른 방법으로는 50 + 25 - 5 - 1 - 1 이나 100 - 25 - 5 - 1 - 1 도 있었다. 어느 방법이든 항상 최소 5개의 단위(지폐나 동전)가 필요했고, 그보다 적게는 낼 수 없었다.

요즘 68유로짜리 책을 사는 것은 더 간단하다: 50 + 20 - 2 = 68, 즉 3개의 단위만 있으면 된다. 이는 우연이 아니다. 많은 경우 유로로 지불하는 편이 길더로 지불하는 것보다 효율적이다. 이것은 유로의 가치와는 아무런 상관이 없고, 오직 선택된 화폐 단위 때문이다. 길더의 단위는 1, 2.5, 5, 10, 25, 50 이었고, 유로의 단위는 1, 2, 5, 10, 20, 50 이다.

이 문제에서는 100센트 이하의 금액만 다룬다. 유로에는 1, 2, 5, 10, 20, 50센트 동전이 있다. 1센트부터 100센트까지의 임의의 금액을 낼 때, 지불 또는 거스름돈으로 평균 2.96개의 동전이 사용된다. 이 기준에서 유로 동전 체계는 최적이 아니다. 동전이 1, 24, 34, 39, 46, 50 이라면 68센트를 동전 두 개(34 + 34)로 낼 수 있고, 1센트부터 100센트까지의 금액을 낼 때 필요한 동전 수의 평균은 2.52개로 줄어든다.

이런 체계는 암산하기는 더 어렵지만, 오늘날 거의 누구나 들고 다니는 휴대전화로는 쉽게 계산할 수 있다. 미래를 대비해, 한 위원회가 100센트 이하 금액에 대해 가장 효율적인 동전 체계를 찾고 있으며 당신의 도움이 필요하다.

동전 체계가 주어졌을 때, 1센트부터 100센트까지의 어떤 금액이든 낼 때 필요한 동전 수의 평균과 최댓값을 계산하는 프로그램을 작성하라. 양쪽 모두 각 동전을 무제한으로 가지고 있다고 가정한다. 금액을 낸다는 것은 동전 몇 개를 내고 거스름돈으로 동전 몇 개를 돌려받는 것을 뜻하며, '사용된 동전 수'는 그 둘의 합이다. 각 금액에 대해 이 합을 최소로 만들어야 한다.

첫째 줄에 테스트 케이스의 수가 주어진다. 각 테스트 케이스는 한 줄에 오름차순으로 정렬된 서로 다른 양의 정수 6개, 즉 동전의 값들로 이루어진다. 첫 번째 값은 항상 1이고, 마지막 값은 100보다 작다.

각 테스트 케이스마다 한 줄에, 1센트부터 100센트까지의 금액을 낼 때 사용되는 동전 수의 평균과 최댓값을 공백으로 구분하여 출력한다. 평균은 항상 소수점 아래 두 자리까지 출력하고, 최댓값은 항상 정수이다.