180  Eeny Meeny
Moderator: Board moderators

 New poster
 Posts: 8
 Joined: Sat Jul 06, 2002 3:46 pm
 Location: CSE, SUST, Bangladesh
 Contact:
Run Time Error
Any one knows what is the causes of Invalid Mamory access (Array boundary overflow etc..)
Re: Run Time Error
the program try to access elemen outside your array limit. In other words, your array size is too small.kuasha wrote:Any one knows what is the causes of Invalid Mamory access (Array boundary overflow etc..)

 Guru
 Posts: 834
 Joined: Wed May 29, 2002 4:11 pm
 Location: Wroclaw, Poland
 Contact:
180 WA
Could anyone tell me, which tricks are in this problem ?
I try to solve it in this way:
compute all chiefs for any number of people, using method:
F(n) = (F(n1) + (n % 15 + 1)) % 15 + 1 and F(1) = 1, F(2) = 2
after that for any bound of people I remove from possible positions F(n) and "n  F(n) + 1" (to n = upper limit people in case, inclusive).... If after this proces still is any not used position < it's a solution
Best regards
Dominik Michniewski
I try to solve it in this way:
compute all chiefs for any number of people, using method:
F(n) = (F(n1) + (n % 15 + 1)) % 15 + 1 and F(1) = 1, F(2) = 2
after that for any bound of people I remove from possible positions F(n) and "n  F(n) + 1" (to n = upper limit people in case, inclusive).... If after this proces still is any not used position < it's a solution
Best regards
Dominik Michniewski
180  Eeny Meeny
I tried solving the question using a lookup table generated just before input reading.. but apparently my data is wrong or my method is wrong.
simply put, my method is:
let F(n) = person to be chosen as chief when there are n people to choose from
let G(n) = person to be chosen as chief when we count from the other direction
clearly F(n) depends on F(n1). so I generate a table starting from F(1) = 0 (means the starting person is chosen). The table is generated until F(1000000).
F(n) = (15 + F(n1)) % n
G(n) = (n  F(n)) % n
Then I simply count which person is not chosen for all cases in the range (inclusive). However, this gets me WA. :p
If anyone has got AC, please run the following test data through your code and see what results it gives?
test data:
my results:
simply put, my method is:
let F(n) = person to be chosen as chief when there are n people to choose from
let G(n) = person to be chosen as chief when we count from the other direction
clearly F(n) depends on F(n1). so I generate a table starting from F(1) = 0 (means the starting person is chosen). The table is generated until F(1000000).
F(n) = (15 + F(n1)) % n
G(n) = (n  F(n)) % n
Then I simply count which person is not chosen for all cases in the range (inclusive). However, this gets me WA. :p
If anyone has got AC, please run the following test data through your code and see what results it gives?
test data:
Code: Select all
113 89
61 386
853 166
808 1273
1435 370
2955 87
1769 2335
5516 5756
6757 6605
6950 325
9807 699
10361 14152
1048 3086
126 8011
5787 10166
21251 5387
6125 22159
18726 3874
10745 11621
29506 17489
7386 20597
14125 3365
36497 46871
14439 43226
11860 60854
34575 42070
61004 34258
72606 73215
36322 28737
57228 10394
26953 90516
63879 99576
48326 45329
66423 35270
22943 35223
120757 72211
89946 54385
36490 132985
132771 5305
116938 91254
151299 51192
18648 28468
58652 147783
125840 118130
180824 97751
123709 29278
132377 176365
136175 109689
178290 27930
167737 110612
122867 79935
60518 179418
125679 195140
102523 180148
244755 52469
147744 275685
127613 184227
41705 221062
50887 115398
15752 192763
318382 144133
192580 194828
51431 118508
362679 96813
219573 270209
229120 244725
31195 295871
345834 134871
442958 72531
121419 88493
204324 297336
319248 115268
31892 295392
123591 87791
129771 188382
145475 141765
428036 491429
27047 159214
473366 443584
429833 498604
116287 511259
530728 466665
596389 434840
478879 675596
381519 385498
437057 466120
422872 433251
255261 89824
240322 39418
57122 552261
395760 81011
371538 225170
773229 519491
755206 374500
372827 300823
96027 599146
110410 299970
125385 835558
772519 492071
170786 216847
0 0
my results:
Code: Select all
1
36
7
1
4
Better estimate needed
4
1
1
65
Better estimate needed
4
4
Better estimate needed
3
14
14
14
1
1
14
29
1
16
44
1
1
1
2
Better estimate needed
14
3
1
1
4
1
5
14
Better estimate needed
1
5
1
5
1
4
14
4
1
14
4
1
5
4
4
65
1
4
36
5
Better estimate needed
1
1
5
20
1
1
Better estimate needed
16
46
1
1
16
Better estimate needed
1
4
1
2
14
1
2
16
2
2
1
1
1
1
20
65
Better estimate needed
20
1
1
33
1
181
20
181
1
1
My program gives different output for only one case.
For the 2nd case, my output is
"Better estimate needed"
For the 2nd case, my output is
"Better estimate needed"
My signature:
 Please make discussion about the algorithm BRFORE posting source code.
We can learn much more in discussion than reading source code.  I HATE testing account.
 Don't send me source code for debug.
The analysis of my program for data set 2 (61 386) is as follows:
First number is the number of people for the current case
second number is the person chosen to be chief if counting is done clockwise
third number is the person chosen to be chief if counting is done anticlockwise
So for the first line, it means that if there are 61 people in the circle, person 18 (17 positions away from the first) and person 45 (44 positions away from the first) will be chosen to be chief. Since in the range 61  386, only person 37 (36 positions away from the first) is not chosen, the answer my program outputs is 36. Which is, sadly, wrong. Can anyone explain to me their logic?
61 people, chosen: 17 44
62 people, chosen: 32 30
63 people, chosen: 47 16
64 people, chosen: 62 2
65 people, chosen: 12 53
66 people, chosen: 27 39
67 people, chosen: 42 25
68 people, chosen: 57 11
69 people, chosen: 3 66
70 people, chosen: 18 52
71 people, chosen: 33 38
72 people, chosen: 48 24
73 people, chosen: 63 10
74 people, chosen: 4 70
75 people, chosen: 19 56
76 people, chosen: 34 42
77 people, chosen: 49 28
78 people, chosen: 64 14
79 people, chosen: 0 0
80 people, chosen: 15 65
81 people, chosen: 30 51
82 people, chosen: 45 37
83 people, chosen: 60 23
84 people, chosen: 75 9
85 people, chosen: 5 80
86 people, chosen: 20 66
87 people, chosen: 35 52
88 people, chosen: 50 38
89 people, chosen: 65 24
90 people, chosen: 80 10
91 people, chosen: 4 87
92 people, chosen: 19 73
93 people, chosen: 34 59
94 people, chosen: 49 45
95 people, chosen: 64 31
96 people, chosen: 79 17
97 people, chosen: 94 3
98 people, chosen: 11 87
99 people, chosen: 26 73
100 people, chosen: 41 59
101 people, chosen: 56 45
102 people, chosen: 71 31
103 people, chosen: 86 17
104 people, chosen: 101 3
105 people, chosen: 11 94
106 people, chosen: 26 80
107 people, chosen: 41 66
108 people, chosen: 56 52
109 people, chosen: 71 38
110 people, chosen: 86 24
111 people, chosen: 101 10
112 people, chosen: 4 108
113 people, chosen: 19 94
114 people, chosen: 34 80
115 people, chosen: 49 66
116 people, chosen: 64 52
117 people, chosen: 79 38
118 people, chosen: 94 24
119 people, chosen: 109 10
120 people, chosen: 4 116
121 people, chosen: 19 102
122 people, chosen: 34 88
123 people, chosen: 49 74
124 people, chosen: 64 60
125 people, chosen: 79 46
126 people, chosen: 94 32
127 people, chosen: 109 18
128 people, chosen: 124 4
129 people, chosen: 10 119
130 people, chosen: 25 105
131 people, chosen: 40 91
132 people, chosen: 55 77
133 people, chosen: 70 63
134 people, chosen: 85 49
135 people, chosen: 100 35
136 people, chosen: 115 21
137 people, chosen: 130 7
138 people, chosen: 7 131
139 people, chosen: 22 117
140 people, chosen: 37 103
141 people, chosen: 52 89
142 people, chosen: 67 75
143 people, chosen: 82 61
144 people, chosen: 97 47
145 people, chosen: 112 33
146 people, chosen: 127 19
147 people, chosen: 142 5
148 people, chosen: 9 139
149 people, chosen: 24 125
150 people, chosen: 39 111
151 people, chosen: 54 97
152 people, chosen: 69 83
153 people, chosen: 84 69
154 people, chosen: 99 55
155 people, chosen: 114 41
156 people, chosen: 129 27
157 people, chosen: 144 13
158 people, chosen: 1 157
159 people, chosen: 16 143
160 people, chosen: 31 129
161 people, chosen: 46 115
162 people, chosen: 61 101
163 people, chosen: 76 87
164 people, chosen: 91 73
165 people, chosen: 106 59
166 people, chosen: 121 45
167 people, chosen: 136 31
168 people, chosen: 151 17
169 people, chosen: 166 3
170 people, chosen: 11 159
171 people, chosen: 26 145
172 people, chosen: 41 131
173 people, chosen: 56 117
174 people, chosen: 71 103
175 people, chosen: 86 89
176 people, chosen: 101 75
177 people, chosen: 116 61
178 people, chosen: 131 47
179 people, chosen: 146 33
180 people, chosen: 161 19
181 people, chosen: 176 5
182 people, chosen: 9 173
183 people, chosen: 24 159
184 people, chosen: 39 145
185 people, chosen: 54 131
186 people, chosen: 69 117
187 people, chosen: 84 103
188 people, chosen: 99 89
189 people, chosen: 114 75
190 people, chosen: 129 61
191 people, chosen: 144 47
192 people, chosen: 159 33
193 people, chosen: 174 19
194 people, chosen: 189 5
195 people, chosen: 9 186
196 people, chosen: 24 172
197 people, chosen: 39 158
198 people, chosen: 54 144
199 people, chosen: 69 130
200 people, chosen: 84 116
201 people, chosen: 99 102
202 people, chosen: 114 88
203 people, chosen: 129 74
204 people, chosen: 144 60
205 people, chosen: 159 46
206 people, chosen: 174 32
207 people, chosen: 189 18
208 people, chosen: 204 4
209 people, chosen: 10 199
210 people, chosen: 25 185
211 people, chosen: 40 171
212 people, chosen: 55 157
213 people, chosen: 70 143
214 people, chosen: 85 129
215 people, chosen: 100 115
216 people, chosen: 115 101
217 people, chosen: 130 87
218 people, chosen: 145 73
219 people, chosen: 160 59
220 people, chosen: 175 45
221 people, chosen: 190 31
222 people, chosen: 205 17
223 people, chosen: 220 3
224 people, chosen: 11 213
225 people, chosen: 26 199
226 people, chosen: 41 185
227 people, chosen: 56 171
228 people, chosen: 71 157
229 people, chosen: 86 143
230 people, chosen: 101 129
231 people, chosen: 116 115
232 people, chosen: 131 101
233 people, chosen: 146 87
234 people, chosen: 161 73
235 people, chosen: 176 59
236 people, chosen: 191 45
237 people, chosen: 206 31
238 people, chosen: 221 17
239 people, chosen: 236 3
240 people, chosen: 11 229
241 people, chosen: 26 215
242 people, chosen: 41 201
243 people, chosen: 56 187
244 people, chosen: 71 173
245 people, chosen: 86 159
246 people, chosen: 101 145
247 people, chosen: 116 131
248 people, chosen: 131 117
249 people, chosen: 146 103
250 people, chosen: 161 89
251 people, chosen: 176 75
252 people, chosen: 191 61
253 people, chosen: 206 47
254 people, chosen: 221 33
255 people, chosen: 236 19
256 people, chosen: 251 5
257 people, chosen: 9 248
258 people, chosen: 24 234
259 people, chosen: 39 220
260 people, chosen: 54 206
261 people, chosen: 69 192
262 people, chosen: 84 178
263 people, chosen: 99 164
264 people, chosen: 114 150
265 people, chosen: 129 136
266 people, chosen: 144 122
267 people, chosen: 159 108
268 people, chosen: 174 94
269 people, chosen: 189 80
270 people, chosen: 204 66
271 people, chosen: 219 52
272 people, chosen: 234 38
273 people, chosen: 249 24
274 people, chosen: 264 10
275 people, chosen: 4 271
276 people, chosen: 19 257
277 people, chosen: 34 243
278 people, chosen: 49 229
279 people, chosen: 64 215
280 people, chosen: 79 201
281 people, chosen: 94 187
282 people, chosen: 109 173
283 people, chosen: 124 159
284 people, chosen: 139 145
285 people, chosen: 154 131
286 people, chosen: 169 117
287 people, chosen: 184 103
288 people, chosen: 199 89
289 people, chosen: 214 75
290 people, chosen: 229 61
291 people, chosen: 244 47
292 people, chosen: 259 33
293 people, chosen: 274 19
294 people, chosen: 289 5
295 people, chosen: 9 286
296 people, chosen: 24 272
297 people, chosen: 39 258
298 people, chosen: 54 244
299 people, chosen: 69 230
300 people, chosen: 84 216
301 people, chosen: 99 202
302 people, chosen: 114 188
303 people, chosen: 129 174
304 people, chosen: 144 160
305 people, chosen: 159 146
306 people, chosen: 174 132
307 people, chosen: 189 118
308 people, chosen: 204 104
309 people, chosen: 219 90
310 people, chosen: 234 76
311 people, chosen: 249 62
312 people, chosen: 264 48
313 people, chosen: 279 34
314 people, chosen: 294 20
315 people, chosen: 309 6
316 people, chosen: 8 308
317 people, chosen: 23 294
318 people, chosen: 38 280
319 people, chosen: 53 266
320 people, chosen: 68 252
321 people, chosen: 83 238
322 people, chosen: 98 224
323 people, chosen: 113 210
324 people, chosen: 128 196
325 people, chosen: 143 182
326 people, chosen: 158 168
327 people, chosen: 173 154
328 people, chosen: 188 140
329 people, chosen: 203 126
330 people, chosen: 218 112
331 people, chosen: 233 98
332 people, chosen: 248 84
333 people, chosen: 263 70
334 people, chosen: 278 56
335 people, chosen: 293 42
336 people, chosen: 308 28
337 people, chosen: 323 14
338 people, chosen: 0 0
339 people, chosen: 15 324
340 people, chosen: 30 310
341 people, chosen: 45 296
342 people, chosen: 60 282
343 people, chosen: 75 268
344 people, chosen: 90 254
345 people, chosen: 105 240
346 people, chosen: 120 226
347 people, chosen: 135 212
348 people, chosen: 150 198
349 people, chosen: 165 184
350 people, chosen: 180 170
351 people, chosen: 195 156
352 people, chosen: 210 142
353 people, chosen: 225 128
354 people, chosen: 240 114
355 people, chosen: 255 100
356 people, chosen: 270 86
357 people, chosen: 285 72
358 people, chosen: 300 58
359 people, chosen: 315 44
360 people, chosen: 330 30
361 people, chosen: 345 16
362 people, chosen: 360 2
363 people, chosen: 12 351
364 people, chosen: 27 337
365 people, chosen: 42 323
366 people, chosen: 57 309
367 people, chosen: 72 295
368 people, chosen: 87 281
369 people, chosen: 102 267
370 people, chosen: 117 253
371 people, chosen: 132 239
372 people, chosen: 147 225
373 people, chosen: 162 211
374 people, chosen: 177 197
375 people, chosen: 192 183
376 people, chosen: 207 169
377 people, chosen: 222 155
378 people, chosen: 237 141
379 people, chosen: 252 127
380 people, chosen: 267 113
381 people, chosen: 282 99
382 people, chosen: 297 85
383 people, chosen: 312 71
384 people, chosen: 327 57
385 people, chosen: 342 43
386 people, chosen: 357 29
36
First number is the number of people for the current case
second number is the person chosen to be chief if counting is done clockwise
third number is the person chosen to be chief if counting is done anticlockwise
So for the first line, it means that if there are 61 people in the circle, person 18 (17 positions away from the first) and person 45 (44 positions away from the first) will be chosen to be chief. Since in the range 61  386, only person 37 (36 positions away from the first) is not chosen, the answer my program outputs is 36. Which is, sadly, wrong. Can anyone explain to me their logic?
61 people, chosen: 17 44
62 people, chosen: 32 30
63 people, chosen: 47 16
64 people, chosen: 62 2
65 people, chosen: 12 53
66 people, chosen: 27 39
67 people, chosen: 42 25
68 people, chosen: 57 11
69 people, chosen: 3 66
70 people, chosen: 18 52
71 people, chosen: 33 38
72 people, chosen: 48 24
73 people, chosen: 63 10
74 people, chosen: 4 70
75 people, chosen: 19 56
76 people, chosen: 34 42
77 people, chosen: 49 28
78 people, chosen: 64 14
79 people, chosen: 0 0
80 people, chosen: 15 65
81 people, chosen: 30 51
82 people, chosen: 45 37
83 people, chosen: 60 23
84 people, chosen: 75 9
85 people, chosen: 5 80
86 people, chosen: 20 66
87 people, chosen: 35 52
88 people, chosen: 50 38
89 people, chosen: 65 24
90 people, chosen: 80 10
91 people, chosen: 4 87
92 people, chosen: 19 73
93 people, chosen: 34 59
94 people, chosen: 49 45
95 people, chosen: 64 31
96 people, chosen: 79 17
97 people, chosen: 94 3
98 people, chosen: 11 87
99 people, chosen: 26 73
100 people, chosen: 41 59
101 people, chosen: 56 45
102 people, chosen: 71 31
103 people, chosen: 86 17
104 people, chosen: 101 3
105 people, chosen: 11 94
106 people, chosen: 26 80
107 people, chosen: 41 66
108 people, chosen: 56 52
109 people, chosen: 71 38
110 people, chosen: 86 24
111 people, chosen: 101 10
112 people, chosen: 4 108
113 people, chosen: 19 94
114 people, chosen: 34 80
115 people, chosen: 49 66
116 people, chosen: 64 52
117 people, chosen: 79 38
118 people, chosen: 94 24
119 people, chosen: 109 10
120 people, chosen: 4 116
121 people, chosen: 19 102
122 people, chosen: 34 88
123 people, chosen: 49 74
124 people, chosen: 64 60
125 people, chosen: 79 46
126 people, chosen: 94 32
127 people, chosen: 109 18
128 people, chosen: 124 4
129 people, chosen: 10 119
130 people, chosen: 25 105
131 people, chosen: 40 91
132 people, chosen: 55 77
133 people, chosen: 70 63
134 people, chosen: 85 49
135 people, chosen: 100 35
136 people, chosen: 115 21
137 people, chosen: 130 7
138 people, chosen: 7 131
139 people, chosen: 22 117
140 people, chosen: 37 103
141 people, chosen: 52 89
142 people, chosen: 67 75
143 people, chosen: 82 61
144 people, chosen: 97 47
145 people, chosen: 112 33
146 people, chosen: 127 19
147 people, chosen: 142 5
148 people, chosen: 9 139
149 people, chosen: 24 125
150 people, chosen: 39 111
151 people, chosen: 54 97
152 people, chosen: 69 83
153 people, chosen: 84 69
154 people, chosen: 99 55
155 people, chosen: 114 41
156 people, chosen: 129 27
157 people, chosen: 144 13
158 people, chosen: 1 157
159 people, chosen: 16 143
160 people, chosen: 31 129
161 people, chosen: 46 115
162 people, chosen: 61 101
163 people, chosen: 76 87
164 people, chosen: 91 73
165 people, chosen: 106 59
166 people, chosen: 121 45
167 people, chosen: 136 31
168 people, chosen: 151 17
169 people, chosen: 166 3
170 people, chosen: 11 159
171 people, chosen: 26 145
172 people, chosen: 41 131
173 people, chosen: 56 117
174 people, chosen: 71 103
175 people, chosen: 86 89
176 people, chosen: 101 75
177 people, chosen: 116 61
178 people, chosen: 131 47
179 people, chosen: 146 33
180 people, chosen: 161 19
181 people, chosen: 176 5
182 people, chosen: 9 173
183 people, chosen: 24 159
184 people, chosen: 39 145
185 people, chosen: 54 131
186 people, chosen: 69 117
187 people, chosen: 84 103
188 people, chosen: 99 89
189 people, chosen: 114 75
190 people, chosen: 129 61
191 people, chosen: 144 47
192 people, chosen: 159 33
193 people, chosen: 174 19
194 people, chosen: 189 5
195 people, chosen: 9 186
196 people, chosen: 24 172
197 people, chosen: 39 158
198 people, chosen: 54 144
199 people, chosen: 69 130
200 people, chosen: 84 116
201 people, chosen: 99 102
202 people, chosen: 114 88
203 people, chosen: 129 74
204 people, chosen: 144 60
205 people, chosen: 159 46
206 people, chosen: 174 32
207 people, chosen: 189 18
208 people, chosen: 204 4
209 people, chosen: 10 199
210 people, chosen: 25 185
211 people, chosen: 40 171
212 people, chosen: 55 157
213 people, chosen: 70 143
214 people, chosen: 85 129
215 people, chosen: 100 115
216 people, chosen: 115 101
217 people, chosen: 130 87
218 people, chosen: 145 73
219 people, chosen: 160 59
220 people, chosen: 175 45
221 people, chosen: 190 31
222 people, chosen: 205 17
223 people, chosen: 220 3
224 people, chosen: 11 213
225 people, chosen: 26 199
226 people, chosen: 41 185
227 people, chosen: 56 171
228 people, chosen: 71 157
229 people, chosen: 86 143
230 people, chosen: 101 129
231 people, chosen: 116 115
232 people, chosen: 131 101
233 people, chosen: 146 87
234 people, chosen: 161 73
235 people, chosen: 176 59
236 people, chosen: 191 45
237 people, chosen: 206 31
238 people, chosen: 221 17
239 people, chosen: 236 3
240 people, chosen: 11 229
241 people, chosen: 26 215
242 people, chosen: 41 201
243 people, chosen: 56 187
244 people, chosen: 71 173
245 people, chosen: 86 159
246 people, chosen: 101 145
247 people, chosen: 116 131
248 people, chosen: 131 117
249 people, chosen: 146 103
250 people, chosen: 161 89
251 people, chosen: 176 75
252 people, chosen: 191 61
253 people, chosen: 206 47
254 people, chosen: 221 33
255 people, chosen: 236 19
256 people, chosen: 251 5
257 people, chosen: 9 248
258 people, chosen: 24 234
259 people, chosen: 39 220
260 people, chosen: 54 206
261 people, chosen: 69 192
262 people, chosen: 84 178
263 people, chosen: 99 164
264 people, chosen: 114 150
265 people, chosen: 129 136
266 people, chosen: 144 122
267 people, chosen: 159 108
268 people, chosen: 174 94
269 people, chosen: 189 80
270 people, chosen: 204 66
271 people, chosen: 219 52
272 people, chosen: 234 38
273 people, chosen: 249 24
274 people, chosen: 264 10
275 people, chosen: 4 271
276 people, chosen: 19 257
277 people, chosen: 34 243
278 people, chosen: 49 229
279 people, chosen: 64 215
280 people, chosen: 79 201
281 people, chosen: 94 187
282 people, chosen: 109 173
283 people, chosen: 124 159
284 people, chosen: 139 145
285 people, chosen: 154 131
286 people, chosen: 169 117
287 people, chosen: 184 103
288 people, chosen: 199 89
289 people, chosen: 214 75
290 people, chosen: 229 61
291 people, chosen: 244 47
292 people, chosen: 259 33
293 people, chosen: 274 19
294 people, chosen: 289 5
295 people, chosen: 9 286
296 people, chosen: 24 272
297 people, chosen: 39 258
298 people, chosen: 54 244
299 people, chosen: 69 230
300 people, chosen: 84 216
301 people, chosen: 99 202
302 people, chosen: 114 188
303 people, chosen: 129 174
304 people, chosen: 144 160
305 people, chosen: 159 146
306 people, chosen: 174 132
307 people, chosen: 189 118
308 people, chosen: 204 104
309 people, chosen: 219 90
310 people, chosen: 234 76
311 people, chosen: 249 62
312 people, chosen: 264 48
313 people, chosen: 279 34
314 people, chosen: 294 20
315 people, chosen: 309 6
316 people, chosen: 8 308
317 people, chosen: 23 294
318 people, chosen: 38 280
319 people, chosen: 53 266
320 people, chosen: 68 252
321 people, chosen: 83 238
322 people, chosen: 98 224
323 people, chosen: 113 210
324 people, chosen: 128 196
325 people, chosen: 143 182
326 people, chosen: 158 168
327 people, chosen: 173 154
328 people, chosen: 188 140
329 people, chosen: 203 126
330 people, chosen: 218 112
331 people, chosen: 233 98
332 people, chosen: 248 84
333 people, chosen: 263 70
334 people, chosen: 278 56
335 people, chosen: 293 42
336 people, chosen: 308 28
337 people, chosen: 323 14
338 people, chosen: 0 0
339 people, chosen: 15 324
340 people, chosen: 30 310
341 people, chosen: 45 296
342 people, chosen: 60 282
343 people, chosen: 75 268
344 people, chosen: 90 254
345 people, chosen: 105 240
346 people, chosen: 120 226
347 people, chosen: 135 212
348 people, chosen: 150 198
349 people, chosen: 165 184
350 people, chosen: 180 170
351 people, chosen: 195 156
352 people, chosen: 210 142
353 people, chosen: 225 128
354 people, chosen: 240 114
355 people, chosen: 255 100
356 people, chosen: 270 86
357 people, chosen: 285 72
358 people, chosen: 300 58
359 people, chosen: 315 44
360 people, chosen: 330 30
361 people, chosen: 345 16
362 people, chosen: 360 2
363 people, chosen: 12 351
364 people, chosen: 27 337
365 people, chosen: 42 323
366 people, chosen: 57 309
367 people, chosen: 72 295
368 people, chosen: 87 281
369 people, chosen: 102 267
370 people, chosen: 117 253
371 people, chosen: 132 239
372 people, chosen: 147 225
373 people, chosen: 162 211
374 people, chosen: 177 197
375 people, chosen: 192 183
376 people, chosen: 207 169
377 people, chosen: 222 155
378 people, chosen: 237 141
379 people, chosen: 252 127
380 people, chosen: 267 113
381 people, chosen: 282 99
382 people, chosen: 297 85
383 people, chosen: 312 71
384 people, chosen: 327 57
385 people, chosen: 342 43
386 people, chosen: 357 29
36
Ok.. I finally got AC.. but that's after I found a swedish webpage with some hints... (and spending 2 hours trying to find a swedish to english translator).
Anyway, apparently if the position found is greater or equal to lower limit /2, then it should be rejected.. I have no idea why since the question does not mention it in any way. Anyone can shed some light?
Anyway, apparently if the position found is greater or equal to lower limit /2, then it should be rejected.. I have no idea why since the question does not mention it in any way. Anyone can shed some light?

 Experienced poster
 Posts: 169
 Joined: Wed Oct 31, 2001 2:00 am
 Location: Singapore
I have a feeling it has to do with the fact that you're in a circle... but I can't really pinpoint where.
Another question: for the second test case (61 386), I noticed that 36 is the one and ONLY possible position to stand in... which is what confuses me. Since you can count in 2 directions, shouldn't you have at least 2 safe places to stand in (one the opposite of the other)? Or is there something wrong with my logic?
Btw, your method for this problem is wonderful! Never thought such a recurrence exists.
Another question: for the second test case (61 386), I noticed that 36 is the one and ONLY possible position to stand in... which is what confuses me. Since you can count in 2 directions, shouldn't you have at least 2 safe places to stand in (one the opposite of the other)? Or is there something wrong with my logic?
Btw, your method for this problem is wonderful! Never thought such a recurrence exists.

 Experienced poster
 Posts: 169
 Joined: Wed Oct 31, 2001 2:00 am
 Location: Singapore
Ok so that's where the odd number comes in.
By the way I think I figured out why the answer must be less than half the lower bound. The question never numbered the positions, just that you have to find how many position away from Mxgobgwq. In short 1 can mean position 1 left or 1 right. Therefore, if you have a position more than half the lower bound it doesn't exist already... WA...
Hope this helps.
By the way I think I figured out why the answer must be less than half the lower bound. The question never numbered the positions, just that you have to find how many position away from Mxgobgwq. In short 1 can mean position 1 left or 1 right. Therefore, if you have a position more than half the lower bound it doesn't exist already... WA...
Hope this helps.

 Experienced poster
 Posts: 147
 Joined: Fri Jun 13, 2003 10:46 pm
Re: 180 Eeny Meeny.. WA??
How does the recursive relation F(n) = (15 + F(n1)) % njunbin wrote: let F(n) = person to be chosen as chief when there are n people to choose from
let G(n) = person to be chosen as chief when we count from the other direction
clearly F(n) depends on F(n1). so I generate a table starting from F(1) = 0 (means the starting person is chosen). The table is generated until F(1000000).
F(n) = (15 + F(n1)) % n
G(n) = (n  F(n)) % n
work?
Lets say that there are N people in the line and we want to remove every Kth one (in the problem K is always 15) until the last one, F(N), is left.
So to start with the line looks like:
1, 2, 3, 4, ... N
Ok, so take out the Kth one and it looks like this:
K+1, K+2, K+3,.... N, 1, 2, 3, ... K2, K1
Now the solution to this problem is F(N1). But notice that given F(N1) you can always find out what it's original position is.
So to start with the line looks like:
1, 2, 3, 4, ... N
Ok, so take out the Kth one and it looks like this:
K+1, K+2, K+3,.... N, 1, 2, 3, ... K2, K1
Now the solution to this problem is F(N1). But notice that given F(N1) you can always find out what it's original position is.
Yes, it is due to the fact that you're in a circle. Let me explain:junjieliang wrote:I have a feeling it has to do with the fact that you're in a circle... but I can't really pinpoint where.
Another question: for the second test case (61 386), I noticed that 36 is the one and ONLY possible position to stand in... which is what confuses me. Since you can count in 2 directions, shouldn't you have at least 2 safe places to stand in (one the opposite of the other)? Or is there something wrong with my logic?
Btw, your method for this problem is wonderful! Never thought such a recurrence exists.
Now, there are 2 possible directions you can count, clockwise or anticlockwise, now there are 2 positions closest to the person the count is started with, should these 2 positions be labelled as position 1, or for example, with 61 people, the 2 positions be labelled as position 1 and position 30 respectively? The question is not very clear on this. Anyway, since 36 > (floor(61/2) = 30) the equivalent position from the other direction of count would be 61  36 = 25. Think of it this way:
For 5 people,
Mxgobgwq
1 1
2 2
Get the idea?
I admit when it first came to me, I thought it a 'dumb' idea to consider the two situations counting from both directions.
However, when I think over it twice, I now agree with junbin's idea.
My reason is as follows:
The problem is to look for a safe place to stand in.
Let's still take the following example (61, 386)
If you count 35 people away from Mxgobgwq, and hold that place no. 36, whatever number of people (between 61 and 386) and whichever the direction the counting, you'll always be safe.
Some people may argue that when 36 is larger than half the number of people in the circle, then it makes no sense to count 36, coz you may as well count 25 (i.e. when there are 61 people). Then I would give the following two arguments:
1. You actually don't know exactly how many people are there. You only have a guessed range, you wouldn't be able to find the 'equivalent position (as in the above 25,36/61 case).
2. Now that the problem says you may count either way, then I should be able to count in either direction. Then you should not reject either one.
I believe the std answer given by the judge only includes lesserthanhalf positions, just for a save for calculation, and thought they would be completely equivalent anyway.
However, the above case proves it wrong. The FACT is indeed that if you stand on the 36th position from Mxgobgwq, then you needn't worry. And this is exactly what the problem is asking for a dangerfree position.
I think the approach to support rejection of these cases with grammatical analysis is not that applausible in that if we were really in a position like this, we would with no hesitation choose that place and save our lives rather than thinking whether the number makes sense.
Would love to hear anybody's opinions.
However, when I think over it twice, I now agree with junbin's idea.
My reason is as follows:
The problem is to look for a safe place to stand in.
Let's still take the following example (61, 386)
That should be adequate to prove the following fact:junbin wrote:The analysis of my program for data set 2 (61 386) is as follows:
First number is the number of people for the current case
second number is the person chosen to be chief if counting is done clockwise
third number is the person chosen to be chief if counting is done anticlockwise
So for the first line, it means that if there are 61 people in the circle, person 18 (17 positions away from the first) and person 45 (44 positions away from the first) will be chosen to be chief. Since in the range 61  386, only person 37 (36 positions away from the first) is not chosen, the answer my program outputs is 36. Which is, sadly, wrong. Can anyone explain to me their logic?
61 people, chosen: 17 44
62 people, chosen: 32 30
63 people, chosen: 47 16
64 people, chosen: 62 2
65 people, chosen: 12 53
66 people, chosen: 27 39
67 people, chosen: 42 25
68 people, chosen: 57 11
69 people, chosen: 3 66
70 people, chosen: 18 52
71 people, chosen: 33 38
72 people, chosen: 48 24
73 people, chosen: 63 10
74 people, chosen: 4 70
75 people, chosen: 19 56
76 people, chosen: 34 42
77 people, chosen: 49 28
78 people, chosen: 64 14
79 people, chosen: 0 0
80 people, chosen: 15 65
81 people, chosen: 30 51
82 people, chosen: 45 37
83 people, chosen: 60 23
84 people, chosen: 75 9
85 people, chosen: 5 80
86 people, chosen: 20 66
87 people, chosen: 35 52
88 people, chosen: 50 38
89 people, chosen: 65 24
90 people, chosen: 80 10
91 people, chosen: 4 87
92 people, chosen: 19 73
93 people, chosen: 34 59
94 people, chosen: 49 45
95 people, chosen: 64 31
96 people, chosen: 79 17
97 people, chosen: 94 3
98 people, chosen: 11 87
99 people, chosen: 26 73
100 people, chosen: 41 59
101 people, chosen: 56 45
102 people, chosen: 71 31
103 people, chosen: 86 17
104 people, chosen: 101 3
105 people, chosen: 11 94
106 people, chosen: 26 80
107 people, chosen: 41 66
108 people, chosen: 56 52
109 people, chosen: 71 38
110 people, chosen: 86 24
111 people, chosen: 101 10
112 people, chosen: 4 108
113 people, chosen: 19 94
114 people, chosen: 34 80
115 people, chosen: 49 66
116 people, chosen: 64 52
117 people, chosen: 79 38
118 people, chosen: 94 24
119 people, chosen: 109 10
120 people, chosen: 4 116
121 people, chosen: 19 102
122 people, chosen: 34 88
123 people, chosen: 49 74
124 people, chosen: 64 60
125 people, chosen: 79 46
126 people, chosen: 94 32
127 people, chosen: 109 18
128 people, chosen: 124 4
129 people, chosen: 10 119
130 people, chosen: 25 105
131 people, chosen: 40 91
132 people, chosen: 55 77
133 people, chosen: 70 63
134 people, chosen: 85 49
135 people, chosen: 100 35
136 people, chosen: 115 21
137 people, chosen: 130 7
138 people, chosen: 7 131
139 people, chosen: 22 117
140 people, chosen: 37 103
141 people, chosen: 52 89
142 people, chosen: 67 75
143 people, chosen: 82 61
144 people, chosen: 97 47
145 people, chosen: 112 33
146 people, chosen: 127 19
147 people, chosen: 142 5
148 people, chosen: 9 139
149 people, chosen: 24 125
150 people, chosen: 39 111
151 people, chosen: 54 97
152 people, chosen: 69 83
153 people, chosen: 84 69
154 people, chosen: 99 55
155 people, chosen: 114 41
156 people, chosen: 129 27
157 people, chosen: 144 13
158 people, chosen: 1 157
159 people, chosen: 16 143
160 people, chosen: 31 129
161 people, chosen: 46 115
162 people, chosen: 61 101
163 people, chosen: 76 87
164 people, chosen: 91 73
165 people, chosen: 106 59
166 people, chosen: 121 45
167 people, chosen: 136 31
168 people, chosen: 151 17
169 people, chosen: 166 3
170 people, chosen: 11 159
171 people, chosen: 26 145
172 people, chosen: 41 131
173 people, chosen: 56 117
174 people, chosen: 71 103
175 people, chosen: 86 89
176 people, chosen: 101 75
177 people, chosen: 116 61
178 people, chosen: 131 47
179 people, chosen: 146 33
180 people, chosen: 161 19
181 people, chosen: 176 5
182 people, chosen: 9 173
183 people, chosen: 24 159
184 people, chosen: 39 145
185 people, chosen: 54 131
186 people, chosen: 69 117
187 people, chosen: 84 103
188 people, chosen: 99 89
189 people, chosen: 114 75
190 people, chosen: 129 61
191 people, chosen: 144 47
192 people, chosen: 159 33
193 people, chosen: 174 19
194 people, chosen: 189 5
195 people, chosen: 9 186
196 people, chosen: 24 172
197 people, chosen: 39 158
198 people, chosen: 54 144
199 people, chosen: 69 130
200 people, chosen: 84 116
201 people, chosen: 99 102
202 people, chosen: 114 88
203 people, chosen: 129 74
204 people, chosen: 144 60
205 people, chosen: 159 46
206 people, chosen: 174 32
207 people, chosen: 189 18
208 people, chosen: 204 4
209 people, chosen: 10 199
210 people, chosen: 25 185
211 people, chosen: 40 171
212 people, chosen: 55 157
213 people, chosen: 70 143
214 people, chosen: 85 129
215 people, chosen: 100 115
216 people, chosen: 115 101
217 people, chosen: 130 87
218 people, chosen: 145 73
219 people, chosen: 160 59
220 people, chosen: 175 45
221 people, chosen: 190 31
222 people, chosen: 205 17
223 people, chosen: 220 3
224 people, chosen: 11 213
225 people, chosen: 26 199
226 people, chosen: 41 185
227 people, chosen: 56 171
228 people, chosen: 71 157
229 people, chosen: 86 143
230 people, chosen: 101 129
231 people, chosen: 116 115
232 people, chosen: 131 101
233 people, chosen: 146 87
234 people, chosen: 161 73
235 people, chosen: 176 59
236 people, chosen: 191 45
237 people, chosen: 206 31
238 people, chosen: 221 17
239 people, chosen: 236 3
240 people, chosen: 11 229
241 people, chosen: 26 215
242 people, chosen: 41 201
243 people, chosen: 56 187
244 people, chosen: 71 173
245 people, chosen: 86 159
246 people, chosen: 101 145
247 people, chosen: 116 131
248 people, chosen: 131 117
249 people, chosen: 146 103
250 people, chosen: 161 89
251 people, chosen: 176 75
252 people, chosen: 191 61
253 people, chosen: 206 47
254 people, chosen: 221 33
255 people, chosen: 236 19
256 people, chosen: 251 5
257 people, chosen: 9 248
258 people, chosen: 24 234
259 people, chosen: 39 220
260 people, chosen: 54 206
261 people, chosen: 69 192
262 people, chosen: 84 178
263 people, chosen: 99 164
264 people, chosen: 114 150
265 people, chosen: 129 136
266 people, chosen: 144 122
267 people, chosen: 159 108
268 people, chosen: 174 94
269 people, chosen: 189 80
270 people, chosen: 204 66
271 people, chosen: 219 52
272 people, chosen: 234 38
273 people, chosen: 249 24
274 people, chosen: 264 10
275 people, chosen: 4 271
276 people, chosen: 19 257
277 people, chosen: 34 243
278 people, chosen: 49 229
279 people, chosen: 64 215
280 people, chosen: 79 201
281 people, chosen: 94 187
282 people, chosen: 109 173
283 people, chosen: 124 159
284 people, chosen: 139 145
285 people, chosen: 154 131
286 people, chosen: 169 117
287 people, chosen: 184 103
288 people, chosen: 199 89
289 people, chosen: 214 75
290 people, chosen: 229 61
291 people, chosen: 244 47
292 people, chosen: 259 33
293 people, chosen: 274 19
294 people, chosen: 289 5
295 people, chosen: 9 286
296 people, chosen: 24 272
297 people, chosen: 39 258
298 people, chosen: 54 244
299 people, chosen: 69 230
300 people, chosen: 84 216
301 people, chosen: 99 202
302 people, chosen: 114 188
303 people, chosen: 129 174
304 people, chosen: 144 160
305 people, chosen: 159 146
306 people, chosen: 174 132
307 people, chosen: 189 118
308 people, chosen: 204 104
309 people, chosen: 219 90
310 people, chosen: 234 76
311 people, chosen: 249 62
312 people, chosen: 264 48
313 people, chosen: 279 34
314 people, chosen: 294 20
315 people, chosen: 309 6
316 people, chosen: 8 308
317 people, chosen: 23 294
318 people, chosen: 38 280
319 people, chosen: 53 266
320 people, chosen: 68 252
321 people, chosen: 83 238
322 people, chosen: 98 224
323 people, chosen: 113 210
324 people, chosen: 128 196
325 people, chosen: 143 182
326 people, chosen: 158 168
327 people, chosen: 173 154
328 people, chosen: 188 140
329 people, chosen: 203 126
330 people, chosen: 218 112
331 people, chosen: 233 98
332 people, chosen: 248 84
333 people, chosen: 263 70
334 people, chosen: 278 56
335 people, chosen: 293 42
336 people, chosen: 308 28
337 people, chosen: 323 14
338 people, chosen: 0 0
339 people, chosen: 15 324
340 people, chosen: 30 310
341 people, chosen: 45 296
342 people, chosen: 60 282
343 people, chosen: 75 268
344 people, chosen: 90 254
345 people, chosen: 105 240
346 people, chosen: 120 226
347 people, chosen: 135 212
348 people, chosen: 150 198
349 people, chosen: 165 184
350 people, chosen: 180 170
351 people, chosen: 195 156
352 people, chosen: 210 142
353 people, chosen: 225 128
354 people, chosen: 240 114
355 people, chosen: 255 100
356 people, chosen: 270 86
357 people, chosen: 285 72
358 people, chosen: 300 58
359 people, chosen: 315 44
360 people, chosen: 330 30
361 people, chosen: 345 16
362 people, chosen: 360 2
363 people, chosen: 12 351
364 people, chosen: 27 337
365 people, chosen: 42 323
366 people, chosen: 57 309
367 people, chosen: 72 295
368 people, chosen: 87 281
369 people, chosen: 102 267
370 people, chosen: 117 253
371 people, chosen: 132 239
372 people, chosen: 147 225
373 people, chosen: 162 211
374 people, chosen: 177 197
375 people, chosen: 192 183
376 people, chosen: 207 169
377 people, chosen: 222 155
378 people, chosen: 237 141
379 people, chosen: 252 127
380 people, chosen: 267 113
381 people, chosen: 282 99
382 people, chosen: 297 85
383 people, chosen: 312 71
384 people, chosen: 327 57
385 people, chosen: 342 43
386 people, chosen: 357 29
36
If you count 35 people away from Mxgobgwq, and hold that place no. 36, whatever number of people (between 61 and 386) and whichever the direction the counting, you'll always be safe.
Some people may argue that when 36 is larger than half the number of people in the circle, then it makes no sense to count 36, coz you may as well count 25 (i.e. when there are 61 people). Then I would give the following two arguments:
1. You actually don't know exactly how many people are there. You only have a guessed range, you wouldn't be able to find the 'equivalent position (as in the above 25,36/61 case).
2. Now that the problem says you may count either way, then I should be able to count in either direction. Then you should not reject either one.
I believe the std answer given by the judge only includes lesserthanhalf positions, just for a save for calculation, and thought they would be completely equivalent anyway.
However, the above case proves it wrong. The FACT is indeed that if you stand on the 36th position from Mxgobgwq, then you needn't worry. And this is exactly what the problem is asking for a dangerfree position.
I think the approach to support rejection of these cases with grammatical analysis is not that applausible in that if we were really in a position like this, we would with no hesitation choose that place and save our lives rather than thinking whether the number makes sense.
Would love to hear anybody's opinions.