2013
12-21

Eeny Meeny

In darkest <name of continent/island deleted to prevent offence> lived a tribe called the “Eeny Meenys”. They got this name from their way of choosing a chief for a year. It appears that a newspaper reporter visited the tribe and managed to get across a few ideas of civilisation, but apparently came to an unfortunate end before finishing the job. Thus the tribe no longer had a permanent chief; the chief’s term was exactly one year. At the end of that time, they ate the current chief, and chose another chief. Their method of choosing a chief was the “Eeny meeny miny mo” method. All eligible tribal members (women were also eligible–one of the blessings of civilisation the tribe had adopted) stood in a circle, a starting place was chosen, and the chief medicine man (who was ineligible for chieftainship) went around counting out E’, e’, n’, y’, M’, e’, e’, n’, y’, M’,i’, n’, y’, M’, o!’, E’, e’, n’, y’, M’, e’, e’, n’, y’, M’, i’, n’, y’, M’, o!’, …. At every o!’, the person indicated was pushed out of the circle which then closed up and the count restarted with his neighbour (the one who would have been E’ anyway). This process continued until only one was left–the new chief.

While the chance of glory for a year makes the job of chief highly attractive to tribal members, you (possessing a computer decades before they were invented) find the brevity of the glory unappealing. You have managed to find out that the count this year will start with Mxgobgwq (a very large person), so you would like to know where not to stand. You don’t know the direction, nor how many eligible people there are, but you can estimate the number (it is certainly less or equal than 1000000).

Write a program that will determine the first’ (i.e. closest to Mxgobgwq) safe position to stand, regardless of the actual number of people and the direction of count (clockwise or anti-clockwise).

Input will consist of a series of lines, each line containing the upper and lower estimates of the number of eligible people (both numbers inclusive). The file will be terminated by a line containing two zeroes (0 0).

Output will consist of a series of lines, one for each line of the input. Each line will consist of a single number giving the number of the position closest to Mxgobgwq that will not be chosen as chief for any number in the given range and for either direction of elimination. If no position is safe then print "Better estimate needed".

80 150
40 150
0 0

1
Better estimate needed

Time limit: 3.000 seconds

Problem问题

In darkest <name of continent/island deleted to prevent offence> lived a tribe called the “Eeny Meenys”. They got this name from their way of choosing a chief for a year. It appears that a newspaper reporter visited the tribe and managed to get across a few ideas of civilisation, but apparently came to an unfortunate end before finishing the job. Thus the tribe no longer had a permanent chief; the chief’s term was exactly one year. At the end of that time, they ate the current chief, and chose another chief. Their method of choosing a chief was the “Eeny meeny miny mo” method. All eligible tribal members (women were also eligible–one of the blessings of civilisation the tribe had adopted) stood in a circle, a starting place was chosen, and the chief medicine man (who was ineligible for chieftainship) went around counting out E’, e’, n’, y’, M’, e’, e’, n’, y’, M’,i’, n’, y’, M’, o!’, E’, e’, n’, y’, M’, e’, e’, n’, y’, M’, i’, n’, y’, M’, o!’, …. At every o!’, the person indicated was pushed out of the circle which then closed up and the count restarted with his neighbour (the one who would have been E’ anyway). This process continued until only one was left–the new chief.

While the chance of glory for a year makes the job of chief highly attractive to tribal members, you (possessing a computer decades before they were invented) find the brevity of the glory unappealing. You have managed to find out that the count this year will start with Mxgobgwq (a very large person), so you would like to know where not to stand. You don’t know the direction, nor how many eligible people there are, but you can estimate the number (it is certainly less or equal than 1000000).

Write a program that will determine the first’ (i.e. closest to Mxgobgwq) safe position to stand, regardless of the actual number of people and the direction of count (clockwise or anti-clockwise).

Input输入

Input will consist of a series of lines, each line containing the upper and lower estimates of the number of eligible people (both numbers inclusive). The file will be terminated by a line containing two zeroes (0 0).

Output输出

Output will consist of a series of lines, one for each line of the input. Each line will consist of a single number giving the number of the position closest to Mxgobgwq that will not be chosen as chief for any number in the given range and for either direction of elimination. If no position is safe then print “Better estimate needed”.

80 150
40 150
0 0

Analysis分析

Mxgobgwq就是开始计数的位置，我们定为0。由于计数的方向不定，对于某一个确定的候选人数，安全的位置只能以“离Mxgobgwq有多远”来表示。任何大于估计的最少人数一半的安全位置都是没有意义的。比如估计的最少人数是10，而算出的安全位置是8（从0开始编号），那么当实际的人数为10时，你的站位就变成了2（顺时针计数Mxgobgwq右边第8个即逆时针计数的左边第2个）。

Solution解答

#include <algorithm>
#include <iostream>
#include <vector>

typedef std::vector<int>::iterator VECINT_ITER;

int Josephus(int n, int k)
{
static std::vector<int> vecJosephus(1, 0);
if (n <= (int)vecJosephus.size())
return vecJosephus[n - 1];
int j = (Josephus(n - 1, k) + k) % n;
vecJosephus.push_back(j);
return j;
}

int main(void)
{
for (int i = 0; i < 100000; Josephus(++i, 15));
for (int nSizeMin, nSizeMax; std::cin >> nSizeMin >> nSizeMax;) {
if (nSizeMin > nSizeMax)
std::swap(nSizeMin, nSizeMax);
if (nSizeMin == 0 && nSizeMax == 0)
break;
std::vector<int> vecCover(nSizeMin / 2, 0);
for (int nSize = nSizeMin, nJump = 15; nSize <= nSizeMax; ++nSize) {
int j = Josephus(nSize, nJump);
if (j > nSize / 2)
j = nSize - j;
if (j < vecCover.size())
vecCover[j] = 1;
}
VECINT_ITER ir = std::find(vecCover.begin() + 1, vecCover.end(), 0);
if (ir == vecCover.end())
std::cout << "Better estimate needed" << std::endl;
else
std::cout << ir - vecCover.begin() << std::endl;
}
return 0;
}

1. Good task for the group. Hold it up for every yeara??s winner. This is a excellent oppotunity for a lot more enhancement. Indeed, obtaining far better and much better is constantly the crucial. Just like my pal suggests on the truth about ab muscles, he just keeps obtaining much better.