C# – Algorithm – Bear And Prime, Interactive Problem in CodeForces

Posted on June 10, 2016 by

On Wednesday I was participating in a round of the second division of Codeforces.Com and I managed to resolve 2 problems (1 completely, 1 not exactly completely :)).

The third problem was written to be “interactive” and as far as I was a bit tired (Wednesday was a working day) I have decided to take a look at it when I have more time after the competition. Furthermore, I did not see how to “flush” for C#, thus my chances were close to 0. Today, the “after the competition” day has become and I have to take a look at the problem. Here is the description:

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).

Let’s see what I understood – pretty much the problem of the problem is reading and writing the input. The rest is really trivial. Here you are the one to start guessing with numbers and the codeforces.com is the one to answer. Pretty much the roles are reversed. And you have to do this steadily. Once you grasp the idea, you should be aware what are the prime numbers up to 100 and how to guess whether the number of the bear is prime or not with up to 20 questions.

Well, if you have done some Maths at school, you would most probably be aware what are the prime numbers up to 100. If not, you can google it and see that the primes are 25 and the non primes 74. (1 is not included in the problem).

There is a trick, saying that every divisor of a composite number is either a prime number or can be divided to a composite number, learnt somewhere in 4. grade at school. By using this, we may start asking with prime numbers up to 47 (because 48,49 and 50 are composites) and make sure that if the number has two divisors from our list, then it is a prime. Furthermore, we may ask for the squares of the primes, less than 50. E.g. 4,9,25 and 49. Thus, a possible solution is here:

using System;
using System.Collections.Generic;

class CompositeAndPrime
{
    static void Main()
    {
        List<int> l_prime = new List<int> { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47 };
        List<int> l_composite_sq = new List<int> { 4, 9, 25, 49 };

        int i_sum = 0;
        int i_new_number = 0;
        int i_internal_counter = 0;

        for (int i = 0; i < l_prime.Count ; i++)
        {
            Console.WriteLine(l_prime[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;
                }
            }
            if (i_internal_counter < l_composite_sq.Count)
            {
                i_new_number = (int)(Math.Pow(l_prime[i_internal_counter], 2));
                i_internal_counter++;
                Console.WriteLine(i_new_number);
                Console.Out.Flush();
                string reader2 = Console.ReadLine();
                if (reader2.Equals("yes"))
                {
                    Console.WriteLine("composite");
                    Console.Out.Flush();
                    return;
                }
            }        
        }
        Console.WriteLine("prime");
        Console.Out.Flush();
        return;
    }
}

using System;

using System.Collections.Generic;

class CompositeAndPrime

{

static void Main()

{

List<int> l_prime = new List<int> { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47 };

List<int> l_composite_sq = new List<int> { 4, 9, 25, 49 };

int i_sum = 0;

int i_new_number = 0;

int i_internal_counter = 0;

for (int i = 0; i < l_prime.Count ; i++)

{

Console.WriteLine(l_prime[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;

}

if (i_internal_counter < l_composite_sq.Count)

{

i_new_number = (int)(Math.Pow(l_prime[i_internal_counter], 2));

i_internal_counter++;

Console.WriteLine(i_new_number);

Console.Out.Flush();

string reader2 = Console.ReadLine();

if (reader2.Equals("yes"))

{

Console.WriteLine("composite");

Console.Out.Flush();

return;

}

Console.WriteLine("prime");

Console.Out.Flush();

return;

}

Actually, while writing this article I simply realized that the problem extremely trivial – we may simply write 19 numbers in a list and ask for confirmation whether they are prime. If we get two confirmations, the result is a composite. Like this:

using System;
using System.Collections.Generic;

class CompositeAndPrime
{
    static void Main()
    {
        List<int> l_prime = new List<int> { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 4, 9, 25, 49 };
        int i_sum = 0;

        for (int i = 0; i < l_prime.Count; i++)
        {
            Console.WriteLine(l_prime[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;
    }
}

using System;

using System.Collections.Generic;

class CompositeAndPrime

{

static void Main()

{

List<int> l_prime = new List<int> { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 4, 9, 25, 49 };

int i_sum = 0;

for (int i = 0; i < l_prime.Count; i++)

{

Console.WriteLine(l_prime[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;

}

Now it looks humiliating 🙂 It is definitely easier to code than the first two problems and not that sophisticated. 🙂 And it passes all 50+ tests of codeforces. Man should just think for 5 minutes and he can come up with the 19 numbers 🙂

Here is my submission history on this problem:

Pretty much that is it! Enjoy the Europe Cup and code as much as you want! 😀

Here is the code in GitHub. First case, second case.

In the article here, I make the lists with the primes variable. Because writing hard-coded magic values is not my thing.

Tagged with: C#, codeforces

C# – Algorithm – Bear And Prime, Interactive Problem in CodeForces

Related posts: