Skip to content

Instantly share code, notes, and snippets.

@mattsan mattsan/file0.cpp
Created Mar 19, 2013

Embed
What would you like to do?
第8回オフラインリアルタイムどう書くの参考問題の回答例。C++で。その2 ref: http://qiita.com/items/1af0536fa20bc26ec0fb
#include <iostream>
#include <sstream>
#include <string>
static const std::string NIBBLES[] =
{
"0000", "1000", "0100", "1100", "0010", "1010", "0110", "1110",
"0001", "1001", "0101", "1101", "0011", "1011", "0111", "1111"
};
static const std::string HEXES = "0123456789abcdef";
static const int STATES[][2] =
{
{ 1, 5 }, { 6, 2 }, { 3, 11 }, { 16, 4 },
{ 17, 7 }, { 23, 8 }, { 13, 9 }, { 10, 20 },
{ 12, 26 }, { 14, 15 }, { 18, 19 }, { 21, 22 }, { 24, 25 }
};
static const int CHAR_CODE = 13;
static const int INVALID_CODE = 18;
static const int TERMINAL = 26;
char state2char(int state)
{
return "tsnid cloaerh"[state - CHAR_CODE];
}
std::string solve(const std::string& input)
{
std::string bits;
for(std::string::const_iterator i = input.begin(); i != input.end(); ++i)
{
bits += NIBBLES[HEXES.find(*i)];
}
std::string::size_type pos = 0;
std::string result;
int state = 0;
for(;;++pos)
{
if(bits.size() <= pos) { pos = std::string::npos; break; }
state = STATES[state][bits[pos] - '0'];
if(state == INVALID_CODE) { pos = std::string::npos; break; }
if(state == TERMINAL) { break; }
if(state >= CHAR_CODE) { result += state2char(state); state = 0; }
}
if(pos != std::string::npos)
{
std::ostringstream output;
output << result << ":" << (pos + 1);
return output.str();
}
else
{
return "*invalid*";
}
}
void test(const std::string& input, const std::string& expected)
{
std::string actual = solve(input);
std::cout << actual << " => " << (actual == expected ? std::string("o") : ("x:" + expected)) << "¥n";
}
int main(int, char* [])
{
/*0*/ test( "16d9d4fbd", "ethanol:30" );
/*1*/ test( "df", "e:5" );
/*2*/ test( "ad7", "c:10" );
/*3*/ test( "870dcb", "t:6" );
/*4*/ test( "880f63d", "test:15" );
/*5*/ test( "a57cbe56", "cat:17" );
/*6*/ test( "36abef2", "roll:23" );
/*7*/ test( "ad576cd8", "chant:25" );
/*8*/ test( "3e2a3db4fb9", "rails:25" );
/*9*/ test( "51aa3b4c2", "eeeteee:18" );
/*10*/ test( "ad5f1a07affe", "charset:31" );
/*11*/ test( "4ab8a86d7afb0f", "slideshare:42" );
/*12*/ test( "ac4b0b9faef", "doctor:30" );
/*13*/ test( "cafebabe", "nlh:17" );
/*14*/ test( "43e7", "sra:15" );
/*15*/ test( "53e7", "eera:15" );
/*16*/ test( "86cf", "tera:16" );
/*17*/ test( "b6cf", "hon:15" );
/*18*/ test( "0", "*invalid*" );
/*19*/ test( "c", "*invalid*" );
/*20*/ test( "d", "*invalid*" );
/*21*/ test( "e", "*invalid*" );
/*22*/ test( "babecafe", "*invalid*" );
/*23*/ test( "8d", "*invalid*" );
/*24*/ test( "ad", "*invalid*" );
/*25*/ test( "af", "*invalid*" );
/*26*/ test( "ab6e0", "*invalid*" );
/*27*/ test( "a4371", "*invalid*" );
/*28*/ test( "a4371", "*invalid*" );
/*29*/ test( "96e3", "*invalid*" );
/*30*/ test( "0dc71", "*invalid*" );
/*31*/ test( "2a9f51", "*invalid*" );
/*32*/ test( "a43fb2", "*invalid*" );
/*33*/ test( "ab6e75", "*invalid*" );
/*34*/ test( "a5dcfa", "*invalid*" );
/*35*/ test( "ca97", "*invalid*" );
/*36*/ test( "6822dcb", "*invalid*" );
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.