DEV Community

Cover image for Interactive problems
Hasbi Hamza
Hasbi Hamza

Posted on

Interactive problems

About "Interactive problems"

In this kind of problems, the input given may not be predetermined but is built specifically for your solution.Jury writes a special "Interactor" ,such that its output is redirected to the input of your solution, and the output of your program is sent to interactor's input.
So to sum up interactive problems gives input depending on your solution's output …before handling an exemple you must pay attention to flush the output just to avoid some bugs caused by the buffer.
To flush you can use (just after printing an integer and end-of-line):

fflush(stdout) in C++;
System.out.flush() in Java;
stdout.flush() in Python;
flush(output) in Pascal;

See the documentation for other languages.
Now let's move forward to the example :
Bear and prime 100


As mentioned in the problem statement we have to ask at most 20 queries to guess if the secret number is composite or prime as we all know a prime number is divisible only by 1 and itself so we can check in each query if we have a yes "which means the hidden number is divisible by the number in the output" we increment a count if our count is equal to 2 we break and we are sure that the hidden number is composite ,but we must pay attention that we don't output 1 (all number are divisible by 1) ….We have just finished a part of the solution we still have some special cases to handle , if we have a perfect square for example 25 is divisible by 1 and 5 as i mentioned we can't output 1 so we will have only the number 5 as a query because we have a maximum of 20 query starting by 2 in this case our count will be equal to 1 and then we will consider 25 as a prime number which is false ….
To avoid this wrong answer we can simply store all the prime numbers < 50 in a vector and also the perfect square numbers so our vector will contain {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,4,9,25,49} (19 number) so we will have at most 19 queries to ask and with that vector we handled all the special cases and of course if the count of divisors is equal to 2 we still have to break ….And that's it , the problem is not that hard and is fun to solve and i hope you enjoyed the topic
Problem's link: Bear and prime 100
Code : Solution
Comments and feedback are welcome

Thank you ;

Top comments (0)