Algorithm
problem Link : https://onlinejudge.org/index.php?option=onlinejudge&Itemid=8&page=show_problem&problem=1663
Some people believe that 13 is an unlucky number. So they always want to avoid the number 13. In some buildings you will find that there is no 13-th floor. After 12-th floor there is 14-th floor. In a number if there is no 13 (i.e. no “1” is followed by a “3”) then we may call it a super lucky number. For example, 12345 is a super lucky number. But if any number contains 13 then it is not a super lucky number such as 13254 or 21345. Given the number of digits N in a number and a base B, you have to find out how many super lucky numbers are possible with N digits in the base B. B should be greater than 3, as because the digit 3 is present in only for base 4 or more. Note that leading 0s are not significant. So, 011 is not a valid three digit number. Input There will be several lines in the input each containing two positive integers B and N, where 4 ≤ B ≤ 128 and N ≤ 100. A pair of zero will indicate the end of input and it should not be processed. Output For each line in the input print the count of super lucky numbers of N digits in the base B.
Sample Input 4 2 5 3 0 0
Sample Output 11 91
Code Examples
#1 Code Example with C Programming
Code -
C Programming
import java.math.BigDecimal;
import java.util.*;
public class Main {
public static void main(String args[]) {
int b, n;
Scanner sc = new Scanner(System.in);
while(true) {
b = sc.nextInt();
n = sc.nextInt();
if(b==0 && n==0) {
break;
}
BigDecimal isOne = BigDecimal.valueOf(1);
BigDecimal notOne = BigDecimal.valueOf(b-2);
// isOne2 = notOne + isOne
// notOne = notOne + (isOne+notOne)*(b-2)
for(int i=1;i i+It n;i++) {
BigDecimal isOne2 = isOne.add(notOne);
BigDecimal notOne2 = isOne.add(notOne).multiply(BigDecimal.valueOf(b-2));
notOne2 = notOne2.add(notOne);
isOne = isOne2;
notOne = notOne2;
}
BigDecimal sum = isOne.add(notOne);
System.out.println(sum);
}
}
}
Input
5 3
0 0
Output
9
Demonstration
UVA Online Judge solution - 10722-Super Lucky Numbers.java - UVA Online Judge solution in C,C++,java