zoj 3485 Identification Number

zoj 3485 Identification Number

#include<stdio.h>#include<string.h>#include<iostream>#include<map>using namespace std;#define pb push_back#define mp make_pair#define X first#define Y second#define inf 0xfffffffint day[22]={10086,31,28,31,30,31,30,31,31,30,31,30,31};int W[22]={7,9,10,5,8,4,2,1,6,3,7,9,10,5,8,4,2,1};bool is_run(int x){if(x == 1900)return false;return x%4 == 0;}string str;string f_15(int x,int y,int z,int &cnt){x%=100;int x1=x/10;int x2=x%10;int y1=y/10;int y2=y%10;int z1=z/10;int z2=z%10;string t=str;t[6]='0'+x1;t[7]='0'+x2;t[8]='0'+y1;t[9]='0'+y2;t[10]='0'+z1;t[11]='0'+z2;cnt=0;for(int i=0;i<15;i++)if(str[i] != t[i])cnt++;return t;}char calc(string t){int S=0;for(int i=0;i<17;i++)S+=W[i]*(t[i]-'0');int a1=(12-S%11)%11;char f;if(a1 == 10)f='X';elsef='0'+a1;return f;}string f_18(int x,int y,int z,int &cnt){int x4=x%10;x/=10;int x3=x%10;x/=10;int x2=x%10;x/=10;int x1=x%10;int y1=y/10;int y2=y%10;int z1=z/10;int z2=z%10;string t=str;t[6]='0'+x1;t[7]='0'+x2;t[8]='0'+x3;t[9]='0'+x4;t[10]='0'+y1;t[11]='0'+y2;t[12]='0'+z1;t[13]='0'+z2;t[17]=calc(t);cnt=0;for(int i=0;i<18;i++)if(str[i] != t[i])cnt++;return t;}int main(){int cas;scanf("%d",&cas);for(int cc=1;cc<=cas;cc++){cin >> str;int n=str.size();string ans="";int dif=10086;for(int x=1900;x<=2011;x++){if(is_run(x))day[2]++;for(int y=1;y<=12;y++)for(int z=1;z<=day[y];z++){if(x == 2011){if(y > 4)continue;if(y == 4){if(z > 2)continue;}}if(n == 15){int cnt;string now=f_15(x,y,z,cnt);if(cnt < dif){dif=cnt;ans=now;}}else{int cnt;string now=f_18(x,y,z,cnt);if(cnt < dif){dif=cnt;ans=now;}}}if(is_run(x))day[2]--;}cout << ans << endl;}return 0;}