영수증 세 장의 정확한 합계가 10센트면 현금 정산의 합계도 10일까요? 캐나다의 2013년 안내는 최종 현금 금액을 가까운 5센트로 반올림했어요. 이를 가상 영수증에만 적용하자.
금액은 양의 정수 센트이며, 영수증은 세 장이에요. 각각 별도로 정산해요. 실제 매장의 세금·결제 조건은 묻지 않아요. p₁,p₂,p₃는 원금액, T는 정확합계, S는 정산합계다. ⌊w⌋는 w 이하 최대 정수이며, K는 0 이상 정수예요. x도 양의 정수이고 kᵢ=R(pᵢ)/5입니다.
모든 정수 T≥3에서 가능한 S와 이를 만드는 원금액을 찾아보세요. 한 장의 정산값이 5k이면 k=0에서는 원금액이 1·2뿐이에요. k≥1에서는 5k−2부터 5k+2까지 다섯 정수예요. 작은 양수도 0으로 정산된다.
정산값이 양수인 장수를 z라 하면 z≤min(3,K)입니다. 원합계 하한은 5K+3−3z이며, z를 가장 크게 잡으면 아래 m이 돼요. 상한은 항상 5K+6입니다.
충분성도 만들 수 있어요. min(3,K)장에 k=1을 주고 남은 K를 그중 한 장에 더해요. K=0이면 모두 0입니다. 각 원금액을 최저로 시작해 필요한 만큼 더하자. k=0인 장은 1, 양수인 장은 4까지 늘릴 수 있어 상한까지 모든 정수가 나와요. 다른 원상도 k₁+k₂+k₃=K와 위 한 장 범위·원합계 T를 함께 만족하는 경우 전부예요.
T=10이면 S는 5·10·15입니다. 최소 5의 원상은 (7,1,2)의 여섯 순서와 (6,2,2)의 세 순서뿐이에요. 최대 15는 (4,3,3)의 세 순서뿐이에요. (1,1,8)은 10을 만들어요. 정확합계만 한 번 반올림해서는 이 선택들을 복원하지 못해요.
착안: Canada.