题目描述
上课的时候总会有一些同学和前后左右的人交头接耳,这是令小学班主任十分头疼的一件事情。不过,班主任小雪发现了一些有趣的现象,当同学们的座次确定下来之后,只有有限的D对同学上课时会交头接耳。
同学们在教室中坐成了M行N列,坐在第i行第j列的同学的位置是(i,j),为了方便同学们进出,在教室中设置了K条横向的通道,L条纵向的通道。
于是,聪明的小雪想到了一个办法,或许可以减少上课时学生交头接耳的问题:她打算重新摆放桌椅,改变同学们桌椅间通道的位置,因为如果一条通道隔开了22会交头接耳的同学,那么他们就不会交头接耳了。
请你帮忙给小雪编写一个程序,给出最好的通道划分方案。在该方案下,上课时交头接耳的学生的对数最少。
//洛谷P1056 排座椅
#include<iostream>
using namespace std;
int m,n,k,l,d,i,j,p,t=0;//学生分M行N列,在其中插入K行,L列 ,D对同学会交头接耳
int dd[100][5]; //存储交头接耳的一对同学的行、列位置
int stu[1001][1001]={0}; //学生座位表
int kk[1001]={0},ll[1001]={0};
int paixuk[1001]={0},paixul[1001]={0};
int tem=0;
//kk[1001]存储第k行是过道时,能分开的说话同学有几对,ll[1001]存储第l列是过道时,能分开的说话同学有几对
//paixuk[1001]是对kk[1001]中的数字进行排序,最后排序输出共k行的行号
//paixul[1001]是对ll[1001]中的数字进行排序,最后排序输出共l列的列号
int maxnum=0,s;
int main()
{
cin>>m>>n>>k>>l>>d;
for(i=1;i<=d;i++)
cin>>dd[i][1]>>dd[i][2]>>dd[i][3]>>dd[i][4];
//输入d对相互讲话的同学的坐标
for(i=1;i<=m-1;i++)
for(p=1;p<=d;p++)
if((dd[p][1]==i&&dd[p][3]-1==i)||(dd[p][1]-1==i&&dd[p][3]==i))
//如果某一对讲话的同学,他们的行坐标为i和i+1,则被分开
kk[i]++;
//以上for循环求出第i行和第i+1行之间有过道时,能够分开的讲话同学的有几对
for(j=1;j<=n-1;j++)
for(p=1;p<=d;p++)
if((dd[p][2]==j&&dd[p][4]-1==j)||(dd[p][2]-1==j&&dd[p][4]==j))
//如果某一对讲话的同学,他们的列坐标为j和j+1,则被分开
ll[j]++;
//以上for循环求出第j列和第j+1列之间有过道时,能够分开的讲话同学的有几对
//for(i=1;i<=m-1;i++)
//cout<<"kk["<<i<<"]="<<kk[i]<<endl;
//for(j=1;j<=n-1;j++)
//cout<<"ll["<<j<<"]="<<ll[j]<<endl;
s=1;
//找出横向k条线
while(s<=k)
{
maxnum=0;t=1;
for(i=1;i<=m-1;i++)
if(maxnum<kk[i])
{
maxnum=kk[i];
t=i;
}
paixuk[s]=t;
kk[t]=0;
s++;
}
s=1;
//找出纵向l条线
while(s<=l){
maxnum=0;t=1;
for(i=1;i<=n-1;i++)
if(maxnum<ll[i])
{
maxnum=ll[i];
t=i;
}
paixul[s]=t;
ll[t]=0;
s++;
}
for(i=1;i<=k;i++)
for(j=i+1;j<=k;j++)
{
if(paixuk[i]>paixuk[j])
{
tem=paixuk[i];
paixuk[i]=paixuk[j];
paixuk[j]=tem;
}
}
for(i=1;i<=l;i++)
for(j=i+1;j<=l;j++)
{
if(paixul[i]>paixul[j])
{
tem=paixul[i];
paixul[i]=paixul[j];
paixul[j]=tem;
}
}
for(i=1;i<=k;i++)
cout<<paixuk[i]<<" ";
cout<<endl;
for(j=1;j<=l;j++)
cout<<paixul[j]<<" ";
cout<<endl;
return 0;
}
测试点2输入数据:
200 200 53 80 2000
10 55 11 55
162 110 162 109
81 144 80 144
44 4 44 3
106 173 105 173
148 21 149 21
172 137 173 137
167 101 167 102
73 49 73 50
48 115 48 114
113 107 113 106
60 58 60 57
37 118 36 118
89 100 89 99
181 3 181 2
92 23 91 23
165 199 165 200
22 51 21 51
194 106 194 107
10 180 10 181
117 105 116 105
182 147 182 148
139 52 139 53
10 115 9 115
89 9 88 9
134 65 134 66
2 195 1 195
161 22 162 22
9 47 9 48
5 21 5 22
102 192 103 192
85 177 85 178
52 123 52 124
158 58 158 59
176 59 175 59
105 44 105 45
40 62 40 61
64 74 64 73
101 44 101 45
81 4 82 4
105 83 106 83
66 93 67 93
105 123 105 122
164 130 164 129
64 46 64 45
194 187 194 188
178 148 179 148
129 149 128 149
135 53 134 53
63 144 63 143
19 78 19 79
105 44 106 44
90 166 89 166
173 177 174 177
130 118 129 118
128 191 129 191
192 32 193 32
144 157 144 156
44 62 43 62
70 70 70 69
139 142 140 142
187 133 187 134
7 99 8 99
2 98 2 97
180 104 180 103
163 183 163 184
153 6 153 7
112 163 112 162
194 171 195 171
135 143 134 143
112 179 112 178
89 186 89 185
165 172 165 171
178 7 179 7
106 136 107 136
123 48 123 49
118 144 118 143
115 18 114 18
22 79 23 79
98 30 99 30
130 135 131 135
44 140 44 141
194 47 195 47
31 160 32 160
95 146 95 145
17 180 16 180
15 151 16 151
152 60 152 59
78 153 78 154
83 60 84 60
42 196 41 196
7 167 7 166
106 41 105 41
117 184 118 184
52 156 53 156
94 27 95 27
104 6 104 5
70 110 70 109
173 74 172 74
98 73 98 72
128 28 127 28
112 21 112 20
125 164 126 164
135 117 135 116
99 20 99 21
63 194 64 194
75 84 75 83
124 163 124 162
166 84 166 85
141 103 141 104
34 115 34 116
119 21 119 22
174 54 175 54
172 93 173 93
48 100 47 100
132 95 131 95
148 78 148 79
21 60 20 60
153 47 153 48
49 28 48 28
19 157 18 157
160 96 160 97
36 147 37 147
189 74 189 75
184 107 183 107
52 78 51 78
77 114 78 114
122 132 121 132
162 132 162 133
65 63 65 62
67 119 67 118
24 103 25 103
11 169 11 170
147 157 148 157
139 73 138 73
10 40 10 39
45 122 45 121
185 92 186 92
69 134 68 134
46 180 47 180
48 186 48 187
62 11 62 10
77 1 76 1
120 72 120 71
147 178 147 179
39 36 38 36
77 29 78 29
152 138 153 138
170 106 170 105
150 145 150 144
153 159 154 159
165 71 165 72
15 156 15 155
134 191 133 191
67 6 67 5
192 71 192 70
180 51 180 52
183 79 182 79
41 141 42 141
54 14 54 13
9 148 10 148
115 179 116 179
60 131 60 130
143 165 142 165
17 10 18 10
97 93 96 93
171 170 171 169
148 57 148 56
130 8 131 8
169 119 170 119
111 62 110 62
64 50 64 51
12 113 13 113
8 135 9 135
136 64 136 63
109 167 109 168
153 67 154 67
158 41 158 42
72 131 73 131
90 88 90 89
55 181 55 182
182 155 183 155
71 190 72 190
58 189 59 189
123 190 123 189
117 19 116 19
7 194 7 193
56 13 57 13
182 88 181 88
6 11 5 11
17 125 18 125
137 41 136 41
196 148 196 149
108 64 109 64
112 176 111 176
106 114 105 114
163 111 164 111
185 95 186 95
116 133 115 133
27 9 28 9
169 164 169 165
150 162 150 161
90 109 91 109
179 174 179 175
114 10 113 10
107 58 107 57
106 120 107 120
141 123 142 123
89 113 89 114
128 85 128 84
194 69 194 68
11 162 10 162
108 73 109 73
92 66 91 66
146 132 146 131
129 21 130 21
21 27 20 27
110 51 110 50
95 41 96 41
13 77 13 78
182 187 181 187
153 50 154 50
60 75 61 75
165 44 166 44
197 117 197 116
189 103 189 104
150 53 151 53
24 95 24 94
74 143 74 144
43 82 44 82
23 164 23 163
40 95 41 95
108 39 108 40
56 52 56 51
94 154 93 154
23 200 24 200
50 30 49 30
93 19 92 19
36 169 36 170
146 188 145 188
137 67 137 66
165 54 164 54
66 75 65 75
75 128 75 129
138 156 139 156
160 46 160 47
66 129 67 129
90 167 91 167
14 98 14 99
64 174 64 173
100 178 99 178
190 54 191 54
45 124 45 125
161 132 161 133
75 118 76 118
72 56 73 56
43 175 43 174
85 17 86 17
95 99 95 100
136 132 136 133
44 91 43 91
168 133 169 133
155 150 154 150
187 84 186 84
178 177 178 178
199 95 198 95
74 13 73 13
188 95 187 95
157 2 157 3
72 52 72 51
22 100 21 100
66 9 65 9
74 179 73 179
78 78 77 78
113 190 114 190
34 33 34 34
63 55 64 55
139 119 139 120
168 46 168 45
101 132 102 132
31 61 32 61
19 78 19 77
157 6 157 7
12 185 13 185
145 51 144 51
101 50 102 50
181 39 182 39
75 5 74 5
54 130 55 130
76 4 76 5
106 48 106 49
43 128 43 129
178 147 178 146
94 154 94 155
89 132 88 132
84 79 84 78
35 49 35 50
180 34 180 35
182 7 181 7
162 171 163 171
177 105 177 104
147 108 147 107
7 88 7 87
22 67 23 67
69 119 70 119
122 20 122 21
159 53 160 53
103 174 102 174
109 170 109 171
180 133 180 134
172 98 173 98
130 180 130 181
54 2 53 2
135 162 135 161
3 59 3 60
63 189 62 189
163 168 162 168
14 122 14 121
115 100 116 100
166 154 166 153
110 189 110 188
99 2 99 1
104 183 105 183
73 139 72 139
157 87 157 88
96 136 96 135
153 69 153 70
154 177 154 178
159 25 160 25
183 21 184 21
172 55 173 55
24 93 24 94
95 162 95 161
31 3 30 3
184 62 184 63
14 105 14 106
176 128 175 128
9 23 8 23
155 40 156 40
92 30 92 31
74 45 73 45
108 161 108 160
46 22 46 21
56 110 55 110
29 34 30 34
189 98 188 98
38 116 37 116
87 171 88 171
188 186 189 186
178 53 179 53
28 159 29 159
16 31 16 32
179 186 180 186
73 122 73 121
144 109 143 109
186 70 187 70
132 159 133 159
11 199 10 199
122 9 121 9
135 145 135 144
190 31 190 30
78 48 77 48
25 85 25 84
120 173 120 174
72 36 72 37
3 137 4 137
64 132 63 132
17 68 18 68
13 133 13 132
4 137 5 137
158 200 158 199
71 98 71 99
96 103 97 103
113 33 113 34
140 9 141 9
9 155 9 154
186 100 185 100
148 198 147 198
61 182 61 183
28 187 28 188
146 26 146 27
75 12 76 12
153 24 153 25
75 197 75 196
189 15 188 15
174 116 173 116
179 12 180 12
30 9 31 9
62 194 62 193
153 183 152 183
189 184 188 184
41 80 40 80
120 124 120 125
27 83 27 84
24 90 24 89
120 138 120 139
138 40 137 40
111 38 111 39
120 99 120 100
115 64 115 65
58 17 59 17
119 148 120 148
73 153 72 153
158 114 158 113
93 135 94 135
121 35 121 34
123 178 123 179
151 106 151 105
29 150 29 151
136 139 137 139
117 68 117 69
142 56 143 56
89 149 89 148
42 54 42 55
37 12 36 12
156 101 155 101
194 143 193 143
160 75 161 75
20 187 20 188
149 97 149 96
169 120 168 120
161 115 161 114
65 14 66 14
37 56 37 55
5 198 5 197
14 68 15 68
89 165 90 165
166 30 165 30
107 90 108 90
79 126 79 127
124 175 124 176
113 7 114 7
107 191 106 191
191 4 191 5
26 124 27 124
12 188 11 188
80 145 81 145
171 28 172 28
47 108 47 107
171 114 171 113
103 114 104 114
129 138 130 138
156 102 156 103
121 20 120 20
106 82 106 83
190 161 189 161
175 99 176 99
89 27 89 26
150 5 150 4
40 18 40 17
197 157 197 156
200 156 200 155
76 2 77 2
95 73 94 73
111 138 111 137
118 171 119 171
44 9 44 10
14 22 14 23
90 46 89 46
37 6 38 6
16 69 15 69
110 9 109 9
161 44 161 45
7 131 6 131
157 56 157 57
186 51 187 51
185 86 184 86
176 33 177 33
187 5 187 4
108 8 108 9
118 53 119 53
194 58 194 57
101 195 100 195
199 154 200 154
98 174 98 173
152 145 151 145
78 81 77 81
105 83 106 83
18 107 17 107
74 109 74 108
3 2 2 2
65 86 65 85
63 99 64 99
128 173 127 173
94 19 94 18
194 117 194 116
193 12 193 13
97 4 97 3
198 21 199 21
45 188 46 188
6 79 6 80
29 71 29 70
37 77 38 77
189 189 189 188
34 85 35 85
39 149 39 148
34 1 35 1
200 93 200 94
15 8 14 8
55 22 54 22
48 69 48 70
44 103 45 103
119 11 119 10
182 127 181 127
183 103 184 103
167 8 166 8
96 21 95 21
186 100 186 101
137 166 137 165
123 188 122 188
200 83 199 83
52 167 52 168
96 186 96 185
88 23 89 23
194 102 193 102
16 105 17 105
47 63 47 62
76 110 76 109
23 181 23 182
67 112 68 112
14 107 14 108
136 183 136 184
200 107 199 107
75 88 75 87
179 178 178 178
140 38 140 39
68 2 69 2
130 61 129 61
37 30 36 30
117 155 118 155
77 169 76 169
156 127 157 127
50 108 51 108
5 89 5 88
128 172 127 172
196 199 196 200
100 85 101 85
76 159 76 158
85 139 86 139
73 130 73 129
112 89 112 88
100 133 100 132
116 157 117 157
158 171 159 171
136 34 137 34
90 31 89 31
121 116 122 116
65 95 66 95
57 39 58 39
195 142 195 141
89 108 89 109
179 3 178 3
104 23 103 23
44 168 44 169
189 160 188 160
16 64 15 64
40 144 40 143
38 125 37 125
87 197 87 198
97 195 98 195
47 144 48 144
41 60 42 60
187 27 188 27
192 126 192 125
139 99 138 99
184 189 183 189
56 111 56 112
187 99 187 98
47 37 47 38
133 24 134 24
200 118 199 118
44 11 45 11
162 10 163 10
158 6 157 6
100 159 100 158
151 50 151 51
2 147 3 147
127 23 127 24
84 175 83 175
173 125 173 126
45 99 46 99
168 4 168 3
61 18 61 19
39 86 39 85
145 17 146 17
41 167 41 168
116 15 116 14
191 40 191 39
5 128 5 129
109 15 109 16
75 28 75 29
43 183 43 182
112 46 113 46
108 113 108 114
169 20 168 20
178 146 178 145
73 1 73 2
189 59 189 60
71 70 72 70
91 60 91 61
182 192 181 192
43 131 43 132
89 95 89 94
3 143 4 143
32 7 32 8
23 96 23 95
114 81 115 81
111 138 112 138
7 60 6 60
46 31 45 31
91 53 91 54
171 172 170 172
75 113 75 114
123 89 124 89
37 31 38 31
17 114 18 114
44 106 44 105
63 115 63 114
29 64 28 64
101 6 101 5
42 170 42 169
119 15 119 14
136 153 136 154
24 65 24 64
175 72 175 71
46 33 46 32
88 61 89 61
130 11 131 11
28 198 28 197
36 61 36 62
29 47 28 47
101 184 101 183
161 84 161 85
7 191 8 191
40 181 41 181
191 182 191 181
114 114 113 114
104 187 104 186
44 45 44 44
71 148 72 148
63 149 64 149
24 30 25 30
94 39 94 40
131 37 132 37
66 139 66 140
67 117 68 117
104 162 104 161
193 77 193 78
142 177 142 176
6 133 5 133
88 10 88 9
124 84 123 84
135 60 135 61
149 123 148 123
102 90 103 90
16 121 15 121
149 198 149 199
15 157 15 156
182 46 182 45
105 97 105 98
29 123 28 123
20 144 20 145
147 107 147 106
24 17 24 18
145 52 145 53
15 164 15 163
45 138 46 138
15 40 16 40
47 114 47 113
152 62 152 63
132 65 132 64
150 64 150 63
113 22 113 23
101 181 102 181
53 28 53 29
158 110 158 109
51 25 50 25
50 143 49 143
37 189 37 190
69 41 68 41
114 151 114 152
93 188 93 187
189 135 190 135
67 48 68 48
146 80 146 79
190 75 190 76
125 151 126 151
180 8 179 8
9 137 9 136
30 68 31 68
28 142 28 141
125 108 126 108
147 31 148 31
183 167 182 167
95 106 96 106
124 77 123 77
86 37 85 37
91 27 91 28
8 68 7 68
155 125 155 126
88 16 89 16
1 106 1 107
177 151 177 152
53 111 53 110
101 160 101 161
141 27 142 27
1 102 2 102
195 73 195 72
109 97 108 97
102 55 102 54
174 46 174 45
103 45 102 45
62 122 62 121
45 97 46 97
172 29 171 29
146 100 146 101
126 125 126 126
180 104 180 105
86 10 86 11
67 20 67 21
100 200 100 199
108 135 108 134
50 103 50 102
153 4 153 3
176 130 177 130
107 80 106 80
106 195 106 196
186 126 187 126
7 17 8 17
53 172 53 171
137 84 137 83
59 29 60 29
44 75 44 76
57 134 58 134
35 141 36 141
138 87 138 88
68 10 69 10
7 25 6 25
176 11 177 11
18 197 18 196
73 77 74 77
96 7 96 8
138 102 139 102
39 136 39 135
58 20 58 19
142 28 143 28
149 197 150 197
145 126 146 126
137 116 137 115
197 74 198 74
119 170 120 170
77 127 77 128
61 75 61 74
57 174 56 174
105 119 105 118
50 169 50 168
17 13 16 13
25 171 25 170
100 56 100 57
9 163 9 164
61 39 61 38
43 6 43 5
48 82 48 81
48 72 47 72
36 3 35 3
42 59 43 59
153 100 153 101
151 66 151 67
190 61 189 61
21 150 20 150
60 93 59 93
12 177 12 178
87 132 88 132
120 148 120 147
113 117 113 118
3 36 3 35
39 77 39 76
192 60 192 59
40 55 41 55
17 112 17 111
91 187 91 188
170 16 170 17
49 126 49 127
67 39 67 38
133 147 133 148
181 48 181 47
95 199 95 200
186 44 187 44
24 63 23 63
9 57 9 58
54 95 54 96
17 164 16 164
167 120 167 119
103 18 103 17
133 30 133 31
41 198 40 198
167 32 167 31
18 64 19 64
173 123 173 122
123 62 123 61
138 200 138 199
133 91 132 91
139 90 140 90
127 135 127 134
46 55 45 55
102 65 101 65
3 178 2 178
181 104 181 103
173 27 173 28
67 193 66 193
174 163 173 163
154 193 155 193
150 68 150 67
67 59 68 59
61 71 61 70
76 6 75 6
156 7 156 6
175 6 174 6
62 191 62 190
160 27 160 28
69 176 69 175
147 122 146 122
70 49 71 49
18 41 18 40
110 114 111 114
199 16 199 15
121 112 120 112
198 40 197 40
22 147 23 147
98 126 98 127
86 68 86 67
7 197 7 196
185 187 185 186
24 88 25 88
111 58 111 57
54 46 53 46
126 189 125 189
18 172 18 173
8 39 7 39
4 44 3 44
195 112 196 112
30 172 31 172
149 56 149 55
146 33 147 33
191 167 191 168
40 66 39 66
161 157 161 156
32 187 33 187
1 15 2 15
169 175 169 176
52 159 52 160
148 7 148 6
167 176 167 175
102 181 103 181
142 182 142 181
77 17 78 17
42 48 41 48
28 182 27 182
50 87 50 88
80 188 81 188
136 19 136 20
1 125 1 126
12 181 12 182
106 30 107 30
34 182 34 181
198 92 199 92
142 31 142 30
46 46 46 47
56 30 57 30
187 117 188 117
80 74 79 74
65 64 64 64
170 171 170 170
10 61 9 61
174 87 173 87
123 16 122 16
73 115 74 115
80 198 79 198
15 200 16 200
152 13 152 12
4 4 4 3
81 4 80 4
59 6 60 6
127 65 127 64
87 168 86 168
83 83 83 82
117 54 117 55
73 190 74 190
10 143 9 143
45 159 46 159
33 28 33 27
86 91 86 92
127 136 127 135
161 68 161 67
64 111 65 111
44 64 44 63
190 18 190 19
126 39 127 39
146 23 146 22
169 127 168 127
44 194 45 194
42 117 42 116
67 92 67 93
171 180 171 181
65 117 66 117
127 35 126 35
2 17 2 18
20 22 21 22
137 96 136 96
93 46 94 46
78 175 78 174
35 190 36 190
71 36 70 36
96 117 97 117
178 53 178 52
40 135 40 134
45 79 44 79
178 107 178 108
170 16 170 15
143 64 143 65
62 33 61 33
172 129 172 130
191 119 191 118
80 54 80 55
160 179 161 179
120 68 120 67
72 130 73 130
134 109 135 109
157 62 156 62
170 51 169 51
170 124 171 124
118 169 118 168
145 18 144 18
191 52 191 51
1 61 2 61
82 152 82 153
145 165 144 165
197 23 196 23
151 116 151 117
38 115 39 115
74 46 75 46
29 171 29 172
61 20 61 19
1 165 1 164
199 50 200 50
158 25 159 25
145 197 145 196
39 115 40 115
40 54 41 54
51 134 52 134
167 53 167 54
6 13 6 14
16 149 16 148
119 93 118 93
114 88 113 88
71 107 72 107
117 75 116 75
103 132 102 132
29 174 29 173
103 116 103 115
198 154 198 153
56 93 56 94
37 68 37 69
94 180 93 180
200 125 199 125
90 65 90 64
178 109 177 109
46 108 47 108
105 131 105 132
132 33 131 33
55 136 56 136
15 55 16 55
90 190 90 189
81 165 81 164
102 101 102 102
58 90 59 90
95 19 95 20
3 120 3 121
71 44 72 44
141 187 141 188
184 59 185 59
14 75 14 74
27 142 26 142
38 158 38 159
181 27 180 27
63 2 62 2
4 7 5 7
162 4 161 4
62 177 62 176
142 133 142 132
183 171 182 171
103 109 104 109
17 167 16 167
1 184 2 184
117 136 117 135
167 56 167 57
32 91 32 92
2 101 3 101
47 195 48 195
200 120 199 120
10 72 10 73
35 55 36 55
17 7 16 7
130 58 129 58
73 71 73 72
25 115 25 116
128 43 128 44
167 29 166 29
53 185 53 186
134 43 134 42
110 178 110 179
169 129 170 129
143 48 143 47
186 107 186 106
30 153 30 152
31 91 32 91
104 108 104 109
108 121 108 122
4 27 5 27
65 88 64 88
74 51 74 52
117 110 117 109
175 112 176 112
38 184 37 184
111 12 111 13
189 186 190 186
145 119 144 119
12 85 12 86
10 77 10 78
73 71 74 71
150 137 149 137
95 37 95 38
52 42 51 42
76 164 75 164
180 167 180 166
124 196 123 196
128 185 129 185
108 77 109 77
155 70 154 70
7 182 7 181
73 27 74 27
144 18 144 17
53 1 53 2
115 172 115 171
26 93 26 92
1 174 1 173
111 86 111 85
170 76 171 76
62 167 61 167
118 65 118 64
193 14 192 14
61 127 61 128
82 123 81 123
115 104 116 104
131 118 131 117
197 181 196 181
48 169 47 169
60 147 60 146
169 155 169 156
138 12 138 13
22 66 22 65
125 184 125 185
17 149 17 148
75 41 76 41
94 140 95 140
149 182 149 181
66 169 65 169
15 198 14 198
196 109 195 109
127 197 127 198
11 125 11 126
188 194 187 194
25 148 25 147
36 183 36 184
140 140 140 139
132 16 132 17
137 51 137 50
200 103 200 102
86 122 86 121
66 148 67 148
116 131 116 132
29 70 29 69
165 112 165 111
30 168 31 168
73 50 74 50
141 101 141 100
123 180 124 180
156 191 156 190
85 100 85 99
109 122 110 122
27 139 27 138
3 27 4 27
23 15 23 14
70 8 70 7
197 29 196 29
193 91 193 90
79 182 80 182
66 109 66 108
186 86 187 86
77 97 76 97
127 128 126 128
108 138 108 139
66 74 66 75
126 4 126 3
193 58 192 58
195 182 196 182
42 80 43 80
98 99 97 99
83 11 83 10
145 58 144 58
67 107 66 107
122 68 121 68
128 198 128 197
175 52 175 51
97 61 98 61
77 83 76 83
72 54 72 53
147 173 147 174
113 166 114 166
129 61 129 60
97 189 97 190
125 181 126 181
158 91 158 92
169 46 168 46
23 113 23 112
44 34 45 34
108 65 108 64
82 115 83 115
148 195 148 194
125 37 124 37
59 88 60 88
54 89 54 90
122 163 122 162
76 85 75 85
150 147 151 147
96 147 96 148
83 28 84 28
56 130 55 130
55 174 56 174
7 93 8 93
88 104 88 105
186 89 186 90
174 77 173 77
32 195 32 194
167 87 166 87
81 45 82 45
199 115 200 115
166 81 166 80
119 134 119 135
149 1 148 1
34 139 34 140
56 109 57 109
186 4 186 5
187 21 188 21
58 101 58 100
21 121 20 121
146 34 146 33
48 31 47 31
96 165 96 166
37 118 37 117
184 147 183 147
57 20 56 20
184 127 184 126
73 174 73 175
49 41 48 41
169 159 168 159
188 15 188 14
174 72 173 72
50 161 51 161
187 153 188 153
9 55 9 56
84 138 84 139
62 153 63 153
170 194 171 194
127 66 127 65
141 66 141 65
117 185 116 185
142 64 141 64
53 200 52 200
27 101 26 101
15 151 14 151
34 86 33 86
93 50 93 49
50 68 50 69
66 71 65 71
35 199 36 199
147 151 146 151
176 109 176 110
65 193 64 193
130 67 131 67
180 95 180 94
122 142 121 142
158 28 158 27
77 193 77 194
101 112 100 112
160 135 160 136
25 68 25 67
90 30 90 29
66 167 66 168
194 65 195 65
129 7 130 7
48 184 49 184
43 17 43 16
155 77 154 77
131 192 131 191
189 24 189 25
191 2 190 2
177 32 176 32
175 70 176 70
1 114 1 113
85 49 85 50
189 62 189 61
2 57 3 57
95 196 94 196
182 109 183 109
29 59 29 60
71 45 70 45
193 102 193 101
67 48 67 49
161 168 161 169
17 136 17 135
71 124 71 123
158 48 158 47
113 174 112 174
42 58 42 59
66 21 65 21
147 67 146 67
38 11 38 10
78 35 78 34
189 109 189 108
120 197 120 198
29 119 30 119
149 49 149 50
149 131 149 132
47 180 47 179
70 58 70 59
95 113 96 113
117 179 118 179
171 61 172 61
181 175 182 175
68 106 67 106
46 151 46 150
136 53 136 54
24 111 23 111
18 192 19 192
103 130 103 131
191 192 191 191
129 88 128 88
107 150 107 151
64 70 63 70
192 45 193 45
101 28 100 28
159 63 159 62
13 143 14 143
144 93 144 94
70 170 70 169
118 166 119 166
24 48 23 48
133 192 132 192
197 191 198 191
112 19 112 18
183 4 184 4
136 74 136 73
96 96 96 95
16 151 16 150
11 157 11 158
106 111 106 110
150 164 151 164
49 23 48 23
99 112 99 113
127 116 127 115
189 63 190 63
68 77 68 78
66 91 66 90
101 159 101 158
113 97 112 97
123 134 122 134
104 133 104 134
122 186 121 186
157 149 157 150
39 97 38 97
31 153 32 153
93 60 93 61
44 32 44 33
156 196 155 196
147 76 146 76
11 63 12 63
24 153 24 152
40 161 40 160
161 160 161 159
64 167 63 167
159 95 159 96
32 48 31 48
128 87 129 87
68 79 68 80
5 66 5 67
111 9 110 9
89 10 89 11
105 4 105 3
138 9 139 9
85 51 86 51
129 114 128 114
113 124 113 125
93 61 92 61
163 32 162 32
138 63 138 64
158 103 158 102
84 64 84 65
184 164 185 164
58 194 58 195
152 139 152 140
66 107 66 106
182 86 183 86
3 112 3 111
179 175 179 176
170 100 170 101
152 150 153 150
180 73 180 72
176 179 177 179
157 63 156 63
158 88 158 87
48 161 47 161
15 92 16 92
51 168 51 169
198 141 198 140
43 112 44 112
183 161 182 161
110 15 110 14
49 89 49 88
174 10 175 10
30 16 30 17
63 165 63 166
57 26 58 26
173 51 174 51
167 83 167 82
52 104 51 104
18 79 18 78
134 100 133 100
16 22 16 23
12 140 13 140
75 100 74 100
41 38 41 39
152 45 153 45
106 147 106 148
43 10 43 9
172 163 173 163
171 159 171 158
29 71 29 72
103 8 102 8
90 139 90 138
18 154 18 153
95 14 94 14
126 134 126 133
38 128 37 128
102 144 102 143
45 70 46 70
105 27 106 27
20 52 20 51
119 154 118 154
149 169 149 170
62 108 61 108
32 82 32 81
200 76 199 76
174 99 175 99
125 119 124 119
90 154 91 154
86 9 85 9
51 185 51 186
164 120 164 119
33 161 33 160
193 13 193 14
119 19 119 20
159 49 159 50
170 37 170 38
75 96 74 96
26 42 27 42
197 13 196 13
117 107 118 107
91 39 91 40
105 9 105 10
128 24 129 24
193 194 193 195
84 122 83 122
83 127 84 127
11 102 12 102
94 77 94 76
172 48 173 48
170 167 170 166
158 163 157 163
47 23 47 24
127 183 127 182
95 144 94 144
54 171 53 171
177 78 178 78
65 115 64 115
100 1 100 2
142 162 143 162
114 200 113 200
139 29 139 30
161 200 160 200
71 174 72 174
85 133 85 132
105 191 104 191
11 116 10 116
123 66 123 67
14 108 14 109
114 197 113 197
171 73 170 73
191 116 192 116
106 121 106 120
153 150 153 149
179 11 180 11
177 9 177 8
16 174 16 175
140 131 141 131
6 21 7 21
199 192 199 191
38 121 39 121
130 24 130 25
57 108 57 109
194 140 194 141
157 39 158 39
161 113 162 113
44 175 45 175
10 14 10 15
63 158 62 158
152 39 152 38
30 33 30 32
27 99 27 100
99 80 99 79
137 195 137 194
129 137 130 137
63 170 63 169
14 190 14 191
131 106 131 107
194 145 194 146
125 185 124 185
101 74 101 75
134 58 133 58
123 133 124 133
122 49 122 50
112 25 112 26
136 188 136 189
196 166 197 166
70 135 70 136
121 48 121 47
167 75 168 75
112 71 112 70
162 157 163 157
54 93 54 94
151 140 151 139
144 16 144 17
99 65 99 64
157 183 157 184
111 120 110 120
162 27 161 27
100 124 99 124
124 181 124 180
148 62 147 62
183 124 183 125
49 33 49 32
31 83 31 82
51 187 50 187
82 70 82 69
171 147 171 146
120 182 121 182
57 177 57 176
69 72 69 71
111 183 112 183
168 95 167 95
165 57 166 57
150 139 150 140
17 51 17 52
127 193 127 194
149 83 149 82
55 146 56 146
91 166 90 166
157 89 156 89
152 166 152 167
188 5 187 5
101 49 101 48
169 102 168 102
174 186 174 187
167 119 166 119
8 30 8 31
106 97 105 97
53 163 52 163
135 177 135 176
174 136 175 136
4 47 3 47
134 120 135 120
91 94 91 93
197 106 197 105
52 133 53 133
112 172 111 172
200 105 200 106
68 68 67 68
158 131 159 131
139 140 138 140
170 52 171 52
108 106 108 105
199 29 198 29
175 114 175 115
130 27 130 28
139 110 140 110
118 197 119 197
142 153 142 152
52 113 52 112
70 137 69 137
87 85 87 86
111 65 110 65
28 129 28 130
85 125 85 126
58 164 58 165
181 76 182 76
169 40 168 40
148 54 147 54
184 64 184 63
137 161 136 161
17 81 18 81
175 25 175 26
120 195 120 194
51 96 51 95
182 33 182 32
165 141 164 141
121 193 122 193
127 22 126 22
113 92 114 92
97 25 96 25
72 25 72 26
94 179 94 178
158 152 157 152
85 117 84 117
99 154 98 154
129 82 129 81
48 137 49 137
8 164 8 165
173 24 172 24
126 24 126 23
29 108 29 107
194 33 195 33
52 79 52 78
69 96 68 96
59 1 59 2
13 1 13 2
26 112 25 112
66 101 65 101
132 139 132 138
71 121 72 121
192 98 192 97
88 73 89 73
88 170 88 169
102 105 102 106
169 11 169 10
12 61 12 62
130 59 129 59
99 72 98 72
77 119 77 120
144 1 145 1
18 73 17 73
19 192 19 191
58 157 58 156
103 97 104 97
88 142 89 142
156 175 156 176
173 168 172 168
46 140 45 140
159 75 159 76
21 155 20 155
142 129 141 129
65 37 64 37
87 21 88 21
37 167 36 167
73 27 73 28
57 76 57 75
69 36 69 35
183 185 183 184
4 38 4 39
185 177 186 177
89 142 89 143
177 56 178 56
133 27 132 27
156 157 155 157
194 134 194 133
150 70 149 70
9 7 10 7
117 31 117 30
69 132 69 131
80 39 81 39
13 139 12 139
123 25 123 26
103 77 102 77
97 185 97 186
184 130 185 130
54 82 53 82
159 174 159 175
51 69 51 70
48 21 48 20
101 157 101 156
136 28 136 27
133 124 132 124
37 19 36 19
185 137 185 136
197 31 197 32
177 45 177 44
171 91 171 90
54 27 53 27
109 167 109 166
179 47 179 48
92 78 92 77
32 10 31 10
34 23 34 24
44 171 45 171
198 56 197 56
28 138 29 138
165 81 166 81
199 4 200 4
185 183 185 182
69 145 68 145
10 193 10 194
76 78 76 77
189 114 190 114
64 45 64 44
105 146 106 146
8 99 9 99
75 193 75 194
24 100 23 100
111 186 112 186
165 191 166 191
44 27 45 27
187 111 188 111
77 61 78 61
115 134 114 134
189 43 189 42
132 149 133 149
128 90 127 90
108 127 109 127
114 5 114 4
166 42 166 41
165 186 165 185
2 173 1 173
25 61 26 61
98 130 98 131
183 177 184 177
107 95 107 94
33 23 32 23
134 57 134 56
156 5 156 6
100 83 99 83
43 16 44 16
185 30 185 29
100 22 101 22
45 121 45 120
89 139 90 139
149 33 149 34
147 141 148 141
9 159 9 160
70 54 71 54
5 2 5 1
88 152 88 151
129 96 128 96
109 135 110 135
71 195 72 195
198 84 198 85
26 66 25 66
125 57 125 58
188 96 189 96
66 180 65 180
28 112 28 113
29 115 30 115
78 189 79 189
94 82 94 81
61 156 62 156
60 187 59 187
129 128 130 128
4 124 5 124
149 80 149 81
35 143 35 142
197 24 197 25
198 17 199 17
195 166 195 167
142 133 143 133
27 5 27 6
133 44 134 44
33 13 33 14
86 137 86 136
160 192 160 193
124 118 124 119
158 154 158 153
13 190 13 189
151 197 151 198
47 96 46 96
150 48 151 48
87 194 86 194
103 35 103 36
200 128 199 128
17 179 17 180
53 16 52 16
88 172 88 173
42 20 43 20
14 141 15 141
22 144 21 144
92 135 92 134
173 82 174 82
40 139 41 139
135 105 135 104
170 26 170 25
116 155 117 155
154 104 154 103
122 84 121 84
36 80 36 79
126 197 127 197
169 67 168 67
58 44 59 44
117 84 116 84
16 33 16 32
138 20 138 21
108 69 107 69
55 85 55 84
64 177 64 176
36 13 36 12
47 2 47 1
123 195 124 195
189 181 188 181
57 87 57 86
104 98 104 97
176 48 177 48
53 151 52 151
168 42 168 41
71 117 70 117
159 69 159 68
86 114 87 114
118 122 119 122
18 41 19 41
22 174 22 173
44 180 43 180
98 13 98 12
159 97 160 97
5 67 4 67
117 150 117 151
119 122 120 122
164 106 164 105
131 65 131 64
69 20 68 20
45 143 45 142
1 197 2 197
14 44 14 45
53 116 52 116
176 122 175 122
62 183 62 182
177 150 177 149
101 68 101 67
12 161 11 161
195 81 196 81
140 147 140 148
171 148 170 148
98 13 98 14
28 78 29 78
179 166 179 165
125 79 125 78
187 43 188 43
21 186 20 186
63 21 62 21
37 48 36 48
103 44 103 45
166 76 165 76
145 67 146 67
123 52 122 52
135 153 135 154
70 103 70 104
199 150 198 150
133 95 134 95
166 68 165 68
149 144 149 145
110 165 110 166
60 91 60 92
28 57 29 57
46 171 45 171
3 47 3 48
140 33 140 34
29 176 30 176
98 118 98 117
158 117 157 117
50 46 51 46
66 196 65 196
175 13 174 13
124 145 123 145
31 42 30 42
187 118 187 117
167 28 166 28
133 10 133 9
133 60 133 61
19 22 19 23
55 175 54 175
15 132 15 133
112 55 112 54
80 28 80 29
148 140 147 140
101 15 101 16
27 76 27 75
51 37 51 36
158 188 157 188
33 176 32 176
67 116 67 117
55 183 55 182
116 175 116 176
26 146 27 146
107 70 108 70
184 26 184 27
44 70 43 70
98 105 98 106
94 13 95 13
66 100 66 99
90 4 91 4
118 180 117 180
74 60 73 60
68 149 68 148
135 118 136 118
110 147 110 148
195 37 194 37
150 91 151 91
189 95 188 95
104 98 105 98
101 114 102 114
47 102 47 103
136 105 135 105
55 126 55 127
159 27 159 26
84 150 84 151
23 136 23 135
41 86 42 86
188 49 187 49
53 108 53 109
59 80 59 81
144 131 145 131
188 200 189 200
193 127 192 127
151 169 151 168
64 59 63 59
107 59 106 59
141 145 141 146
42 145 42 144
170 82 169 82
33 36 32 36
88 113 89 113
193 147 192 147
120 98 121 98
82 147 81 147
49 66 49 65
97 69 97 68
119 185 118 185
165 92 166 92
147 119 147 118
198 73 199 73
164 197 164 196
99 89 99 88
89 170 88 170
9 156 9 157
160 151 161 151
38 185 37 185
2 32 1 32
68 69 68 70
38 153 37 153
60 17 61 17
161 26 161 25
83 56 84 56
199 101 198 101
109 157 109 158
189 183 188 183
195 136 195 137
116 196 117 196
141 144 140 144
83 173 83 174
91 56 92 56
6 176 5 176
27 65 28 65
112 61 111 61
196 95 196 96
140 6 140 5
194 183 194 182
159 82 158 82
11 116 11 115
32 30 32 31
194 171 194 172
93 160 93 161
169 180 169 179
186 184 185 184
189 175 189 176
64 27 64 28
177 113 177 114
108 144 108 145
116 17 116 16
24 24 24 25
144 144 143 144
12 51 12 50
105 18 105 17
156 113 157 113
172 113 173 113
153 146 152 146
157 191 157 190
31 77 32 77
81 90 81 89
97 7 96 7
91 118 91 119
116 159 116 158
160 172 160 173
90 198 90 197
172 124 172 123
111 45 111 46
17 122 17 123
111 158 111 157
29 150 29 149
5 20 4 20
99 94 100 94
4 9 5 9
126 38 125 38
14 179 13 179
106 117 107 117
197 32 198 32
125 88 125 87
1 46 2 46
81 173 81 174
51 131 51 130
82 69 81 69
168 124 168 125
159 6 159 7
168 103 168 104
84 182 83 182
126 107 126 106
103 14 102 14
141 1 141 2
45 165 45 164
165 178 166 178
176 131 175 131
74 128 74 129
131 151 131 152
105 63 104 63
131 52 132 52
118 174 118 173
63 11 63 10
17 23 18 23
34 141 34 142
47 54 47 53
152 35 152 36
125 92 124 92
5 58 5 59
161 101 161 102
6 185 6 184
139 110 138 110
150 190 150 189
98 24 99 24
188 154 188 153
135 116 136 116
124 58 124 59
46 19 46 20
85 105 85 104
13 64 12 64
33 71 32 71
84 88 83 88
47 45 47 44
182 171 181 171
136 170 135 170
200 115 200 116
181 87 180 87
97 194 97 195
122 8 121 8
163 197 163 196
16 62 16 61
148 25 147 25
177 138 177 139
192 198 193 198
111 166 112 166
122 13 122 14
182 179 182 178
89 120 90 120
62 15 61 15
160 39 159 39
104 160 105 160
34 65 35 65
172 106 171 106
44 103 44 104
62 40 62 39
156 184 155 184
1 2 2 2
29 151 29 150
134 77 134 76
85 3 84 3
48 17 48 18
73 161 73 162
14 73 13 73
62 48 62 49
120 136 119 136
58 82 59 82
22 18 21 18
64 19 65 19
82 160 82 161
70 166 70 165
181 133 181 132
35 4 35 5
10 81 9 81
测试点2输出数据:
1 4 15 17 20 28 31 36 37 40 43 44 45 47 52 63 64 65 68 71 73 77 83 88 94 102 105 106 111 113 116 118 121 123 128 129 138 144 147 165 168 170 172 173 175 181 182 183 187 188 192 198 199
1 3 4 5 10 12 13 14 16 17 19 20 25 27 30 32 38 39 44 47 49 51 57 61 64 67 68 69 71 77 78 84 87 93 95 99 100 103 105 106 108 109 113 115 116 118 121 125 131 132 135 138 139 144 147 148 150 153 156 158 160 164 165 166 168 169 173 174 175 178 181 182 185 187 189 193 194 196 197 199