Created
March 19, 2013 23:52
-
-
Save mattsan/5201225 to your computer and use it in GitHub Desktop.
第8回オフラインリアルタイムどう書くの参考問題の回答例。C++で。その2 ref: http://qiita.com/items/1af0536fa20bc26ec0fb
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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