식품의 구성 성분

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

요약

함량이 감소하는 순서로 주어진 재료들에 대해 일부는 함량이 명시되어 있을 때, 각 재료 함량의 최솟값과 최댓값을 구하고 불가능하면 EI SAA를 출력한다.

난이도: 보통10점 중 6점
유형: 그리디, 수학, 구현, 누적 합
정답자: 아직 제출이 없습니다

문제

식품 포장지에는 그 제품을 이루는 구성 성분이 적혀 있으며, 항상 함량이 많은 순서대로 나열됩니다. 즉, 가장 많이 들어 있는 성분을 맨 앞에 쓰고, 그다음으로 많은 성분을 그 뒤에 쓰는 식입니다. 어떤 성분은 함량이 정확히 명시되어 있지만, 명시되지 않은 성분도 있습니다.

각 함량은 백분율(%)로 나타내며 $0.1\%$ 의 배수이고, 모든 성분은 적어도 $0.1\%$ 이상 들어 있습니다. 나열된 성분들이 제품 전체를 이루므로 함량의 합은 정확히 $100\%$ 입니다. 목록이 함량의 엄격한 감소 순서이므로, 각 성분의 함량은 바로 앞 성분보다 반드시 더 작습니다(두 성분의 함량이 같을 수는 없습니다).

성분 목록이 주어질 때, 각 성분이 가질 수 있는 함량의 최솟값과 최댓값을 구하세요.

입력

첫째 줄에 성분의 개수 $N$ ( $1 \le N \le 45$ )이 주어집니다.

다음 $N$ 개의 줄에는 함량이 많은 순서대로 각 성분이 주어집니다. 각 줄은 성분의 이름만 있거나, 이름 뒤에 공백 하나를 두고 그 함량이 함께 주어집니다. 이름은 알파벳 대소문자(A–Z, a–z)로만 이루어지며 길이는 최대 $20$ 자입니다. 명시된 함량은 $0.1$ 의 배수인 백분율 값입니다.

출력

주어진 순서대로 각 성분을 한 줄에 하나씩, 이름과 함께 가능한 최솟값 및 최댓값 함량을 공백으로 구분하여 출력합니다. 모든 수는 소수점 아래 한 자리까지, 소수점 기호로 마침표를 사용하여 출력합니다.

만약 주어진 목록이 불가능하다면(성분 함량을 어떻게 배정해도 조건을 만족할 수 없다면), 대신 EI SAA 한 줄만 출력합니다.

예제4

예제 1

입력

3
Jahu
Piim
Suhkur

예상 출력

Jahu 33.5 99.7
Piim 0.2 49.9
Suhkur 0.1 33.2

예제 2
입력
```
2
Siga
Kana 50
```
예상 출력
```
EI SAA
```
예제 3
입력
```
1
Vesi
```
예상 출력
```
Vesi 100.0 100.0
```

예제 4

입력

3
Jahu
Piim 20
Suhkur

예상 출력

Jahu 60.1 79.9
Piim 20.0 20.0
Suhkur 0.1 19.9