다이버전스 미터

시간 제한2초메모리 제한512 MB

요약
소수점 여섯 자리로 주어진 표시값에 대해 0 이상 999 이하의 정수 99개가 그 값을 만들 수 있는지 판정하고, 가능하면 그러한 수열을 출력하거나 MISMATCH를 출력한다.
난이도

보통10점 중 7점

유형
구현, 수학, 완전 탐색, 정렬
정답자
아직 제출이 없습니다

문제

다이버전스 미터(Divergence Meter)는 99개의 정수 x1, x2, ..., x99 (0 ≤ xi ≤ 999)를 입력으로 받아, 그 정수들의 통계적 특성을 정수부 한 자리와 소수부 여섯 자리, 총 일곱 자리를 가지는 실수로 표시하는 장치이다. 이 장치는 아래와 같은 세 개의 값을 계산하여 통계적 특성을 표시한다.

  • 평균: 99개 정수의 평균 avg를 계산하여, A = (avg를 소숫점 첫째 자리에서 반올림한 수)로 계산한다.
  • 평균과의 차이가 큰 수들의 개수: B = (xi들 중 평균과 10 이상 차이나는 수들의 개수)로 계산한다.
  • 중앙값과의 차이가 큰 수들의 개수: C = (xi들 중 중앙값과 10 이상 차이나는 수들의 개수)로 계산한다.

다이버전스 미터가 최종적으로 표시하는 실수는 10-2 × A + 10-4 × B + 10-6 × C로 정의된다. 즉, 출력된 실수에서 소숫점을 지웠을 때, 앞의 세 자리가 A를, 그 다음 두 자리가 B를, 마지막 두 자리가 C를 나타낸다.

다이버전스 미터의 성질을 연구하고 있는 대학원생 크리스티나는, 연구가 잘 풀리지 않자 다이버전스 미터가 고장난 것이 아닌지 의심하기 시작했다. 크리스티나는 다이버전스 미터가 지금 표시하고 있는 실수가 어떤 입력을 주어도 나올 수 없는 값이라고 주장하기 시작하였다. 여러분은 이 주장을 확인하는 프로그램을 작성하기로 하였다. 다이버전스 미터가 표시한 실수를 입력으로 받아, 해당 결과를 만들 수 있는 입력 x1, x2, ..., x99를 출력하는 프로그램을 작성하라.

입력

다이버전스 미터가 표시한 실수 D가 정확히 소수점 여섯째 자리까지 주어진다. (0.000000 ≤ D ≤ 9.999999)

출력

문제의 조건을 만족하는 99개의 정수 x1, x2, ..., x99가 존재한다면, 첫 줄에 "MATCH"를 큰따옴표 없이 출력한다. 이후, 두 번째 줄에 x1, x2, ..., x99를 공백으로 구분하여 출력한다. 만약 조건을 만족하는 수열이 여러 가지 존재한다면, 그 중 아무 것이나 출력한다.

문제의 조건을 만족하는 정수들이 존재하지 않는다면, 첫 줄에 "MISMATCH"를 큰따옴표 없이 출력한다.

예제3

  1. 예제 1

    입력
    0.571046
    
    예상 출력
    MATCH
    46 46 46 46 46 46 46 46 46 47 47 47 47 47 47 47 47 47 47 47 47 47 47 47 47 47 47 47 47 47 47 47 47 47 47 47 47 47 47 47 47 47 47 47 47 47 47 47 47 47 56 56 56 66 66 66 66 66 66 66 66 66 66 66 66 66 66 66 66 66 66 66 66 66 66 66 66 66 66 66 66 66 66 66 66 66 66 66 66 66 66 66 66 66 66 66 66 66 115
    
  2. 예제 2

    입력
    1.048596
    
    예상 출력
    MATCH
    0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 10 10 10 113 113 113 113 113 113 113 113 113 113 113 113 113 113 114 114 114 114 114 114 114 114 114 114 114 114 114 114 114 114 114 114 114 114 114 114 114 114 114 114 114 114 114 334 999 999 999 999 999
    
  3. 예제 3

    입력
    0.571082
    
    예상 출력
    MISMATCH