High School Programming League Problems Archive

Would you like to play a game with my computer? Sonya (yes, that's her name) will think of a polynomial and you will have to guess it.

Sonya, who is very loyal and just responds to my commands, has been instructed to listen and respond to a finite set of commands (each command should be followed by the newline, please avoid additional white spaces) that may come from you:

• GETDEGREE: She will answer with an integer number 1=<D<=100, the degree of the polynomial + 1.
• EVAL N: She will evaluate the polynomial for the integer number -100<=N<=100 and answer with the result.
• GUESS c₀ c₁ ... c_D-1: She, depending on the correctness of your guess, will answer 'YES' or 'NO'.
• SURRENDER: You may accept she is smarter than you and forfeit the current challenge.
• QUIT: You may stop playing with her.

Please, notice that:

• You may not EVAL, GUESS or SURRENDER before you GETDEGREE.
• After GETDEGREE, you may not QUIT until GUESSing or SURRENDERing.
• Sonya gets tired sometimes, so she may give you a negative degree. I warn you, you should QUIT immediately or you will lose the game (i.e., your solution will be judged as Wrong Answer).

You may assume all coefficients are non-zero integers lying in range [-10, 10].

Scoring

For each correctly guessed polynomial, you will get Max(Degree - EvalCommands + 1, 0) points.

The number of points given in the ranking is scaled so that it is equal to 10 for the contestant whose solution has the highest score, and is proportionally less for all solutions with lower scores.

Example 1

You: GETDEGREE
Sonya: 2
You: EVAL 19
Sonya: -63
You: EVAL 84
Sonya: -258
You: GUESS -6 -3
Sonya: YES
You: GETDEGREE
Sonya: 96
You: SURRENDER
You: GETDEGREE
Sonya: 3
You: EVAL 0
Sonya: 2
You: GUESS 2 3 4
Sonya: NO
You: SURRENDER
You: GETDEGREE
Sonya: -1
You: QUIT

For the above example your program scores 2-2+1=1 point.

Example 2

You: GETDEGREE
Sonya: 100
You: EVAL -26
Sonya: 11798651065720264067499767442922933495089861550491775802607783136228117083825041
76434876472883967901162673180896259770097086737461876133367600
You: SURRENDER
You: GETDEGREE
Sonya: 3
You: EVAL 0
Sonya: 7
You: EVAL 1
Sonya: 13
You: EVAL 2
Sonya: 23
You: GUESS 7 4 2
Sonya: YES
You: GETDEGREE
Sonya: 2
You: EVAL 8
Sonya: 31
You: EVAL 72
Sonya: 223
You: GUESS 7 3
Sonya: YES
You: GETDEGREE
Sonya: 31
You: SURRENDER
You: QUIT

For the above example your program scores 1+1=2 points (3-3+1=1 i 2-2+1=1).

Attention: the program should clear the output buffer after printing each line. It can be done using fflush(stdout) command or by setting the proper type of buffering at the beginning of the execution - setlinebuf(stdout).