In Part 1 here I have shown the code that gives full points in the interactive CodeForces.Com problem for Bear And Prime.
The trick is that writing hard-coded values in a code is really far away from a good practice in programming and although in that case it was ok, because this was a competition, in general it is not well accepted.
Thus, I have decided to rewrite the problem a little, thus avoiding the hard-coded values. Thus, I have decided to change the problem into the following – read the maximal number for the values, which the bear can think of and start printing.
Thus, I have to manage to build the two lists by myself – the list of the prime numbers from [2 to the user’s input] and the list of squares of those prime number up to the input. The first one is actually exactly Sieve of Eratosthenes and the second one has to do with squaring the results from the Sieve. Then we simply concatenate the two lists and we start asking, using them. As you see, this is the result for 200, the second list is with the squares, equal to 4,9,25,49,121,169.
The code looks like this:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 |
using System; using System.Collections.Generic; using System.Linq; class CompositeAndPrime { static void Main() { int int_final = int.Parse(Console.ReadLine()); List<int> l_prime = GeneratePrimesUpTo(int_final); List<int> l_prime_squares = GeneratePrimesSquaresUpTo(l_prime,int_final); string str_prime1 = string.Join(",", l_prime.ToArray()); Console.WriteLine(str_prime1); string str_prime2 = string.Join(",", l_prime_squares.ToArray()); Console.WriteLine(str_prime2); List<int> union = l_prime.Concat(l_prime_squares).ToList(); string str_prime3 = string.Join(",", union.ToArray()); Console.WriteLine(str_prime3); int i_sum = 0; for (int i = 0; i < union.Count; i++) { Console.WriteLine(union[i]); Console.Out.Flush(); string reader1 = Console.ReadLine(); if (reader1.Equals("yes")) { i_sum++; if (i_sum >= 2) { Console.WriteLine("composite"); Console.Out.Flush(); return; } } } Console.WriteLine("prime"); Console.Out.Flush(); return; } static List<int> GeneratePrimesSquaresUpTo(List<int> l_primes ,int int_final) { List<int> list_result = new List<int> {}; for (int i = 0; i < int_final; i++) { if (l_primes[i]* l_primes[i] >= int_final) { break; } list_result.Add(l_primes[i] * l_primes[i]); } return list_result; } static List<int> GeneratePrimesUpTo(int int_final) { List<int> list_result = new List<int> {2}; int int_next = 3; for (int i = 0; i<int_final; i++) { bool b_is_prime = true; int int_sqrt = int_next * int_next; for (int k = 0; k < list_result.Count; k++) { if (int_next % list_result[k] == 0) { b_is_prime = false; break; } } if (b_is_prime) { list_result.Add(int_next); } int_next+=2; } return list_result; } } |
Here is the code in github.com, enjoy it! 😀