codeforces 679A A. Bear and Prime 100 (交互题,构造)

题目链接

题意:存在一个[2..100]之间的数,每次可以询问一个数是否是该数的因子,返回yes或者no,最多询问20次。每次要输出询问的数,以及最后要输出这个数是否是质数。

思路:第一次做交互题。。。发现完全不能按照以前的思路。。。

更像是相反的。。。把output看做某种输入。。。input里是某种结果。。。我要根据input里的东西来确定一些东西。

就是先有output,再有input。。。output是选手的输入(最后一个除外),input是返回结果(不是你写的代码的返回结果)

对于这道题。。我们要尽可能少得猜一个数的因子,以确定该数是否为质数。

一个数不是质数的话,就有至少两个大于1的因子。。。

很容易想到。。。判素因子。。。

由于至少有2个非1的因子才不是素数。。。最小为2,因此另一个因子不会大于50.。。

此外。。。有可能有两个相同质因数组成的因子。。。。

因此还要判一下22,35,55,77

 1/* ***********************************************
 2Author :111qqz
 3Created Time :Sun 02 Oct 2016 08:22:44 PM CST
 4File Name :code/cf/problem/679A.cpp
 5************************************************ */
 6#include <cstdio>
 7#include <cstring>
 8#include <iostream>
 9#include <algorithm>
10#include <vector>
11#include <queue>
12#include <set>
13#include <map>
14#include <string>
15#include <cmath>
16#include <cstdlib>
17#include <ctime>
18#define fst first
19#define sec second
20#define lson l,m,rt<<1
21#define rson m+1,r,rt<<1|1
22#define ms(a,x) memset(a,x,sizeof(a))
23typedef long long LL;
24#define pi pair < int ,int >
25#define MP make_pair
26using namespace std;
27const double eps = 1E-8;
28const int dx4[4]={1,0,0,-1};
29const int dy4[4]={0,-1,1,0};
30const int inf = 0x3f3f3f3f;
31int prime[19]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,4,9,25,49};
32string st;
33int main()
34{
35	#ifndef  ONLINE_JUDGE 
36	freopen("code/in.txt","r",stdin);
37  #endif
38	int cnt = 0 ;
39	for ( int i = 0 ; i < 19 ; i++)
40	{
41	    cout<<prime[i]<<endl;
42	    fflush(stdout);
43	    cin>>st;
44	    if (st=="yes") cnt++;
45	}
46	if (cnt>=2) puts("composite");
47	else puts("prime");
48	fflush(stdout);
49  #ifndef ONLINE_JUDGE  
50  fclose(stdin);
51  #endif
52    return 0;
53}