오페라의 개막 밤입니다. 당신의 친구는 프리마돈나(주연 여성 성악가)입니다. 당신은 관객석에 있지는 않지만, 그녀가 모든 관객이 일어나 손뼉을 치는 기립박수를 받기를 원합니다.
처음에는 모든 관객이 자리에 앉아 있습니다. 각 관객은 수줍음 정도(shyness level) 를 가지고 있습니다. 수줍음 정도가 Si인 관객은, 이미 최소 Si명의 다른 관객이 일어나 박수를 치고 있을 때에만 일어나서 박수를 치기 시작합니다. 조건이 만족되면 즉시 일어납니다.
Si = 0인 관객은 다른 사람과 상관없이 즉시 일어나 박수를 칩니다.
예를 들어 Si = 2인 관객은 처음에는 앉아 있다가, 두 명 이상의 다른 사람이 이미 서서 박수를 치고 있는 것을 보면 그때 일어납니다.
당신은 관객들의 수줍음 정도를 모두 알고 있으며, 모든 관객이 결국 일어나도록 보장하기 위해 프리마돈나의 친구들을 추가로 초대할 수 있습니다. 이 친구들은 어떤 수줍음 정도라도 가질 수 있으며, 서로 같을 필요도 없습니다.
목표
최종적으로 모든 관객이 기립박수를 치도록 보장하기 위해 초대해야 하는 친구의 최소 인원 수를 구하시오.
입력
입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. 이후 T개의 테스트 케이스가 이어진다.
각 테스트 케이스는 한 줄로 이루어져 있으며,
Smax: 관객 중 가장 높은 수줍음 정도
길이가 Smax + 1인 문자열 하나
가 주어진다.
이 문자열의 k번째 문자(0부터 시작) 는 수줍음 정도가 k인 관객의 수를 의미한다.
예시
문자열 "409" 는 다음을 의미한다.
Si = 0인 관객: 4명
Si = 1인 관객: 0명
Si = 2인 관객: 9명
각 수줍음 정도별 관객 수는 항상 0 이상 9 이하이다.
문자열은 절대 0으로 끝나지 않는다. → 즉, 관객은 항상 최소 한 명 이상 존재한다.
제한 조건
1 ≤ T ≤ 100
0 ≤ Smax ≤ 6
출력
각 테스트 케이스마다 다음 형식으로 한 줄을 출력한다.
Case #x: y
x : 테스트 케이스 번호 (1부터 시작)
y : 초대해야 하는 최소 친구 수
힌트
Case #1: 관객만으로도 순차적으로 모두 일어나 기립박수가 이루어진다. → 친구를 초대할 필요가 없다.
Case #2: 수줍음 정도가 0인 친구 1명을 초대하면, 그 이후 모든 관객이 일어난다.
jtw7913 11달 전
문제
오페라의 개막 밤입니다. 당신의 친구는 프리마돈나(주연 여성 성악가)입니다. 당신은 관객석에 있지는 않지만, 그녀가 모든 관객이 일어나 손뼉을 치는 기립박수를 받기를 원합니다.
처음에는 모든 관객이 자리에 앉아 있습니다. 각 관객은 수줍음 정도(shyness level) 를 가지고 있습니다.
수줍음 정도가
Si인 관객은, 이미 최소Si명의 다른 관객이 일어나 박수를 치고 있을 때에만 일어나서 박수를 치기 시작합니다. 조건이 만족되면 즉시 일어납니다.Si = 0인 관객은 다른 사람과 상관없이 즉시 일어나 박수를 칩니다.Si = 2인 관객은 처음에는 앉아 있다가, 두 명 이상의 다른 사람이 이미 서서 박수를 치고 있는 것을 보면 그때 일어납니다.당신은 관객들의 수줍음 정도를 모두 알고 있으며, 모든 관객이 결국 일어나도록 보장하기 위해 프리마돈나의 친구들을 추가로 초대할 수 있습니다.
이 친구들은 어떤 수줍음 정도라도 가질 수 있으며, 서로 같을 필요도 없습니다.
목표
최종적으로 모든 관객이 기립박수를 치도록 보장하기 위해 초대해야 하는 친구의 최소 인원 수를 구하시오.
입력
입력의 첫 줄에는 테스트 케이스의 수
T가 주어진다.이후
T개의 테스트 케이스가 이어진다.각 테스트 케이스는 한 줄로 이루어져 있으며,
가 주어진다.
이 문자열의 k번째 문자(0부터 시작) 는 수줍음 정도가
k인 관객의 수를 의미한다.예시
문자열
"409"는 다음을 의미한다.Si = 0인 관객: 4명Si = 1인 관객: 0명Si = 2인 관객: 9명각 수줍음 정도별 관객 수는 항상 0 이상 9 이하이다.
문자열은 절대 0으로 끝나지 않는다.
→ 즉, 관객은 항상 최소 한 명 이상 존재한다.
제한 조건
출력
각 테스트 케이스마다 다음 형식으로 한 줄을 출력한다.
x: 테스트 케이스 번호 (1부터 시작)y: 초대해야 하는 최소 친구 수힌트
→ 친구를 초대할 필요가 없다.
0인 친구 1명을 초대하면, 그 이후 모든 관객이 일어난다.2인 관객 2명을 추가하는 것이 최적의 해 중 하나이다.