시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 128 MB | 3880 | 1005 | 757 | 27.729% |
구사과국은 동전만 사용하고, 동전의 가치는 다음과 같다.
1, 10, 25, 100, 1000, 2500, 10000, 100000, 250000, 1000000 ...
즉, 식으로 표현하면 K ≥ 0를 만족하는 모든 K에 대해서, 가치가 10K인 동전과 25×100K인 동전이 있는 것이다.
구사과국에 살고 있는 구사과는 초콜릿을 하나 구매해 5차원 세계로 이사가려고 한다. 초콜릿의 가격이 주어졌을때, 이를 구매하기 위해 필요한 동전 개수의 최솟값을 구해보자. 각 동전의 개수는 무한하고, 구매할 때는 정확하게 초콜릿의 가격만큼만 지불해야 한다.
첫째 줄에 테스트 케이스의 개수 T가 주어진다. 둘째 줄부터 T개의 줄에 초콜릿의 가격이 주어진다. 가격의 1015보다 작거나 같은 자연수이다.
총 T개의 줄에 각각의 테스트 케이스의 필요한 동전의 개수를 출력한다.
2 47 9
5 9
2 250111 76540123
4 16