Problem H: | Shifted Coefficient Number System |
Time Limit: 5 seconds Memory Limit: 32 MB |
Let us define the Shifted Coefficient Number System as a number system that has B base and uses the coefficients L, L+1, L+2,... , L+B-1. As you'd soon find out if certain constraints are not met it would not be possible to express all integers in the SCNS. For this problem you'd have to find the SCNS representation of integers given in Decimal Number System, and when the representation is not possible you'd state so.
There can be multiple test cases. Each test case consists of 3 integers: B, 1 < B < 17 the base for the number system, L, |L| < 10 the least valued coefficient in the number system and N, |N| < 2^{15}-1 a number given in Decimal Number System.
For each of test cases, print two lines. The first line would be of format: "CASE# x:" where x is the test case number (starting at 1). In the next line print a SCNS representation of the number in the following format: c_{n}*B^^{n} c_{n-1}*B^^{n-1} ... c_{0}*B^^{0} = N. If there are multiple solutions print the one that uses the least number of coefficients. For two numbers in SCNS P_{a} and P_{b}, P_{a} gets preference over P_{b} when C_{ai} < C_{bi}, and for all i=n..i-1 C_{ai} = C_{bi}. In other words between two representation of a number with same number of coefficients choose the one that has the smallest most significant digit (if they are equal then the smallest next significant digit and so on...). None of the representations should use more than 15 coefficients. If it is not possible to represent the number in SCNS with 15 or less coefficients, then print the words NOT REPRESENTABLE.
2 0 5 2 1 5 2 2 5
CASE# 1: +1*2^2+0*2^1+1*2^0 = 5 CASE# 2: +2*2^1+1*2^0 = 5 CASE# 3: NOT REPRESENTABLE
Problem Setter: Monirul Hasan (Tomal), CSE Dept, Southeast University, Bangladesh
Job Interviews are so cool... the interviewers get to ask all the question that they know and the interviewee is not supposed to know. For the interviewee the experience is even cooler... they get to anticipate questions which are never asked. Those are the questions that they should have answers to, but the interviewer has no clue of.