레이팅 미적용농부 존(Farmer John)은 최근 동네 정사각형 마트(물론 정사각형 물건만 파는 가게이다)에서 구입한 정사각형 타일들로 헛간 바닥을 리모델링하려고 한다. 안타깝게도 구입 전에 헛간의 크기를 제대로 재지 않아서, 이제 타일 몇 개를 다른 크기의 새 정사각형 타일로 교환해야 한다.
FJ가 이전에 구입한 N개의 정사각형 타일의 한 변의 길이는 A_1...A_N이다. 존은 이 중 일부를 새 정사각형 타일로 교환하여, 타일들의 넓이의 총합이 정확히 M이 되게 하고 싶다. 정사각형 마트는 현재 특별 행사를 진행 중이다. 한 변의 길이가 A_i인 타일을 |A_i-B_i|*|A_i-B_i| 단위의 비용으로 한 변의 길이가 B_i인 새 타일과 교환할 수 있다. 하지만 이 행사는 이전에 구입한 타일에만 적용된다. 즉, FJ는 다른 타일을 교환해서 얻은 타일을 다시 교환할 수 없다 (예를 들어, 크기 3인 타일을 크기 2인 타일로 교환한 뒤 그것을 다시 크기 1인 타일로 교환할 수는 없다).
타일들의 넓이의 합이 M이 되도록 교환하는 데 필요한 최소 비용을 구하시오. 넓이 M을 만드는 것이 불가능하면 -1을 출력한다.
첫째 줄: 공백으로 구분된 두 정수 N (1<=N<=10)과 M (1<=M<=10,000).
둘째 줄부터 1+N번째 줄까지: 각 줄에 입력 정사각형의 한 변의 길이를 나타내는 정수 A_1부터 A_N 중 하나가 주어진다 (1<=A_i<=100).
총 넓이 M을 얻기 위해 타일을 교환하는 최소 비용, 불가능하면 -1.
tilechng.in · 출력을 쓸 파일 tilechng.out3 6
3
3
15Input details: There are 3 tiles. Two are squares of side length 3, and one is a square with side length 1. We would like to exchange these to make a total area of 6.
Output details: Exchange one of the side-3 squares for a side-2 square, and another side-3 square for a side-1 square. This gives the desired area of 4+1+1=6 and costs 4+1=5 units.
riseoj 작성
출처 올림피아드 > USACO > 2011-2012 > November > Silver