Algorithm
problem Link : https://onlinejudge.org/index.php?option=onlinejudge&Itemid=8&page=show_problem&problem=1853
All of you know a bit or two about hashing. It involves mapping an element into a numerical value
using some mathematical function. In this problem we will consider a very ‘simple minded hashing’.
It involves assigning numerical value to the alphabets and summing these values of the characters.
For example, the string “acm” is mapped to 1 + 3 + 13 = 17. Unfortunately, this method does not
give one-to-one mapping. The string “adl” also maps to 17 (1 + 4 + 12). This is called collision.
In this problem you will have to find the number of strings of length L, which maps to an integer S,
using the above hash function. You have to consider strings that have only lowercase letters in strictly
ascending order.
Suppose L = 3 and S = 10, there are 4 such strings.
1. abg
2. acf
3. ade
4. bce
“agb” also produces 10 but the letters are not strictly in ascending order.
“bh” also produces 10 but it has 2 letters.
Input
There will be several cases. Each case consists of 2 integers L and S (0 < L, S < 10000). Input is
terminated with 2 zeros.
Output
For each case, output ‘Case#:’ where # is replaced by case number. Then output the result. Follow
the sample for exact format. The result will fit in 32 signed integers.
Code Examples
#1 Code Example with C Programming
Code -
C Programming
#include <bits/stdc++.h>
using namespace std;
int memo[27][352][27];
int solve(int remLen, int val, int pos){
if(remLen == 0 && val == 0) return 1;
else if(remLen < = 0 || val <= 0 || pos> 26) return 0;
if(memo[remLen][val][pos] != -1) return memo[remLen][val][pos];
int res = 0;
for(int i=pos;i<=26;i++)
res += solve(remLen-1,val-i,i+1);
return memo[remLen][val][pos] = res;
}
int main()
{
memset(memo,-1,sizeof memo);
int tc=1,l,s;
while(scanf("%d %d",&l,&s),(l+s)!=0>{
printf("Case %d: %d\n",tc++, (l > 26 || s > 352) ? 0 : solve(l,s,1));
}
}
Input
2 3
0 0
Output
Case 2: 1
Demonstration
UVA Online Judge solution - 10912-Simple Minded Hashing - UVA Online Judge solution in C,C++,java