칸토어 집합

면접 대비

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

요약
소수점 이하 6자리 이내의 0과 1 사이 실수 x가 주어질 때, 1을 포함하지 않는 삼진 전개가 존재하는지, 즉 x가 칸토어 집합에 속하는지 판정한다.
난이도

보통10점 중 5점

유형
수학, 정수론, 구현, 조합론
정답자
아직 제출이 없습니다

문제

어떤 수의 삼진 전개(ternary expansion)는 그 수를 밑이 3인 진법으로 나타낸 것이다. 한 수는 삼진 전개를 두 가지 이상 가질 수 있다. 삼진 전개임을 나타내기 위해 아래 첨자 3을 붙인다. 예를 들어 1=13=0.222…31 = 1_3 = 0.222\ldots_3 이고, 0.875=0.212121…30.875 = 0.212121\ldots_3 이다.

칸토어 집합(Cantor set)은 0 이상 1 이하의 실수 중에서, 숫자 1을 포함하지 않는 삼진 전개를 가지는 수들의 집합으로 정의된다. 어떤 수가 삼진 전개를 여러 개 가진다면, 그중 하나라도 숫자 1을 포함하지 않으면 칸토어 집합에 속한다.

예를 들어 0=0.000…30 = 0.000\ldots_3 이고 1=0.222…31 = 0.222\ldots_3 이므로 두 수 모두 칸토어 집합에 속한다. 하지만 0.875=0.212121…30.875 = 0.212121\ldots_3 이고 이것이 유일한 삼진 전개이므로, 0.875는 칸토어 집합에 속하지 않는다.

주어진 수가 칸토어 집합에 속하는지 판별하시오.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다.

각 테스트 케이스는 십진법으로 표기된 수 xx가 한 줄에 하나씩 주어진다. 0≤x≤10 \le x \le 1 이며, 소수점 아래 자릿수는 최대 6자리이다.

입력의 마지막 줄은 END이며, 이는 테스트 케이스가 아니다.

출력

각 테스트 케이스마다, xx가 칸토어 집합에 속하면 MEMBER를, 속하지 않으면 NON-MEMBER를 한 줄에 출력한다.

예제1

  1. 예제 1

    입력
    0
    1
    0.875
    END
    
    예상 출력
    MEMBER
    MEMBER
    NON-MEMBER