중국 신분증 번호

면접 대비

시간 제한2초메모리 제한512 MB

요약

중국 주민등록번호 18자리가 유효한지 검사합니다. 지역 코드 목록, 1900년에서 2011년 사이의 생년월일, 000이 아닌 일련번호를 확인하고 체크섬을 mod 11 가중합으로 검증한 뒤 일련번호의 홀짝으로 성별을 판별합니다.

문제

중국 시민은 모두 신분증 번호를 가지고 있다. 신분증 번호는 18자리이다. 처음 17자리는 숫자이고, 마지막 1자리는 숫자이거나 'X'이다.

처음 17자리는 3개의 연속된 부분으로 나뉜다. 각 부분은 차례대로 지역 코드, 생일 코드, 순서 코드를 나타낸다.

지역 코드는 6자리이다. 올바른 지역 코드는 정부가 미리 정해 두었으며, 여기에 포함되지 않은 6자리 코드는 올바른 지역 코드가 아니다.
생일 코드는 8자리이고 YYYYMMDD 형식이다. 처음 4자리는 연도, 다음 2자리는 월, 마지막 2자리는 일을 나타낸다.
- 월이나 일이 한 자리 수이면 앞에 0을 붙여 두 자리로 만든다.
- 올바른 생일 코드는 1900년 1월 1일부터 2011년 12월 31일 사이의 날짜를 나타내야 한다.
순서 코드는 3자리 숫자이다. 3자리 숫자는 임의로 정해지며 "000"은 불가능하다. 나머지 수는 모두 올바른 순서 코드이다. 순서 코드가 홀수이면 남자, 짝수이면 여자를 나타낸다.

신분증 번호의 마지막 숫자는 체크섬 코드이고, 수식으로 계산한다. 신분증 번호의 처음 17자리 숫자를 A1, A2, ..., A17이라 할 때, 아래 방정식으로 체크섬 코드를 구한다.

x + A1×2^17 + A2×2^16 + A3×2^15 + ... + A16×2^2 + A17×2^1 ≡ 1 (mod 11)

위 방정식을 만족하는 x는 항상 하나뿐이다. x가 10이면 체크섬 코드가 'X'이고, 그 외의 경우에는 x가 체크섬 코드이다.

신분증 번호 하나와 올바른 지역 코드의 목록이 주어졌을 때, 신분증 번호가 올바른지 아닌지, 올바르다면 남자인지 여자인지 구하는 프로그램을 작성하시오.

첫째 줄에 신분증 번호가 주어진다. 신분증 번호는 18자리이고, 처음 17자리는 0부터 9까지 숫자로만 이루어져 있다. 마지막 1자리는 0부터 9까지 숫자이거나 'X'이다.

둘째 줄에는 올바른 지역 코드의 개수 N(1 ≤ N ≤ 50)이 주어진다.

셋째 줄부터 N개의 줄에는 올바른 지역 코드가 한 줄에 하나씩 주어진다. 지역 코드는 6자리이고 0부터 9까지 숫자로만 이루어져 있다. 또, 0으로 시작하지 않는다. 입력으로 주어지는 지역 코드는 중복되지 않는다.

입력으로 주어진 신분증 번호가 올바르지 않은 경우에는 "I"를 출력한다. 올바르면서 남자인 경우에는 "M"을, 여자인 경우에는 "F"를 출력한다.