[Login|Register]
Problems

Status

Rank

Problem 1283
Hashing reversed
Time Limit: 1000ms
Memory Limit: 65536kb
Description

The following code implements a simple hashing function for strings.

unsigned int hash(const char *str)
{
    unsigned int res=0;
    for(;*str;++str)
    {
        res*=1000000007;
        res+=*str;
    }
    return res;
}

Given a hash value h, your task is to find the shortest original string which contains only lowercase letters(’a’..’z’).

Input

The input consists of multiple test cases. Each test case contains exactly one integer h, which is described above.

A test case with h=0 indicates the end of input and should not be processed.

Output

For each test case, output the answer after “Case x: ”, where x is the case number. If there’re multiple possible answers, output the lexicographically smallest one. You may assume the answer always exists and contains no more than 8 characters.

Sample Input
3403101377
446150741
3017941386
863509366
2321877736
0
Sample Output
Case 1: xyz
Case 2: ustc
Case 3: ustcif
Case 4: hash
Case 5: acmicpc
University of Science and Technology of China
Online Judge for ACM/ICPC
Processed in 0.9ms with 1 query(s).