C11SEQ3 - Dãy số

Giới hạn
  • Thời gian: 1.0s
  • Bộ nhớ: 1536MB
  • Mã nguồn: 50000 bytes

Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.

Link đọc đề trên VNOJ

Cho dãy số F dài vô tận. Nguyên tắc xây dựng dãy F rất đơn giản.

  • F[1] = 1
  • Với i > 1, đầu tiên ta lấy F[i] = F[i - 1] * 2, sau đó sắp xếp các chữ số trong F[i] theo thứ tự tăng dần. (Các chữ số 0 ở đầu F[i], ta coi như là không có nghĩa và có thể xóa đi).

Như vậy, các số đầu tiên trong dãy số F là:

1, 2, 4, 8, 16, 23, 46, 29, 58, ...

Cho số n, bạn hãy tìm số F[n]. Biết rằng số lượng chữ số của F[n] luôn nhỏ hơn 10 6.

Dữ liệu

  • Một số nguyên dương duy nhất là n (1 ≤ n ≤ 10 9 ).

Kết quả

  • Một số nguyên dương duy nhất là số cần tìm.

Ví dụ 

Input:
7

Output:
46

  • Người up: tohuuquan