A+B

면접 대비

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

요약

주어진 숫자들을 앞자리가 0이 아닌 두 정수로 재배열하여 합이 가장 커지도록 하고, 그 최대 합을 출력합니다.

문제

오늘의 첫 문제는 $a$ + $b$ 만큼 쉽다.

숫자로 이루어진 문자열이 주어진다. 이 숫자들을 재배열하여 음이 아닌 정수 $a$ 와 $b$ 를 만들고, 합 $a + b$ 가 최대가 되도록 하라.

각 수는 적어도 한 자리 숫자로 이루어져야 한다. 앞자리 0은 허용되지 않지만, 숫자 0 한 자리로 이루어진 수 0은 허용된다. 주어진 입력 문자열에 나타나는 각 숫자를 나타난 횟수만큼 정확히 사용해야 한다.

입력 파일의 첫 줄에 테스트 케이스의 개수 $t$ 가 주어진다. 각 테스트 케이스 앞에는 빈 줄이 있다. 각 테스트 케이스는 숫자로 이루어진 문자열 한 줄로 구성된다. 문자열의 길이가 3자리 이상이면 모든 자리가 0인 것은 아니다.

각 테스트 케이스마다 얻을 수 있는 합의 최댓값을 정수 하나로 한 줄에 출력한다.

처음 두 테스트 케이스는 쉬운 입력 파일 a1.in에 나올 수 있고, 나머지 두 개는 어려운 입력 파일 a2.in에만 나올 수 있다.

각 테스트 케이스의 최적 숫자 배열 하나는 10+0, 71+5, 1+2, 44444+4이다.