#PQJ2601x15045. QOJ 2601_15045

    ID: 2845 传统题 2000ms 512MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:省选赛事:SNOI 2018枚举二分

QOJ 2601_15045

2018 陕西省青少年信息学(计算机)奥林匹克集训队试题1 2018 年4 月22 日 猜数字 题目描述 据不可靠的小道消息称,吕布小时候其实也是个爱学习的孩子。后来弃文从武,源自于 他父亲有一次跟他玩的猜数字游戏。 他的父亲会在纸上默写一个整数,并告诉吕布,这个数字是在1~K 之间的,然后,吕 布会连续的猜N 次,每次猜两个数字X1,X2(保证两个数字不同奇偶性)然后,他的父亲 会告诉他,哪个数字更接近纸上的数字。 例如,纸上的数字是8,吕布猜的两个数字是4,11,他的父亲会告诉他,11 更接近一 些。(因为11 距离8 只有3 的距离,而4 距离8 有4 的距离)。 现在,已知吕布猜了N 次,而且这N 次的结果已经足够让正常人推断出这个数字是多 少了,可吕布并没有猜出来,他的父亲就很气,把吕布猜的这N 次拿给了你,并且,不告 诉你每次的结果是多少(也就是说,你并不能得到父亲的反馈)。 问:父亲的反馈有多少种可能性?为了简便,你只需要输出一个数字,表示可能性即可。 更多的内容请看样例。 输入格式 第一行,输入一个数字K,表示纸上的数字的取值范围。 第二行,输入一个数字N,表示吕布猜的次数。 接下来N 行,每行两个数字X1,X2,表示吕布这一次猜的数字是多少。 输出格式 一个数字,表示答案的可能性。 输入样例 4 3 1 4 1 2 2 3 输出样例 2 样例解释 假设答案是1,那么父亲的反馈是(1,1,2),显然根据前两次询问,已经可以断定答案 是1。 假设答案是2,那么父亲的反馈是(1,2,2),显然根据前两次询问,已经可以断定答案 是2。 假设答案是3 或者4,那么父亲的反馈都是(4,2,3),那么,我们显然无法确定答案是 3 还是4。 所以父亲的回答只有两种可能性,(1,1,2)或者(1,2,2)。

2018 陕西省青少年信息学(计算机)奥林匹克集训队试题1 2018 年4 月22 日 数据范围 Case K N 0 1000 1000 1 2 3 100000000 20 4 5 100000 6 7 8 9