CF #356 div1 A. Bear and Prime 100

题目链接：http://codeforces.com/contest/679/problem/A

CF有史以来第一次出现交互式的题目，大致意思为选择2到100中某一个数字作为隐藏数，你可以询问最多20次问题，每一次询问一个数字x，如果预先选定的隐藏数是x的倍数，则回复"yes",否则回复"no"，你只需要判那个数字是否为质数（不一定需要知道具体是多少）

如果一个数字是两个质数积的倍数，则这个数字一定是合数，另外需要注意，两个质数是可以相同的。即如果隐藏数是a*b的倍数（其中a和b为两个质数），则隐藏数是合数。由此，我们只需要枚举50以内的质数即可（超过50的质数乘以2也已经大于100了）。则2到50有15个质数，分别是2，3，5，7，11，13，17，19，23，29，31，37，41，43，47。

只需要判断隐藏数是否为其中至少两个数字的倍数即可，特别注意在2，3，5，7回复"yes后，需要再判断是否为4，9，25，49的倍数。

 import java.io.OutputStream;

 import java.io.IOException;

 import java.io.InputStream;

 import java.io.PrintWriter;

 import java.util.List;

 import java.util.StringTokenizer;

 import java.io.IOException;

 import java.io.BufferedReader;

 import java.io.InputStreamReader;

 import java.util.ArrayList;

 import java.io.InputStream;

 public class Main {

     public static void main(String[] args) {

         InputStream inputStream = System.in;

         OutputStream outputStream = System.out;

         InputReader in = new InputReader(inputStream);

         PrintWriter out = new PrintWriter(outputStream);

         TaskA solver = new TaskA();

         solver.solve(1, in, out);

         out.close();

     }

     static class TaskA {

         public void solve(int testNumber, InputReader in, PrintWriter out) {

             List<Integer> primes = new ArrayList<>();

             for (int i = 2; i <= 50; i++) {

                 boolean isPrime = true;

                 for (int j = 2; j * j <= i; j++) {

                     if (i % j == 0) {

                         isPrime = false;

                     }

                 }

                 if (isPrime) {

                     primes.add(i);

                 }

             }

             int cnt = 0;

             for (Integer prime : primes) {

                 out.println(prime);

                 out.flush();

                 String reply = in.next();

                 cnt += (reply.equals("yes") ? 1 : 0);

                 if (prime * prime <= 100) {

                     out.println(prime * prime);

                     out.flush();

                     reply = in.next();

                     cnt += (reply.equals("yes") ? 1 : 0);

                 }

                 if (cnt > 1) {

                     out.println("composite");

                     return;

                 }

             }

             out.println("prime");

         }

     }

     static class InputReader {

         private BufferedReader reader;

         private StringTokenizer tokenizer;

         public InputReader(InputStream stream) {

             reader = new BufferedReader(new InputStreamReader(stream));

             tokenizer = null;

         }

         public String next() {

             while (tokenizer == null || !tokenizer.hasMoreTokens()) {

                 try {

                     tokenizer = new StringTokenizer(reader.readLine());

                 } catch (IOException e) {

                     throw new RuntimeException(e);

                 }

             }

             return tokenizer.nextToken();

         }

     }

 }

巴特西

CF #356 div1 A. Bear and Prime 100

最新文章

热门文章