1998 ACM South Central USA Collegiate Programming Contest
Rice University

Gizilch

Solution    Judge's input     Judge's output   Clarifications      Comments

Scenario

The game of gizilch has very simple rules.  First 100 grapes are labeled, in nontoxic ink, with the numbers 1 to 100.  Then, with a cry of ``GIZILCH!'', the referee fires the grapes up into the air with a giant gizilcher.  The two players, who each start with a score of  ``1'', race to eat the falling (or, shortly thereafter, fallen) grapes and, at the same time, multiply their scores by the numbers written on the grapes they eat.  After a minute, the hungry squirrels are let loose to finish the remaining grapes, and each contestant reports his score, the product of the numbers on the grapes he's eaten.  The unofficial winner is the player who announces the highest score.

Inevitably, though, disputes arise, and so the official winner is not determined until the disputes are resolved.  The player who claims the lower score is entitled to challenge his opponent's score.  The player with the lower score is presumed to have told the truth, because if he were to lie about his score, he would surely come up with a bigger better lie.  The challenge is upheld if the player with the higher score has a score that cannot be achieved with grapes not eaten by the challenging player.  So, if the challenge is successful, the player claiming the lower score wins.

So, for example, if one player claims 343 points and the other claims 49, then clearly the first player is lying; the only way to score 343 is by eating grapes labeled 7 and 49, and the only way to score 49 is by eating a grape labeled 49.  Since each of two scores requires eating the grape labeled 49, the one claiming 343 points is presumed to be lying.

On the other hand, if one player claims 162 points and the other claims 81, it is possible for both to be telling the truth (e.g. one eats grapes 2, 3 and 27, while the other eats grape 81), so the challenge would not be upheld.

Unfortunately, anyone who is willing to referee a game of gizilch is likely to have himself consumed so many grapes (in a liquid form) that he or she could not reasonably be expected to perform the intricate calculations that refereeing requires.  Hence the need for you, sober programmer, to provide a software solution.

Input

Pairs of unequal, positive numbers, with each pair on a single line, that are claimed scores from a game of gizilch.

Output

Numbers, one to a line, that are the winning scores, assuming that the player with the lower score always challenges the outcome.

Sample Input

343 49
3599 610
62 36

Sample Output

49
610
62

 

Solution

#include <iostream.h>
#include <fstream.h>

#include <iomanip.h>

unsigned* factorList(unsigned n, unsigned& size)
{
  unsigned listSize = 100;
  unsigned* fact = new unsigned[listSize];
  unsigned nFacts = 0;
  fact[nFacts++] = 1;
  unsigned i;
  for (i = 2; i*i <= n; ++i)
    if (n % i == 0)
      {
        if (nFacts == listSize)
          {
            unsigned* old = fact;
            listSize *= 2;
            fact = new unsigned[listSize];
            for (unsigned j = 0; j < nFacts; ++j)
              fact[j] = old[j];
            delete[] old;
          }
        fact[nFacts++] = i;
      }
  {
    unsigned* old = fact;
    listSize = 2*nFacts;
    if (fact[nFacts-1] * fact[nFacts-1] == n)
      --listSize;
    fact = new unsigned[listSize];
    for (unsigned j = 0; j < nFacts; ++j)
      fact[j] = old[j];
    delete[] old;
  }
  for (i = 0; i < nFacts; ++i)
    fact[listSize-1-i] = n/fact[i];
  size = listSize;
  return fact;
}

int main()
{
  ifstream in("gizilch.inp");
  unsigned score1, score2;
  while (in >> score1 >> score2)
    {
      if (score1 > score2)
        { unsigned t = score1; score1 = score2; score2 = t; }

      unsigned size1;
      unsigned* factors1 = factorList(score1, size1);
      unsigned size2;
      unsigned* factors2 = factorList(score2, size2);

      // after num==k, feasible[i,j] is k>0 if the score pair (i,j) is possible
      // with only "grapes" labelled 1 to k (and not 1 to k-1), 0 otherwise
      unsigned tblsize = size1*size2;
      unsigned* feasible = new unsigned[tblsize];
      for (unsigned i = tblsize; i--; )
        feasible[i] = 0;
      feasible[0] = 1;

      unsigned f1next = 0;
      unsigned f2next = 0;

      while (f1next < size1 || f2next < size2)
        {
          unsigned num;
          if (f1next == size1)
            num = factors2[f2next++];
          else if (factors1[f1next] < factors2[f2next])
            num = factors1[f1next++];
          else
            {
              if (factors1[f1next] == factors2[f2next])
                ++f1next;
              num = factors2[f2next++];
            }
          if (num > 100)
            break;

          unsigned k = 0;
          for (unsigned i = 0; i < size1; ++i)
            for (unsigned j = 0; j < size2; ++j, ++k)
              if (feasible[k] && feasible[k] < num)
                // see what new pairs can be validated with grape "num"
                {
                  unsigned ii, f1 = factors1[i]*num;
                  for (ii =  i+1; factors1[ii] != f1 && ii < size1; ++ii)
                    {}
                  if (ii < size1)
                    {
                      unsigned p = ii*size2+j;
                      if (! feasible[p]) feasible[p] = num;
                    }
 
                  unsigned jj, f2 = factors2[j]*num;
                  for (jj =  j+1; factors2[jj] != f2 && jj < size2; ++jj)
                    {}
                  if (jj < size2)
                    {
                      unsigned p = i*size2+jj;
                      if (! feasible[p]) feasible[p] = num;
                    }
                }
          if (feasible[tblsize-1] == num)
            break;
        }

      // see what is possible...
      unsigned winscore;
      if (feasible[tblsize-1])
        winscore = score2;      // both could be honest
      else if (!feasible[(size1-1)*size2])
        winscore = score2;      // 1 definitely lied
      else
        winscore = score1;      // they can't both be honest, so 1 wins
 
      cout << winscore << "\n";
      delete[] feasible;
      delete[] factors2;
      delete[] factors1;
    }
  return 0;
}
 

Judge's Input

294 202
62 36
343 49
3599 610
194 178
1324 1996
2310 513
804 887
41235 2474
6231 1500
144 162
3537 644
260 395
275 4590
817 903
424 183
824 85
941 3
1 101
256 64
138 258
213 215
151 127
110 119
112 186
249 267
184 160
125 243
189 283
237 266
266 278
195 211
267 154
131 245
182 236
224 205
294 202
151 167
254 153
261 196
128 288
185 243
267 106
265 103
262 134
253 220
144 103
262 218
122 227
157 245
179 283
251 194
170 159
148 257
129 206
106 290
238 216
114 162
216 125
281 234
243 122
133 236
260 279
171 101
236 161
260 105
229 144
175 193
214 239
188 221
102 271
134 217
282 115
286 153
206 274
151 148
173 134
293 210
248 110
220 149
256 262
266 297
293 210
291 299
226 205
185 282
110 100
152 265
220 280
139 104
285 175
225 165
114 171
276 197
243 197
119 187
223 249
165 156
273 201
113 257
199 167
113 298
226 211
146 266
236 288
178 126
173 287
271 117
252 288
291 183
222 244
228 285
263 259
141 276
275 278
263 185
244 189
213 211
161 126
145 196
203 170
170 229
199 200
107 108
225 157
242 174
231 122
252 124
194 115
147 176
178 265
246 276
192 151
188 263
131 133
232 206
111 174
148 244
289 274
291 289
195 235
264 140
192 135
279 192
150 290
295 168
231 289
181 202
270 286
271 180
161 287
229 290
146 133
208 163
181 101
199 286
114 129
222 207
128 292
205 290
229 175
129 291
288 142
133 275
219 242
294 292
209 213
177 182
211 295
174 169
250 179
289 234
252 264
180 129
135 232
245 256
143 179
288 107
279 257
214 287
240 122
249 109
109 133
196 132
299 163
269 176
177 201
191 140
203 215
129 120
117 164
224 243
162 229
246 143
267 225
183 134
222 142
295 112
164 210
285 226
288 185
278 150
176 265
226 293
181 111
158 149
147 231
150 274
280 133
168 278
124 215
145 192
108 239
185 102
118 234
158 162
284 201
184 189
241 202
153 158
228 263
187 152
135 209
175 255
175 188
153 257
258 122
188 245
194 100
271 205
251 101
108 114
277 165
269 115
130 277
149 237
199 199
231 217
267 179
266 297
185 241
127 249
285 115
176 253
136 230
168 110
219 108
242 299
149 146
138 241
181 226
238 147
247 200
139 296
166 285
271 256
133 189
251 212
126 257
156 152
110 284
253 129
279 182
182 277
268 202
202 112
265 279
156 144
170 265
119 165
193 141
184 259
100 111
244 235
204 220
289 221
213 271
269 270
294 187
193 217
288 140
195 190
159 206
286 197
162 243
147 192
146 262
179 284
252 144
195 198
214 237
246 182
164 246
122 165
168 292
290 261
259 217
254 204
245 247
125 280
238 165
190 241
299 197
177 210
247 167
216 173
263 147
117 265
171 185
146 237
141 161
170 266
179 145
107 138
213 201
216 114
198 152
217 264
226 165
145 132
196 285
155 192
188 255
267 112
130 217
142 272
293 128
105 160
138 146
282 272
254 277
185 259
234 203
259 245
145 147
101 283
267 281
187 247
102 264
211 137
193 117
237 213
241 228
119 118
216 102
170 142
168 145
102 186
259 174
246 119
143 297
170 208
148 227
185 122
190 183
243 101
201 182
224 195
176 298
211 222
211 109
259 212
259 248
183 177
271 234
231 224
277 135
163 161
151 244
284 193
275 219
172 141
249 291
263 284
258 141
166 263
244 110
135 106
168 160
262 223
264 207
273 183
113 116
134 271
141 203
254 228
117 148
118 231
121 109
169 198
255 162
144 209
260 274
244 239
110 289
249 220
181 164
122 147
221 128
252 178
173 129
189 259
252 179
217 260
289 283
295 187
239 235
288 203
258 112
267 253
268 147
168 111
254 129
195 293
208 260
269 162
223 229
249 205
249 224
284 124
113 181
289 257
187 232
255 199
190 160
211 283
204 112
261 282
108 111
268 294
186 271
144 184
155 127
260 148
186 226
111 231
145 252
127 210
249 128
148 259
168 267
150 288
246 229
110 291
285 237
252 276
275 185
222 241
257 200
108 126
113 201
180 261
290 200
216 268
179 299
249 257
121 104
217 190
128 212
116 212
251 115
253 264
100 164
159 112
106 144
210 277
117 294
241 206
139 207
293 120
136 154
188 103
103 288
215 299
124 108
190 155
293 210
172 138
187 197
226 148
197 102
149 255
191 120
167 266
108 148
262 142
152 140
110 126
188 258
270 256
113 134
293 241
187 266
212 274
106 118
273 213
282 170
102 214
197 231
205 153
101 108
218 238
164 266
270 223
207 102
279 126
279 106
265 239
133 114
299 105
128 286
129 243
137 197
277 264
240 108
252 218
111 193
290 240
146 115
173 104
145 125
162 299
142 174
290 187
116 266
162 189
165 166
173 285
258 246
113 110
297 271
220 191
184 195
205 236
148 199
171 154
176 119
174 256
166 292
103 134
279 291
256 214
266 190
163 165
261 102
212 280
111 271
197 110
290 153
117 274
185 167
160 269
293 258
132 277
216 212
185 176
117 204
238 158
253 188
268 281
155 196
139 166
170 196
254 289
188 195
112 298
185 171
251 153
185 169
284 162
130 221
128 281
216 174
156 292
120 130
175 275
235 280
257 248
131 135
208 286
190 162
239 140
141 258
237 118
155 193
173 207
150 208
107 193
152 152
226 280
298 184
213 233
117 259
292 134
256 207
291 167
264 150
209 127
123 116
221 156
131 261
240 100
227 195
243 200
219 242
191 145
291 149
230 181
273 117
133 192
179 204
278 274
235 269
135 181
269 130
124 131
298 282
125 153
146 241
136 133
203 197
292 137
276 297
250 157
232 124
100 182
107 119
162 192
214 185
121 213
226 187
242 250
126 122
260 206
233 136
169 266
175 225
169 199
131 133
144 274
208 107
176 256
216 208
215 250
201 210
270 126
210 176
191 267
209 229
244 227
186 240
135 182
231 213
189 130
146 161
233 220
275 135
274 125
226 166
220 118
220 143
183 153
110 184
226 109
130 234
174 271
172 113
210 136
155 201
185 291
144 155
149 195
256 266
106 231
290 185
210 109
247 201
124 287
252 171
156 175
257 185
273 292
135 285
217 266
251 150
285 139
221 190
203 207
135 212
111 269
102 162
265 279
250 151
221 206
270 194
133 283
286 219
166 232
219 249
189 282
248 235
248 216
145 271
124 104
249 196
226 294
128 160
208 260
150 209
297 223
235 244
188 151
130 287
237 197
144 103
110 170
161 216
131 163
125 112
184 182
188 163
187 260
239 276
113 260
290 248
105 107
123 250
138 213
291 126
102 113
199 110
243 160
125 206
286 244
239 121
270 209
234 175
257 205
243 141
265 230
102 219
133 184
182 139
175 107
195 287
208 238
247 239
230 157
271 133
128 220
137 177
215 265
122 179
133 234
157 156
131 164
106 195
292 175
164 272
138 250
121 178
164 218
120 122
260 178
276 244
138 137
210 160
267 102
244 236
103 108
131 120
157 165
279 263
263 160
198 280
117 170
173 288
178 294
226 157
104 277
245 171
228 140
250 183
186 119
112 165
159 145
127 201
104 145
283 199
253 179
211 228
277 235
240 225
185 234
173 282
144 223
171 163
102 164
226 293
147 158
263 195
284 226
272 136
244 191
240 260
168 264
107 147
133 190
168 244
154 230
114 201
245 224
133 251
231 139
208 275
271 297
215 112
127 223
102 228
264 169
189 222
110 206
126 101
147 121
223 257
149 203
168 217
183 136
299 124
184 152
174 144
125 234
186 284
135 136
225 182
133 117
226 244
112 191
180 195
160 292
164 289
161 295
294 267
149 183
261 213
224 251
171 253
158 199
239 262
149 189
154 237
162 188
240 238
237 162
190 196
228 177
167 219
119 210
295 125
248 173
132 174
145 107
287 153
266 106
199 182
177 166
240 266
249 239
133 165
142 287
243 105
150 191
233 143
207 214
168 234
264 218
278 176
272 290
115 196
289 273
240 269
155 243
170 244
200 140
203 272
187 197
267 161
111 126
248 206
112 130
194 232
260 141
157 211
128 255
285 239
218 165
164 258
114 123
275 179
135 100
233 223
123 246
198 269
206 150
126 176
284 206
118 263
117 176
280 181
263 289
167 169
254 254
257 174
287 136
120 248
192 175
263 267
167 248
140 268
277 206
162 164
296 218
259 103
291 130
247 113
126 201
136 243
213 188
265 224
266 169
210 195
217 293
221 236
167 244
237 230
146 280
180 106
295 165
209 266
189 154
115 180
197 264
272 252
190 191
284 201
242 269
258 299
107 230
156 249
299 203
138 132
149 202
252 251
119 177
296 229
228 178
258 177
284 204
159 189
298 199
168 248
136 278
111 272
269 130
138 138
138 147
266 182
272 278
146 270
169 204
225 106
176 136
110 213
258 246
222 277
257 252
159 157
100 194
289 163
160 289
297 192
189 229
277 122
209 154
215 180
213 296
266 144
177 109
126 282
191 271
155 213
106 206
287 209
246 211
152 219
116 139
112 146
252 129
139 267
104 223
298 220
178 123
133 160
158 218
114 200
181 253
160 292
126 221
106 299
253 111
132 256
121 256
287 289
126 183
221 158
215 150
227 278
161 182
241 138
224 229

Judge's Output

294
62
49
610
178
1996
2310
804
41235
6231
162
644
395
4590
817
424
85
3
1
256
258
215
151
119
186
249
184
243
189
266
266
195
267
245
236
224
294
167
153
261
288
243
267
265
134
253
144
262
122
245
283
194
170
148
129
290
238
162
216
234
243
236
279
171
236
260
144
175
239
221
102
217
282
286
274
148
134
210
248
220
256
297
210
299
205
282
110
265
280
104
285
225
171
276
243
119
249
165
273
257
199
298
226
266
288
178
287
117
288
183
244
285
259
276
275
185
244
213
161
196
203
170
200
108
225
242
231
252
194
176
265
276
192
188
133
232
174
244
289
291
235
264
192
279
290
295
231
202
286
180
161
290
146
208
181
286
129
222
292
290
175
129
288
275
242
294
213
182
295
174
250
234
264
180
232
256
143
288
279
287
240
249
133
196
299
176
177
140
215
129
164
243
162
246
267
183
222
295
210
285
288
150
265
293
111
158
231
150
280
168
215
192
108
185
234
162
284
189
241
158
228
187
209
255
188
153
258
245
194
205
251
114
165
115
130
237
199
231
267
297
185
249
285
253
230
168
219
299
146
138
226
238
247
296
285
256
189
212
126
156
284
253
279
182
268
112
279
156
265
165
141
259
111
244
220
221
213
270
294
217
288
195
159
286
243
192
146
284
252
198
237
246
246
165
292
290
217
204
247
280
238
190
299
210
247
216
147
265
185
237
161
266
145
138
201
216
198
264
165
145
285
192
255
267
217
272
128
160
146
282
277
185
234
259
147
283
267
247
264
211
117
213
228
119
216
170
168
186
259
246
297
208
148
185
190
243
201
224
176
222
211
259
259
177
234
231
135
161
244
284
275
172
249
284
258
166
244
135
168
262
264
273
116
134
203
228
148
231
121
198
255
209
260
244
110
249
164
147
221
252
129
259
252
260
289
295
235
288
258
267
268
168
129
195
260
162
229
249
249
284
181
289
232
255
190
283
204
282
111
294
186
184
155
260
186
231
252
210
249
259
267
288
246
291
285
276
275
222
200
126
201
261
290
268
299
249
104
217
212
212
115
264
164
159
144
210
294
241
207
120
154
188
288
299
124
190
210
172
187
148
102
255
120
266
148
142
152
126
258
270
134
293
266
212
106
273
282
102
231
205
108
238
266
270
207
279
279
265
133
299
286
243
197
264
240
252
111
290
146
104
125
299
174
290
266
189
166
285
258
110
297
220
195
236
148
171
176
256
292
134
291
256
266
165
261
280
111
110
290
117
185
160
258
132
216
185
204
238
253
268
196
166
196
289
195
112
185
153
185
284
221
128
216
292
130
275
280
248
135
286
190
140
258
237
155
207
208
193
152
280
184
213
259
292
256
291
264
209
123
221
261
240
195
243
242
145
291
230
273
192
204
278
235
135
130
124
282
153
146
136
203
292
297
250
232
182
119
192
185
213
187
250
126
260
136
266
225
199
133
144
208
256
216
250
210
270
210
267
209
244
240
182
231
189
161
220
275
125
166
220
220
183
184
226
234
174
172
210
201
291
155
195
266
231
290
210
247
287
252
175
185
292
285
266
150
285
221
207
212
111
162
279
250
221
270
133
286
232
219
282
248
248
145
124
249
294
160
260
209
297
244
188
287
237
144
170
216
163
125
184
188
260
276
260
290
105
250
213
291
102
110
243
125
286
239
270
234
205
243
265
219
184
182
175
287
238
247
230
133
220
177
215
122
234
156
164
195
292
272
250
178
164
122
260
276
138
210
267
236
108
120
165
279
160
280
170
288
294
226
104
245
228
250
186
165
159
201
145
283
253
228
235
240
234
282
144
171
164
293
158
195
284
272
244
260
264
147
190
244
230
201
245
133
231
275
297
215
223
228
264
222
110
126
147
257
203
217
183
299
184
174
234
284
136
225
133
244
112
195
292
164
295
294
183
261
224
253
158
262
189
237
188
240
237
196
228
219
210
125
248
174
145
287
266
182
177
266
249
165
287
243
150
143
207
234
264
176
290
196
273
240
243
244
200
272
187
267
126
248
130
232
260
211
255
285
165
258
123
275
135
233
123
198
150
176
284
118
176
280
289
169
254
174
287
248
192
267
248
268
277
164
296
259
291
247
201
243
213
265
266
210
217
236
244
237
280
180
295
266
189
180
264
272
190
284
242
299
230
249
299
138
202
252
177
296
228
258
284
189
298
248
136
272
130
138
147
266
272
270
204
225
176
213
258
222
252
159
194
289
160
297
189
122
209
215
296
266
177
282
271
213
106
287
246
219
116
146
252
267
104
220
178
160
158
200
253
292
221
299
253
256
256
287
183
221
215
278
182
138
224

Clarifications

A clarification was made at the beginning of the contest to resolve some ambiguity in the problem description noticed a couple of days before the contest. The rules for deciding the winner of a game of gizilch are, first, if both players might be telling the truth, the larger score wins.  Second, if the player with the lower score cannot be telling the truth, the player with the higher score wins.  Finally, if neither of the previous two conditions holds, the lower score wins..

Comments

Clearly, the test case was excessively large.  While that does penalize all but the algorithmically efficient solutions, it happened here more out of distraction than intent.  I generated these random number pairs,