异想天开

What's the true meaning of light, Could you tell me why

笨小熊

日期:2015-06-09 19:33:22
  
最后更新日期:2015-06-16 15:28:52
描述
笨小熊的词汇量很小,所以每次做英语选择题的时候都很头疼。但是他找到了一种方法,经试验证明,用这种方法去选择选项的时候选对的几率非常大!
这种方法的具体描述如下:假设maxn是单词中出现次数最多的字母的出现次数,minn是单词中出现次数最少的字母的出现次数,如果maxn-minn是一个质数,那么笨小熊就认为这是个Lucky Word,这样的单词很可能就是正确的答案。

输入
第一行数据N(0每组测试数据输入只有一行,是一个单词,其中只可能出现小写字母,并且长度小于100。
输出
每组测试数据输出共两行,第一行是一个字符串,假设输入的的单词是Lucky Word,那么输出“Lucky Word”,否则输出“No Answer”;
第二行是一个整数,如果输入单词是Lucky Word,输出maxn-minn的值,否则输出0
样例输入
2
error
olympic
样例输出
Lucky Word
2
No Answer
0
解析:
[code lang="cpp"]
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cassert>
using namespace std;

int cmp(const void *a,const void *b){
const char *pa=(char *)a;
const char *pb=(char *)b;
return *pa-*pb;
}

const int PRIMELEN=1010;
const int ARRAYLEN=(PRIMELEN+7)/8;
static char prime[ARRAYLEN];

void primeinit(){
prime[0]=0xfc; //2是个质数
for (int i=1; i<ARRAYLEN; ++i){
prime[i]=0xff;
}
for (int i=2; i<=PRIMELEN; ++i){
for (int j=i; j<=PRIMELEN; ++j){
char m=prime[j/8]&(1<<(j%8));
if (0==m){
continue;
}
i=j;
break;
}

for (int j=i+i; j<=PRIMELEN; j +=i){
prime[j/8] = prime[j/8]&(~(1<<(j%8)));
}

}
}


int isprime(int n){
assert(n>=0);
unsigned char m=prime[n/8]&(1<<(n%8));
return m>0?1:0;
}

int solve(){
int t;
scanf("%d", &t);
while (t--){
const int N=1010;
char buf[N];
scanf("%s",buf);
int len=strlen(buf);
if ( len && buf[len-1]=='\n'){
buf[len-1]=0;
len--;
}

if (0==len){
printf("No Answer\n0\n");
continue;
}
qsort((char*)buf,len,sizeof(char),cmp);


char pre=buf[0];
int min=10000,max=0,repeat=1;
for (int i=1; i<len; ++i){
if (buf[i]==pre){
++repeat;
} else {
if (repeat<min){
min=repeat;
}
if (repeat>max){
max=repeat;
}
pre=buf[i];
repeat=1;
}
}
if (repeat<min){
min=repeat;
}
if (repeat>max){
max=repeat;
}

if (isprime(max-min)){
printf("Lucky Word\n%d\n",max-min);
} else {
printf("No Answer\n0\n");
}
}
return 0;
}

int test(){
printf("start...\n");
primeinit();
printf("end...\n");
for (int i=0; i<ARRAYLEN; ++i){
printf("%x ",0xff&prime[i]);
}
printf("\n");
return 0;
}

int test1(){
primeinit();
int n;
while (scanf("%d",&n)!=-1){
if (isprime(n)){
printf("%d is prime\n",n);
} else {
printf("%d is not prime\n",n);
}
}
return 0;
}

int main()
{
primeinit();
solve();
return 0;
}
[/code]

涉及质数,验证质数的算法:
[code lang="cpp"]
#!/usr/bin/python
def test():
l=[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97]
for i in l:
print i

def test1():
for i in range(101):
print i

if __name__=='__main__':
test()
[/code]