Cantor

Cantor

时间： 10ms        内存：128M

描述：

 

The ternary expansion of a number is that number written in base 3. A number can have more than one ternary expansion. A ternary expansion is indicated with a subscript 3. For example, 1 = 1₃ = 0.222...₃, and 0.875 = 0.212121...₃.

The Cantor set is defined as the real numbers between 0 and 1 inclusive that have a ternary expansion that does not contain a 1. If a number has more than one ternary expansion, it is enough for a single one to not contain a 1.

For example, 0 = 0.000...₃ and 1 = 0.222...₃, so they are in the Cantor set. But 0.875 = 0.212121...₃ and this is its only ternary expansion, so it is not in the Cantor set.

Your task is to determine whether a given number is in the Cantor set.

 

 

输入：

The input consists of several test cases.

Each test case consists of a single line containing a number x written in decimal notation, with 0 <= x <= 1, and having at most 6 digits after the decimal point.

The last line of input is END. This is not a test case.

输出：

For each test case, output MEMBER if x is in the Cantor set, and NON-MEMBER if x is not in the Cantor set.

示例输入：

0
1
0.875
END

示例输出：

MEMBER
MEMBER
NON-MEMBER

提示：

参考答案（内存最优[752]）：

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
int main()
{
	int i,t;
	double x;
	char a[9];
	while(gets(a),strcmp(a,"END"))
	{
		x=atof(a);
		t=0;
		if(x==0||x==1)
			printf("MEMBER\n");
		else
		{
			i=13;
			while(i--)
			{
				x=(x-(int)x)*3;
				if((int)x==1)
				{
					printf("NON-MEMBER\n");
					t++;
					break;
				}
			}
			if(t==0)
				printf("MEMBER\n");
		}
	}
	return 0;
}

参考答案（时间最优[0]）：

#include <iostream>
#include <set>
#include <cstring>
#define INF 100000
#define LNF 1000000
#define MAX 666667
using namespace std;
void om()
{
    cout<<"MEMBER"<<endl;
}
int main()
{
    char n[10];
    char end[]="END";
    while(cin>>n)
    {
        if(strcmp(n,end)==0)break;
        int len=strlen(n);
        if(len==1)
        {
            om();
            continue;
        }
        int num=0;
        int i;
        set<int> st;
        for(i=2;i<len;i++)
        {
            num=num*10+n[i]-'0';
        }
        int count=0;
        while(num<INF)
        {
            if(count++>=5)break;
            num*=10;
        }
        if(num==0)
        {
            om();
            continue;
        }
        bool achive=false;
        while(1)
        {
            while(num<LNF)num*=3;
            if(st.count(num))break;
            st.insert(num);
            if(num/LNF==1)
            {
                achive=true;
                break;
            }
            num%=LNF;
        }
        if(!achive)om();
        else cout<<"NON-MEMBER"<<endl;
    }
    return 0;
}

题目和答案均来自于互联网，仅供参考，如有问题请联系管理员修改或删除。