Here are both Lithorian's and JaWiB's code, included together since they essentially used the exact same algorithm.
JaWib:
Code:
class JaWiB
{
public:
std::string originalNecklace(int numwhite, int numgold, int k)
{
int total=numwhite+numgold;
std::string ret;
ret.reserve(total); //reserve space for string
ret.assign(total,'w'); //fill string with w's
int h=1; //used to see if gold pearl needs to be added
for (int i=0,j=0;i<numgold;h++)
{
if (ret[j]=='g') //hit a gold pearl
{
--h;
if (++j==total) //skip this pearl
j=0;
continue;
}
if(h%k) //add a gold every k times; this is not a k time...
{
ret[j]='w';
}
else
{
ret[j]='g';
++i; //increment gold pearl counter
}
if (++j==total) //move on to next pearl, is it highest index?
j=0; //if so, go back to first pearl
}
return ret;
}
};
Lithorien:
Code:
class Lithorien
{
public:
std::string originalNecklace(int numWhite, int numGold, int k)
{
char *tArry = new char[numWhite + numGold]; // Dynamically allocate the char array.
// Initalize every array element to NULL.
for (int q = 0; q <= (numWhite + numGold); q++)
{
tArry[q] = '\0';
}
// Algorithm.
int x = 1, z = 0; // Counter for the inner for() loop, 'g' counter.
if (numGold > 0)
{
while (z < numGold) // While there aren't enough 'g's..
{
for (int y = 0; y < (numWhite + numGold); y++) // Go through the array..
{
if ((x == k) && (tArry[y] != 'g') && (z < numGold)) // If x is the next k, and the array ISN'T on a 'g' already..
{
tArry[y] = 'g'; // Make the array element g.
x = 1; // Make our 'counter' move back to 1.
z++; // Increment our 'g' counter.
}
else if (tArry[y] != 'g') // Assume w if not on a 'g' currently.
{
tArry[y] = 'w';
x++; // Increment our x.
}
// If the counter is on a g already, there's no need to do anything. So we skip it, and we don't update x. This lets us keep a constant 'k' without having to shift arrays.
}
}
}
else // If all whites are inputted, we need to handle that. Otherwise the program'd hang.
{
for (int r = 0; r < numWhite; r++)
{
tArry[r] = 'w';
}
}
// Return a string.
std::string s(tArry); // Make our string the char array. This is why we initalized to NULL - It ensures that this string will be null terminated. If we didn't, originalNecklace(9, 13, 11) would output garbage characters.
return(s);
}
};
Both produced correct results for every test case and more or less used the same algorithm I described above with only minor modifications. Both I give 10 points for correct solution, and + 2 snazzy points for nice concise algorithm. This was a tough call, but if we need a winner I'll award an extra .5 points to JaWib since his algorithm automatically handles the special case where there are no gold pearls.
Originally Posted by jverkoey
The font size is no different than normal for me... I'll take the size tags off of the problem header and see if that helps. Let me know.
I took on this contest because my work wasn't giving me anything to code and I had lots of extra time, then mid march they suddenly slapped a huge project on me thats taken up all of my free time. But I am finishing with that today so tomorrow night I can guarantee I can finish this contest. Thanks for your patience!
