3343
备注:
|
3357
|
删除的内容标记成这样。 | 加入的内容标记成这样。 |
行号 1: | 行号 1: |
两个数 | = 两个数 = |
行号 3: | 行号 3: |
设有两个自然数X、Y,2<=X<=Y<=99,S先生知道这两个数的和S,P先生知道这两个数的积 P ,他们二人进行了如下对话: | 设有两个自然数X、Y,2<=X<=Y<=99,S先生知道这两个数的和S,P先生知道这两个数的积 P ,他们二人进行了如下对话: |
行号 13: | 行号 13: |
------ |
两个数
设有两个自然数X、Y,2<=X<=Y<=99,S先生知道这两个数的和S,P先生知道这两个数的积 P ,他们二人进行了如下对话:
S:我确信你不知道这两个数是什么,但我也不知道。
P: 一听你说这句话,我就知道这两个数是什么了。
S: 我也是,现在我也知道了。
现在你能通过他们的会话推断出这两个数是什么吗?(当然,S和P先生都是非常聪明的)
1 #include <cstdlib>
2 #include <vector>
3 #include <algorithm>
4 #include <iostream>
5 using namespace std;
6 struct comb{
7 int x;
8 int y;
9 int sum;
10 int product;
11 bool erased;
12 };
13
14 bool bysum(const comb &a, const comb &b) {
15 return a.sum < b.sum;
16 }
17
18 bool byproduct(const comb &a, const comb &b) {
19 return a.product < b.product;
20 }
21 bool byerased(const comb &a, const comb &b) {
22 return a.erased < b.erased;
23 }
24
25 int main() {
26 int i, j;
27 const int max = 99;
28 vector<comb> combines;
29
30 //init all combinations
31 comb c;
32 c.erased = false;
33 for (c.x = 2; c.x <= max; c.x++) {
34 for(c.y = c.x; c.y <= max; c.y++) {
35 c.sum = c.x+c.y;
36 c.product = c.x*c.y;
37 combines.push_back(c);
38 }
39 }
40
41 //remove combinations not consist with first clause
42 sort(combines.begin(), combines.end(), bysum);
43 for(i = 0; i < combines.size();) {
44 for(j = i+1; j < combines.size() && combines[i].sum == combines[j].sum;j++)
45 ;
46 if(j == i+1) {
47 combines[i].erased = true;
48 } else {
49 int m;
50 for(m = i; m < j; m++) {
51 int k;
52 for(k = 0; k < combines.size(); k++)
53 if(k!=m && combines[m].product == combines[k].product)
54 break;
55 if(k == combines.size()) {
56 for(int a = i; a < j; a++)
57 combines[a].erased = true;
58 break;
59 }
60 }
61 }
62 i = j;
63 }
64
65 //accually remove combinations
66 sort(combines.begin(), combines.end(), byerased);
67 for(i = 0; i < combines.size() && !combines[i].erased;i++);
68 combines.erase(combines.begin()+i, combines.end());
69
70 //remove combinations not consist with second clause
71 sort(combines.begin(), combines.end(), byproduct);
72 for(i = 0; i < combines.size();) {
73 for( j = i+1; j< combines.size() && combines[i].product == combines[j].product; j++)
74 ;
75 if(j == i+1)
76 i++;
77 else
78 combines.erase(combines.begin()+i, combines.begin()+j);
79 }
80
81 //remove combinations not consist with third clause
82 sort(combines.begin(), combines.end(), bysum);
83 for(i = 0; i < combines.size();) {
84 for( j = i+1; j< combines.size() && combines[i].sum == combines[j].sum; j++)
85 ;
86 if(j == i+1)
87 i++;
88 else
89 combines.erase(combines.begin()+i, combines.begin()+j);
90 }
91
92 //output the result
93 for(i = 0; i < combines.size(); i++) {
94 cout << combines[i].x << " "<< combines[i].y <<" " <<combines[i].sum
95 <<" "<< combines[i].product<< endl;
96 }
97 }