NOI '02 P2 - Naughty Kid

View as PDF

Points: 15 (partial)
Time limit: 5.0s
Memory limit: 512M

Problem type

A group of children were playing games on the lawn, and a curious passer came over and they had the following conversation:

"Children, what game are you playing?"

"One of us is the referee, and the rest are divided into two teams: people on the Star team, and people on the Moon team. If you guess who the referee is, I'll tell you what game we're playing."

"Alright, can I ask for hints?"

"Of course. You can ask us if someone belongs to a certain team, but you can't ask if someone is a referee. The Star team's members always tell the truth when asked; the Moon team's members always tell the lie. The referee, when you ask him an odd number of times, he will tell the truth, and the even number of times he will tell the lies."

"Okay. Can I ask any question?"

This passer was smart enough to not only guess who the referee was, but also tell which team everyone else was on. Can you write a program that does the same job?

Interaction

This is an interactive problem. The interactor has three operations:

• GetNM: This operation should be called once at the beginning and return the value of and , respectively. .
• Ask Child1 Child2 T: It is used to query the child Child1 "Does Child2 belong to the team", where is either or , is for the Star team, and for the Moon team. If the interactor returns , it means Child1 answered "Yes"; if the interactor returns , it means Child1 answered "No". .
• Answer Ans: It should be called times consecutively, starting from to , to output the role of each child in order. The value of parameter Ans is , or . for the Star team, for the Moon team, and for the referee. Terminate your program immediately after calling this operation times.

Sample Interaction

>>> denotes your output; don't actually print this out.

>>> GetNM
1 1
0
1
0
>>> Answer 0

Explanation

Operation Return Value Explanation
GetNM 1 1 There is one member in the Star team and one member in the Moon team.
Ask 1 2 0 0 Child1 said Child2 is not a member of the Star team.
Ask 2 1 0 1 Child2 said Child1 is a member of the Star team.
Ask 3 1 1 0 Child3 said Child1 is not a member of the Moon team.
Answer 2 None Child1 is the referee.
Answer 1 None Child2 is a member of the Moon team.
Answer 0 None Child3 is a member of the Star team.

Scoring

1. You only guessed who is the referee correctly. In this case, if you ask a child more than three (including three) questions, then you can only get of the points, otherwise, you can get of the points;
2. You guessed who is the referee and which team each of the remaining children belongs to correctly. In this case, if you ask a child more than three (including three) questions, then you can only get of the points, otherwise, you will get full marks for that test case.

Problem translated to English by Tommy_Shan.