Codeforces679A—— Bear and Prime 100(人生第一道交互题)

ime limit per test: 1 second
memory limit per test: 256 megabytes
input: standard input
output: standard output

This is an interactive problem. In the output section below you will see the information about flushing the output.

Bear Limak thinks of some hidden number — an integer from interval [2, 100]. Your task is to say if the hidden number is prime or composite.

Integer x > 1 is called prime if it has exactly two distinct divisors, 1 and x. If integer x > 1 is not prime, it's called composite.

You can ask up to 20 queries about divisors of the hidden number. In each query you should print an integer from interval [2, 100]. The system will answer "yes" if your integer is a divisor of the hidden number. Otherwise, the answer will be "no".

For example, if the hidden number is 14 then the system will answer "yes" only if you print 2, 7 or 14.

When you are done asking queries, print "prime" or "composite" and terminate your program.

You will get the Wrong Answer verdict if you ask more than 20 queries, or if you print an integer not from the range [2, 100]. Also, you will get the Wrong Answer verdict if the printed answer isn't correct.

You will get the Idleness Limit Exceeded verdict if you don't print anything (but you should) or if you forget about flushing the output (more info below).

Input
After each query you should read one string from the input. It will be " yes" if the printed integer is a divisor of the hidden number, and " no" otherwise.
Output

Up to 20 times you can ask a query — print an integer from interval [2, 100] in one line. You have to both print the end-of-line character and flush the output. After flushing you should read a response from the input.

In any moment you can print the answer "prime" or "composite" (without the quotes). After that, flush the output and terminate your program.

To flush you can use (just after printing an integer and end-of-line):

  • fflush(stdout) in C++;
  • System.out.flush() in Java;
  • stdout.flush() in Python;
  • flush(output) in Pascal;
  • See the documentation for other languages.

Hacking. To hack someone, as the input you should print the hidden number — one integer from the interval [2, 100]. Of course, his/her solution won't be able to read the hidden number from the input.

Examples Input
yes
no
yes
Examples Output
2
80
5
composite
Examples Input
no
yes
no
no
no
Examples Output
58
59
78
78
2
prime

题目大意:

有一个[2,100]内的数,有不超过20次机会询问某个数是不是它的约数,判断这个数是不是素数。

题解:

根据唯一分解定理(任何大于1的自然数,都可以唯一分解成有限个质数的乘积)。

容易推出每个合数的唯一分解式一定是两个及以上的素数的乘积。

所以枚举所有的素数,如果有两个及以上素数约数则是合数。

由于还有可能是某个素数的平方所以还要枚举素数的平方,一共询问19次。

代码:

另外最好只要有输出就跟一个fflush

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>

using namespace std;

int p[] = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,4,9,25,49};
string s;

int main(){
	
	int ans = 0;
	for(int i=0 ; i<19 ; i++){
		printf("%d\n",p[i]);
		fflush(stdout);
		cin>>s;
		if(s == "yes")++ans;
	}
	if(ans >= 2)printf("composite\n");
	else printf("prime\n");
	fflush(stdout);
	
	return 0;
}
相关文章
相关标签/搜索