Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
Statistical Charts
Submit Problem
Online Status
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Alternative Scale of Notation
Time Limit: 1000MSMemory Limit: 30000K
Total Submissions: 2218Accepted: 829


One may define a map of strings over an alphabet ΣB = { C1, C2, . . . CB } of size B to non-negative integer numbers, using characters as digits C1 = 0, C2 = 1, . . . , CB = B - 1 and interpreting the string as the representation of some number in a scale of notation with base B. Let us denote this map by UB , for a string α[ 1...n ] of length n we put

For example, U3(1001) = 1*27 + 0*9 + 0*3 + 1*1 = 28.

However, this correspondence has one major drawback: it is not ont-to-one. For example,
28 = U3(1001) = U3(01001) = U3(001001) = ... ,
infinitely many strings map to the number 28.

In mathematical logic and computer science this may be unacceptable. To overcome this problem, the alternative interpretation is used. Let us interpret characters as digits, but in a slightly different way: C1 = 1, C2 = 2, . . . , CB = B . Note that now we do not have 0 digit, but rather we have a rudiment B digit. Now we define the map VB in a similar way, for each string α[ 1...n ] of length n we put

For an empty string ε we put VB(ε) = 0.

This map looks very much like UB , however, the set of digits is now different. So, for example, we have V3(1313) = 1*27 + 3*9 + 1*3 + 3*1 = 60.

It can be easily proved that the correspondence defined by this map is one-to-one and onto. Such a map is called bijective, and it is well known that every bijective map has an inverse. Your task in this problem is to compute the inverse for the map VB . That is, for a given integer number x you have to find the string α, such that VB(α) = x.


The first line contains B (2 <= B <= 9) and the second line contains an integer number x given in a usual decimal scale of notation, 0 <= x <= 10100.


Output in one line such string α, consisting only of digits from the set { 1, 2, . . . , B }, that VB(α) = x .

Sample Input


Sample Output



[Submit]   [Go Back]   [Status]   [Discuss]

Home Page   Go Back  To top

All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator