UESTC TRAINING FOR SUMMER SELECTION B

B · FBI Universal Control Numbers

The FBI has recently changed its Universal Control Numbers (UCN) for identifying individuals who are in the FBI’s fingerprint database to an eight digit base 27 value with a ninth check digit. The digits used are:

 

0123456789ACDEFHJKLMNPRTVWX

 

Some letters are not used because of possible confusion with other digits:

 

B->8, G->C, I->1, O->0, Q->0, S->5, U->V, Y->V, Z->2

 

The check digit is computed as:

 

(2*D1 + 4*D2 + 5*D3 + 7*D4 + 8*D5 + 10*D6 + 11*D7 + 13*D8) mod 27

 

Where Dn is the nth digit from the left.

This choice of check digit detects any single digit error and any error transposing an adjacent pair of the original eight digits.

 

For this problem, you will write a program to parse a UCN input by a user. Your program should accept decimal digits and any capital letter as digits. If any of the confusing letters appear in the input, you should replace them with the corresponding valid digit as listed above. Your program should compute the correct check digit and compare it to the entered check digit. The input is rejected if they do not match otherwise the decimal (base 10) value corresponding to the first eight digits is returned.

 

Input

 

The first line of input contains a single decimal integer P, (1 £ P £ 10000), which is the number of data sets that follow. Each data set should be processed identically and independently.

 

Each data set consists of a single line of input. It contains the data set number, K, followed by a single space, followed by 9 decimal digits or capital (alphabetic) characters.

 

Output

 

For each data set there is one line of output. The single output line consists of the data set number, K, followed by a single space followed by the string “Invalid” (without the quotes) or the decimal value corresponding to the first eight digits.

 

 

Sample Input

Sample Output

3

1 12345678A

2 12435678A

3 12355678A

1 11280469652

2 Invalid

3 Invalid

 

理解好题意就可，貌似和之前一道普及组题目很相似，校验码这样的题目。

用 map 映射即可：

（我感觉题目的表述有点问题，也可能是我英语太差。。。。

#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<set>
#include<map>
using namespace std;
typedef long long ll;
#define maxn 200005
#define inf 0x3f3f3f3f
#define ii 0x3f
const int mod = 1e9 + 7;


ll read() {
	ll x = 0, f = 1;
	char ch = getchar();
	while (ch < '0' || ch > '9') {
		if (ch == '-') {
			f = -1;

		}
		ch = getchar();
	}
	while (ch >= '0'&&ch <= '9') {
		x = x * 10 + ch - '0';
		ch = getchar();
	}
	return x * f;
}

ll quickpow(ll a, ll b) {
	ll ans = 1;
	while (b > 0) {
		if (b % 2)ans = ans * a;
		b = b / 2;
		a = a * a;
	}
	return ans;
}
//char s[maxn];

int gcd(int a, int b) {
	return b == 0 ? a : gcd(b, a%b);
}

map<char, int>mp;
int f[8] = { 2,4,5,7,8,10,11,13 };
int main() {
	ios::sync_with_stdio(false);
	int t;
	cin >> t;
	mp['0'] = 0; mp['1'] = 1; mp['2'] = 2; mp['3'] = 3; mp['4'] = 4;
	mp['5'] = 5; mp['6'] = 6; mp['7'] = 7; mp['8'] = 8; mp['9'] = 9;
	mp['A'] = 10; mp['B'] = 8; mp['C'] = 11; mp['D'] = 12;
	mp['E'] = 13; mp['F'] = 14; mp['G'] = 11; mp['H'] = 15;
	mp['I'] = 1; mp['J'] = 16; mp['K'] = 17; mp['L'] = 18;
	mp['M'] = 19; mp['N'] = 20; mp['O'] = 0; mp['P'] = 21; mp['Q'] = 0;
	mp['R'] = 22; mp['S'] = 5; mp['T'] = 23; mp['U'] = 24; mp['V'] = 24;
	mp['Y'] = 24; mp['W'] = 25; mp['X'] = 26; mp['Z'] = 2;
		while (t--) {
			int ct;
			cin >> ct;
			string s;
			cin >> s;
			int i;
			int ans = 0;
			ll sum = 0;
			for (i = 0; i < 8; i++) {
				sum = sum * 27 + mp[s[i]];
				ans += f[i] * mp[s[i]];
			}
			if (ans % 27 == mp[s[8]])cout << ct << ' ' << sum << endl;
			else cout << ct << ' ' << "Invalid" << endl;
		}
}