• Новая папка
  NEWORDER 

Description
Numbers are normally ordered by their magnitude, so 10 comes before 110 which comes before 1000. In this question we will consider a different way of ordering the numbers. We are also going to restrict ourselves to numbers that only use the digits 0 and 1.The new order rule is: If a number is written with fewer 1s than another number, the number with the fewest 1s comes first. If both numbers are written with the same number of 1s the number with the smallest magnitude comes first.With this ordering, 1000 now comes before 110 (since it has fewer 1s) but still comes after 10 (since it has a greater magnitude). The order of the 16 numbers that have no more than 4 digits is: 

Task
(a) 21 marks
In the new order, all the numbers with the same number of 1s are grouped together. Write a program NEWORDER to find the n^th number with exactly m 1s.The input will be a single line consisting of two integers. The first integer n (1<=n<=10⁹) indicates you are to find the n^th number. The second integer m (0<=m<=30) indicates the number of required 1s.Your output should consist of the single number which solves the requested task. Input data will be chosen so that a valid solution exists and requires no more than 30 digits. Since your answer might contain as many as 30 digits, you should put a single space after every 6^th digit in your answer (eg. output 110111  110 rather than 110111110).

(b) 7 marks
Suppose we are interested in the n^th number that has no more than m digits (where 0 is the 1st number). What is the answer when:

1. n=3 and m=4

2. n=1 and m=24

3. n=32 and m=5

4. n=6410 and m=14

5. n=1000000 and m=21

(c) 3 marks
How many numbers are there between 1000001 and 11000001 (exclusive) using no more than 8 digits?

(d) 5 marks
What is the largest number of digits that can change between two consecutive numbers (in the new order), consisting of no more than m digits? Justify your answer


Example

Input file
3  4

Output file
11011