Xâu nhị phân 2

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Thời gian:
Python 3 10.0s
Tác giả:
Small
Dạng bài
Điểm: 300 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Một tập hợp \(S\) gồm các dãy \(N\) bit \(0, 1\) trong đó không có hai bit \(1\) nào kề nhau. Ví dụ \(N = 5\) thì \(S\) gồm các dãy \(00000, 00001, 00101,…\) Tập \(S\) được sắp xếp theo thứ tự từ điển.

Yêu cầu: Cho một số nguyên \(N\) (\(N < 63\)) cho biết:

  • Xâu nhị phân \(S\) (có độ dài \(N\)) nằm ở vị trí nào của tập.
  • Vị trí thứ \(K\) (\(K \le 10^{18}\)) là xâu nhị phân nào?

Input

  • Dòng đầu chứa một số nguyên \(N\), là độ dài của các xâu nhị phân.
  • Dòng thứ hai chứ một xâu nhị phân \(S\) có độ dài bằng \(N\).
  • Dòng thứ ba chứa một số nguyên \(K\).

Output

  • In trên từng dòng là kết quả từng yêu cầu của bài toán.

Example

Test 1

Input 
5
00001
3
Output 
2
00010

Bình luận