#arc070d. [arc070_d]HonestOrUnkind
[arc070_d]HonestOrUnkind
现在有 个人,编号从 。这些人中有 个人是诚实的,剩下的 个人是不友好的。这 个人都知道各自的身份,但是你只知道有 个诚实的人和 个不友好的人,你现在试图通过询问来得知他们的身份。
你可以进行询问,询问格式类似于 ? x y
,表示向 询问 是否是诚实的。返回答案按照如下规则:
- 如果 是诚实的人,那么他会按照事实返回答案,也就是说如果 是诚实的,返回答案就为 ,否则返回 。
- 如果是不友好的人,那么他会任意选择 和 来回答。也就是说 是可以按照某种策略来回答你的问题的。
现在请你在 次询问以内确定 个人的身份,如果不可能,请输出 Impossible
,否则请按照 ! S0S1S2...Sn-1
的格式输出(其中 都为下标, 表示 的身份,如果第 个人是诚实的,请输出 ,否则输出 ,身份之间没有空格)。
如下是一个成功的询问的示例:
void query(int x,int y){printf("? %d %d\n",x,y);fflush(stdout);scanf("%s",s);}
上面这个交互函数中的 为字符串变量,用来读入返回的答案。