1’s For All

시간 제한15초메모리 제한1024 MB

요약

100000 이하의 각 n에 대해 1, 덧셈, 곱셈, 괄호, 자릿수 이어붙이기를 사용해 n을 만드는 데 필요한 1의 최소 개수를 구한다.

난이도: 보통10점 중 7점
유형: 동적 계획법, 완전 탐색
정답자: 아직 제출이 없습니다

문제

The complexity of an integer is the minimum number of $1$ 's needed to represent it using only addition, multiplication and parentheses. For example, the complexity of $2$ is $2$ (writing $2$ as $1+1$ ) and the complexity of $12$ is $7$ (writing $12$ as $(1+1+1)\times (1+1+1+1)$ ). We'll modify this definition slightly to allow the concatenation operation as well. This operation (which we'll represent using ©) takes two integers and "glues" them together, so $12\$ © $\ 34$ becomes the four digit number $1234$ . Using this operation, the complexity of $12$ is now $3$ (writing it either as $(1 \$ © $\ 1) + 1$ or $1\$ © $\ (1+1)$ ). Note that the concatenation operation ignores any initial zeroes in the second operand: $1\$ © $\ 01$ does not result in $101$ but results in $11$ .

We'll give you $1$ guess what the object of this problem is.

입력

Each test case consists of a single line containing an integer $n$ , where $0 < n \leq 100\\, 000$ .

출력

Output the complexity of the number, using the revised definition above.

예제2

예제 1
입력
```
2
```
예상 출력
```
2
```
예제 2
입력
```
12
```
예상 출력
```
3
```