Bear and Prime 100
题意翻译
这是一道交互题。
有一个在闭区间[2,100]里面的整数X，你的任务是判断整数x是质数还是合数。
你可以向系统询问一个数是否为该数的约数，询问方式如下：
1.你输出一个在闭区间[2,100]里面的整数
2.系统回答yes或者no(yes表示你输出的数是该数的约数，no表示你输出的数不是该数的约数)
注意：你最多只能提出20次询问！
每输出一个询问，你需要使用flush，下面提供一些语言的flush语法：
C++语言: fflush(stdout)
JAVA语言: System.out.flush()
Python语言: stdout.flush()
Pascal语言: flush(output)
注：以下内容为译者良心添加
以C++语言为例做一个交互示范(假设x=50):
```
#include<bits/stdc++.h>
using namespace std;
int main()
{
char s[10],cnt=0;
cout<<2<<endl;
fflush(stdout);
cin>>s;//此时读入为yes，因为2是50的约数
if(s[0]=='y') cnt++;
cout<<25<<endl;
fflush(stdout);
cin>>s;//此时读入为yes，因为25是50的约数
if(s[0]=='y') cnt++;
if(cnt>=2) cout<<"composite"<<endl;
fflush(stdout);
return 0;
}
```
题目描述
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).
输入输出格式
输入格式
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.
输出格式
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.
输入输出样例
输入样例 #1
yes
no
yes
输出样例 #1
2
80
5
composite
输入样例 #2
no
yes
no
no
no
输出样例 #2
58
59
78
78
2
prime
说明
The hidden number in the first query is $ 30 $ . In a table below you can see a better form of the provided example of the communication process.
The hidden number is divisible by both $ 2 $ and $ 5 $ . Thus, it must be composite. Note that it isn't necessary to know the exact value of the hidden number. In this test, the hidden number is $ 30 $ .
$ 59 $ is a divisor of the hidden number. In the interval $ [2,100] $ there is only one number with this divisor. The hidden number must be $ 59 $ , which is prime. Note that the answer is known even after the second query and you could print it then and terminate. Though, it isn't forbidden to ask unnecessary queries (unless you exceed the limit of $ 20 $ queries).