题目:
已知两个1~30之间的数字,甲知道两数之和,乙知道两数之积。
甲问乙:"你知道是哪两个数吗?"乙说:"不知道";
乙问甲:"你知道是哪两个数吗?"甲说:"也不知道";
于是,乙说:"那我知道了";
随后甲也说:"那我也知道了";
这两个数是什么?
解答:
隐含条件:乙不知道答案,则说明这两个数之积不是素数。当甲回答说不知道答案后,乙马上知道了答案,说明乙能利用这一信息来排除掉一些选项,从而剩下唯一的选项。反过来,乙得出答案并告诉了甲后,甲亦能利用这一信息来排除一些选项,从而也剩下唯一的选项。
举例子:
假设这两个数是x,y。A=x+y;B=x*y。
站在乙方的角度,这时假设B=6,这能推出(1,6)和(2,3)两种组合。此时乙在这两个组合间犹豫不定时,甲告诉乙不知道答案。
假设答案是(1,6),则A=7。此时,甲手上的选项应该是(1,6),(2,5)和(3,4)。此时甲的确无法知道答案,因此(1,6)是候选答案。假设答案是(2,3),则A=5。此时,甲手上的选项是(1,4)和(2,3),因此甲也无法知道答案。这时,(2,3)也成为了候选答案。此种情况下出现了两个候选答案,因此乙到了最后还是无法得出答案。这与题设矛盾,一次可以排除这些组合。
假设,B=4.
站在乙方的角度,这时乙的选项是(1,4)和(2,2)。
假设答案是(1,4)。则A=5。分析如上。乙把(1,4)作为候选答案。假设答案是(2,2),则A=4。此时,甲手上的选项是(1,3)和(2,2)。因为(1,3)之积是素数,因此被排除。则乙告诉甲不知道答案的时候,甲应该能知道答案,而事实上甲不知道答案。因此(2,2)是不可能的。最后乙手上只剩下一个候选答案,因此他推出了答案。反过来,甲亦能根据此信息推出答案。因此(1,4)符合题设。
void BrainTester::ABOf1_30() {multimap<int, pair<int, int> > mid_result;for (int x = 1; x <= 30; ++x) {for (int y = x; y <= 30; ++y) {if (!this->isPrime(x * y)) {mid_result.insert(make_pair(x * y, make_pair(x, y)));}}}set<int> key_set;multimap<int, pair<int, int> >::iterator it;for (it = mid_result.begin(); it != mid_result.end(); ++it) {key_set.insert(it->first);}set<int>::iterator it_set;for (it_set = key_set.begin(); it_set != key_set.end(); ++it_set) {if (mid_result.count(*it_set) <= 1) {while ((it = mid_result.find(*it_set)) != mid_result.end())mid_result.erase(it);}}key_set.clear();//reset key_setfor (it = mid_result.begin(); it != mid_result.end(); ++it) {key_set.insert(it->first);}multimap<int, pair<int, int> >::iterator beg;multimap<int, pair<int, int> >::iterator en;bool flag = false;multimap<int, pair<int, int> > result;for (it_set = key_set.begin(); it_set != key_set.end(); ++it_set) {beg = mid_result.equal_range(*it_set).first;en = mid_result.equal_range(*it_set).second;for (; beg != en; ++beg) {int x = beg->second.first;int y = beg->second.second;int sum = x + y;if (sum > 3) {int half = sum / 2;flag = false;for (int i = 1; i <= half; ++i) {if (mid_result.find(i * (sum - i)) != mid_result.end()) {if (flag) {result.insert(make_pair(x * y, make_pair(x, y)));break;} else {flag = true;}}}}}}key_set.clear();for (it = result.begin(); it != result.end(); ++it) {key_set.insert(it->first);}for (it_set = key_set.begin(); it_set != key_set.end(); ++it_set) {if (result.count(*it_set) != 1) {while ((it = result.find(*it_set)) != result.end())result.erase(it);}}for (it = result.begin(); it != result.end(); ++it) {cout << it->first << " (" << it->second.first << ","<< it->second.second << ")" << endl;}
}