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

Posted by 111qqz on Sunday, October 2, 2016

TOC

题目链接

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

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

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

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

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

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

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

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

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

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

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

「真诚赞赏,手留余香」

111qqz的小窝

真诚赞赏,手留余香

使用微信扫描二维码完成支付