Số may mắn thứ K (Spoj)

Link bài : http://www.spoj.com/PTIT/problems/BCSRETAN/

Số may mắn thứ k

 

Chí Phèo thời IT rất yêu thích các số may mắn. Số may mắn là số mà chỉ chứa các chữ số may mắn (có hai chữ số may mắn là 4 và 7) trong biểu diễn thập phân. Các số may mắn sắp xếp tăng dần tạo thành dãy số may mắn. Một số số hạng đầu tiên của dãy số may mắn là: 4,7,44,47,74,77,… Biết Chí có niềm yêu thích như vậy, Thị Nở liền đố Chí tìm số may mắn thứ K trong dãy. Bài toán thực sự hóc búa với Chí, bạn hãy giúp anh Chí câu hỏi này nhé !

Input

Một số nguyên K duy nhất (1≤K≤109)

Output

Số may mắn thứ K trong dãy số may mắn.

Example

Input:
1
Output:
4
Input:

15

Output:

444

Hướng tiếp cận:
Nếu chúng ta để ý, các số sẽ được biểu diễn bởi 2 chữ số => Có thể coi đây là 1 dãy các số nhị phân
Vậy ta có các số 4,7,44,47,74,77 trở thành 0,1,00,01,10,11,…

Nếu ta thêm số 1 vào trước mỗi số thì ta sẽ được dãy nhị phân liên tiếp tăng dần.
VD:
Số nhị phân thứ 1:  0 -> Thêm 1 ở trước thành 10, có giá trị ở hệ 10 là 2
Số nhị phân thứ 2 : 1 -> Thêm 1 ở trước thành 11, có giá trị ở hệ 10 là 3

Số nhị phân thứ 3: 00 ->Thêm 1 ở trước thành 100, có giá trị ở hệ 10 là 4

Như vậy số nhị phân thứ K sau khi thêm 1 sẽ có giá trị ở hệ 10 là K+1

Giải thuật:

Với số K nhập vào ta sẽ tìm giá trị nhị phân của số thứ K+1

Với dãy số nhị phân thu được, gặp 0 sẽ chuyển thành 4, gặp 1 chuyển thành 7.
Kết quả in ra sẽ bỏ số 7 đầu tiên

Code tham khảo:

 

 

Share
Share