SRM583 Div2 Medium "IDNumberVerification"
問題
http://community.topcoder.com/stat?c=problem_statement&pm=12610
訳
中華人民共和国の人々は一意のIDとなる文字列を持っている。IDの文字列長は18文字である。最初の17文字(ボディコードと呼ばれる)は全て数字であり最後の文字(チェックサムコードと呼ばれる)は数字か'X'のどちらかである。
ボディコードは左から右に向かって、リージョンコード、バースデイコード、そしてシーケンシャルコードの3つのパートに分かれている。これらは下記のような内容である。
・リージョンコードは6文字である。 この文字列は住所の地域を表しているが、中には不正なものもある。 あなはた正当なリージョンコードのリストregionCodesが与えられる。 ・バースデイコードは8文字である。 これは市民の誕生日をYYYYMMDDの形式で表したものである。 最初の4桁は年であり、次の2桁は月(01から12の0埋めされたもの)で、最後の2桁は日である。 正当なものか検証するにはうるう年を考慮しなくてはならない。 さらに19000101から20111231の間でなくてはならない。 ・シーケンシャルコードは3文字である。 この文字列は"000"を除き任意なものである。 シーケンシャルコードは"007"のような奇数であれば男性である事を示し。 "420"のように偶数であれば女性である事を示す。
IDの最後の文字はチェックサムコードである。前の17文字よりはじきだされる。ボディコードが左から右へ向かってa1, a2, ..., a17であるとする。そして、次のような等式
x + a1*2^17 + a2*2^16 + a3 * 2^15 + ... + a16 * 2^2 + a17 * 2^1 = 1( mod 11 )
を考える。この等式のxは0 <= x <= 10となる。もしx=10であれば、チェックサムコードは'X'であり、そうでなければ、その数字となる。
idが与えられるので、それが正当なものか不正なものかを判断せよ。
制約
特になし
考えた事
スーパーやるだけ問題
・・・しかしうるう年の判定をミスりWA
本番だったらうわーーーーってなってたわ~
ソースコード
class IDNumberVerification { public: bool isReapYear( int year ){ if( year % 400 == 0 ) return true; if( year % 100 == 0 ) return false; if( year % 4 == 0 ) return true; return false; } int maxDay( int y, int m ){ int days[] = { -1, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 }; bool reap = isReapYear( y ); return days[m] + ( reap && m == 2 ? 1 : 0 ); } string verify(string id, vector <string> regionCodes){ // chk region bool ok = false; for( int i = 0; i < regionCodes.size(); i++ ){ if( id.substr( 0, 6 ) == regionCodes[i] ) ok = true; } if( !ok ) return "Invalid"; // chk birthday stringstream ss1, ss2, ss3; ss1 << id.substr( 6, 4 ); ss2 << id.substr( 10, 2 ); ss3 << id.substr( 12, 2 ); int y, m, d; ss1 >> y; ss2 >> m; ss3 >> d; if( y < 1900 || 2011 < y || m < 1 || 12 < m || d < 1 || maxDay( y, m ) < d ){ return "Invalid"; } // chk sequential stringstream ss4; ss4 << id.substr( 14, 3 ); int seq; ss4 >> seq; if( seq == 0 ){ return "Invalid"; } // chksum int mul = 2; int sum = (id[17] == 'X' ? 10 : (id[17] - '0')); for( int i = 16; i >= 0; i-- ){ sum += (id[i] - '0') * mul; mul *= 2; } if( sum % 11 != 1 ){ return "Invalid"; } return (seq % 2 ? "Male" : "Female"); } };