
Originally Posted by
Echo_
This doesn't look too hard, but I agree that the other rounds must be crazy. Here's how you get the next value:
java Code:
public static int nextValue(final int[] m) {
int min = m[0];
for (int i = 1; i < m.length; i++)
if (m[i] < min)
min = m[i];
int value = min + 1;
for (int i = 0; i < m.length; i++)
if (m[i] == value) {
value++;
i = -1;
continue;
}
return value;
}
I may do the rest later just for shits and giggles, I'm not really interested in participating.
I'm not so sure that is correct for Question 3 .. It is only supposed to find the min in the last K elements of M array. Not the whole thing 
GetKnownValues gets all the value in the array M.
Process is supposed to return value M[N - 1]. Only works for Case 1 of Questions 3. GetKnownValues is correct though.. Processing is wrong I think.
C++ Code:
#include <iostream>
#include <fstream>
#include <vector>
#include <sstream>
#include <algorithm>
#include <stdexcept>
template<typename T>
std::string ToString(T Type)
{
std::stringstream SS;
SS<<Type;
return SS.str();
}
template <typename T>
T ToNumber(const std::string &Text)
{
std::istringstream SS(Text);
T Result;
return (SS >> Result ? Result : 0);
}
std::ostream& operator << (std::ostream& Str, const std::vector<int>& IA)
{
if (!IA.empty())
{
Str<<"[";
for (std::size_t I = 0; I < IA.size() - 1; ++I)
{
Str<<IA[I]<<", ";
}
Str<<IA[IA.size() - 1]<<"]";
}
else
{
Str<<"[]";
}
return Str;
}
std::vector<std::string> ReadFileEx(const std::string& FileName, bool BinaryMode)
{
std::string Line;
std::vector<std::string> Result;
std::_Ios_Openmode OpenMode;
if (BinaryMode)
OpenMode = std::ios::in | std::ios::binary;
else
OpenMode = std::ios::in;
std::ifstream File(FileName.c_str(), OpenMode);
if (File.is_open())
{
while (std::getline(File, Line))
{
Result.push_back(Line);
}
File.close();
}
return Result;
}
std::vector<std::string> SplitString(std::string StringToSplit, std::string Delimiter)
{
std::vector<std::string> Result;
std::size_t Pos = StringToSplit.find_first_of(Delimiter);
while(Pos != std::string::npos)
{
if(Pos > 0)
{
Result.push_back(StringToSplit.substr(0, Pos));
}
StringToSplit = StringToSplit.substr(Pos + 1);
Pos = StringToSplit.find_first_of(Delimiter);
}
if(StringToSplit.length() > 0)
{
Result.push_back(StringToSplit);
}
return Result;
}
std::vector<int> StringsToIntegers(std::vector<std::string> Strings)
{
std::vector<int> Result;
for (unsigned I = 0; I < Strings.size(); ++I)
{
Result.push_back(ToNumber<int>(Strings[I]));
}
return Result;
}
std::vector<int> GetKnownValues(std::vector<int> Numbers, std::vector<int> GeneratedNumbers, int &N, int &K)
{
N = Numbers[0];
K = Numbers[1];
std::vector<int> M(1);
int A = GeneratedNumbers[0];
int B = GeneratedNumbers[1];
int C = GeneratedNumbers[2];
int R = GeneratedNumbers[3];
M[0] = A;
for (unsigned I = 1; I < K; ++I)
{
M.push_back((B * M[I - 1] + C) % R);
}
return M;
}
int Process(std::vector<int> KnownValues, int N, int K)
{
int MinValue = *std::min_element(KnownValues.end() - K, KnownValues.end());
for (int I = 0; I < K; ++I)
{
if (std::find(KnownValues.end() - K, KnownValues.end(), ++MinValue) == KnownValues.end())
{
break;
}
}
if (KnownValues.size() < N)
{
KnownValues.push_back(MinValue);
Process(KnownValues, N, K);
}
return KnownValues[N - 1];
}
int main()
{
std::stringstream Output;
std::vector<std::string> Lines = ReadFileEx("TestInput.txt", false);
int LineCount = ToNumber<int>(Lines[0]);
if (LineCount < 1 || LineCount > 50)
throw std::invalid_argument("ERROR! Invalid contraint. Required: 1 <= T <= 50. Got: " + Lines[0]);
int N = 0, K = 0;
for (int I = 1, J = 1; I < LineCount * 2; I += 2, ++J)
{
std::vector<int> Known = GetKnownValues(StringsToIntegers(SplitString(Lines[I], " ")), StringsToIntegers(SplitString(Lines[I + 1], " ")), N, K);
std::cout<<"Case #"<<J<<": "<<Process(Known, N, K)<<"\n\n";
}
return 0;
}