WARush

SRMの結果とか、解けた問題のコードを書いていきます

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");

    }
};