[UVA][bitmask] 11394 - Digit Blocks
|
I I U C O N L I N E C O N T E S T 2 0 0 8 |
|
|
Problem J: Digit Blocks |
|
|
Input: standard input Output: standard output |
|
|
|
|
|
|
|
|
Input |
|
|
Input file contains at most 501 lines of inputs. Each line contains a string which contains only digits of hexadecimal number system (but will not contain zero). These digits denote the blocks that are available. For example if the string is “A1BBB5”, then you have two assume that total six blocks are available. Of them three blocks have shape of B, one block has shape of A, another block has shape of 1 and the last one has shape of 5. The string can be at most 16 characters long.
Input is terminated by a line containing a single ‘#’.
|
|
Output |
|
For each line of input produce one line of output. This line contains a decimal integer number which denotes the value N. Here N is the number of hexadecimal multiples of 5 that can be formed using the given digits. Note that you can use some or all of the given digits to form number. You can safely assume that N will fit in a 64 bit signed integer.
|
|
|
Sample Input |
Output for Sample Input |
A1BBB5B
# |
4 0 |
|
|
|
|
Problem setter: Shahriar Manzoor Special thanks: Derek Kisman |
|
Often
digit blocks are used to teach children formation of numbers. Block sets are
available in the market which contains many blocks, each of which has the
shape of a digit. Small or large numbers can be formed using them by placing
them in a single row. Given the information of the available digit blocks,
your job is to find out the total number of different hexadecimal numbers divisible
by 5 that can be formed using those blocks. To save you from numbers with
leading zeroes you can assume that none of the blocks will have shape of
zero. The available blocks may have shapes of ‘1’, ‘2’, ‘3’, ‘4’, ‘5’, ‘6’,
‘7’, ‘8’,’9’, ‘A’, ‘B’, ‘C’, ‘D’, ‘E’ or ‘F’ which are actually digits of
hexadecimal number system.
從集合中挑選組成一個十六進制數，求其中為 5 的倍數的方法數為何 ?
題目解法：
組合壓縮，與一般排列的壓縮不同，必須將其轉換成 ...
例如說 A 有 1 個，B 有 3 個，1 有 1 個，5 有 1 個，
則 dp[1+1][3+1][1+1][1+1][5] 表示組合情況下的 mod = 0 的方法數。
由於不方便對所有測資進行狀態開陣列，因此要自己計算 row major。
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
int A[20], B[20], C[20];
long long dp[1<<16][5];
int used[1<<16][5] = {};
int cases = 0, n, m;
int getMask() {
int ret = 0;
for(int i = 0; i < m; i++)
ret += C[i] * B[i];
return ret;
}
long long dfs(int mod) {
int mask = getMask();
if(mask == 0)
return mod == 0;
if(used[mask][mod] == cases)
return dp[mask][mod];
used[mask][mod] = cases;
long long &ret = dp[mask][mod];
ret = 0;
for(int i = 0; i < m; i++) {
if(B[i]) {
B[i]--;
ret += dfs((mod * 16 + A[i])%5);
B[i]++;
}
}
if(mod == 0) ret++;
return ret;
}
int main() {
char s[105];
while(scanf("%s", s) == 1 && s[0] != '#') {
n = strlen(s);
sort(s, s + n);
int i, j, prev = -1;
m = 0;
for(i = 0; i < n; i++) {
int num;
if(s[i] >= '0' && s[i] <= '9')
num = s[i] - '0';
else
num = s[i] - 'A' + 10;
if(num != prev) {
A[m] = num, B[m] = 0, m++;
prev = num;
}
B[m-1]++;
}
C[m-1] = 1;
for(i = m-2; i >= 0; i--)
C[i] = C[i+1] * (B[i+1] + 1);
cases++;
printf("%lld\n", dfs(0) - 1);
}
return 0;
}