## 180 - Eeny Meeny

All about problems in Volume 1. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Jorge Pinto
New poster
Posts: 11
Joined: Wed Jan 09, 2002 2:00 am
Location: Portugal
simple problem, don't know what's wrong
i'm just checking the solutions to the lower value because if i check to the higher value, i can't get the "Better estimate needed" with my solution.
anyway.. just need the results for these input cases

thank you in advance

130 500
200 500
11 38
26 34
10 30
80 150
40 150
0 0

Ivan Golubev
Experienced poster
Posts: 167
Joined: Fri Oct 19, 2001 2:00 am
Location: Saint Petersburg, Russia
Output:

65
7
5
2
4
1
Better estimate needed

Jorge Pinto
New poster
Posts: 11
Joined: Wed Jan 09, 2002 2:00 am
Location: Portugal
my output is equal...
any tricks?
really don't know

thanks Ivan

wyvmak
Experienced poster
Posts: 110
Joined: Thu Dec 13, 2001 2:00 am
the following are the number of people, and the position to be selected as chef in clockwise and counter-clockwise direction:

99: 26 73
100: 41 59
101: 56 45
102: 71 31
103: 86 17
104: 101 3
105: 11 94
106: 26 80
107: 41 66
108: 56 52
109: 71 38
110: 86 24
111: 101 10
112: 4 108
113: 19 94
114: 34 80
115: 49 66
116: 64 52
117: 79 38
118: 94 24
119: 109 10
120: 4 116
121: 19 102
122: 34 88
123: 49 74
124: 64 60
125: 79 46
126: 94 32
127: 109 18
128: 124 4
129: 10 119

if input is "99 499" and the above are correct,
it should be "65", right?

Jorge Pinto
New poster
Posts: 11
Joined: Wed Jan 09, 2002 2:00 am
Location: Portugal
well, every value you have in your post, is an exact match with my solution.. so it gives me 65 too, and the chief's give equal to me.

i still don't know what's wrong, it must be a small particular case..

paulhryu
New poster
Posts: 45
Joined: Sat Jan 26, 2002 2:00 am
Contact:
Anybody can look at this please and tell me which ones are wrong? I'm sure that it's some wierd values that throw it off... I got W.A., that's why... like Jorge Pinto before me, all the test cases I devised work...

1: 0 0
2: 1 1
3: 1 2
4: 0 0
5: 0 0
6: 3 3
7: 4 3
8: 3 5
9: 0 0
10: 5 5
11: 9 2
12: 0 0
13: 2 11
14: 3 11
15: 3 12
16: 2 14
17: 0 0
18: 15 3
19: 11 8
20: 6 14
21: 0 0
22: 15 7
23: 7 16
24: 22 2
25: 12 13
26: 1 25
27: 16 11
28: 3 25
29: 18 11
30: 3 27
31: 18 13
32: 1 31
33: 16 17
34: 31 3
35: 11 24
36: 26 10
37: 4 33
38: 19 19
39: 34 5
40: 9 31
41: 24 17
42: 39 3
43: 11 32
44: 26 18
45: 41 4
46: 10 36
47: 25 22
48: 40 8
49: 6 43
50: 21 29
51: 36 15
52: 51 1
53: 13 40
54: 28 26
55: 43 12
56: 2 54
57: 17 40
58: 32 26
59: 47 12
60: 2 58
61: 17 44
62: 32 30
63: 47 16
64: 62 2
65: 12 53
66: 27 39
67: 42 25
68: 57 11
69: 3 66
70: 18 52
71: 33 38
72: 48 24
73: 63 10
74: 4 70
75: 19 56
76: 34 42
77: 49 28
78: 64 14
79: 0 0
80: 15 65
81: 30 51
82: 45 37
83: 60 23
84: 75 9
85: 5 80
86: 20 66
87: 35 52
88: 50 38
89: 65 24
90: 80 10
91: 4 87
92: 19 73
93: 34 59
94: 49 45
95: 64 31
96: 79 17
97: 94 3
98: 11 87
99: 26 73
100: 41 59
101: 56 45
102: 71 31
103: 86 17
104: 101 3
105: 11 94
106: 26 80
107: 41 66
108: 56 52
109: 71 38
110: 86 24
111: 101 10
112: 4 108
113: 19 94
114: 34 80
115: 49 66
116: 64 52
117: 79 38
118: 94 24
119: 109 10
120: 4 116
121: 19 102
122: 34 88
123: 49 74
124: 64 60
125: 79 46
126: 94 32
127: 109 18
128: 124 4
129: 10 119
130: 25 105
131: 40 91
132: 55 77
133: 70 63
134: 85 49
135: 100 35
136: 115 21
137: 130 7
138: 7 131
139: 22 117
140: 37 103
141: 52 89
142: 67 75
143: 82 61
144: 97 47
145: 112 33
146: 127 19
147: 142 5
148: 9 139
149: 24 125
150: 39 111
151: 54 97
152: 69 83
153: 84 69
154: 99 55
155: 114 41
156: 129 27
157: 144 13
158: 1 157
159: 16 143
160: 31 129
161: 46 115
162: 61 101
163: 76 87
164: 91 73
165: 106 59
166: 121 45
167: 136 31
168: 151 17
169: 166 3
170: 11 159
171: 26 145
172: 41 131
173: 56 117
174: 71 103
175: 86 89
176: 101 75
177: 116 61
178: 131 47
179: 146 33
180: 161 19
181: 176 5
182: 9 173
183: 24 159
184: 39 145
185: 54 131
186: 69 117
187: 84 103
188: 99 89
189: 114 75
190: 129 61
191: 144 47
192: 159 33
193: 174 19
194: 189 5
195: 9 186
196: 24 172
197: 39 158
198: 54 144
199: 69 130
200: 84 116
201: 99 102
202: 114 88
203: 129 74
204: 144 60
205: 159 46
206: 174 32
207: 189 18
208: 204 4
209: 10 199
210: 25 185
211: 40 171
212: 55 157
213: 70 143
214: 85 129
215: 100 115
216: 115 101
217: 130 87
218: 145 73
219: 160 59
220: 175 45
221: 190 31
222: 205 17
223: 220 3
224: 11 213
225: 26 199
226: 41 185
227: 56 171
228: 71 157
229: 86 143
230: 101 129
231: 116 115
232: 131 101
233: 146 87
234: 161 73
235: 176 59
236: 191 45
237: 206 31
238: 221 17
239: 236 3
240: 11 229
241: 26 215
242: 41 201
243: 56 187
244: 71 173
245: 86 159
246: 101 145
247: 116 131
248: 131 117
249: 146 103
250: 161 89
251: 176 75
252: 191 61
253: 206 47
254: 221 33
255: 236 19
256: 251 5
257: 9 248
258: 24 234
259: 39 220
260: 54 206
261: 69 192
262: 84 178
263: 99 164
264: 114 150
265: 129 136
266: 144 122
267: 159 108
268: 174 94
269: 189 80
270: 204 66
271: 219 52
272: 234 38
273: 249 24
274: 264 10
275: 4 271
276: 19 257
277: 34 243
278: 49 229
279: 64 215
280: 79 201
281: 94 187
282: 109 173
283: 124 159
284: 139 145
285: 154 131
286: 169 117
287: 184 103
288: 199 89
289: 214 75
290: 229 61
291: 244 47
292: 259 33
293: 274 19
294: 289 5
295: 9 286
296: 24 272
297: 39 258
298: 54 244
299: 69 230
300: 84 216
301: 99 202
302: 114 188
303: 129 174
304: 144 160
305: 159 146
306: 174 132
307: 189 118
308: 204 104
309: 219 90
310: 234 76
311: 249 62
312: 264 48
313: 279 34
314: 294 20
315: 309 6
316: 8 308
317: 23 294
318: 38 280
319: 53 266
320: 68 252
321: 83 238
322: 98 224
323: 113 210
324: 128 196
325: 143 182
326: 158 168
327: 173 154
328: 188 140
329: 203 126
330: 218 112
331: 233 98
332: 248 84
333: 263 70
334: 278 56
335: 293 42
336: 308 28
337: 323 14
338: 0 0
339: 15 324
340: 30 310
341: 45 296
342: 60 282
343: 75 268
344: 90 254
345: 105 240
346: 120 226
347: 135 212
348: 150 198
349: 165 184
350: 180 170
351: 195 156
352: 210 142
353: 225 128
354: 240 114
355: 255 100
356: 270 86
357: 285 72
358: 300 58
359: 315 44
360: 330 30
361: 345 16
362: 360 2
363: 12 351
364: 27 337
365: 42 323
366: 57 309
367: 72 295
368: 87 281
369: 102 267
370: 117 253
371: 132 239
372: 147 225
373: 162 211
374: 177 197
375: 192 183
376: 207 169
377: 222 155
378: 237 141
379: 252 127
380: 267 113
381: 282 99
382: 297 85
383: 312 71
384: 327 57
385: 342 43
386: 357 29
387: 372 15
388: 387 1
389: 13 376
390: 28 362
391: 43 348
392: 58 334
393: 73 320
394: 88 306
395: 103 292
396: 118 278
397: 133 264
398: 148 250
399: 163 236
400: 178 222
401: 193 208
402: 208 194
403: 223 180
404: 238 166
405: 253 152
406: 268 138
407: 283 124
408: 298 110
409: 313 96
410: 328 82
411: 343 68
412: 358 54
413: 373 40
414: 388 26
415: 403 12
416: 2 414
417: 17 400
418: 32 386
419: 47 372
420: 62 358
421: 77 344
422: 92 330
423: 107 316
424: 122 302
425: 137 288
426: 152 274
427: 167 260
428: 182 246
429: 197 232
430: 212 218
431: 227 204
432: 242 190
433: 257 176
434: 272 162
435: 287 148
436: 302 134
437: 317 120
438: 332 106
439: 347 92
440: 362 78
441: 377 64
442: 392 50
443: 407 36
444: 422 22
445: 437 8
446: 6 440
447: 21 426
448: 36 412
449: 51 398
450: 66 384
451: 81 370
452: 96 356
453: 111 342
454: 126 328
455: 141 314
456: 156 300
457: 171 286
458: 186 272
459: 201 258
460: 216 244
461: 231 230
462: 246 216
463: 261 202
464: 276 188
465: 291 174
466: 306 160
467: 321 146
468: 336 132
469: 351 118
470: 366 104
471: 381 90
472: 396 76
473: 411 62
474: 426 48
475: 441 34
476: 456 20
477: 471 6
478: 8 470
479: 23 456
480: 38 442
481: 53 428
482: 68 414
483: 83 400
484: 98 386
485: 113 372
486: 128 358
487: 143 344
488: 158 330
489: 173 316
490: 188 302
491: 203 288
492: 218 274
493: 233 260
494: 248 246
495: 263 232
496: 278 218
497: 293 204
498: 308 190
499: 323 176
500: 338 162

Jorge Pinto
New poster
Posts: 11
Joined: Wed Jan 09, 2002 2:00 am
Location: Portugal
made myoutput from 1 to 500 just like you

this is the result of "diff myout yourout"

so you see:
(line)c(col)
myout
---
yourout

1c1
< 1: 0 1
---
> 1: 0 0

4,5c4,5
< 4: 0 4
< 5: 0 5
---
> 4: 0 0
> 5: 0 0

9c9
< 9: 0 9
---
> 9: 0 0

12c12
< 12: 0 12
---
> 12: 0 0

17c17
< 17: 0 17
---
> 17: 0 0

21c21
< 21: 0 21
---
> 21: 0 0

79c79
< 79: 0 79
---
> 79: 0 0

338c338
< 338: 0 338
---
> 338: 0 0

there are quite some diferences

anyway.. still w.a. here

Ivan Golubev
Experienced poster
Posts: 167
Joined: Fri Oct 19, 2001 2:00 am
Location: Saint Petersburg, Russia
Jorge, if you want, send your source code to me: ivan(at)golubev.com. I'll try to check what's wrong with it.

wyvmak
Experienced poster
Posts: 110
Joined: Thu Dec 13, 2001 2:00 am
well, my first thought is, at least,
338: 0 338
but only 338 people, if start from 0, it shouldn't be a position as 338. right?

Jorge Pinto
New poster
Posts: 11
Joined: Wed Jan 09, 2002 2:00 am
Location: Portugal
Oops, a missplaced printf was giving that output, but my final answer wasn't being afected.

made new ouput, this time, complety equal to paulhryu.

I'm sending in the code Ivan, thanks..

(it must be really just 1 case)

Ivan Golubev
Experienced poster
Posts: 167
Joined: Fri Oct 19, 2001 2:00 am
Location: Saint Petersburg, Russia
Input:
12 39
13 39
14 39
15 39
16 39
17 39
18 39
21 49
22 49
23 49
0 0

Correct output:
Better estimate needed
Better estimate needed
Better estimate needed
Better estimate needed
Better estimate needed
Better estimate needed
9
Better estimate needed
Better estimate needed
Better estimate needed

Tip: search answer in range [1, (low limit) / 2] only.

Jorge Pinto
New poster
Posts: 11
Joined: Wed Jan 09, 2002 2:00 am
Location: Portugal
Accepted,

Yeap, <=(min/2)

the tricky part was that - the problem doesn't give a clue about it, but it makes sense.

Thanks Ivan

paulhryu
New poster
Posts: 45
Joined: Sat Jan 26, 2002 2:00 am
Contact:
Jesus Christ?!? That's it?!? And I thought something was wrong with my darned function... Good problem though.

dh3014
New poster
Posts: 24
Joined: Tue Mar 26, 2002 2:00 am
Location: Taiwan
Contact:
I got several WA and don't what's the problem is...can anyone provides some test data or help testing my program?
Thanks your reading anyway.
-----------------------------

#include <stdio.h>
#include <string.h>

#define MAXTABLE 501

#define MOVELENGTH 15

typedef struct People People;

struct People {
int next, last;
};

int chief[MAXTABLE][2];

void makeTable (void);

int main (void) {
int down, up;
register int i;
char table[MAXTABLE], flag;

makeTable ();

while (scanf ("%d %d", &down, &up) && (up || down)) {
memset (table, 0, sizeof (table));
if (down > up)
down ^= up ^= down ^= up;
for (i = down; i <= up; ++i)
table[chief[0]] = 1;
for (flag = 0, i = 1; !flag && i <= down; ++i)
if (!table)
flag = 1;
if (flag && (down == 1 || i <= down / 2))
printf ("%dn", i - 1);
else
puts ("Better estimate needed");
}

return 0;
}

void makeTable (void) {
People eligible[MAXTABLE];
register int i, j, k;
int numOfPeople, nowUser;

for (i = 1; i < MAXTABLE; ++i) {

for (j = 0; j < i; ++j) {
eligible[j].next = j + 1;
eligible[j].last = j - 1;
}
eligible[0].last = i - 1;
eligible.next = 0;

numOfPeople = i;
nowUser = 0;

k = MOVELENGTH;

while (numOfPeople) {
for (j = 0; j < k; ++j)
nowUser = eligible[nowUser].next;
eligible[eligible[nowUser].next].last = eligible[nowUser].last;
eligible[eligible[nowUser].last].next = eligible[nowUser].next;
--numOfPeople;
}
chief[0] = nowUser;
chief[1] = chief[0] ? i - chief[0] : 0;
#ifdef DEBUG
printf ("In Table %d, dangerous position is %d and %dn", i, chief[0], chief[1]);
scanf ("%*c");
#endif
}

return ;
}

rgrig
New poster
Posts: 3
Joined: Fri Jul 05, 2002 8:51 pm

### another question: I receive NO reply whatsoever. Why?

This is my email (ofcourse, w/o BBCode formatting):

@begin_of_source_code
[cpp]// @JUDGE_ID: <my_correct_ID> 180 C++
#include <iostream>
#include <string>
//#include "profile.h"
using namespace std;
const long MAX_PERS = 1000000;
const long EENY_MEENY = 15 - 1;
//const string InitVectorDescr("InitVector");
//const string InitLinkedListDescr("InitLinkedList");
//const string ExcludeNextDescr("ExcludeNext");
//const string MakeBadPosDescr("MakeBadPos");
//const string WriteResultDescr("WriteResult");
//const string NextGoodPosDescr("NextGoodPos");
//RG::Profiler prof;
struct node_t
{
node_t* prev;
node_t* next;
};
bool goodPos[MAX_PERS]; // records the results of countings
node_t chief[MAX_PERS]; // used for each counting
node_t* chiefHead;

// Fills the first sizeOne positions with true
// and the last positions (until MAX_PERS-1)
// with false
void InitVector(bool v[], long sizeOne = MAX_PERS)
{
//prof.Start(InitVectorDescr);
long i;
for (i = 0; i < sizeOne; ++i)
v = true;
for (i = sizeOne; i < MAX_PERS; ++i)
v = false;
//prof.Stop(InitVectorDescr);
}

// Initializes the first size locations of chief
// to contain pointers of a circulary double-linked
// list.
void InitLinkedList(long size)
{
//prof.Start(InitLinkedListDescr);
long i;
chief[0].prev = chief + size - 1;
chief[0].next = chief + 1;
for (i = 1; i < size-1; ++i)
{
chief.prev = chief + i - 1;
chief.next = chief + i + 1;
}
chief[size-1].prev = chief + size - 2;
chief[size-1].next = chief;
//prof.Stop(InitLinkedListDescr);
}

// Count EENY_MEENY true positions in chief (modulo MAX_PERS),
// eliminate from list the reached position and makes start
// point to the next position
void ExcludeNext(node_t*& start)
{
//prof.Start(ExcludeNextDescr);
long i;
for (i = 0; i < EENY_MEENY; ++i)
start = start->next;
// eliminate from list
start->prev->next = start->next;
start->next->prev = start->prev;
start = start->next;
//prof.Stop(ExcludeNextDescr);
}

// Marks positions chiefIdx and (size-chiefIdx) in
// goodPos as false.
void MakeBadPos(long chiefIdx, long size, bool goodPos[])
{
//prof.Start(MakeBadPosDescr);
goodPos[chiefIdx] = false;
goodPos[size-chiefIdx] = false;
//prof.Stop(MakeBadPosDescr);
}

// Writes where the first true can be found starting
// from 1 position and looking up to and including floor(minPers/2).
// If there is no true in this range then print "Better estimate needed".
void WriteResult(bool goodPos[], long minPers)
{
//prof.Start(WriteResultDescr);
long i;
minPers /= 2;
for (i = 1; i <= minPers; ++i)
{
if (goodPos)
{
cout << i << endl;
return;
}
}
cout << "Better estimate needed" << endl;
//prof.Stop(WriteResultDescr);
}
// Updates goodPosIdx to point to the
// first true component of goodPos
void NextGoodPos(long& goodPosIdx, bool goodPos[])
{
//prof.Start(NextGoodPosDescr);
while (!goodPos[goodPosIdx])
{
if (++goodPosIdx == MAX_PERS)
break;
}
//prof.Stop(NextGoodPosDescr);
}

int main()
{
long chiefIdx;
long goodPosIdx = 1;
node_t* excluded; // last excluded = after him we start counting
long minPers, maxPers;
long i, j;
while (1)
{
// TODO: what if minPers is really small (like 0 or 1) ?
cin >> minPers >> maxPers;
if ((minPers == 0) && (maxPers == 0))
{
//prof.Dump(cout);
return 0;
}
InitVector(goodPos);
for (i = minPers; i <= maxPers; ++i)
{
InitLinkedList(i);
excluded = chief;
for (j = 1; j < i; ++j)
ExcludeNext(excluded);
// Now excluded points to the only item left in the list
// so we compute it's position and get the chiefIdx
chiefIdx = excluded - chief;
MakeBadPos(chiefIdx, i, goodPos);
if (chiefIdx == goodPosIdx)
NextGoodPos(goodPosIdx, goodPos);
if (goodPosIdx > minPers/2)
break;
}
WriteResult(goodPos, minPers);
}
}[/cpp]
@end_of_source_code